作者：京东科技 王军
前言
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][9]。
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 // 输出到指定行的列 edge [vi][index [idx]] ←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-aware
NUMA 介绍
根据处理器的拜访内存的办法不同，可将核算机体系分类为 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 0 |
|---|---|
| Master 规模 | 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 次文件读取：
1.核算入边信息；
2.生成图存储结构（bitmap、index）；
3.边数据存储。
进口函数：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 的上限。
优点：
1.提升了内存的拜访功率；
2.减少了内存的零头（在这个进程中，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/%E5%9B%BE_(%E6%95%B0%E5%AD%A6) 3. https://oi-wiki.org/graph/save/ 4. https://github.com/thu-pacman/GeminiGraph.git 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/Sparse_matrix#Coordinate_list_(COO) 9. https://programmer.ink/think/implementation-of-coo-and-csr-based-on-array-form-for-sparse-matrix.html 10. https://frankdenneman.nl/2016/07/06/introduction-2016-numa-deep-dive-series/ 11. https://frankdenneman.nl/2016/07/13/numa-deep-dive-4-local-memory-optimization/
内容来源：京东云开发者社区[www.jdcloud.com/]
