详解图嵌入Graph Embedding之 社交网络应用

社交网络推荐是图嵌入(Graph Embedding)的经典应用场景。这篇文章会介绍图嵌入具体到社交网络问题中,派生出的解决算法。

研究问题

协同过滤

协同过滤(Collaborative Filtering)算法在给定用户(user)对于物品(item)的评分矩阵R后,将用户和物品都投影到同样的低维空间中,而用户对于物品的期望评分应该可以用双方在低维空间投影向量的相似度刻画。[1]

社交网络推荐

社交网络推荐(Social Recommendation)着重研究的是在社交网络中特有的性质——节点蕴含的信息可以通过社交网络的邻居进行扩散。在社交网络的邻居倾向于拥有相同的偏好。[1]

社交网络的特点

数据稀疏

社交网络的一大特点是稀疏性[1],不仅一个节点的邻居非常稀疏,而且通常来说用户的反馈也是稀疏的。社交网络推荐系统的典型应用就是通过少数用户的标签推测出其他用户的标签,这种场景下可见的标签必然是及其稀疏的。

属性多元性

相比于其它问题中,图的节点信息较少。在社交网络图结构中,一个节点(用户)拥有非常多的属性,如年龄、性别、地域、经历等等。[1] 同时,两个节点的联系也存在不同的属性,他们可能是亲属、同事、同学,或者仅仅是兴趣相同的线上朋友。这意味着图中的连边并不一定意味着相同的兴趣爱好(相同的标签)[2]。

小世界现象

小世界现象(Small World Phenomenon)说的是在一个比较大的人口集合中,选取任意两个人作为起点终点,计算从起点到终点的“认识链”(即链上的人依次互相认识),这个链长平均为5.7。该现象暗示社交网络图的直径非常小,而且信息扩散是指数级别的,而一般来说社交网络中的“局部”指的是从起点开始1到2跳形成的邻域。[2]

节点度数分布

节点度数的规模无关现象(Scale-free property)说的是在社交网络图里面,节点的度数基本上是与社交网络规模无关的(具体来说应该是O(loglogn))的关系。[3]

引用

[1] Wu, L., Sun, P., Hong, R., Fu, Y., Wang, X., & Wang, M. (2018). SocialGCN: An Efficient Graph Convolutional Network based Model for Social Recommendation. arXiv preprint arXiv:1811.02815.Chicago

[2] Travers, J., & Milgram, S. (1977). An experimental study of the small world problem. In Social Networks (pp. 179-197). Academic Press.

[3] Chakrabarti, D., & Faloutsos, C. (2006). Graph mining: Laws, generators, and algorithms. ACM computing surveys (CSUR)38(1), 2.

详解图嵌入Graph Embedding之 经典数据集

Yelp数据集

Yelp数据集是由美国最大的点评网站Yelp公开维护的数据集,网站开放了能够做预测的几乎所有数据。包括——

  • [bussiness]餐馆详情:名称、地址、坐标、评分、类别、营业时间、有没有WIFI……
  • [checkin]餐馆的登记时间戳
  • [photo]餐馆上传的室内/室外照片
  • [review]用户对餐厅的评价
  • [tip]大概是用户对餐厅的建议
  • [user]用户信息,历史好评/差评数量,及其好友列表

Yelp还定期举办比赛,看哪个团队的预测结果最准确。写这篇文章的时候,比赛已经进行到了第13轮。一个需要注意的是在数据集下载界面中的“Please sign by entering your initials”是让你输入姓名中姓和名的大写首字母。[1]

Wikipedia数据集

Wikipedia数据集从英文维基百科的存档中截取了1,000,000个字节的数据,并将单词的出现建立成一张图。而单词的词性标注(part-of-speech tags)被看做这个节点的标记。不过由于我不太懂NLP方面的东西,也没有找到具体建图的流程,只在[2]里面看到了一个粗略的介绍,如果有读者知道的话,欢迎留言。一个经过处理后的图数据集可以在这里找到。

BlogCatalog数据集

BlogCatalog3数据集 是从著名博客目录网站BlogCatalog抓取的博客数据集,其中节点代表了每一个用户(博客),而节点的标签则是用户在网站中所属的用户组别,在一定程度上,标签反映了用户本身感兴趣的种类。[3] 数据集包括——

  • [edges] 所有边所连接的端点的表
  • [group-edges] 所有标签对应的节点编号
  • [nodes] 所有的节点编号
  • [groups] 所有的标签编号

引用

[1] Wu, L., Sun, P., Hong, R., Fu, Y., Wang, X., & Wang, M. (2018). SocialGCN: An Efficient Graph Convolutional Network based Model for Social Recommendation. arXiv preprint arXiv:1811.02815.

[2] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2019). A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596.

[3] Wang, H., Wang, J., Wang, J., Zhao, M., Zhang, W., Zhang, F., … & Guo, M. (2018, April). Graphgan: Graph representation learning with generative adversarial nets. In Thirty-Second AAAI Conference on Artificial Intelligence.

详解图嵌入Graph Embedding之 相关文献综述

详解图嵌入系列传送门:https://mhy12345.xyz/graph-embedding-tutorials/

文献综述

Relational learning via latent social dimensions

在这篇文章之前,图的多标签分类是传统算法的天下。在此之前,甚至人们探讨的都是如何给社交网络划分集群等传统问题。当时人们的思想还是类似于page-rank一样的影响力模型,一个节点的邻居是什么标签,那么这个点也应该是什么标签。

这篇文章提出了先为图中每个节点识别出一个K维向量,然后将图的分类问题转换为向量的分类问题。而这个向量本身,是图的Modularity矩阵的前K大的特征向量。Modularity细节一言难尽,可以参考实际的论文。不过感性上来看,第K个特征向量中1的项暗示了这个节点可以被分到第K类。

这篇文章算是将矩阵、线性代数那一波东西引入图嵌入中比较成功的一个例子。也是图分类从统计学、线性代数等传统方法向深度学习的图嵌入的中间产物。

DeepWalk: Online Learning of Social Representations

这篇文章首先说:“从图中一个指定点出发随机游走较短距离遍历过的点,从频数分布来说与普通英文文章中的词频相似,都符合幂律分布(power-law distribution)。”

社交网络的路径遍历和普通文章的词频相似,因此可能存在共通的分析方法。

接下来,节点的Embedding就变成了将从他开始若干路径视为“句子”,使用NLP中的词嵌入算法生成的Embedding。文章还介绍了一个称之为Hierarchical Softmax的分层求解Softmax的方法。可以使模型更加高效。

Structural Deep Network Embedding

文章首先介绍了一阶相似度(first-order proximity)和二阶相似度(second-order proximity),其中,一阶相似度要求两个节点的编码能够有效的表征其间是否存在连边,而二阶相似度要求两个节点的编码能够有效表征他们的共同邻居的存在。实际上,一个合理的Embedding方式,应该能够同时满足一阶/二阶相似度的关联性。因此我们将一阶/二阶相似度引入到Loss函数中,作为优化的一项参数即可。

SocialGCN: An Efficient Graph Convolutional Netowork based Model for Social Recommendation

文章指出之前的很多文章没有考虑到社交网络中的信息扩散效益,通过K轮迭代的方式,使得图中中每个节点内部的信息(即节点的Embedding)有机会扩展到距离为K的节点中。

GraphGAN: Graph representation learning with generative adversarial nets.

文章指出了图表示学习诸多算法的一种分类方式——基于生成性&判别性分类。并进一步设计了基于图的生成模型算法。具体来说,生成器G尝试拟合节点v_c的真实邻居的概率分布p_{true}(v|v_c)。并从这个分布中采样一部分邻居用以迷惑判别器D。同时判别器D需要判断出某一个节点真的是邻居还是生成器G假装生成的。

比较特别的是,这篇文章由于存在采样,因此使用的是强化学习Policy Gradient中的“随机梯度下降算法(Stochastic gradient descent)”方法进行学习。

参考文献

[3] Wang, H., Wang, J., Wang, J., Zhao, M., Zhang, W., Zhang, F., … & Guo, M. (2018, April). Graphgan: Graph representation learning with generative adversarial nets. In Thirty-Second AAAI Conference on Artificial Intelligence.

详解图嵌入Graph Embedding之 算法概述

详解图嵌入系列传送门:https://mhy12345.xyz/graph-embedding-tutorials/


算法概述

将深度学习放在图上

深度学习在近十年有着井喷式的突破,随着研究者们在该领域投入大量的人力物力,大量新颖有效的结构被创造了出来,比如能够完成手写数字识别的卷积神经网络CNN,能够提取语句情感色彩的LSTM结构,能够生成图片的对抗神经网络GAN……

CIFAR-10 Samples
CIFAR-10 数据集的分类是机器学习中一个公开的基准测试问题,其任务是对一组32x32RGB的图像进行分类

现有的神经网络大多都是建立在图像和序列上的,还有少量建立在树形结构上。如何将神经网络迁移到图上,成为了很多学者研究的问题,为什么会尝试把神经网络迁移到图上呢?在笔者看来有两个原因——

第一个原因是图结构本身就是所有数据组织结构的大杂烩。我们平常处理的“链式结构”,“树形结构”,“二维网格图”都可以被“图”这样一个概念囊括。如果我们能够提出一个建立在图上面的,足够高效智能的算法,其意义在机器学习问题中不亚于大统一理论在物理中的意义。

图本身就是大量数据结构的抽象化结果,比如计算机视觉中,卷积神经网络处理的二维图像,从某种意义上也是图的一种,研究者们尝试将CNN的模型迁移到图上,就成为了现在的图卷积神经网络GCN。[1]

第二个原因是图上的分类问题,在我们生活中也大有应用。比如基于关注列表的商品推荐、社交网络中的朋友推荐、以及社交网络中的兴趣推荐等等。这些问题的核心都是将用户的关注列表抽象为图结构,并从中提取出有用的信息。

既有实现深度学习大统一的“仰望星空”,又有解决实际问题的“脚踏实地”,基于图的深度学习算法,在近年来逐渐火了起来。

图嵌入识别节点空间结构

相比于传统的深度学习问题,基于图的神经网络不仅需要处理节点自带的若干属性,还需要处理节点在图上的空间结构。

我们将通过社交网络中一类重要的数据集类别“博客”为例,讲解图嵌入的意义。博主通常会为自己的博客添加一些标签作为博客本身的介绍。这些标签同时还可以优化博客的检索与搜索。但是,并不是所有博主都会上传自己博客的标签,甚至有些博主会由于某些因素上传一些不那么准确的标签。这就要求我们的模型能从博客的关注图结构以及部分博客标签中,补全其他节点的标签。[4]

与博客网络相似的还有基于社交网络的广告推荐。不过不同的是,对于广告推荐而言,有效样本占总体数据的比重非常非常的小(毕竟只有很小一拨人会点击广告并被我们的模型捕获)。这也要求模型花更多精力投入到识别图结构本身的特征而非节点上蕴含的信息。后者对标签特征的提取与图本身无关,可以套用传统的深度学习模型,而后者对图特征的提取就需要特殊的算法解决了。而计算节点在图中的空间特征的算法就是图嵌入(Graph Embedding)或网络嵌入(Network Embedding)。

图嵌入的目标是将图中的节点表示为一个低维向量,该向量保留了节点在网络中的拓扑结构以及节点内部信息。通过这个表示向量,其他的经典深度学习算法才得以被应用到图中,最终实现分类、聚类、推荐等问题。[3]

数据集与模型评价

综述文章[3]中有一张很大的表,记录了基于图深度学习文章常用的数据集。包括类别、规模以及引用。本系列的另一篇文章会详细描述我在学习过程中了解过的数据集。

在表中,数据集被分为了引用网络(Citation Network),社交网络(Social Network), 化学/生物的图结构(Chemical/Biological Graphs),去结构化的图(Unstructured Graphs)和其他(Others)。每一种类型都对应了不同的问题,比如社交网络数据集着重于测试模型能否捕获临近节点的信息,以及识别出节点的空间特征,而去结构的图则着重测试模型是否可以成功泛化一些本可以有更强结构信息的图。

在图嵌入这个问题中,节点所处的空间特征很重要,因此相关的论文喜欢用社交网络数据集进行测试。一个最简洁的社交网络数据集有如下组成部分——

  • 节点表:记录了这个图结构所有节点
  • 边表:记录了图中的所有有向边
  • 标签表:记录图中所有节点所述的分类

对于图上的分类算法的测试,我们一般将标签表中一部分点的数据隐藏,让模型试图通过没有隐藏的节点标签推导出这部分隐藏数据,并计算准确率。[4] 由于这是一个多标签分类问题,学术界通常使用Micro-F1和Macro-F1两个指标来衡量模型效果。

当然,对于图嵌入算法来说,模型输出的并不是分类本身,而是一个表征了节点信息的向量。在这样的情境下,我们一般以这个向量为输入,跑一个简单的分类算法。例如文章[5]就使用了一个“一对多的逻辑回归(one-vs-rest logistic regression)”来分类这些节点的embedding。

算法发展

从历史的角度来看图嵌入算法的发展历程,最初这类算法使用传统概率模型,通过类似于page-rank的思路计算出每个节点属于每一类的概率。接下来,在传统领域,有些学者引入了图的拉普拉斯矩阵与模块度矩阵来优化分类效果。这类做法归根结底是使用更为复杂精巧的数学模型解决问题。

当然,随着深度学习的发展,有很多学者使用了诸多深度学习的方法,比如之前所说的图嵌入与图卷积神经网络。这类方法尝试重现深度学习在其他领域的突破性成功。至今为止,start-of-art的模型当然是基于深度学习的。我们可以从paperwithcode网站的排行榜上面看到当前最新的图嵌入算法。

这些基于深度学习的图算法有很多不同的思路,比如是以DeepWalk[5]、SocialGCN[7]为代表算法的通过随机游走、多重迭代等遍历策略来生成的图嵌入算法。另一种是以SDNE[6]为代表,通过设计损失函数引导梯度下降,来保证嵌入向量能够表示某种特定的图结构信息。详细的介绍可以看本系列另一篇文章 详解图嵌入Graph Embedding之 相关文献综述

更多资料

GraphEmbedding复现代码:https://github.com/shenweichen/GraphEmbedding

详解图嵌入系列传送门:https://mhy12345.xyz/graph-embedding-tutorials/

引用

[1] Niepert, M., Ahmed, M., & Kutzkov, K. (2016, June). Learning convolutional neural networks for graphs. In International conference on machine learning (pp. 2014-2023).

[2] Wang, H., Wang, J., Wang, J., Zhao, M., Zhang, W., Zhang, F., … & Guo, M. (2018, April). Graphgan: Graph representation learning with generative adversarial nets. In Thirty-Second AAAI Conference on Artificial Intelligence.

[3] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2019). A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596.

[4] Tang, L., & Liu, H. (2009, June). Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 817-826). ACM.

[5] Perozzi, B., Al-Rfou, R., & Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710). ACM.

[6] Wang, D., Cui, P., & Zhu, W. (2016, August). Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1225-1234). ACM.

[7] Wu, L., Sun, P., Hong, R., Fu, Y., Wang, X., & Wang, M. (2018). SocialGCN: An Efficient Graph Convolutional Network based Model for Social Recommendation. arXiv preprint arXiv:1811.02815.

浅析文本摘要算法(Document Summarization)

概述

文本摘要算法,指的是在一篇文章中,摘要出核心观点的算法。主流的文本摘要算法生成一篇文章的摘要,摘要长度在3~4句话左右。

历史

在深度学习算法出现之前,人们使用了贪心算法、图算法来研究文本摘要。同时,为了衡量一段生成的摘要是否和标准摘要(gold summary)相似,学术界提出了一系列标准,这些标准现在广泛用于文本摘要算法的模型评价,其中最为常用的就是ROUGE – A Package for Automatic Evaluation of Summarieszz中提到的ROUGE-x系列算法。

深度学习提出后,LSTM/GRU作为摘要生成的强有力工具,一举打破传统算法的效果。最为主流的摘要生成模型是基于抽取式和生成式的,这两种模型将在后面详述。

随着深度学习的发展,很多其他算法也被引入。如一些文章使用强化学习,直接尝试训练一个能够获得最高ROUGE得分的模型。一些文章借助机器视觉方向的研究,优化模型结构。也有文章训练模型,判断句子相对于文章的重要性,进而间接实现摘要提取。

抽取式和生成式文本摘要

既然是摘要,那么显然,摘要中很大一部分都应该是原文中出现过的词语。同时,基于语法的考虑,也需要引入一些没有在原文中出现的词。

这时,就引出了文本摘要算法的两大学派—— 抽取式(extractive)和生成式(abstractive)。

  • extractive算法希望直接从文本中,抽出若干词语,连成一句话。词汇的抽取通常使用循环神经网络,配合注意力机制。得到“下一个词”可能是谁的概率分布。
  • abstractive算法希望从词汇表中,直接选出“下一个词”。

不论是abstractive的文本摘要,还是extractive的文本摘要,模型都由两个部分构成的,即一个编码器(encoder)和一个解码器(decoder)。

  • 对于编码器来说,通常都是将输入文本导入一个循环神经网络,生成出一个上下文特征向量c
  • 对于解码器来说,通常也是使用一个循环神经网络。以编码器生成的表征原文的上下文特征向量c,和之前生成的词汇{y_1, y_2, \dots, y_t},生成出摘要的下一个词y_t

数据集

当前研究人员多使用CNN/DailyMail作为数据集,在该数据集中,每一组数据是一个新闻稿,平均每篇文章39句话。同时还有一个“多句”的摘要。

著名论文

Get To The Point: Summarization with Pointer-Generator Networks

这篇文章提出了一个Pointer-Generator模型,既可以通过Pointer拷贝原文的文字,也可以通过Generator生成不存在原文中的文本。这两个模型通过一个开关p_{gen}进行选择——

P(w) = p_{gen} P_{vocab}(w) + (1-p_{gen})\sum_{i:w_i=w} a_i^t

其中P_{vocab}表示从词汇表中选择一个单词的概率分布,而a_i则是从原文选择第i个词汇的概率分布。

在此基础上,本文还提出了一种称之为覆盖率机制(coverage mechanism)的方式,用以解决抽取式摘要中最容易出现的内容重复的问题。

SummaRuNNer: A Recurrent Neural Network based Sequence Model for Extractive Summarization of Documents

这篇文章核心目标是仅仅是在“句子级别”进行摘要,即从原文中选择若干适合作为摘要的句子。该文章使用两层GRU,依次在“词语”级别和“句子”级别总结信息,最终获得一个可以表征全局性质的向量d。接着,再参考句子级别的特征向量s_i、全局特征向量d、以及RNN的隐状态h_i,生成对于句子的评分。

Ranking Sentences for Extractive Summarization with Reinforcement Learning

这篇文章的核心目标是给一篇文章的句子按照与主题的相关度进行排序,文章指出,在之前的方法中,通常是训练模型,使得对于每一个句子的估价尽量靠近一个指定的ground-true。但提升对于ground-true的近似并不一定能够提高模型的ROUGE评分。因此,文章提出使用强化学习的方式,直接学习句子的label,进一步最大化ROUGE评分(注意,这里ROUGE评价指标是不可导的,因此才需要用到强化学习)。

Neural Document Summarization by Jointly Learning to Score and Select Sentences

这篇文章仍然是句子级别摘要的算法,其思想借鉴了MMR算法,在MMR算法中,借助一个建立在语句集合中的评分函数r(S),迭代选择能够最大化加入后r(S')值的句子。即

g(S_i) = r(S_{t-1} \cap {S_i}) - r(S_{t-1})

g(S_i)可以看做在选择了S_{t-1}后,第i篇文章S_i的评分。使用神经网络结构去学习g(S_i)即可实现——能够参考之前选取句子集合信息的语句选择算法。

BanditSum: Extractive Summarization as a Contextual Bandit

这篇文章也是借助强化学习尝试拟合文本的ROUGE得分,并且提出了新的结构用于防止摘要倾向于前面的句子。

Bottom-Up Abstractive Summarization

这篇文章与Pointer-Generator相似,不过为了解决前文中文本拷贝倾向于拷贝整句话的bug。在输入给Pointer-Generator模型之前,先给输入的文本加了一个mask,过滤掉其中一部分,这样就导致文本不再倾向于拷贝连续的内容。

DeepChannel: Salience Estimation by Contrastive Learning for Extractive Document Summarization

这篇文章训练模型,拟合P(D|S),即给定摘要S,能够恢复原文D的概率。而函数P(D|S)的训练,可以借助文章D,摘要S,一句不重要的话S_2这三部分进行训练。生成P(D|S)后,再使用贪心算法构造摘要集合。

Visdom教程(3):绘制折线图

这是Visdom教程的第三篇文章,主要讲了绘制折线图的方法。


Visdom中,使用函数vis.line绘制折线图,该函数参数表如下——

折线的Y坐标是必要参数。它可以是一个一维数组表示一条直线,也可以是二维数组表示多条折线。该函数的调用可以看示例代码的demo1函数。

line函数还可以设置update参数为’append’。在这种情况下,可以每次只传入新增的数据。示例代码demo2即使一个使用append优化了的绘制深度学习loss函数的例子。

Visdom教程(2):实时展示图片

这是Visdom教程的第二篇文章。主要讲了如何使用Visdom在本地查看服务器上的一个图片。


我们常常使用Visdom实时展示模型训练时刻的图像输出。Visdom支持展示numpy数组形式的若干张图片。展示图片用到了如下两个函数

  • visdom.image(img, win)
  • visdom.images(imgs, win)

第一个函数在win指定的窗口,展示单张图片,而第二个函数则用来展示一系列图片。

  • img是一个表示图片的numpy数组,形状(3,width,height)或者(width,height)形状
  • imgs是表示一系列图片的numpy数组,形状为(batch, 3, width, height)。
  • win表示窗口id,应该可以为任意类型。如果不指定win,服务端将自动新建一个窗口放图片,然后你的浏览器中将堆满密密麻麻的图片窗口。

下面是一个例子——

Visdom教程(1):开启Visdom服务

这是Visdom教程系列文章的第一篇,主要介绍了Visdom的安装。


Visdom是一个Python的远程可视化工具,经常用于配合深度学习训练进行可视化。

Visdom的工作原理是先在远端服务器上面运行一个Server,该服务器将绑定localhost:8097,同时,任意远端运行的Python程序可以通过引入visdom包,实现与该Server的交互。

Visdom服务端假设在服务器上的8097端口,我们只需要执行

安装visdom,并且执行

打开服务端,此时服务端将自动监听8097端口。

下面是一个最简单的visdom程序,该程序在example环境中,新建了一个text_window号窗口,里面写上了Here is the text这句话。

值得注意的是,Visdom中的环境可以理解为工作区,比如一个训练神经网络的程序,训练loss折线图可以输出到train环境中,而模型的内部可视化信息则输出到model环境中。这样可以使我们的工程井井有条。

我们既可以直接通过 server_of_hostname:8097 访问可视化界面,也可以通过ssh命令,将服务器上面的端口映射到本地,并进一步通过 localhost:8097 访问。

ssh name@host.com -p 3522 -L 8097:*:8097 .

 

从零开始使用docker搭建wordpress博客

  • 之前已经写了一个建站日记了Ubuntu 16.04 & Docker 搭建 WordPress,不过之前的版本有点像记流水账一样,现在有时间想重新组织语言,记录一下wordpress博客的搭建流程。
  • 这篇文章适用于那些不希望无脑搭建博客,但又希望以最简单的方式明明白白搭一个博客的读者取用。

本博客是由Wordpress搭建而成,如果你感兴趣的话,可以在博客中四处逛逛,看看这是不是可以解决你的需求的东西。实际上,Wordpress不仅仅可以搭建个人博客,而且还可以设计为公司主页,产品展示页面。接下来,我将从原理上介绍搭建Wordpress的流程。

WordPress博客的组成部分

PHP编写的后端逻辑

WordPress博客是一个使用PHP编写而成的博客系统,Wordpress使用PHP这个世界上最好的语言实现网站的内部逻辑,诸如用户登录,插件管理等功能。至于PHP为什么是世界上最好的语言,有图为证↓。

对于初学者而言,一个使用PHP编写的站点最大的优势,就是我们可以比较方便地修改它。比如这篇文章末尾的转载标签,就是通过手工修改PHP代码实现的(当然这里的手工也是通过博客页面上面的工具实现的),即使你不会PHP,只要知道在PHP语言中 <?php ... ?> 这个代码块内部实现的是程序逻辑,而代码块外面是我们需要显示的HTML代码就好了,也就是说,我们将希望修改的内容放在 <?php ... ?> 外面,就可以很轻松在程序母版上实现内容的添加。

搭载在Nginx服务器上

如果说站点的底层逻辑是使用PHP编写的,那么在这之上,是可以搭载该逻辑的服务器系统,由于服务器独立于实现逻辑(PHP程序和Nginx服务器的关系有点像C++语言和Linux系统一样)。主流的服务器有Nginx和Apache,在这里,我们使用Nginx,服务器本身的功能是监听端口,响应请求,平衡负载。

对于一个没有经过特殊设置的Wordpress博客系统,Nginx服务器将监听80端口(也就是我们使用HTTP访问IP没有指定端口时的默认端口)。网页访问者在该端口上的任何请求都会由Nginx解析,并调用指定的PHP程序渲染出我们希望的页面。

Mysql数据库储存网站数据

在结构上和Nginx服务端并列的,是数据库。数据库是一个为了实现数据的查询和储存设计出来的高性能系统,其功能也仅仅限于提供数据的储存于查询接口。诸如注册用户列表,文章内容等都是存在于数据库中的。Wordpress使用了Mysql数据库,这是一个基于表的关系型数据库,就效率上来说比其他数据库会好一些。

正在执行的一个PHP代码,在特定时候需要访问网站的数据(例如处理用户登录时,需要从数据库拉取指定用户的密码用以检验。)。这时,PHP程序将访问数据库,查询指定用户名对应的密码。

一个未经特殊设置的Mysql数据库,监听端口3306,而本机的其他程序,可以通过向该端口发送消息来与数据库交互。

多模块结合工作

在一般的情况下,打在了PHP网页逻辑的Nginx服务器是一个单一模块,Mysql是另一个模块。Nginx服务器在运行时会时不时地向3306端口发送请求以实现对数据库的查询。

两个模块力求尽可能的独立,这样,倘若因为错误的插件安装,你的网站逻辑部分崩了,你只需要重装Nginx-PHP模块,而不会丢失任何的用户数据。同理,对于数据库的修改也不会影响网站本身。

Docker是什么

Docker的原理

WordPress包含两个模块,他们各自的卸载与重装都不会对另一个模块产生影响。当你的服务器上不仅仅有Wordpress,还部署了其他的网站(这个情况实际上非常常见,谁也不能保证你的服务器永远只有一个博客),情况就不一样了。比如多个网站依赖于不同版本的服务端,或者网站各自的模块重装会互相影响等等…..

这时,我们就开始想Linux下面是否有类似于Python中的Anaconda一样的虚拟环境。倘若将这些模块装在互不影响的虚拟环境中,就可以实现相互独立了。或者说,有没有一个像虚拟机一样的东西,将Wordpress需要的两个模块分别运行在不同的虚拟机中,并使用一定的机制将它们关联在一起?这不,还真是有这么样一个虚拟环境,那就是Docker。

Docker在Linux中充当了虚拟机的角色,但是比虚拟机拥有更高的效率。也许是机智的Linux设计者早就预料好了有今天的需求,Linux的诸多设计使得在Docker这样的虚拟环境成为可能。在Docker中,一个虚拟环境的进程可以和主机进程并行运行(没有一个虚拟机一样的机器做翻译),并且从进程内部看,好像在一个与外界隔离的虚拟机中运行一样。

为了尝试说明Docker的原理,你只要知道下面的事实就好了——

  • Linux中有一个chroot指令,这条指令可以将接下来派生进程的根目录设置为主机的某一个目录,考虑如果有一个目录下有完备的/bin、/etc等Linux必备文件(本身Linux的就有Everything is Files的说法),那么我们使用了chroot将一个进程根目录设置为这个目录,那么看起来,这个进程接下来的运行就好像在一个全新的系统中运行一样!
  • 机智的Linux设计者还提供了其他东西,来解决诸如IP地址冲突,端口冲突的问题,总之,一个“虚拟机”中的进程可以实际运行在主机中而不干扰主机的任何工作。
  • Linux有文件映射与可持久化的机制,可以在一个固定文件版本的基础上,通过增量的方式快速构造另一个只有少量修改的文件版本(比如我有一个Ubuntu系统,我可以同时构造出一个安装了Wordpress的Ubuntu系统和安装了Mysql的Ubuntu系统,而总共占据了1个Ubuntu系统多一点的空间)。

确定了解了上述事实后,我们就很容易理解Docker究竟在干什么了——

Docker中存在两个概念,镜像与容器,镜像是一系列静态的文件打包,比如Ubuntu镜像,里面包含了所有Ubuntu运行需要的文件(也就是我们平常所看到的新的Ubuntu系统从根目录向下的所有文件);而容器则可以理解为可以运行、停止镜像,比如运行着的Ubuntu容器,在镜像的基础上,由于容器自身的运行,其内部的一些文件必然发生改变,Docker以花费极少的空间,用可持久化的方式追踪这些文件。而镜像和容器的关系是:一个镜像可以派生出多个容器,容器在运行并修改了自身后,又可以由特定docker命令固化为镜像。倘若之后读者成功建立了Docker容器,不妨到 /var/lib/docker/aufs/mnt 目录看看,你就知道容器是什么东西了。

在使用Docker建立出的纯净的系统中,我们可以从零开始搭建自己想要搭建的东西,自然而然就会有人建立一些常用环境的镜像并开源。这些镜像都收录于DockerHub中。比较著名的是Ubuntu镜像Mysql镜像以及WordPress镜像。当然,如果将整个系统镜像上传打包实际上是不妥的,用户并不能知晓这个镜像是如何制造出来的,故存在一个称之为Dockerfile的文件可以将生成这些镜像的方法“开源”,Dockerfile内部指名了这个镜像是基于什么镜像,并在该镜像基础上执行了哪些Bash命令得到的。比如我们需要基于Ubuntu镜像生成Mysql镜像可以理解为在Ubuntu镜像的文件系统中执行一条Mysql安装语句(当然,实际的实现可能会复杂一些)得到的新的文件系统。

使用Docker搭建一个博客

下面将介绍如何使用docker的原生命令建立一个Wordpress,该方法也可以在Wordpress的DockerHub镜像页面找到。不过这个方法可以被下一节中的Docker-Compose方法取代——

首先,我们先拉取我们需要的wordpress,以及mysql镜像

这里已经可以看到Docker镜像的文件系统的分层性质了,每一个十六进制的Tag都表示一个文件系统的版本。在生成mysql镜像的时候复用了wordpress镜像的一部分文件。这些文件就是这两个镜像所共有的Linux内核。

在DockerHub的Mysql页面,我们可以找到生成Mysql的容器的命令——

这里,输出结果 5f99a8d32f88f047da392fc764a5bf247a2b07440416a13942fb02891c0ce550 是新建出的容器ID,之后可以使用 docker ps 查看。在这一个步骤,我们建立了名为some-mysql的数据库容器,其密码为my-secret-pw,是基于mysql镜像建立的。

同理,在DockerHub的Wordpress页面,我们可以找到生成Wordpress容器的命令——

这里,我们新建了一个名为some-wordpress的Wordpress容器,依赖于名为wordpress的镜像。单独讲解一下–link参数的意义:由于两个容器互不干扰,可以理解为两个独立的主机,那么他们的通讯方法之一就是使用IP+端口通讯,那么这个参数的意义就是将some-mysql容器的IP地址储存在新建的some-wordpress容器的hosts文件中的一个名为mysql的项中,换句话说,之后再some-wordpress中,访问mysql:3306就能够访问到some-mysql的主机3306端口,进而建立起不同容器的通讯。而-p参数则代表将容器内部的80端口暴露为主机的8080端口。

更多细节有,docker常用的命令还有:

  • docker build :自己写一个Dockerfile,并让docker依照该Dockerfile新建一个镜像
  • docker ps -A :同时打印出由于各种错误导致停止的容器,而非正在运行的容器
  • docker stop :停止容器
  • docker restart :运行一个之前停止的容器

倘若之前的步骤没有任何问题的话,使用 docker ps 可以看到刚刚建立的两个进程正在运行。而如果有问题的话,也可以使用 docker ps -A 看到已经停止运行的容器,并用 docker logs <Container ID> 查看运行日志。

而访问主机的127.0.0.1:8080可以进入Wordpress的初始欢迎页面——

剩余部分就可以自由发挥啦~

Docker-Compose

Docker-Compose是一个可以将之前执行的一系列安装命令自动化的脚本。安装Compose可以按照官方文档的指示安装,由于这个依赖于平台,就不细讲了,如Linux可使用如下命令安装。

安装一个Wordpress使用Docker-Compose只需要在一个自定义的目录中,写一个如下的 Wordpress/docker-compose.yml 文件——

实际上,这个文件中的每一行,都是用来提供之前命令中需要的参数,而与上一节的内容对应,读者应该很容易了解每一行都在干什么——

  • 第一行是新建容器标识,仅仅用于内部的解析使用
  • 第二行是容器基于的镜像名称
  • 第三行、第四行表示内部端口和外部端口的映射
  • 第五行表示一些内部的设置,比如数据库密码等
  • 第六行用于连接mysql容器
  • 第七行是容器名
  • 后面mysql的部分相似

接着,使用 docker-compose -f Wordpress/docker-compose.yml up -d 命令启动。这一个命令可以得到上一节的相同结果。

更多细节是,docker-compose的up参数可以替换为stop、rm等命令。

注意事项

在本文中,我们将内部wordpress的80端口映射到了外部的8022端口,读者倘若希望仅仅建立博客的话,应该映射到外部80端口(因为80端口是HTTP请求的默认端口)。我这样做的原因是我的服务器上面搭载了不同的网站,而这些网站需要通过判断用户访问的域名来决定究竟将请求分发到那个处理容器中,因此在我的处理中,我还有一个外部的nginx服务器,用于域名的分发,将mhy12345.xyz这个域名下的所有访问都映射到8022端口上去,进而被容器截获。

无锁编程教程:强内存模型与弱内存模型


内存重排有非常多种类,但是并不是所有的内存重排都会经常发生。这决定于你是用的处理器类型以及你是用的工具链(toolchain)

一个内存模型告诉你,对于一个指定的处理器或工具链,究竟哪种类型的内存重排可能出现。需要时刻警醒,内存重排仅仅会在多线程无锁编程中才会显现。

经过一段时间的研究——查阅网上的资料以及亲手实验,我成功的将他们总结成为如下4种类型。在下图中,对于所有右边的模型,不仅满足其左侧模型的所有要求,并且还更近一步。通过图示,我们可以画出一条清晰地界限指定强/弱内存模型。

上图中,所有的实际的硬件类型都对应了一个硬件内存模型,而硬件内存模型又对应了一个内存重排的严格性等级。

在内存重排方面,不同类别的处理器表现不尽相同。不过这些表现只有在多核条件下才能表现出来,鉴于多核是当今的一个主流趋势,所以我们需要对这些内存顺序问题有所理解。

有了硬件内存模型,我们也有软件内存模型。技术上来说,当你编写并调试可移植的C11,C++11或Java的无锁代码,你只需要关心软件内存模型。但是了解了硬件内存模型,你可以知道为什么一个错误的代码在某些处理器上运行毫无问题。

弱内存模型

在一个弱的内存模型中,我们可能遇到所有的四种内存重排。这些重排我在之前的文章中已经讲解过了,在不影响单线程程序的情况下,任何的读写操作都会有概率互相交换顺序,这些重排源于编译器和处理器的共同作用。

当一个处理器是弱内存模型,我们倾向于说是“弱有序(weakly-ordered)”,我们又是也会称之为relaxed 内存模型.弱内存模型的一个经典的例子是DEC Alpha. 不过主流的处理器都不是弱有序的。

C11和C++11所描述的弱内存模型在很多方面都是收Alpha影响的,当我们在这些语言中使用底层原子操作时,即便你使用了 x86/64这一类强有序的硬件,你也应该保证正确的内存顺序来保证编译器正确处理编译期间的内存重排。

保证数据依赖性的弱有序模型

虽然Alpha现在已经不再流行了,我们仍然有若干的线代CPU模型继承了弱有序硬件模型的性质

  • ARM,实现中很多手机、平板的处理器,在多核环境下也越来越普及
  • PowerPC,以Xbox 360为典型,也在生活中普及
  • Itanium,现今已经不被Window支持维护,但是仍然被Linux支持,存在于一些HP服务器端。

这些类别对应的内存模型,在很多方面都和Alpha类似,但是他们抱着了数据依赖性(data dependency ordering)。具体来说,如果你在C/C++中写了A->B,那么你永远保证对于B的读取一定至少比A要新,这是Alpha所不能霸主的。对于数据依赖性,我不在这里深究了。

强内存模型

先让我们看看硬件内存模型,强内存模型和弱内存模型的区别是什么呢?对于这个问题,确实有一些争议。但是就我的感觉而言,对于80%的情况,大多数人都有共同的认识。归纳如下——

strong hardware memory model is one in which every machine instruction comes implicitly with acquire and release semantics. As a result, when one CPU core performs a sequence of writes, every other CPU core sees those values change in the same order that they were written.

强硬件内存模型是指,硬件的所有指令都保证了 acquire和release语义。这意味着,当处理器核心进行了一系列写操作,其他处理器核心看到值的改变的一定符合相同的顺序。

这不难通过版本控制的例子想象出来,所有的修改都向共享内存以指定顺序渗透(没有#StoreStore重排),而所有的读取也按照固定顺序(没有#LoadLoad重排),指令的处理也都按照顺序执行(没有#LoadStore重排),在此基础上#StoreLoad仍然是可能的。

在上述的定义下,x86/64系列处理器通常是强有序的,但是在一些特定情况下,这个强有序的保证是不存在的,不过对于应用编写者,我们完全可以忽视这些情况,处理器确实会乱序执行指令,但是这仅仅是处理器内部的问题,重要的是即使如此,所有的内存指令仍然是有序的,因此在多核环境中,我们仍然将其视为强有序的。

运行在TSO模式下的SPARC处理器是另一个强硬件有序的例子,TSO意思是储存全有序(total store order),换句话说,对于向内存的写操作,所有核心有一个唯一的全局的顺序,x86/64也保证了这个性质。从我知道的来看,TSO性质并不被程序员们关注,但是这确实是想顺序一致性又进了一步。

顺序一致性

在顺序一致性内存模型中,内存重排不复存在,整个程序多个线程的指令可以看做不在相交,这时,之前例子中r1 = r2 = 0的情况将不复存在。

现在,想要找到一个多核设备保证了顺序一致性并不容易,不过回顾历史,在1989年,386系列的 Compaq SystemPro 从Intel手册上来看,并没有足够“先进”以至于能够引入运行时内存重排。

顺序一致性一般而言都是作为一个软件内存模型存在的,在编写高级语言时,比如Java5以上你可以定义volatile,在C++11,你可以使用缺省的memory_order指示符,memory_order_seq_cst来实现顺序一致性。倘若你读过Herlihy & Shavit的 多核编程的艺术,注意他们的大多数例子都是基于顺序一致性的。

更多

关于内存模型,还有很多重要的细节,但是在我看来都在工程中不那么重要,比如control dependencies, causal consistency, and different memory types。而对他们的大部分研究都会回到我之前说过的四种组合。

如果你真的希望深入研究,你可以看看剑桥大学的admirably detailed work,以及Paul McKenney的accessible overview 。