[EuroSys 15] PowerLyra基于基于混合切分策略的大图处理系统 学习总结

    今天要讲的文章是EuroSys 2015年的一篇文章，PowerLyra：Differentiated Graph Computation and Partitioning on Skewed Graphs。本文主要想解决的问题就是：现有的图数据，如社交网络、Web网页等都是一种Power-law幂律图的特征。所谓Power-law幂律图就是指在图数据中顶点的度数分配不均匀。有的图顶点的度数很高，有的顶点度数很低。并且顶点度数呈现着幂律分布的特征，对于这种Power-law的图数据，会存在很大的计算分配不均匀的特征。现有的工作PowerGraph分析了在幂律图的特征情况下，采用vertex-cut划分的策略。对于高度顶点，采用vertex-cut，切分成若干个Mirror顶点。利用Mirror顶点减少了高度顶点计算任务繁重的问题，并且采用vertex-cut划分策略产生很少一部分的Mirror。但是PowerLyra的作者发现，在幂律图的情况下，单单只采用vertex-cut的划分策略对于低度顶点来说会产生更多的Mirror。但是低度顶点的度很少，它希望顶点计算尽量在本地执行。所以PowerLyra就采用了一种Hybrid 切分策略，对于高度顶点采用vertex-cut的策略，对于低度顶点采用edge-cut的切分方式。现在我们具体来说说PowerLyra是怎么做的。

1.BackGround

        现如今我们生活在大数据这样的一个时代, 在这样数据的背后吸引着数据科学家们设计出常用的数据分析算法可以作为其中图计算。如交通生物与社交网络。如何使大数据十分有效率处理成为一个重要而及时的话题。

1.1 Graph-parallel Processing

        大多数现有的图处理系统都遵循一个顶点哲学：设计一个图处理算法作为一个以顶点为中心的图处理程序去并行处理每个顶点，并且沿着这些顶点的边进行通信。列如PageRank就可以表示为迭代通信计算模型。每个顶点都会收集它邻居顶点的Rank值，并累加这些Rank值作为它自己新的Rank值，并且这个顶点也会触发**这个顶点的邻居顶点。最终所有的顶点都达到最终收敛状态。一个进行PageRank的算法程序就像这样。

        首先Gather阶段收集邻居顶点数据信息。将收集的信息进行累加，得到一个最终的sum值。

        然后通过Update阶段将累加后的Sum值进行本地更新，将顶点属性值更新到一个全新的状态。

        最后更新Master顶点所有Mirror的属性值，并且根据邻居顶点的出边将邻居顶点执行状态更新为**状态。

1.2 Natural Graphs are Skewed

        目前研究表面，在现实世界中图计算具有真正的挑战性。网络图通常遵循幂律分布。这就意味着有大多数顶点有相对较少的邻居，而少数顶点有着相对较多的邻居。社交网络图是这样一个典型的列子。有的图顶点的度数很高，有的顶点度数很低。并且顶点度数呈现着幂律分布的特征，对于这种Power-law的图数据，会存在很大的计算分配不均匀的特征。

2.Challenge: LOCALITY vs. PARALLELISM

        对于低度顶点来说，低度顶点希望顶点计算LOCALITY更好，具体来说，就是低度顶点希望顶点计算都能够在本地执行，并且能够隐藏网络延迟。高度顶点采用edge-cut，由于高度顶点的边很多，采用edge-cut会造成更多的Mirror。但是对于高度顶点来说，会造成严重的负载不均衡以及很高的锁抢占的开销，以及会带来很高的网络传输的开销。

        对于高度顶点来说，高度顶点希望所有的顶点被并行的执行，高度顶点被切分成多个Mirror顶点来防止顶点执行负载不均衡。但是对于低度顶点来说，低度顶点采用vertex-cut划分的策略会造成更多的Mirror。这样会造成更多的冗余计算和通信开销。在高度顶点PARALLELISM和低度顶点LOCALITY之间，存在一个locality和Parallelism的冲突选择。它们中的任何一个特性都是不能被忽视。

3.Existing Efforts: One Size Fits All

4. Graph Partitioning

        现在我们来研究PowerLyra的Graph Partitioning .对于高度和低度的不同切分方法的改进是收到了edge-cut和vertex-cut的启发。这里有一个列子来描述low-cut和high-cut。

        Low-cut：平均分配低度的顶点沿着他们的边（只能是一个方向的边,比如是入边）通过hash目标顶点均匀分配到各个机器中。

        High-Cut：平均分配高度的入边到每个机器中通过hash他们source顶点。

        从上图中我们发现，PowerLyra的hybrid-cut混合切分策略，复制因子更少。PowerLyra的混合切分策略能够减少复制因子的生成，使整个系统的复制因子更少。

5.Constructing Hybrid-cut

6. Graph Computation

        我们介绍hybrid计算模型：对于与我们的高度顶点和低度顶点都有着不同的计算模型。对于高度顶点来说：分解高度顶点的负载不均衡问题。对于低度顶点模型来说：最小化低度顶点通信开销。         我们都知道在并行图处理系统都有着很差的locality以及很高的通信干扰。在这里我们只讨论通信中存在的问题。通常来说Messages在Master和mirror中交换消息会被批次周期打包发送。并且接收到消息来自不同的节点将会并行的更新顶点信息通过额外的RPC。这将会造成极差的locality由于不匹配的顺序在消息发送方和接受方之间。并且还会造成严重的通信干扰（抢占）。
PowerLyra 则通过局部意识图形布局优化图处理系统中通信极差的locality和通信抢占问题。

PowerLyra 强制在通信上优化locality，但是这也造成了图数据初始化的进入时间开销。

8. Evaluation