1.3 图数据高效计算的挑战
早期的大规模图计算系统主要关注的是两个问题：（1）提升可扩展性，即通过将图计算系统横向扩展到单机多核乃至于多机分布式环境下获得更高的处理速度，同时通过增加计算节点的数量扩大系统能够处理的数据规模；（2）加强易用性，即通过设计简单的编程接口的方式抽象出一个编程模型，屏蔽底层复杂细节方便程序员的使用。简单地说，这两个问题属于“能不能”的范畴之内。如果系统无法有效地扩展其计算速度和处理容量，那么它就无法应对当前海量数据所带来的挑战（要么直接存不下，要么存得下但是运算速度太慢，以至于没有实际意义）。同时，即便是解决了可扩展性的问题，如果系统的易用性不够，以至于编程的难度高于普通程序员所能接受的范围的话，这样的系统即便存在也很难得到推广。相对的，由于在这两个方面取得的重大进展，目前大规模图计算系统在各方面都已经到达了可用的阶段，并且已经投入大规模实用，成为各大商业公司数据处理系统的标准配备之一[6,10]。
在解决了“能不能”的问题之后，业界和学术界的研究人员就将目光转向了“好不好”的方向。具体来说，当前图计算的主要热点研究方向在于回答当前的图计算系统的效率是否足够高，是否完全利用了硬件的能力，还有没有优化的空间等问题。然而，由于图计算应用本身的一些特点，对其进行性能调优是非常困难的，因此早期的简单实现往往效率不高。
1.3.1 图计算的特点
图计算应用主要有以下几个特点。
（1）其计算具有很高的访存计算比。以PageRank这个最常见的图计算应用为例，在每一轮迭代过程中，程序所需进行的计算是每条边做一次累和（计算新的PageRank值），每个点做一次除法（除以对应点的出度），然后每条边再做一次赋值，都是非常简单的操作。因此，在这种情况下，程序的整体运行时间被数据的读写所主导。换句话说，对于一个单机的图计算应用，往往是内存带宽成为限制其速度的瓶颈，而不是CPU的处理速度。
（2）其数据局部性差，因此对系统缓存的利用率往往都不高。图计算典型的数据访问模式是在访问了图中的一个点之后访问其临域范围内的边和点。为了提升程序的数据局部性，一个简单的想法就是将一个点和其邻域内的数据放在一起。但是，由于图中点与点之间复杂的联系，很难同时提升所有点的局部性，往往会出现的一种情况是提升了一个点的局部性的同时降低了多个其他点的局部性。所以，如何设计一个能够综合考虑全局的方法是非常重要的，但同时也是非常困难的。
（3）其结构不规则。和数据分布非常规则的稠密矩阵等数据类型不同，现实生活中的图数据往往分布非常不均匀。正如将在2.1.2节详细描述的，从实际生产生活中采集到的图数据基本都符合聚集效应（power law）的性质，即点的度数非常不均匀。可能有一小部分点拥有极其大量的边与之相连，同时又有大量的点只有有限的几条边与之相连。在这种情况下，一个简单的规则划分方法就经常产生非常大的负载不均衡，从而影响程序的效率[3]。
（4）受数据驱动。一个图计算应用在实际执行的过程中产生的访问模式等特性基本都取决于其输入的图数据。因此，即便是同一个种类的图计算应用，在接受不同的图数据作为其输入数据时表现出来的特性的差别也可能很大。而图数据本身的种类又非常丰富，这无疑增加了优化的难度。
事实上，上述四个不同的特性是相互关联的，比如（1）和（2），（2）和（3），还有（3）和（4）这几组特性之间都存在某种放大关系。正是因为图计算的访存计算比高，所以对图计算应用来说其系统缓存的利用率就显得非常重要，而图计算应用数据局部性不好的特性使得其对缓存的利用率先天就不高。同时，由于图数据结构的不规则性，对其进行局部性优化比对稠密矩阵计算这一类规则数据上的优化要难得多。最后，图计算应用本身受数据驱动的特点导致用户也很难通过针对计算过程本身的特性进行效率优化，只能考虑针对图的特性进行优化。综上所述，由于图计算同时具有上述四个特性，其效率优化是非常复杂的一个问题。
1.3.2 现状和主要优化方向
鉴于图计算的这些特点，一个简单的实现和一个经过深思熟虑地优化后的实现相比经常会有非常巨大的性能差别。而在早期图计算系统的设计和实现之中，一般开发人员主要专注于解决之前提到的两个“能不能”的问题，例如提升系统的可扩展性。相对的，他们对单个计算节点上的运行效率的关注度不高，因此其硬件资源的利用也都没有做到极限。举例来说，来自微软的研究人员在他们的调研过程中测量了一种被他们命名为COST（configuration that outperforms a single thread）的指标[24]。一个系统的COST值为c意味着这一系统只有在横向扩展到c个计算节点的规模之后，其运行速度才能超过一个经过仔细人工优化后的单线程实现。显然，COST的值越小意味着系统对硬件性能的利用率越高。但是，根据微软的研究人员的测试，很多非常常用的分布式图计算系统的COST值都高达上百[24]。这也意味着，虽然这些系统具有不受单机内存容量限制、编程简单等诸多优势，但它们在运行效率方面都还有着非常大的优化空间。
为了解决这一问题，目前也已经有很多的工作着力于提升图计算系统的效率。相关的工作会在第2章介绍。不过总体上来说，由于对于图计算的高访存计算比，其性能的优化主要集中于提升将数据载入到合适位置的速度。因此，根据不同情况下数据的载入途径，本书将优化的方法根据其应用场景分为四个不同的类别。图1.1给出了在不同种类的图计算系统下图数据的载入途径。
首先，对于分布式图计算系统来说，其每一个计算节点维护的是一张子图的数据。同时，由于数据图中各点之间普遍存在的联系，原图中部分点或者部分边会被同时指派给多个计算节点。在实际的计算过程中，这些同时被分配给多个计算节点的点和边会需要通过远程的数据通信来进行数据的同步。因此，对于这一系统，其数据的载入途径分为两个阶段：一是从其他计算节点上通过网络将需要用于同步的数据读取到本地的内存中；第二步则是与单机的图计算系统一样，将数据载入系统的缓存中以供计算。由于第二步从内存到缓存是被多种不同类型的图计算系统所共享的，所以其相关的优化会稍后提到。相对的，第一步的从网络上读取数据到本地的内存是分布式系统所独有的过程。为了尽可能地缩短这一步骤所需的时间，最显而易见的方法就是减少网络通讯的总量。而在分布式图计算系统中，对其运行时的通讯量起到决定性影响的因素就是其任务的划分方法。因此，目前有很多工作着眼于如何巧妙地划分图计算任务和图数据，从而应对在保障各个计算节点间的负载基本均衡的情况下尽可能地减少通讯量这一问题。在2.1.2节将对已有的几种划分方法进行介绍。总体来说，它们中很多都是基于图数据中点的度数分布是满足聚集效应的这一性质进行的。
图1.1 各种图计算系统中数据载入的途径
其次，1.2节中提到，除分布式图计算系统之外，外存图计算系统也是很大的一类大规模图计算系统。在这一类图计算系统中，数据的载入过程也是分为两个步骤，并且第二步与分布式图计算系统一样，是从内存载入缓存中进行计算。不过，不一样的地方在于外存图计算系统数据载入的第一步是从外存设备而不是从网络将数据载入内存中。因此，由于当前外存设备顺序访问和随机访问间巨大的带宽差距，在这一情况下主要的优化方法在于提升对外存设备访问的顺序性。2.2节将简述几种图数据在磁盘上的组织和访问方式。它们应对这一挑战的主要方式都可以总结为通过巧妙的数据组织，将随机访问转化成多次的连续块状访问。
无论是从网络还是从外存设备，将图数据载入本地的内存之后都需要进一步地将其载入缓存中用于计算。而为了提升这一过程的效率，主要的方法是提升程序的数据局部性，从而提升缓存命中的概率。目前，这一环节的主流优化方式是通过利用图这一数据结构和稀疏矩阵间数学上的等价特性将图计算操作转化成矩阵操作，再利用高性能计算领域内已有的针对矩阵计算的优化方法对其进行优化。具体的方法将在2.3节介绍。
最后，与上述这几种路径都不同，目前以PIM为代表的新型体系结构给出了一种全新的基于存算融合技术的计算模式。存算融合的情况下，存储设备是和相应的计算设备用三维堆叠技术堆叠在一起的。换句话说，在这种体系结构中并没有多层的数据载入途径，而是直接在数据上进行计算。这一模式也被称为近数据计算。不过，由于这是一种全新的体系结构，如果上层的系统不根据其独有的特性进行优化就无法发挥其最好的性能。因此，目前有一些研究人员提出了在这一架构下专用的图计算系统。2.4节将简述这一方向下的几种主要方案。