从数据划分到任务执行的分布式图数据计算简介

一、图数据划分

如同人们所熟知的数据组织方式会影响读写性能，图数据的划分和布局也会对后续的处理性能产生影响。当图的规模超过单个处理器核或单个计算节点的处理能力时，就需要对图进行划分。现有的分布式图计算系统通常将数据的划分简单地等同于任务的划分，其划分目标主要有两方面：一是划分的大小尽量均匀，避免负载不均衡；二是尽可能地减少通讯开销，跨分块的边尽量少。对于一般的图来说，图划分问题是一个NP-完全问题，在实际应用过程中都是采用近似算法来完成的。多级图划分是目前最常用的图划分算法，其基本想法是不断通过收缩顶点和边来粗化（coarsen）图的结构，规模较小时使用已有的较好的算法来做划分，之后再逐步把图还原成原来的样子，并不断优化（refine）划分。这样的算法既能保证较快的速度，也能提供很好的划分结果。这里划分结果好坏的评判是与计算过程密切相关的，同样的划分结果针对不同计算场景的表现有可能存在较大的差异，并不存在所谓“唯一最优”的划分方法或结果。现有的分布式图计算系统通常将数据的划分简单地等同于任务的划分，因此数据划分与编程模型直接相关，可粗略地分成以下几类：

1. Pregel系统所使用的以点为中心的划分方法，也被称为一维划分方法。按照此方法，数据图中的顶点被均匀地划分给不同的机器，每个顶点与它所有的邻边都存储在一起。由于图中的边表示交互关系，如果一条边对应的两个顶点被分到了不同的机器上，在计算过程中这两台机器之间就会产生一次远程通讯。换句话说，在一维划分中，最终的通讯量和被分割的边的数量成正比。由于其简单性，一维划分被广泛使用。尽管如此，一维划分在应对遵循幂律分布的图数据时，仍会产生严重的负载不均衡，影响执行效率。虽然Mizan和GPS进一步引入了动态调整顶点划分的优化技术，但并不能从根本上解决负载不均衡问题。

2. PowerGraph所提出的基于边的划分方法，也被称为点切分（vertex-cut）或二维划分方法。不同于维划分，二维划分将图中的边（而不是点）均分给各个计算节点从而达到负载均衡的目的，这样做的原因是：在大部分图计算应用中，计算开销一般和边数成正比，如果各个计算节点被分配数目基本相同的边，它们的计算负载就基本是均衡的。在二维划分中，度数非常高的顶点被划分给多个节点，因而计算可以并行进行。但由于实际应用要求将与一个顶点相关的所有计算都一次性完成，因此PowerGraph提出了GAS模式与二维划分配合，使得对同一顶点不同边的并行计算成为现实。在二维划分中，通讯量的大小和副本的数量（即顶点被切分成的份数）成正比，虽然PowerGraph以及随后的一些论文都提出了不少减少副本数量的方法，但它们往往难以在划分速度和划分效果两方面都取得很好的结果。

3. PowerLyra系统中所采用的是混合划分（hybrid-cut）方法。混合划分的思想很简单，就是区别对待高度数顶点和低度数顶点。当一条边的终点度数小于预先给定的阈值（一般设为100-200）时，混合划分按照这条边终点的哈希值对其进行分配，反之则按源点的哈希值分配。如此一来，度数较小的顶点对应的所有边都会被分配到同一个计算节点之上（相当于对这些顶点使用了一维划分方法），而度数较大的顶点对应的边则被分配给了不同的计算节点（相当于对这些顶点使用了二维划分方法）。

4. OSDI 2016会议上提出的三维划分方法。上述三种划分方法都将顶点或边所对应的属性作为一个不可分割的整体，但三维划分方法发现，在许多数据挖掘和机器学习应用中，数据图中顶点和边的权值经常是一个向量，可以被再次划分，因此，该方法将数据图中的每个点进一步划分成子点，并把同一个点划分出的不同子点分配给不同的计算节点。正因为引入了这一全新的维度，该划分方法被称为三维划分。三维划分和其他划分算法的主要区别在于：每一个子点只包含原来完整点权中的一部分数据，因此我们可以将更多的子点放在同一计算节点之中。

二、图计算任务执行

图计算任务的执行实际上是要完成任务到资源的映射，其关键是提升数据的局部性。图计算任务的执行除了所遵循的编程模型不同之外，与其他大数据任务的执行并没有根本性的差异。这也是GraphX基于Spark实现的原因之一。传统意义上，人们认为网络是分布式图计算的主要性能瓶颈，因而已有的很多图计算框架的优化工作重心都放在降低网络数据传输的开销上，例如PowerLyra的实验都是在1Gbps甚至100Mbps的以太网环境下进行的。在这样的网络环境下，对单机的性能优化往往被忽略，因而导致很多单机图计算框架（如GraphChi和X-Stream）的性能在某些情况下甚至胜过一个分布式系统，GRAM系统把InfiniBand应用到图计算中，其2-3us的低延迟和高达40Gbps的网络带宽凸显了提升单机处理性能的必要性。

除了利用最新的硬件特性之外，转换数据结构也是发挥硬件潜能、提升执行效率的重要方式现有的分布式图计算框架大部分用图作为后端处理引擎的处理对象。这种方式往往会导致计算顺序的随机性，数据局部性差，因而影响到硬件执行部件的效率。加州大学伯克利分校的研究人员发现，图数据和稀疏矩阵数据在逻辑上是等价的。利用这一特性，他们找到了一系列等价于稀疏矩阵运算的常见的图计算操作，并将它们集合成一个以矩阵为中心的图计算框架CombBLAS。借助于很多已有的矩阵计算优化技巧，CombbLAS具有很高的执行效率。GraphMat也采用了类似的方式，能够自动将用户编写的以图为主要数据结构的程序映射成矩阵操作，并交给矩阵计算引擎进行计算，从而提升后台计算的效率。Gemini系统在上述工作的基础上，针对当前图计算系统的性能与最新的共享内存系统相比还有较大差距的情形，进一步提出了以计算为中心的设计思想，给出了一系列与体系结构（主要是多核处理器和高速互联网络）相关的优化，在保证可扩展性的同时，提升了图计算的执行效率。

区分活动边（活动顶点，即持续更新的顶点所对应的出边）稠密与否的双向更新传播模型。对于稀疏情形，采取推送（push）模型，由活动顶点直接将更新结果推送给邻居顶点，这样，只要处理出边即可；对于稠密的情形，则采取拉取（pull）模型，由顶点主动收集邻居顶点的更新，这样，顶点更新引起的竞争减少了。轻权、基于数据块（chunk）的多级数据划分方法。对于有p个节点的集群，考虑图本身固有的局部性，将其划分成p个连续的顶点块；将顶点对应的出边和入边分别用压缩稀疏行（Compressed Sparse Row，CSR）和压缩稀疏列（Compressed Sparse Column，CSC）格式来表示，进一步减少了内存访问；允许系统根据底层的硬件架构对顶点块做进一步的划分，使得系统能够同时满足更快速的内存访问和更高的Cache利用率。

细粒度的任务调度。在整个集群层面，Gemini采用计算和通信的联合调度，更加有效地实现计算和跨节点通信的重叠；而在计算节点内部Gemini设计了更细粒度的工作窃取机制，以确保不同CPU内核之间的负载均衡。如此一来，硬件得到了有效利用，性能也有了提升。将图计算任务映射到硬件上去执行涉及到众多的因素，既需要考虑硬件自身的特性，也需要结合计算框架和计算过程本身的特点。