1.2　图计算系统的分类

利用图对问题进行建模和计算是一门古老的数学分支，其历史最早可以追溯到欧拉于1736年对著名的哥尼斯堡七桥问题的论述，这比第一台通用计算机的诞生时间还要早大约200年。同时，由于图这一数据结构天然适合于研究用某种方式联系起来的若干事物之间的二元或多元关系，图计算一经提出就一直是热点研究方向之一。在计算机研究方面，各种图论算法（如最短路径、最小生成树）和其他通过图进行建模的机器学习和数据挖掘算法（如PageRank，聚落挖掘）都被广泛地应用于生产生活的方方面面，产生了巨大的价值^[10]。然而，随着大数据时代的到来，目前被收集到并希望用计算机系统分析处理的图数据的规模正以极快的速度不断增长。如1.1节中提到的Facebook社交网络的例子，目前需要计算的图数据的规模往往高达数百、数千万乃至上亿条边的级别。在这种情况下，传统的单机全内存图计算系统的计算性能和数据容量就变得不再能满足实际的需求。因此，目前有很多的新技术新方法被业界和学术界的研究人员提出，用于搭建大规模图数据的处理系统。

具体来说，为了解决单机系统内存容量这一瓶颈所带来的问题，一个显而易见的方法就是开发分布式图计算系统。这些分布式图计算系统通过增加机器数的方式横向扩展系统的数据容量和计算能力，因此可以处理极大规模的图数据。前面提到的Giraph系统就是一个典型的分布式图计算系统，其设计原理参考的是谷歌公司于2010年的SIGMOD会议上公开的Pregel系统的论文^[2]。为了方便程序员的使用，这一类系统一般都会提供一个简单易用的上层编程抽象，可称之为编程模型。基于谷歌公司提出的“像点一样思考”的原理，这些编程模型提供的接口函数一般仅仅允许程序员访问和操作整张数据图中的一个点以及其相关的邻域范围内⁽¹⁾的数据。这样做的好处主要有两方面：（1）它极大地简化了程序员的编程过程。在利用这一编程模型进行编程的过程中，程序员并不需要考虑各种各样的底层细节，如当前被处理的这个点具体被分配到了哪台机器上、访问邻域时相邻点的所在是否需要进行远程通讯等问题。因此，无论是单机还是分布式，也无论是一个包含多少台机器的集群，程序员完全可以用同样的一份程序进行计算。系统的横向扩展基本上是完全由系统自动完成的。（2）通过限定每次只操作一个点的邻域使得自动地并行化变得可能。自动并行之所以难以实现的最大问题在于很难自动地推断出一段程序会访问哪一部分的数据，通过直接在编程模型中对这一条件进行限定的方式，图计算的自动并行变得非常简单：只要两个点的邻域交集为空，这两个点对应的程序就可以被并行地执行。

编程模型提供的抽象极大地方便了用户的使用，它同时也意味着用户无法直接访问到全局的信息，以至于很难进行特殊优化。因此，整个程序运行的性能大概率地取决于系统的实现。举例来说，由于用户编程时完全不需要考虑远程通讯，因此整个程序最后产生的通讯量的大小就取决于系统对数据的划分这一自动的过程。如果系统选用了一个效果不佳的划分算法，就很可能导致通讯量过大，从而影响系统的整体性能^[11]。事实上，由于图计算自身的性质，以及单机内存的带宽一般远大于网络带宽这一物理事实，网络通讯正成为制约当前分布式图计算系统效率的瓶颈之一。因此，设计分布式图计算系统时最重要的挑战之一就是如何设计一个好的任务以及数据划分算法。由于其重要性和实际价值，针对这一问题开展了一系列工作。相关的工作会在2.1.2节中予以更进一步的介绍。

在分布式图计算系统这一方向之外，另外一个主要的大规模图计算系统类别为外存图计算系统。这一类系统通过将图数据存放在外存设备上，从而绕过单机内存容量的限制，使得无法访问集群的普通用户也能够处理大规模图数据^[12]。

具体来说，这一类的系统会选择性地将部分当前需要的数据调入内存之中用于计算，同时将不再需要的部分数据换出，从而避免受限于单机内存容量的瓶颈。不过，为了保障这一计算过程的运行速度，外存图计算系统需要确保其对外存设备的访问具有良好的顺序性。外存存储设备的随机访问带宽远低于其顺序访问带宽，然而，图计算本身的特性导致其对数据的访问具有极强的随机性。因此，如果简单地将点和边的数据按照编号顺序存储在磁盘之上的话，最终系统的效率会明显地受限于极低的随机访问带宽。为了解决这一问题，目前的外存图计算系统都设计了精巧的数据组织格式或者访问模式^[12-14]，从而极大地避免了对外存设备的随机访问。2.2节中将具体地介绍这些技巧。总体来说，根据他们的测试，在中等规模的数据集下，基于相关优化工作的外存图计算系统可以达到由几十个节点组成的分布式图计算系统的效率。

除了上述的两种系统外，单机全内存图计算系统^[15-17]依然是一个重要的研究方向。随着诸如三维堆叠^[18]、PCM^[19,20]等存储技术的发展，在可见的未来内拥有TB级内存存储空间的机器也会越来越多，这一类系统的使用范围也因此会变得越来越广泛。更重要的是，单机全内存图计算系统所依赖的单机图计算引擎事实上是包括上述分布式和外存图计算系统这两类在内的所有图计算系统都共享的一个组件，即便是在分布式或者利用外存的情况下，系统某一时刻在某一特定机器上进行的计算依然可以看成是对一张子图进行单机全内存的计算，在原理上和直接在原图上进行计算没有本质上的区别。因此，在探索如何实现一个高效的图计算引擎的过程中发现和提出的技巧也可应用于分布式或者外存图计算系统的设计过程之中。具体来说，图计算引擎的优化主要分为两个方面：一是利用单机多核架构进行多线程优化；二是优化程序的局部性，从而提升系统高速缓存（cache）的利用率。在本书中，主要关注的是后者的相关工作，其主要的方法是利用图这一数据结构和稀疏矩阵在数学上的等价关系，把图计算问题转化成矩阵计算的问题，再利用高性能计算领域内已有的诸多矩阵计算优化技巧对其进行优化^[5]。2.3节中将进行更详细的介绍。

最后，与上述三种存储设备本身不具有计算能力的方案不同，近期还有一些系统被提出。这一类系统基于一种名为Process-in-Memory（PIM）的新型体系结构^[21,22]。举例来说，Micron公司主导提出的Hybrid Memory Cube（HMC）技术^[23]就是一种利用三维堆叠技术实现存算融合的方案。一般来说，一个HMC设备（一般称为一个立方）会是由一组芯片组成的一个三维芯片栈。其中，每一个立方都是由多个存储层和一个逻辑计算层堆叠在一起组成的，因此这一类设备不仅仅具有内存容量高的特点，还可以直接在内存附近利用逻辑计算层上的元件进行近内存的计算（near-data computing）。由于可以被这些逻辑计算层利用的聚合内部带宽一般远高于外部带宽，利用上述的方法在数据传输到CPU之前进行预处理可以有效地提升系统的效率。不过，由于这一系统与传统的系统在体系结构上有着很多根本上的差别，已有的图计算系统往往都不能很好地利用它的特点，因此也无法发挥出很好的性能。为了解决这一问题，学术界的研究人员设计出了一些专门与这一新型体系结构的特点相配合的图计算系统^[21,22]。具体内容将在2.4节介绍。