PGL Paddle Graph Learning 关于图计算&图学习的基础知识概览：前置知识点学习( 二 ) _生活百科

除了使用向外扩展的分布式图计算系统来处理规模超出单机内存的图数据，也有一些解决方案通过在单台机器上高效地使用外存来完成大规模图计算任务，其中的代表有GraphChi、X-Stream、FlashGraph、GridGraph、Mosaic等。
0.2 图关键技术0.2.1 图数据的组织由于实际图的稀疏性，图计算系统通常使用稀疏矩阵的存储方法来表示图数据，其中最常用的两种是CSR（Compressed Sparse Row）和CSC（Compressed Sparse Column），分别按行（列）存储每行（列）非零元所在列（行），每一行则（列）对应了一个顶点的出边（入边）。
0.2.2图数据的划分将一个大图划分为若干较小的子图，是很多图计算系统都会使用的扩展处理规模的方法；此外，图划分还能增强数据的局部性，从而降低访存的随机性，提升系统效率。对于分布式图计算系统而言，图划分有两个目标：

每个子图的规模尽可能相近，获得较为均衡的负载。
不同子图之间的依赖（例如跨子图的边）尽可能少，降低机器间的通信开销。

图划分有按照顶点划分和按照边划分两种方式，它们各有优劣：

顶点划分将每个顶点邻接的边都放在一台机器上，因此计算的局部性更好，但是可能由于度数的幂律分布导致负载不均衡。
边划分能够最大程度地改善负载不均衡的问题，但是需要将每个顶点分成若干副本分布于不同机器上，因此会引入额外的同步/空间开销。

所有的类Pregel系统采用的均为顶点划分的方式，而PowerGraph/GraphX采用的是边划分的方式。Gemini采用了基于顶点划分的方法来避免引入过大的分布式开销；但是在计算模式上却借鉴了边划分的思想，将每个顶点的计算分布到多台机器上分别进行，并尽可能让每台机器上的计算量接近，从而消解顶点划分可能导致的负载不均衡问题。
0.2.3顶点程序的调度在以顶点为中心的图计算模型中，每个顶点程序可以并行地予以调度。大部分图计算系统采用基于BSP模型的同步调度方式，将计算过程分为若干超步（每个超步通常对应一轮迭代），每个超步内所有顶点程序独立并行地执行，结束后进行全局同步。顶点程序可能产生发送给其它顶点的消息，而通信过程通常与计算过程分离。
同步调度容易产生的问题是：

一旦发生负载不均衡，那么最慢的计算单元会拖慢整体的进度。
某些算法可能在同步调度模型下不收敛。

为此，部分图计算系统提供了异步调度的选项，让各个顶点程序的执行可以更自由，例如：每个顶点程序可以设定优先级，让优先级高的顶点程序能以更高的频率执行，从而更快地收敛。然而，异步调度在系统设计上引入了更多的复杂度，例如数据一致性的维护，消息的聚合等等，很多情况下的效率并不理想。因此，大多数图计算系统采用的还是同步的调度方式；少数支持异步计算的系统也默认使用同步方式进行调度。
0.2.4 计算与通信模式图计算系统使用的通信模式主要分为两种，推动（Push）和拉取（Pull）：

推动模式下每个顶点沿着边向邻居顶点传递消息，邻居顶点根据收到的消息更新自身的状态。所有的类Pregel系统采用的几乎都是这种计算和通信模式。
拉取模式通常将顶点分为主副本和镜像副本，通信发生在每个顶点的两类副本之间而非每条边连接的两个顶点之间。GraphLab、PowerGraph、GraphX等采用的均为这种模式。

除了通信的模式有所区别，推动和拉取在计算上也有不同的权衡：