作者：京東科技 王軍

前言

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]。

分析上表優缺點，可見：上述三種表示方式都不適合冪律分布的 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，所以只能單線程遍歷。

壓縮矩陣算法無法實時更新拓撲結構，所以壓縮矩陣算法只適用靜態或者對數據變化不敏感的場景。

?

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（臺），圖信息見下表。

點邊分布情況

存在出邊 sum = 72

從上表分析可見：

?編號為 0 的機器分配 4 點 38 條邊；

?編號為 1 的機器分配 3 點 12 條邊；

?編號為 2 的機器分配 2 點 22 條邊；

?編號為 3 的機器分配 0 點 0 條邊。

此方法分配會造成負載的偏斜，影響到引擎的計算效率。

Gemini 在切圖時，每個 partition 分配點個數遵循公式

?, 其中平衡因子定義為 α=8*（partitions-1）。

仍然以上圖為例，Gemini 通過ɑ因子平衡了邊的分布。

對比兩次切分的結果，添加 α 增加了出邊較少的點的權重。

通過實際場景應用發現：按照論文中 α 平衡因子設定，很可能出現內存的傾斜（內存分配上相差 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 為例：

在整個過程中，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 次文件讀?。?/p>

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 是共享內存的分布式引擎。在實際生產環境中，通過暴力增加機器解決內存不足的問題，不是最優解。大容量外存不失為更好的解決方案。

參考文獻

???1?????1 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/??

內容來源：京東云開發者社區??https://www.jdcloud.com/??