2.1 基于分布式集群的图计算系统
在大数据时代，用户所收集到并希望进行分析和处理的数据集的规模正以极快的速度进行增长。这一规律也体现在了图数据当中，例如，城市间的道路图是早期图计算系统所需处理的图数据中最大的一类[25]。不过即使是这一类的图数据一般也只是含有数万个点以及不到百万条的边，完全可以被单个计算节点容纳。但是，随着社交网络等大规模网络结构的发展，现有的图计算系统往往被要求能够高效地处理包含数以亿计条边的大规模图数据。很显然，由于单机容量的限制，这种大小的图数据无法被单机的内存完全容纳。因此，基于分布式集群的大规模图计算系统就逐渐成为一种主流的解决方案[6]。
2.1.1 分布式图计算中的基本概念
作为这一趋势的发端，谷歌公司在2010年的SIGMOD会议上公开的Pregel系统[2]可以被认为是现代分布式图计算框架的起源。其定义的数据模型即数据图（data graph）模型和以点为中心的编程模型（vertex-centric programming）目前仍然是绝大多数后续系统参考和借鉴的对象。
数据模型定义的是如何将一个具体的问题中所需要处理的数据进行形式化定义的方法。而在Pregel系统中所有需要处理的数据都必须要存放在如图2.1所示的一张数据图里。依据定义，数据图为一张有向图，其在各个点之间以边表示的拓扑关系（topology）的基础上还允许用户为每一个点或者边定义属性（property），分别称为点权和边权。例如最常见的在网页互联关系图上求每一个页面的PageRank这一图计算应用，每一个页面会被表示成数据图中的一个点，而每一个从网页a指向网页b的超链接就表示数据图中一条由a指向b的边。最后每个点上维护一个点权，即这一页面的PageRank值。可以注意到，在这个例子中边的权值是被省略了的。
图2.1 数据图模型
在定义了数据之后，Pregel系统的用户就可以通过Pregel提供的以点为中心的编程模型对数据进行操作。和数据并行型的编程框架MapReduce[7]一样，Pregel系统的用户只需依据编程模型给出的接口进行上层逻辑的编写，而无需考虑底层的通讯等具体实现。在Pregel系统中，用户实现的程序被称为点程序（vertex program），其操作范围仅为对应点的邻域（即自己的点权和所有相连的边权），而且只被允许读取入边上的值和修改出边上的值。这些限制的主要目的在于方便并行的实现，理论上只要两个点对应的点程序没有操作同样的数据就可以并行地被执行。由于每一次操作的单元都是一个点，这一类的编程方法又被称为按照“点思维”的思想进行设计的。
在用户对数据和计算都给予了明确的定义之后，Pregel的计算系统将按照bulk synchronous parallel（BSP）的计算模式[26]自动地进行分布式的计算。BSP模式的具体过程可以描述为：每一次计算由一系列的超步（superstep）组成，每一个超步又可以分成本地并发计算、全局通信和同步三个步骤，在本地计算时不产生任何通讯，相对的全局通讯时也不进行任何计算。这种计算模式的好处在于非常的简单，基本不需要做任何的并发控制，同时也便于实现基于检查点（checkpoint）的容错机制。同时BSP的缺点在于同步的开销大，如果负载不均衡的话很容易得到次佳的执行效率。在Pregel系统中，每一个超步的本地并发计算阶段就是各个节点分别执行点程序的过程，而全局通信阶段则负责把产生的消息（附带在出边的边权上）送达相应的计算节点。由于Pregel采用的是基于点的图划分方法（即将数据图中的点均匀地划分给不同的机器，每个点与它所有的邻边都存储在一起），每一条被分割的边（即这条边的两个点被分到了不同的机器上）会产生一次远程通讯。
2.1.2 分布式图计算中任务的划分算法
在进行分布式图计算的过程中，一个非常重要的问题是如何对这个图计算任务进行划分，使得集群中的不同节点可以并行地进行计算。一个好的任务划分系统需要尽可能地同时做好两点：一是避免负载的不均衡。在BSP模型下，每一个超步中的本地计算阶段都需等待所有节点中最慢的那个执行完毕才可以结束。这也就意味着如果任务的分配不够均匀，每一轮的超步中都会有大量的计算资源由于消耗在等待其他节点计算完毕的过程中而被浪费。这显然是不经济的。二是尽可能地减少通讯的开销。虽然目前网络技术的发展十分迅速，但不可否认的是在可以展望的未来，单机的计算速度远高于网络的传输速度的情况还是会普遍存在于实际环境之中的。因此，对于分布式计算系统来说，如何减少网络通讯，防止其变成阻碍系统横向扩展的瓶颈就会一直是一个重要的问题。而图计算由于具有计算简单的特殊性质，这一问题的重要性更加凸显。事实上，也有很多调研结果表明通讯量的增加是影响图计算系统可扩展性的最重要的问题之一[11]。
由于图计算任务划分这一问题的重要性，目前已有很多工作对这一领域进行了研究。最早被广泛使用的方案就是谷歌公司的Pregel系统所使用的以点为中心的划分方法，即将数据图中的点均匀地划分给不同的机器，每个点与它所有的邻边都存储在一起。在这种情况下如果一条边的两个点被分到了不同的机器上，它就会产生一次远程通讯。换句话说，在这种分割方式下，最终的通讯量是与被分割的边的数量成正比的。由于图和稀疏矩阵在数学上是等价的，而在表示成矩阵时一个点相关的所有边是被存放在同一行或者同一列内的，因此这种以点为中心的划分方法一般又被称为一维（1D）的划分方法。
一维划分方法由于其简单性被众多的系统所使用，而其效果在图中点所相邻的边数比较均匀的时候也还可以接受。但问题在于，根据许多的调研结果，实际的图计算应用中常见的图数据往往满足聚集效应的性质。在实际的图数据（real-world graph）中，经常存在一定数量的点占据了图中绝大数量的边的现象，即边的分布对于不同的点来说是非常不均匀的。在这种情况下对图进行简单的一维划分就会造成各个计算节点间重大的负载不均衡这会造成大量的计算资源浪费。
为了解决这一问题，卡内基·梅隆大学的研究人员在2012年的OSDI会议上公开了一个名为PowerGraph的系统[3]。其中提出了基于边的划分方法，也称二维（2D）划分方法。简单地说，二维的划分方法就是将图中的边（而不是点）均分给各个计算节点，从而达到负载均衡的目的。这是因为在大部分的图计算应用之中，计算开销一般是和边数成正比的，因此在各个计算节点被分配的边数基本相同的情况下，各个计算节点计算的负载就基本是均衡的。同时，由于那些度数非常高的点在二维划分的情况下可以被划分给多个节点，它们的计算就可以被并行化。为了达到上述目的，最原始的点程序这一编程模型显然是不合适的，因为它要求一次将与一个点相关的所有计算都完成。因此，PowerGraph提出了一种与点程序类似，但在任务划分粒度上完全不同的计算模型gather-apply-scatter（GAS）。GAS和点程序一样都满足每个点相关的计算只访问其邻域的局部特性，但GAS将点程序的执行过程明确地分割成了收集、应用和散发三个步骤，并通过强制要求收集阶段对每一条边的结果进行聚合时的操作必须满足交换律和结合律的方式，使得对一个点中不同边的计算的并行化成为现实。
PowerGraph系统与传统的Pregel系统最大的区别在于它将拥有极大度数的那些点的计算也并行化了，从而降低了可能的负债不均衡。这解决了任务划分的两个基本需求中的第一个——负载均衡。不过，如果只是简单的利用边的哈希值将它们随机地划分给各个计算节点，依然有可能产生巨大的通讯量。具体来说，在二维划分方法中，如果与一个点相关的边被划分给了X个不同的节点，那么这个点在实际的系统中就需要维护包括一个主节点和X-1个副本在内的X份数据。同时，每一次GAS操作时主节点都必须收集相应的X-1个副本的中间计算结果，并将最终计算后得到的值同步给它们。由此可见，在二维划分方法下通讯量的大小是和副本的数量成正比的。为了减少副本的数量，PowerGraph以及随后的一些论文中都提出了各种各样的方法，然而它们经常难以在划分速度和划分结果这两个方面都达到很好的效果。在此基础上，上海交通大学的研究人员在2014年的EuroSys会议上的论文中提出了一个名为PowerLyra的系统[11]，其通过区别对待高度数点和低度数点的方法（hybrid-cut）达成了一个很好的结果，从而获得了当年EuroSys的最佳论文奖。
事实上，hybrid-cut划分方法的原理很简单，即当一条边的终点度数小于一个预先给定的阈值（一般设为100∼200）时，hybrid-cut将按照这条边终点的哈希值对其分配，反之则按源点的哈希值分配。这样的划分方法基本保证了度数较小的点的所有边会被分配到同一个计算节点之上（相当于对这些点使用了一维的划分方法），同时又会将度数较大的点的边分配给不同的计算节点（即对度数较大的点使用的是二维划分方法），因此被称为组合的（hybrid）划分（cut）方法。进行这样的组合划分的依据也很简单，可以概括为度数大的点数量稀少且很难保证其副本的数量，因此优先保证数量众多的度数小的点不存在副本。
综上所述，经过长时间的研究，目前已有的划分方法在一般的图计算任务上已经能够同时在负载均衡和通讯量减少这两个目标上达成一个较优的结果。但同时也可以看到，目前已有的工作都将图计算任务的划分这一问题等价成了图的划分问题。这一等价关系成立的原因在于目前已有的工作都假定数据图中各个点和边的数据都是不可再分的。然而，根据调研发现，在一类重要的图计算应用中，其数据图中点和边的权值事实上是可以被再次划分的。依据这一发现，本书提出了一种新型的图计算任务划分算法，并将其运用于分布式的图计算系统中，即三维的划分方法。实验表明，这一方法可以极大地减少通讯量，从而提升了系统的效率。关于这一种新的划分方法，将在第3章中进行详细的描述。