图计算简介

图计算中的图英文是Graph，用英文完整的表达就是Graph Computing。图计算是研究客观世界当中的任何事物和事物之间的关系，对其进行完整的刻划、计算和分析的一门技术。简单概括一下，就是，图计算是人工智能的一个使能技术。我们可以大致将人工智能的基本能力分成三个部分，第一部分就是理解的能力，第二部分是推理的能力，第三部分就是学习的能力，简称URL（Understanding，Reasoning，Learning）。而图计算是与URL息息相关的。举例来说，要对整个现实世界有一个客观、完整、全面的认识，那就需要一个理解的能力。图计算技术能够把任何事物之间的所有关系全部刻画出来，完整地描述出来。另外，在一些事物和事物之间，其关系并不是那么显性，需要通过一些推理才能够推导出来，图计算就能够通过推理的方式在事物中找到隐藏的一些关系，这个对于我们也非常有帮助。第三个就是图计算为人工智能提供的学习的能力，它能够将第一步中提到的理解刻画能力和第二步中的推理能力相结合，实现对任何一个事物的一个模式上的总结、演绎和描述。也就是说，图计算能够对事物进行抽象，这个抽象的过程就是人脑综合能力的一个重要体现。

图计算 vs 图数据库

图领域按照「应用场景」主要分为2部分：

• 图数据库：主要用于联机事务图的持久化技术，通常直接实时地被应用程序访问，和常见的联机事务处理（online transactional processing, OLTP）数据库是一样的。
• 图计算引擎：主要用于离线图分析技术，通常按照一些列步骤执行，它们可以和其他大数据分析技术看作一类，比如数据挖掘和联机事务分析（online analytical processing，OLAP）。

图数据库

图数据库，是图数据库管理系统的简称，它是一种在线的图数据库管理系统，支持对图数据模型的增、删、改、查(CRUD)方法。图数据库一般应用于事务（OLTP）系统中，所以在研究图数据库技术时需要多加考虑2个特性：

• 底层存储：底层存储分为原生和非原生。某些系统是（Neo4j、OrientDB）为了存储和管理图而专门设计；而也有一些图数据库（比如 Titan、InfiniteGraph）是将图序列化，然后存储到其他数据库中。
• 处理引擎：一些定义要求图数据库使用「免索引邻接」，这意味着，关联节点在数据库里是物理意义上的“指向”彼此。

相比于传统的关系型数据库和其他NoSQL数据库，免索引邻接带了了非常巨大的性能优势，而且我们得到的模型更简单，更具表现力。

图数据库的代表：Neo4j

Neo4j 是一款独立的图数据库产品，偏向于存储和查询。图存储是说它能装那些关联关系比较复杂，实体之间的连接很丰富，就像一张网或一张图的数据。比如社交网络，知识图谱，金融风控等领域的数据。图查询是说它擅长从某个点或某些点出发，根据特定条件在复杂的关联关系中找到目标点或边。比如说在社交网络中找到我三步以内能认识的人，这些人可以认为是我的潜在朋友。这种数据量限定在一定范围内，能短时完成的查询就是所谓的 OLTP 操作。

图计算引擎

图计算引擎技术，偏重于全局查询，通常都对于对与批处理大规模数据做过优化。只有一部分图计算引擎有自己的存储层，其他的都只关注与如果处理外部传入的数据，然后返回结果到其他地方保存。大多数的图计算引擎都是基于Google发布的 Pregel白皮书 ，白皮书中主要介绍了Google如何使用图计算引擎计算网页排名。

图计算的代表：Hadoo/Giraph，Spark/GraphX

GraphX 是一个 Spark 的一个子模块，它是一个图计算系统，也可以说是图分析系统，它不去承担数据存储的职责。图分析和图查询的区别在于：图分析往往是整张图的操作，而且可能是多次迭代；而图查询只涉及图的一部分，且只需一次。对用户而言最直观的感受是：图分析很慢，图查询很快。这种涉及到整图或大量节点/边，较长时间才能完成的查询就是所谓的 OATP 操作。

Giraph是一个迭代的图计算系统。基于Hadoop而建，将MapReduce中Mapper进行封装，未使用reducer。在Mapper中进行多次迭代，每次迭代等价于BSP模型中的SuperStep。一个Hadoop Job等价于一次BSP作业。

Facebook针对图数据处理对Apache Giraph 和 Spark GraphX的比较。他们发现在通常情况下Giraph能够更好地处理生产级负载，而Spark GraphX提供的几个特性，能使图数据处理解决方案的开发更简单。该性能测试有如下关键发现：

• Giraph即使在较小规模的图数据集上执行得也更好些。Giraph的内存使用也更加高效。
• GraphX支持以SQL样式的查询从Hive中读取图，支持任意列转换。使用shell环境中的Scala是一种测试GraphX简单应用的简便方式。

最后，该团队总结说，GraphX不足以支持他们图处理负载的扩展性和性能需要。

图计算系统和图数据库系统有很多相似之处，但是一般来说，二者有如下区别：

图计算系统图数据库实时性offlineonline负载类型graph algorithmsquery，一般要提供查询语言输入数据格式抽象图业务图优化的重点迭代式图遍历高并发写入和查询事务和一致性不要求高要求容错性考虑较少需要考虑，特别是分布式模式下

图计算系统分类

单机内存图处理系统

此类图计算系统单机运行，可直接将图完全加载到内存中进行计算。但是单机的计算能力和内存空间总是有限，故只能解决较小规模的图计算问题，比较有代表性的系统有2013年发布的Ligra和Galois,以及2015年发布的GraphMat和Polymer。

其中Ligra提出了根据图形稠密情况自适应的切换计算模式，并提供了一种基于边映射，顶点映射以及顶点集映射的并行编程算法。Galois使用DSLs（domain-specific languages）写出更复杂的算法完成图分析工作，并发现当输入图是道路网络或者具有较大直径的图时能获得一个数量级的性能提升，在现有的三种图DSLs基础上提供了轻量级的API，简化了图算法的实现。GraphMat是第一个对多核CPU进行优化的以顶点为编程中心的轻量级图计算框架，为用户和开发者提供了个友好的接口。Polymer则是针对在NUMA特性的计算机结构上运行图算法的优化，作者发现无论是随机或者交错地分配图数据都会重大的束缚数据的本地性和并行性，无论是intra-node还是 inter-node，顺序访存都比随机访存的带宽高的多。

单机核外图处理系统

此类图计算系统单机运行，但是将存储层次由RAM拓展到外部存储器如SSD，Flash，SAS，HDD等，使其所能处理的图规模增大。但受限于单机计算能力和核外存储系统的数据交换的带宽限制也无法在可接受的情形下处理超大规模的图数据。典型的图计算系统有 GraphChi, TurboGraph, X-Stream, PathGraph,GridGraph和FlashGraph。

这些系统在最大化磁盘顺序读写，选择调度和同异步计算模式等方面做出了重要探索。TurboGraph和FlashGraph主要采用分页方式分割图来提高内外存的数据交换性能。其中GraphChi采用了传统的以顶点为中心的编程模型，计算模式为隐式GAS。它使用了名为shard的核外数据结构来存储边，而将顶点划分为多个连续的区间。提出了一种基于并行滑动窗口（PSW）模型达到对存储在磁盘上的图数据最大的顺序读写性能。但是构建shard是需要对边按源顶点排序，这样耗费了大量的预处理时间，PWS对计算密集型的算法更有利。另外在构建子图时出现大量的随机访存现象，通过顺序地更新子图内有共享边顶点来避免数据争用问题。

X-Stream则介绍了一种以边为中心的编程模型。在scatter阶段以流的形式处理每条边和产生传播顶点状态更新集，在gather阶段它以流的形式处理每一个更新并应用到对应的顶点上。自然图中顶点集远远大于边集，所以X-Stream把顶点存储在高速存储设备（Cache对于RAM，RAM对于SSD/Disk）中表现为随机读写，把边集和更新集存于低速存储设备中表现为最大程度的顺序读写。X-Stream流式访问图数据，其流划分相比于GraphChi无需对shard内的边进行排序大大缩短了预处理时间，并使用work-stealing避免Scatter-Gather导致的线程间负载不均衡的问题。但是X-Stream在计算过程中，每轮迭代产生的更新集非常庞大，接近于边的数量级；而且需要对更新集中的边进行shuffle操作；缺乏选择调度机制，产生了大量的无用计算。

GridGraph将顶点划分为P个顶点数量相等的chunk，将边放置在以P*P的网格中的每一个block中，边源顶点所在的chunk决定其在网格中的行，边目的顶点所在的chunk决定其在网格中的列。它对Cache/RAM/Disk进行了两层级的网格划分，采用了Stream vertices andedges的图编程模型。计算过程中的双滑动窗口（DualSliding Windows）大大减少了I/O开销，特别是写开销。以block为单位进行选择调度，使用原子操作对保证线程安全的方式更新顶点，消除了X-Stream的更新集和shuffle阶段。其折线式的边block遍历策略不能达到最大化的Cache/Memory命中率。

分布式内存图处理系统

此类图计算系统将图数据全部加载到集群中的内存中计算，理论上随着集群规模的增大其计算性能和内存容量都线性增大，能处理的图数据也按线性扩大。图分割的挑战在分布式系统愈加明显，再加上集群网络总带宽的限制，所以整体性能和所能处理的图规模也存在一定的缺陷。这类图计算系统主要包括同步计算模型的Pregel及其开源实现Piccolo,同时支持同步和异步的系统PowerGraph,GraphLab和GraphX。PowerSwitch和PowerLyra则对PowerGraph做了改进, Gemini则借鉴了单机内存系统的特性提出了以计算为核心的图计算系统。

Pregel是首个采用Vailiat的BSP计算模型[26]的分布式内存图计算系统，计算由一系列的“超步”组成，在一个超步内并行地执行用户自定义函数。Pregel在编程模型上遵循以图顶点为中心的模式，在超级步S中会汇总从超级步S-1中传递过来的消息，改变顶点自身的状态，并向其它顶点发送消息，这些消息经过同步后会在超级步S+1中被其它顶点接受并处理。允许通过增加/删除点和边改变图的拓扑结构，在对同步消息进行了聚合优化。但是有些算法在BSP同步模型下收敛性很差，采用随机hash切边法带来了巨大的网络通信开销。

GraphLab主要是针对MLDM应用开发的图计算系统，故先详细分析了MLDM算法的特性，并对图计算中数据一致性模型做了详细阐述。PowerGraph针对power-low特性的自然图详细分析工作负载，图分割，通信，存储和计算等各方面带来的挑战。提供了完善的图分割数学理论支撑，证明切点法比切边法能提高一个数量级的图计算性能。故PowerGraph使用p-way切点法，采用了以顶点为中心的GAS编程模型，增加了细粒度并发性同时支持同步和异步模型。但它不支持图的动态修改，容错机制未能充分利用顶点副本。

PowerLyra和PowerSwitch分别从图分割和同异步模型两方面对PowerGraph进行了改进。PowerLyra提出了一种混合图分割方法hybrid-cut，即出入度高的顶点采用切点法反之出入度低的顶点采用切边法，经过试验对比性能提高了至少1.24倍。PowerSwitch首先分析了同步和异步计算模型在网络通信和算法收敛速度的特征后提出了一种混合图计算模型Hsync，通过一系列的运行时分析和定量计算可动态的切换计算模式，相比于PowerSwitch有一定的性能提升。

Gemini在单机内存图计算系统的高效性和分布式内存图计算系统良好的伸缩性之间找到差异性，而提出的以计算为中心的图计算系统。它针对图结构的稀疏或稠密情况使用于与Ligra相同的自适应push/pull方式的计算，并在现代NUMA-aware特性的内存中采用基于chunk的图划分进行更细粒度的负载均衡调节。实验表明Gemini的性能得到重大提升了，其性能至少能达到现有已知分布式图处理系统的8.91倍。可见在单机上从内存结构和CPU架构等更细层面提高图计算的能力对整体集群的图数据处理性能的改善也很显著。

分布式核外图处理系统

此类图计算系统将Single-machine out-of-core systems拓展为集群，能够处理边数量级为trillion的图，目前仅有2015年发布的Chaos。Chaos是对X-Stream系统的拓展，分别设计了计算子系统和存储子系统。它的主要贡献表现在：是第一个拓展到多机核外存储结构的图计算系统；采用简单的图分割方案，即不强调数据的本地性和负载均衡，而是通过存储子系统达到核外存储的高效顺序读写；使用work-stealing[26]机制实现动态负载均衡。但是Chaos存在设计缺陷，随着集群规模的伸缩网络将会成为系统瓶颈；简单的拓展未优化的X-Stream，其更新集依然很庞大与边量级相当；计算与存储独立设计增加了系统的复杂性和不可避免的通信开销；存储子系统为了使存储设备时刻忙碌而占用了较多的计算资源。

图计算系统的困难性

本质上是高性能并行计算的问题。

高性能来自于如下4各方面的匹配：

• 要解决的问题
• 算法设计
• 用来运行算法的框架
• 用来运行框架的硬件

图计算带来的挑战：

• 计算量encoded再图结构中（纯静态graph partition效果差）
• 图结构无规律（很难拿partition graph，造成load imbalance）
• 局部性差（难以利用cache，频繁访存）
• 数据访问/计算ratio高（频繁访存）

常见图计算系统

常见的图九三系统及其主要贡献：

图计算系统主要贡献Pregel2、提出Vertex-Centric计算模型

3、使用Combiner&Aggregator 减少通信

Ligra2、Coordinated Scheduling

Polymer1、 提出使用NUMA来提升性能GraphChi2、 Incremental-computation with dynamic graphs

GraphX2、Easy ETL intergration

XStream2、streaming completely unordered edge lists rather than performing random access

PowerGraph2、GAS

3、Vertex-partitioning，3种边分区方法：Random、Coordinate Greedy、Oblivious Greedy

4、3 execution mode：syn、async、async+serializable

5、Delta-cache，caching partial sum

Polymer2、for some remaining random accesses, Polymer carefully converts random remote accesses into sequential remote accesses, by using lightweight replication of vertices across NUMA nodes

Galois2、a topology-aware work-stealing scheduler

3、autonomous, speculative execution

4、allows application-specific control of task scheduling policies.

Gemini2、Locality-preserving Chunk-based partition

3、Dual compression vertex indices

4、fine-grained work-stealing

GMiner2、streamline tasks so that CPU computation, network communication and disk I/O can process their workloads without waiting for each other

JoyGraph简介

JoyGraph是京东自研的单机共享内存式（Shared-Memory-Processing）图计算系统，主要特点为：

• 单机Shared-Memory-Processing
• 增量数据aware
• Vertex-Centric编程模型
• Mult-Level Vertex & Edge Partitioning
• Work-Stealing & Selective-Scheduling
• Push/Pull双模式自适应
• NUMA-aware
• 内置多种算法包
• 算法开发者友好的API
• 可定制性（Parse/Initialization/Algorithms等过程）
• 与“图灵”平台集成

JoyGraph实现

架构以及核心数据结构

• 以顶点为中心构造，邻接表出/入边数组和出/入边索引数组
• 顶点区间分割
• 辅助Bitmap和Vertex_Array
• Multi-Level Partition(详见“负载均衡”)

NUMA-Aware

有研究表明，NUMA(Non-Uniform-Memory-Access)架构下，local(访问本地NUMA-node的本地内存)数据访问带宽是remote(访问远程NUMA-node的内存)的2倍，延迟是remote的1/2。支持NUMA对提高图计算系统性能至关重要，NUMA影响了对图的构造和运行时的动态负载均衡。

以上是图的构造过程，JoyGraph框架是如何执行用户自定义的Vertex-Centric算法？各数据结构在算法迭代过程中是如何起作用的呢？

图计算执行过程

典型的Vertex-Centric执行模式，用户自定义的顶点更新函数，更新顶点和其邻居的状态，并vote活跃状态。JoyGraph框架内部进行了并发处理。

在执行用户自定义的UpdateVertex函数时，由于不同的顶点的出入度不同，沿着出边还是入边更新，代价是不同的，push/pull模式用来自适应地选择最高效的执行方式。

push/pull双模式

负载均衡

图遍历的过程要充分利用NUMA架构，发挥多cpu和多核的计算能力。JoyGraph采用静态和动态负载均衡来实现。

静态负载均衡：两阶段顶点集划分

• 一次划分：首先依据每个Socket(NUMA-Node)分摊到相等数量的边集的标准，将顶点集静态分配到每个Socket（顶点chunk）。由于每个顶点的出入度不同，每个Socket级别分到的顶点chunk大小不一。
• 二次划分：再按照每个Socket内部每个Core(=Thread个数)分摊到相等数据量的边集的标准，再次将顶点集二次划分给每个Socket内部的每个Core，同理，每个Core分到的顶点chunk一般也大小不一。

以上静态划分，并不能完全保证运行时每个Core的负载相同，需要同时采用运行时动态负载均衡措施以充分利用cpu：

• Work-Stealing: JoyGraph每个Thread(每个Core)有2种状态：Working和Idle，Idle时可以steal其他Core的负载，steal负载的粒度可根据图活跃边集的稠密程度来动态调节。
• NUMA架构下，由于NUMA-node间带宽和延迟的代价不同，优先steal同Socket(NUMA-node)下其他Core的任务，然后再按照顺时针(逆时针) steal其他Socket的任务。

小结和展望

JoyGraph目前已实现：lpa、louvain、cc、scc、wcc、mssp、apsp等算法(持续扩充中)，并提供自定义算法开发接口，包括load&parse&filter、graph initialization、dense_vertex_update、sparse_vertex_update、IO等过程均可自定义。未来Joygraph将在如下方向上持续发力：

• 自研图数据库引擎，将图计算内置到图数据库中，实现OLAP
• 图计算集成图数据可视化和调度服务，实现“流程即服务”
• 丰富算法包并持续优化系统性能
• 提供在线Notebook式的交互式图算法开发和分析工具，提供从图数据探索、图算法开发、图算法部署上线的一站式平台，并集成到“图灵”平台中。