图计算的特点与挑战之探讨

图是由点和边构成的一种古老的数据结构，已有上百年历史。由于其优秀的表达能力和坚实的数学基础，图已经在物理、生物、计算机科学等众多领域得到了广泛应用。仅以计算机科学领域为例，图被用来表示通信网络、数据组织、计算流和数据流等。当前广泛应用的分布式计算框架如Dryad、TensorFlow等均根据有向无环图（Directed Acyclic Graph，DAG）作为基本的作业模型。而对互联网和社交网络拓扑结构的分析则揭示了其小世界（smallworld）和无尺度（scale-free）特性。随着信息技术的持续进步以及数据量的不断增长，图上的运算面临越来越多的挑战，基于图的数据处理和分析已经形成了“图计算”这一专门的研究方向，吸引着越来越多的研究者投身其中。

与其他应用相比，图计算应用具有以下几个主要特点：

1. 具有很高的访存计算比。即应用的很大一部分时间都花费在了数据读写（访存）方面，而真正用于计算的时间并不多。对于这类应用而言，其性能的瓶颈在于内存和I/O带宽，优化的关键在于提升数据加载速度，尽可能减少Cache-内存-外存之间的数据交换。此外，重叠计算和通信也会有所帮助。

2. 数据局部性差。数据局部性是为了应对处理器Cache、内存和外存的读写性能差异而引入的提升性能的重要举措，其核心是提升Cache利用率。然而，由于计算模式的多样性以及图顶点之间关联关系的复杂性，尽管已经有了不少优化数据局部性的措施，但现有的图计算应用对系统 Cache的利用率通常都不高。

3. 类型与操作多样。图有很多种类型，从边的连接关系来看，分为有向图、无向图和混合图等；从图本身的特性来看，分为正则图、完全图、二分图、连通图等。图上的操作也是多种多样的，从最简单的度（degree）数统计、邻接点查找、遍历，到复杂的路径查找、着色、流分析（如最大流最小切割）、子图匹配、种子集扩充（seed set expansion），在应用中均有所涉及。二者耦合，产生了丰富的应用场景。

4. 规模巨大，结构不规则。随着社交网络的发展，现实生活中规模达数千万乃至上亿条边的图已经变得十分普遍。更为重要的是，这些图往往遵循幂律（power law）分布，即顶点的度数非常不均匀，一小部分顶点拥有大量的连接，而大量的点只有有限的几条边与之相连，给数据的高效处理带来了巨大的困扰。

上述应用特点并不是孤立的，而是相互交织在一起的。类型与操作多样表明，我们很难找到满足所有应用场景的最优计算方式，甚至连次优方式都很难做到，这也是有大量相关工作存在的最根本的原因。从体系结构的角度来说，由于数据访问速度的差异，高的访存计算比意味着系统Cache的利用率十分重要，然而，图数据本身局部性差使得其对Cache的利用率先天不足。图的巨大规模超出了单台物理机的处理能力，必须扩展到分布式环境中去计算，而局部性差意味着系统需要耗费更多的时间进行大量数据的跨节点传输，而这进一步降低了数据处理的效率；在分布式环境中，由于作业的结束时间就是最后一个任务的结束时间，各个节点之间的负载不均衡会极大影响应用的效率，而结构的不规则如果不加以精心处理，不可避免地会引起负载不均衡。综上，图计算的效率优化是一个非常复杂的问题，充满了挑战。

图计算的一般模型：

计算的基本目标是描述清楚应用需求，在应用需求和硬件环境之间架起桥梁，使得需求中所指定的各种运算能够高效地在给定的硬件上完成，图计算也是如此。应用需求是通过编程模型来描述的，编程模型的易用性和表达能力在很大程度上直接决定了框架的生命力，同时也影响到执行优化的空间；而运算的完成则是由执行框架负责的，它在编程模型所描述的应用需求的指导下，结合硬件环境的特点，自动完成数据的划分、任务到硬件环境的映射（即任务调度）、数据传输和任务执行管理。现有的执行框架通常都支持负载的自动扩展和容错等功能，通过屏蔽底层硬件环境的细节，使得用户能够关注于业务本身。

分布式图计算的任务执行主要有以下三种模式：

一是以 Pregel及其开源实现Giraph为代表的整体同步并行计算（Bulk Synchronous Paralle，BSP）模式。该模式采用以点为中心的编程模型，“每一次计算由一系列的超步（superstep）组成，每一个超步又可以分成本地并发计算、全局通信和同步三个步骤。在本地计算时不产生任何通讯，相对的，全局通讯时也不进行任何计算”。按照这一描述，每一个超步的本地并发计算阶段就是各个节点分别执行点程序的过程，而全局通信阶段则负责把产生的消息送达至相应的计算节点。这种模式的优缺点十分明显：优点是非常简单，无须任何并发控制，而且容易实现基于检查点（checkpoint）的容错机制；缺点是同步开销大，一旦出现负载不均衡，很容易影响执行效率。

二是PowerGraph在GraphLab异步计算模型的基础上所提出的收集-应用-扩散（Gather-Apply-Scatter，GAS）模式。不同于BSP同步计算模型，异步计算模型没有显式的步的概念，每个节点只要有资源就可以调度自己负责的任务，因而运行速度更快。GAS模式采用以边为中心（顶点切割）的编程模型，把度数很大的顶点分割成若干个镜像，每个镜像与一部分边相连，被分配到不同的计算节点上，而程序的执行过程明确地被分割成了收集、应用和扩散三个阶段：在收集阶段，图顶点所有副本同时聚合相邻顶点（可能在本地，也可能在其他节点）的数据并将聚合结果发送给主副本；在应用阶段，主副本将收到的结果汇总到主镜像上，得到该顶点的全局结果（当前值）并将更新后的值同步到所有副本中；在扩散阶段，每个副本将更新后的值按需发送给相邻顶点。GAS模式与BSP模式的最大区别就是，它将那些度数极大的点的计算也并行化了，从而降低了可能的负载不均衡。

三是数据流（dataflow）模式，其典型的代表系统就是GraphX。数据流模式是一种数据驱动的并行计算模型，当输入的数据可用时，对应的程序模块就会被激活，并在资源可用的情况下投入运行，因而可以实现超大规模的并行，而且同步开销更小。GraphX在分布式处理框架Spark的基础上引入了一系列与图计算相关的抽象与操作。如GraphX把图抽象成一对顶点集（collections）和边集，具体的计算则抽象为数据流上的操作。借助于Spark的扩展和容错能力，GraphX能够获得更高的并行度，运行更为可靠。

分布式图计算与单机图计算的差异主要体现在数据传输和任务的执行方面。在单机计算，特别是外存图计算中，系统会选择性地将当前需要的部分数据调入内存之中进行计算，而将不再需要的数据换出，从而避免单机内存容量的限制。数据传输主要是内外存之间的数据交换，任务执行都在本机完成。由于外存存储设备的随机访问带宽远低于其顺序访问带宽，为了保证计算的运行速度，已有的外存图计算系统都设计了精巧的数据组织格式或者访问模式，将随机访问尽可能转变成顺序访问。对于分布式图计算系统，任务执行在多个计算节点上完成，数据传输通过网络将其他计算节点上的数据读取到本地内存之中。与数据的本地读取相比，网络读取延迟更大，速度更慢，因此减少执行过程中的网络通信量对于提升性能至关重要，而这方面起决定作用的因素就是数据和任务的划分。

从数据划分到任务执行实际上经历了两重映射，一是数据到任务的映射，二是任务到资源的映射。从执行效率的角度而言，前者的关键在于保证不同任务之间的负载均衡，并减少不同任务之间的通讯量，而后者的关键在于提升数据的局部性。