作者：京东科技 王军

前言

Gemini是目前state-of-art的分布式内存图计算引擎，由清华陈文光团队的朱晓伟博士于2016年发表的分布式静态数据剖析引擎。Gemini应用以计算为核心的共享内存图分布式HPC引擎。通过自适应抉择双模式更新（pull/push），实现通信与计算负载平衡[‎1]。图计算钻研的图是数据结构中的图，非图片。理论利用中遇到的图，如社交网络中的好友关系、蛋白质构造、电商等[‎2]等，其特点是数据量大（边多，点多），边遵从指数分布（power-law）[‎7]，通常满足所谓的二八定律：20%的顶点关联了80%的边，其中1%的点甚至关联了50%的边。

如何存储大图随着社交媒体、批发电商等业务的倒退。图数据的规模也在急剧增长。如规范测试数据集clueweb-12，生成后的文本数据大小780+GB。单机存储曾经不能满足需要。必须进行图切分。常见的图切分形式有：切边、切点。

切点：又称“以边为核心的切图”，保障边不被切开，一条边在一台机器上被存储一次，被切的点创立多个正本，正本点所在的机器不分明对于此点的相干边。如上图所示，两头点被别离保留三个版本，此点会别离呈现在三台机器上，在做更新时须要更新三次。切边：又称以“顶点为核心的切图”，相比于切点，保障点不被切开。边会被保留两次，作为正本点所在机器能分明感知到此点的相干边。如上图所示信息只进行一次更新。Gemini采纳切边的形式进行存储。定义形象图为G(V,E)，Gemini定义了主正本（master）与镜像正本（mirror），计算时是以master为核心进行计算。如下图所示，集群每台机器上仅保留mirror到master的子图拓扑构造，而mirror点并未被理论存储（比方权重值），每台机器负责一部分master存储（

）。如下图所示，Gemini将图依照partition算法切分到2个不同的机器。其中 mirror作为逻辑构造，没有为其调配理论存储空间；但每条边被存储了两次。

长处：单机能够残缺获取master的拓扑构造，不须要全局保护节点状态。图存储图的常见存储形式：邻接矩阵、邻接表、十字链表，此处不作具体解释，有趣味可参照[‎3]。| 示意办法 | 邻接矩阵 | 邻接表 | 十字链表 | | 长处 | 存储构造简略，访问速度快，程序遍历边 | 节俭空间，访问速度较快 | 在邻接表根底上进一步，节俭存储空间。 | | 毛病 | 占用空间很大（nn存储空间） | 存储应用指针，随遍历边构造，为提高效率，须要同时存储出边入边数据。 | 示意很简单，大量应用了指针，随机遍历边，拜访慢。 |剖析上表优缺点,可见：上述三种示意形式都不适宜幂律散布的graph存储。压缩矩阵算法图计算问题其实是一个HPC（High Performance Computing）问题，HPC问题个别会从计算机系统构造的角度来进行优化，特地在防止随机内存拜访和缓存的无效利用上。有没有一种既保证拜访效率，又能满足内存的局部性，还能节俭空间的算法呢？压缩矩阵存储。常见的图压缩矩阵算法有三种coordinate list（COO）、Compressed sparse row（CSR）、Compressed sparse column (CSC)算法进行压缩‎8。COO压缩算法COO应用了坐标矩阵实现图存储（row,collumn,value），空间复杂度3|E|；对于邻接矩阵来说，如果图中的边比拟稠密，那么COO的性价比是比拟高。

CSR/CSC压缩算法CSC/CSR都存储了column/row列，用于记录以后行/列与上一个行/列的边数。Index列存储边的所在row/column的index。CSC/CSR是在COO根底上进行了行/列压缩，空间复杂度2|E|+n，理论业务场景中的图，边往往远多于点，所以CSR/CSC绝对COO具备更好压缩比。

长处：存储严密，内存局部性强；毛病：遍历边时，须要依赖上一个点的最初一条边的index，所以只能单线程遍历。压缩矩阵算法无奈实时更新拓扑构造，所以压缩矩阵算法只实用动态或者对数据变动不敏感的场景。| CSC伪代码 | CSR伪代码 | | loc← 0 for vi←0 to colmns for idx ←0 to colmn[i] do //输入到指定行的列 edgevi] ←value[loc] loc← loc+1 end end | loc← 0 for vi←0 to rows for idx ←0 to row[i] do //输入到指定列的行 edge [ index[idx]] [vi] ←value[loc] loc← loc+1 end end |Gemini的图压缩Gemini对 CSC/CSR存储并进行了改良，解释了压缩算法的原理。Gemini在论文中指出，index的存储空间复杂度是O(V)，会成为零碎的瓶颈。引出了两种算法：Bitmap Assisted Compressed Sparse Row（bitmap辅助压缩CSR）和Doubly Compressed Sparse Column（双压缩CSC），空间复杂度降到O(|V'|),|V'|为含有入边点的数量。

Gemini改良后的CSR算法应用bitmap替换CSR原有的Rows构造：• ext为bitmap，代码此bit对应的vid是否存在出边，如上id为0/2/4的点存在出边。• nbr为出边id；• ndx示意保留了边的nbr的index范畴；如上图CSR图，点0存在出边（ext[0]为1），通过idx的差值计算出0点存在一条出边（idx[1]-idx[0]=1），绝对于存储0点第一条出边的nbr的下标为0（idx[0]）；同理可推得点1无出边。Gemini 双压缩CSC算法将idx拆分成vtx及off两个构造：• vtx代表存在入边的点汇合；• nbr为入边数组；• Off示意保留入边nbr的index偏移范畴；如上图CSC算法：vtx数组示意点1，2，3，5存在入边，应用5个元素的off存储每个点的偏移量。如点2存在由0指向本人的入边(0ff[2]-off[1]=1), 所以nbr[1]存储的就是点2的入边id（0）。长处：通过改良后的存储构造，同时反对多线程并行。Gemini的双模式更新双模式更新是Gemini的外围：Gemini采纳BSP计算模型，在通信及计算阶段独创性地引入QT中的signal、slot的概念；计算模式上借鉴了ligra的设计[‎5]。Gemini沿用Ligra对双模式阈值定义：当沉闷边数量小于（｜E｜/20，|E|为总边数）时，下一轮计算将应用push模式（sparse图）；否则采纳pull模式（dense图）。这个值为经验值，可依据场景进行调整。

在开始计算前，都须要统计沉闷边的数量，确定图模式。在迭代过程中，每一个集群节点只保留局部计算结果。在分布式系统中，音讯流传间接波及到通信量，间接意味着阈值强相干网络带宽和引擎的计算效率。双模式间接均衡了计算负载与通信负载。圆角矩形标识操作是在本地实现的，Gemini将大量的需通信工作放在本地实现。Gemini 节点构图Gemini在实现上，减少numa个性。如何调配点边，如何感知master在哪台机器，哪个socket上，都间接影响到引擎计算效率。

location aware和numa aware两个feature去解决了上述问题；因为Graph幂律散布的特点，运行时很难取得很好的负载平衡成果，所以在partition时，也引入了均衡因子，达到通信与计算负载平衡。在partition阶段通过减少index构造：partition_offset, local_partition_offset。（partition_offset记录跨机器的vid offset，local_partition_offset记录跨numa的vid offset）。Location-aware以边均匀算法为例，集群规模partitions = 4（台），图信息见下表。点边散布状况| 点s | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | Out Edge | 0 | 3 | 5 | 30 | 2 | 4 | 6 | 2 | 20 |存在出边sum = 72| 切图轮次 | 1 | 2 | 3 | | 残余边 | 72 | 34 | 22 | | 平均分配 | 18 | 12 | | | Master调配后果 | 0: 0～3 | | | | 1： | 4~6 | | | 2： | | 7~8 | | 3: | | |从上表剖析可见：• 编号为0的机器调配4点38条边；• 编号为1的机器调配3点12条边；• 编号为2的机器调配2点22条边；• 编号为3的机器调配0点0条边。此办法调配会造成负载的偏斜，影响到引擎的计算效率。Gemini在切图时，每个partition调配点个数遵循公式

,其中均衡因子定义为=8*（partitions-1）。依然以上图为例，Gemini通过因子均衡了边的散布。| 切图轮次 | 1 | 2 | 3 | 4 | | 残余权重边 | 288 | 208 | 128 | 44 | | 平均分配 | 72 | 70 | 64 | 44 | | Master调配后果 | 0: 0～2 | | | | | 1： | 3～4 | | | | 2： | | 5～7 | | | 3: | | | 8 |比照两次切分的后果，增加减少了出边较少的点的权重。通过理论场景利用发现：依照论文中均衡因子设定，很可能呈现内存的歪斜（内存调配上相差20%左右，造成oom kill）。在理论生产场景中，咱们依据工夫场景和集群配置，从新调整了参数取值设置，内存调配根本浮动在5%左右。Numa-awareNUMA介绍依据处理器的拜访内存的形式不同，可将计算机系统分类为UMA（Uniform-Memory-Access，对立内存拜访）和 NUMA（Non-Uniform Memory Access, 非一致性内存拜访）。

在UMA架构下，所有cpu都通过雷同的总线以共享的形式拜访内存。在物理构造上，UMA就不利于cpu的扩大（总线长度、数据总线带宽都限度cpu的下限）。Numa （Non-Uniform Memory Access, 非一致性内存拜访）是目前内核设计支流方向。每个cpu有独立的内存空间（独享），可通过QPI（quick path Interconnect）实现相互拜访。因为硬件的个性，所以跨cpu拜访要慢[‎11]。

绝对于UMA来说，NUMA解决cpu扩大，进步数据总线宽度总线长度带来的问题，每个cpu都有本人独立的缓存。依据NUMA的硬件个性剖析，NUMA具备更高本地内存的拜访效率，不便CPU扩大。HPC须要数据拜访的高效性，所以NUMA架构更适宜HPC场景（UMA与NUMA无优劣之分）。Gemini充分利用了NUMA对本socket内存拜访低提早、高带宽的个性，将本机上的点跨多socket数据实现NUMA-aware 切分（切分单位CHUNKSIZE）。切分算法参考Location-aware。Gemini的任务调度Gemini计算采纳BSP模型（Bulk Synchronous Parallel）。为进步CPU和IO的利用率做了哪些工作呢？Gemini提出了两个设计：计算通信协同调度、work stealing（偷工作）。计算通信系统调度Geimini在计算过程中引入了任务调度管制。他的调度算法设计比较简单，可简略了解为应用机器节点ID依照规定程序收发数据，防止收发工作碰撞。Gemini将一轮迭代过程称为一个step，把每一个step又拆分为多个mini step（数量由集群规模确定）。• computation communication interleave为了提高效率，缩小线程调度的开销，Gemini将一次迭代计算拆分成了computation和communication两个阶段。在工夫上，每一轮迭代都是先计算，再进行通信，通信任务调度不会掺杂任何计算的工作。这样设计的益处在于既保证上下文切换的开销，又保障内存的局部性（先计算再通信）。毛病就在于须要开拓比拟大的缓存buffer。• Task Schedule简而言之：每个机器都依照特定的程序收发数据

上图列举了集群中master散布状况，以Node0为例：节点Node 0Master范畴0、1阶段1将数据向Node1发送对于点2的数据，接管来自Node2数据阶段2将数据向Node2发送对于点5的数据，接管来自Node1数据阶段3解决本身的数据（本地数据不经网络传输）在整个过程中，node0依照机器id增序发送，依照机器id降序接管，这个feature能够肯定水平避免出现：同时多台机器向同一台机器发送数据的状况，升高通信信道竞争概率。Work stealing该设计是为了解决分布式计算零碎中常见的straggler问题。当某个cpu task解决实现所负责的id，会先判断同一个socket下的其余cpu task是否已实现。如果存在未实现工作，则帮忙其余的core解决工作。(跨机器的work stealing没有意义了，须要经验两次网络io，而网络io提早是大于解决提早。）Gemini开源代码中定义线程状态治理构造，下图援用了开源代码的数据结构，并对变量进行了阐明。

开始计算时，每个core均依照本人的threadstate进行解决数据，更大晋升cpu应用效率。该设计是以点为单位进行的数据处理，但未解决热点的难题（这也是业界难题，能够对热点再次切分，也是须要冲破的一个问题）。上面是2 core的work stealing示意图：

其中在初始状况T0时刻，core1与core2同时开始执行，工作状态都为working；在T1时刻， core2的工作首先执行实现，core1还未实现。为了进步core2的利用率，就能够将core1的任务分配给core2去做。为了防止core1、core2拜访抵触，此处应用原子操作获取stealing要解决id范畴，解决实现之后，通过socket外部写入指定空间。在T2时刻，core2更新工作状态为stealing，帮忙core1实现工作。在开源代码中，在构图设计tune chunks过程，能够实现跨机器的间断数据块读取，晋升跨socket的效率。注：开源代码中，push模式下并未应用到tread state构造，所以tune chunks中能够省略push模式thread state的初始化工作。其中在初始状况T0时刻，core1与core2同时开始执行，工作状态都为working；Gemini API接口设计API设计上借鉴了Ligra，设计了一种双置信号槽的分布式图数据处理机制来拆散通信与计算的过程。屏蔽底层数据组织和计算分布式的细节。算法移植更加不便，简化开发难度。并且能够实现类Pregel零碎的combine操作。将图的稠密、稠密性作为双模式辨别标记。Gemini算法调用应用c++11的lambda函数表达式，将算法实现与框架解耦。

Gemini在框架设计中翻新的应用signal、slot。将每轮迭代分为两个阶段：signal（数据发送），slot（音讯解决），此处实现了通信与数据处理过程的解耦。Gemini源码剖析Gemini代码能够分为初始化，构图，计算三局部。初始化：设置集群配置信息，包含mpi、numa、构图时所需的buffer开销的初始化；构图：根据算法输出的数据特色，实现有/无向图的结构；计算：在已结构实现的图上，应用双模式计算引擎计算。Gemini构图代码剖析Gemini在构图时，须要当时统计每个点的出边、入边信息，再根据统计信息切图，申请存储图所需的空间。以无向图构建为例，整个构图过程经验了3次文件读取：统计入边信息；生成图存储构造（bitmap、index）；边数据存储。入口函数：load_undirected_from_directed开源源码Gemini集群同时分段读取同一份binary文件，每台机器都分段读取一部分数据。

出边信息统计

上图代码分段读取文件，统计每个点的出边信息，见line 456、457，通过openmpi通信，聚合所有点出边信息line 460。Line 451：原理上能够应用omp并发，但因为原子操作锁竞争比拟大效率并不高。Location aware 代码实现Gemini在location aware解决了地址感知，集群负载平衡的工作。

解释最初一行：owned_vertices记录以后机器master点个数，partition_offset[partition_id]记录master节点vid的上限，partition_offset[partition_id+1] 记录master节点vid的下限。益处：晋升了内存的拜访效率；缩小了内存的零头（在这个过程中，Gemini为进步内存块读取的效率，应用pagesize进行内存对齐。）。NUMA aware代码实现NUMA aware作用是在socket上进行了partition，均衡算力和cpu的负载，程序实现与Location aware过程相似。

NUMA aware也进行了a因子均衡和pagesize对齐。总结：机器机器共享同一份出边统计数据，所以在location aware和numa aware阶段的后果都是雷同的，partition后果也不会呈现抵触的状况。注：aware阶段都是对master的切分，未统计mirror的状态；而构图过程是从mirror的视角实现的，所以下一个阶段就须要统计mirror信息。构建边治理构造在实现Location aware和NUMA aware之后，须要思考为边allocate存储空间。因为Gemini应用一维数组存储边，所以必须当时确定所需的存储空间，并allocate相应的内存治理构造。Gemini应用二级索引实现点边遍历。读者很可能呈现这样的误区：建设master->mirror关系映射。这样会带来什么问题？超级顶点。也就意味着通信和计算负载都会回升。这对图计算引擎的效率影响很大。可自行计算万亿级别点，每个socket上存储的index占用的空间。

单节点解决本地数据（依照CHUNCKSIZE大小，分批向集群其余节点散发边数据）。记录mirror点的bitmap及出边信息。

数据发送过程是依照CHUNCKSIZE大小，分批发送。

在发送完结时，需确保所用的数据发送实现，发送字符‘\0‘作为结束符。图存储根据上一阶段构建的治理构造实现边的存储，治理构造解释：Bitmap的作用是确定在此socket下，此mirror点是否存在边；Index标识边的起始地位（见图压缩章节介绍）。下图正文内容介绍了index的构建过程，构建过程中应用了单线程，cpu利用率较低，可自行测试一下。

在边存储时，数据散发实现了并发传输。代码实现过程，见下图代码正文。

边数据散发过程代码：

任务调度代码实现构建任务调度数据结构ThreadState,参数配置tune_chunks代码实现，应用了因子进行均衡。逻辑上将同一个socket的边数据，依照线程进行二次划分（balance）。

计算源码剖析双模式的核心思想：尽可能将通信放到本地内存，缩小网络IO开销。以dense模式为例：pull模式将集群中的其余节点的局部后果pull到本地，实现同步计算。

解决模块代码定义

留神：line1796 send_queue_mutex的应用，通过锁管制发送模块的先后顺序。任务调度算法实现：

为保障每台机器上的计算结果统一，所以在流传过程中每个机器都会接管到雷同的数据，在进行计算。总结Gemini的要害设计：• 自适应双模式计算均衡了通信和计算的负载问题；• 基于块的Partition均衡了集群单机计算负载；• 图压缩升高了内存的耗费。Gemini可持续优化方向：• Proces_edges过程中，发送/接管buffer开拓空间过大，代码如下：

在切换双模运算时，调用了resize办法，此办法实现：当仅超过capacity时，才从新alloc内存空间，未实现进行缩容（空间

）。

a• adj_index会成为零碎瓶颈论文中也提到adj_index一级索引会占用大部分空间（论文中也提到了会成为瓶颈）。改良后的CSC压缩算法应用二级索引构造。在计算时会影响数据访问速度，无向图中压缩成果不好，远高于一级索引的空间复杂度（幂律散布决定，极大局部点存在1条以上的出边，易得空间复杂度2|V’|>|V|）。• 因子调整因子应该依据图的特色进行动静调整，否则很容易造成内存partition偏斜。• 动静更新因为压缩矩阵和partition形式都限度了图的更新。可通过扭转parition切分形式，就义numa个性带来的局部性，通过snapshot实现增量图。• 外存扩大Gemini是共享内存的分布式引擎。在理论生产环境中，通过暴力减少机器解决内存不足的问题，不是最优解。大容量外存不失为更好的解决方案。

参考文献11

  1. Gemini: A Computation-Centric Distributed Graph Processing System
  2. https://zh.wikipedia.org/wiki...(%E6%95%B0%E5%AD%A6)
  3. https://oi-wiki.org/graph/save/
  4. https://github.com/thu-pacman...
  5. Ligra: A Lightweight Graph Processing Framework for Shared Memory
  6. Pregel:a system for large-scale graph processing.
  7. Powergraph: Distributed graph-parallel computation on natural graphs
  8. https://en.wikipedia.org/wiki...(COO)
  9. https://programmer.ink/think/...
  10. https://frankdenneman.nl/2016...
  11. https://frankdenneman.nl/2016...
    内容起源：京东云开发者社区https://www.jdcloud.com/