共计 8942 个字符，预计需要花费 23 分钟才能阅读完成。
作者：京东科技 王军
前言
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]。| 示意办法 | 邻接矩阵 | 邻接表 | 十字链表 | | 长处 | 存储构造简略，访问速度快，程序遍历边 | 节俭空间，访问速度较快 | 在邻接表根底上进一步，节俭存储空间。| | 毛病 | 占用空间很大（n n 存储空间）| 存储应用指针，随遍历边构造，为提高效率，须要同时存储出边入边数据。| 示意很简单，大量应用了指针，随机遍历边，拜访慢。| 剖析上表优缺点, 可见：上述三种示意形式都不适宜幂律散布的 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
- Gemini: A Computation-Centric Distributed Graph Processing System
- https://zh.wikipedia.org/wiki…(%E6%95%B0%E5%AD%A6)
- https://oi-wiki.org/graph/save/
- https://github.com/thu-pacman…
- Ligra: A Lightweight Graph Processing Framework for Shared Memory
- Pregel:a system for large-scale graph processing.
- Powergraph: Distributed graph-parallel computation on natural graphs
- https://en.wikipedia.org/wiki…(COO)
- https://programmer.ink/think/…
- https://frankdenneman.nl/2016…
- https://frankdenneman.nl/2016…
内容起源：京东云开发者社区 https://www.jdcloud.com/
