京东自研图计算系统 | JoyGraph

来这里找志同道合的小伙伴！

图计算简介

1、 图计算 vs 图数据库

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

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

类比graphX和Neo4j，可以初步感受一下：

2、图计算系统的困难性

3、常见图计算系统

如下简要列举一下对JoyGraph实现有比较大影响的图计算系统：

图计算系统	主要贡献
Pregel	1、Bulk-Asynchronous-Processing模式的典型实现 2、提出Vertex-Centric计算模型 3、使用Combiner&Aggregator 减少通信
Ligra	1、提出在dense和sparse模式下分别使用pull和push 2、Coordinated Scheduling
Polymer	1、 提出使用NUMA来提升性能
GraphChi	1、提出Parallel-Sliding-Window来提高缓存命中率 2、 Incremental-computation with  dynamic graphs
GraphX	1、Build on RDD，表达能力强 2、Easy ETL intergration
XStream	1、Edge-centric 2、streaming completely  unordered edge lists rather than performing random access
PowerGraph	1、图的power-law特性 2、GAS 3、Vertex-partitioning，3种边分区方法：Random、Coordinate  Greedy、Oblivious Greedy 4、3 execution mode：syn、async、async+serializable 5、Delta-cache，caching partial sum
Polymer	1、differentially allocates and  places topology data, application-defined data and mutable runtime states of  a graph system according to their access patterns to minimize remote accesses 2、for some remaining random  accesses, Polymer carefully converts random remote accesses into sequential  remote accesses, by using lightweight replication of vertices across NUMA  nodes
Galois	1、supports very fine-grain  tasks 2、a topology-aware  work-stealing scheduler 3、autonomous, speculative  execution 4、allows application-specific  control of task scheduling policies.
Gemini	1、Extend pull/push mode in SMP to  distributed environment 2、Locality-preserving Chunk-based  partition 3、Dual compression vertex  indices 4、fine-grained work-stealing
GMiner	1、computation-intensive and  memory-intensive graph mining workload 2、streamline tasks so that CPU  computation, network communication and disk I/O can process their workloads  without waiting for each other

JoyGrap简介JoyGraph实现

1、架构以及核心数据结构

• 以顶点为中心构造，邻接表出/入边数组和出/入边索引数组

• 顶点区间分割

• 辅助Bitmap和Vertex_Array

• Multi-Level Partition（详见“负载均衡”）

2、NUMA-Aware

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

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

3、图计算执行过程

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

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

4、push/pull双模式

5、负载均衡

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

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

• 一次划分：首先依据每个Socket(NUMA-Node)分摊到相等数量的边集的标准，将顶点集静态分配到每个Socket（顶点chunk）。由于每个顶点的出入度不同，每个Socket级别分到的顶点chunk大小不一。

• 二次划分：再按照每个Socket内部每个Core(=Thread个数)分摊到相等数据量的边集的标准，再次将顶点集二次划分给每个Socket内部的每个Core，同理，每个Core分到的顶点chunk一般也大小不一。

2）以上静态划分，并不能完全保证运行时每个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式的交互式图算法开发和分析工具，提供从图数据探索、图算法开发、图算法部署上线的一站式平台，并集成到“图灵”平台中

RECOMMEND

推荐阅读

京东技术

---关注技术的公众号

长按识别二维码关注