作者：位元組跳動技術團隊 技術架構團隊來源：位元組跳動技術團隊 【責任編輯：未麗燕 TEL：（010）68476606】
https://database.51cto.com/art/202012/633379.htm

一、圖狀結構資料廣泛存在

位元組跳動的所有產品的大部分業務資料，幾乎都可以歸入到以下三種：

• 用戶資訊、用戶和用戶的關系(關注、好友等);
• 內容(視頻、文章、廣告等);
• 用戶和內容的聯系(點贊、評論、轉發、點擊廣告等)，

這三種資料關聯在一起，形成圖狀(Graph)結構資料，

為了滿足 social graph 的在線增刪改查場景，位元組跳動自研了分布式圖存盤系統——ByteGraph，針對上述圖狀結構資料，ByteGraph 支持有向屬性圖資料模型，支持 Gremlin 查詢語言，支持靈活豐富的寫入和查詢介面，讀寫吞吐可擴展到千萬 QPS，延遲毫秒級，目前，ByteGraph 支持了頭條、抖音、 TikTok、西瓜、火山等幾乎位元組跳動全部產品線，遍布全球機房，在這篇文章中，將從適用場景、內部架構、關鍵問題分析幾個方面作深入介紹，

ByteGraph 主要用于在線 OLTP 場景，而在離線場景下，圖資料的分析和計算需求也逐漸顯現，2019 年年初，Gartner 資料與分析峰會上將圖列為 2019 年十大資料和分析趨勢之一，預計全球圖分析應用將以每年 100% 的速度迅猛增長，2020 年將達到 80 億美元，因此，我們團隊同時也開啟了在離線圖計算場景的支持和實踐，

下面會從圖資料庫和圖計算兩個部分，分別來介紹位元組跳動在這方面的一些作業，

二、自研圖資料庫(ByteGraph)介紹

從資料模型角度看，圖資料庫內部資料是有向屬性圖，其基本元素是 Graph 中的點(Vertex)、邊(Edge)以及其上附著的屬性;作為一個工具，圖資料對外提供的介面都是圍繞這些元素展開，

圖資料庫本質也是一個存盤系統，它和常見的 KV 存盤系統、MySQL 存盤系統的相比主要區別在于目標資料的邏輯關系不同和訪問模式不同，對于資料內在關系是圖模型以及在圖上游走類和模式匹配類的查詢，比如社交關系查詢，圖資料庫會有更大的性能優勢和更加簡潔高效的介面，

1、為什么不選擇開源圖資料庫

圖資料庫在 90 年代出現，直到最近幾年在資料爆炸的大趨勢下快速發展，百花齊放;但目前比較成熟的大部分都是面對傳統行業較小的資料集和較低的訪問吞吐場景，比如開源的 Neo4j 是單機架構;因此，在互聯網場景下，通常都是基于已有的基礎設施定制系統：比如 Facebook 基于 MySQL 系統封裝了 Social Graph 系統 TAO，幾乎承載了 Facebook 所有資料邏輯;Linkedln 在 KV 之上構建了 Social Graph 服務;微博是基于 Redis 構建了粉絲和關注關系，

位元組跳動的 Graph 在線存盤場景， 其需求也是有自身特點的，可以總結為：

• 海量資料存盤：百億點、萬億邊的資料規模;并且圖符合冪律分布，比如少量大 V 粉絲達到幾千萬;
• 海量吞吐：最大集群 QPS 達到數千萬;
• 低延遲：要求訪問延遲 pct99 需要限制在毫秒級;
• 讀多寫少：讀流量是寫流量的接近百倍之多;
• 輕量查詢多，重量查詢少：90%查詢是圖上二度以內查詢;
• 容災架構演進：要能支持位元組跳動城域網、廣域網、洲際網路之間主備容災、異地多活等不同容災部署方案，

事實上，我們調研過了很多業界系統， 這個主題可以再單獨分享一篇文章，但是，面對位元組跳動世界級的海量資料和海量并發請求，用萬億級分布式存盤、千萬高并發、低延遲、穩定可控這三個條件一起去篩選，業界在線上被驗證穩定可信賴的開源圖存盤系統基本沒有滿足的了;另外，對于一個承載公司核心資料的重要的基礎設施，是值得長期投入并且深度掌控的，

因此，我們在 18 年 8 月份，開始從第一行代碼開始踏上圖資料庫的漫漫征程，從解決一個最核心的抖音社交關系問題入手，逐漸演變為支持有向屬性圖資料模型、支持寫入原子性、部分 Gremlin 圖查詢語言的通用圖資料庫系統，在公司所有產品體系落地，我們稱之為 ByteGraph，下面，會從資料模型、系統架構等幾個部分，由淺入深和大家分享我們的作業，

2、ByteGraph 的資料模型和 API

1)資料模型

就像我們在使用 SQL 資料庫時，先要完成資料庫 Schema 以及范式設計一樣，ByteGraph 也需要用戶完成類似的資料模型抽象，但圖的資料抽象更加簡單，基本上是把資料之間的關系“翻譯”成有向屬性圖，我們稱之為“構圖”程序，

比如在前面提到的，如果想把用戶關系存入 ByteGraph，第一步就是需要把用戶抽象為點，第二步把"關注關系”、“好友關系”抽象為邊就完全搞定了，下面，我們就從代碼層面介紹下點邊的資料型別，

① 點(Vertex)

點是圖資料庫的基本元素，通常反映的是靜態資訊，在 ByteGraph 中，點包含以下欄位：

點的id(uint64_t): 比如用戶id作為一個點
點的type(uint32_t): 比如appID作為點的type
點的屬性(KV 對)：比如 ‘name’: string，‘age’: int, ‘gender’: male，等自定義屬性
[id, type]唯一定義一個點
② 邊(Edge)

一條邊由兩個點和點之間的邊的型別組成，邊可以描述點之間的關系，比如用戶 A 關注了用戶 B ，可以用以下欄位來描述：

兩個點(Vertex): 比如用戶A和用戶B
邊的型別(string): 比如“關注”

邊的時間戳(uint64_t)：這個t值是業務自定義含義的，比如可以用于記錄關注發生的時間戳
邊屬性(KV對)：比如’ts_us’: int64 描述關系創建時間的屬性，以及其他用戶自定義屬性
③ 邊的方向

在 ByteGraph 的資料模型中，邊是有方向的，目前支持 3 種邊的方向:

正向邊：如 A 關注 B(A -> B)
反向邊：如 B 被 A 關注(B <- A)
雙向邊：如 A 與 B 是好友(A <-> B)

2)場景使用偽碼舉例
構圖完畢后，我們就可以把業務邏輯通過 Gremlin 查詢語言來實作了;為便于大家理解，我們列舉幾種典型的場景為例，

場景一：記錄關注關系 A 關注 B

> // 創建用戶A和B，可以使用 .property('name', 'Alice') 陳述句添加用戶屬性 
> g.addV().property("type", A.type).property("id", A.id) 
> g.addV().property("type", B.type).property("id", B.id) 
> // 創建關注關系 A -> B，其中addE("關注")中指定了邊的型別資訊，from和to分別指定起點和終點， 
> g.addE("關注").from(A.id, A.type).to(B.id, B.type).property("ts_us", now) 

場景二：查詢 A 關注的且關注了 C 的所有用戶
用戶 A 進入用戶 C 的詳情頁面，想看看 A 和 C 之間的二度中間節點有哪些，比如 A->B,B->C，B 則為中間節點，

> // where()表示對于上一個step的每個執行結果，執行子查詢過濾條件，只保留關注了C的用戶， 
> g.V().has("type", A.type).has("id", A.id).out("關注").where(out("關注").has("type", C.type).has("id", C.id).count().is(gte(1))) 

場景三：查詢 A 的好友的好友(二度關系)

> // both("好友")相當于in("好友")和out("好友")的合集 
> g.V().has("type", A.type).has("id", A.id).both("好友").both("好友").toSet() 

3、系統架構

前面幾個章節，從用戶角度介紹了 ByteGraph 的適用場景和對外使用姿勢，那 ByteGraph 架構是怎樣的，內部是如何作業的呢，這一節就來從內部實作來作進一步介紹，

下面這張圖展示了 ByteGraph 的內部架構，其中 bg 是 ByteGraph 的縮寫，

就像 MySQL 通常可以分為 SQL 層和引擎層兩層一樣，ByteGraph 自上而下分為查詢層 (bgdb)、存盤/事務引擎層(bgkv)、磁盤存盤層三層，每層都是由多個行程實體組成，其中 bgdb 層與 bgkv 層混合部署，磁盤存盤層獨立部署，我們詳細介紹每一層的關鍵設計，

1)查詢層(bgdb)

bgdb 層和 MySQL 的 SQL 層一樣，主要作業是做讀寫請求的決議和處理;其中，所謂“處理”可以分為以下三個步驟：

• 將客戶端發來的 Gremlin 查詢陳述句做語法決議，生成執行計劃;
• 并根據一定的路由規則(例如一致性哈希)找到目標資料所在的存盤節點(bgkv)，將執行計劃中的讀寫請求發送給 多個 bgkv;
• 將 bgkv 讀寫結果匯總以及過濾處理，得到最終結果，回傳給客戶端，

bgdb 層沒有狀態，可以水平擴容，用 Go 語言開發，

2)存盤/事務引擎層(bgkv)

• bgkv 層是由多個行程實體組成，每個實體管理整個集群資料的一個子集(shard / partition)，
• bgkv 層的實作和功能有點類似記憶體資料庫，提供高性能的資料讀寫功能，其特點是：

介面不同：只提供點邊讀寫介面;

• 支持算子下推：通過把計算(算子)移動到存盤(bgkv)上，能夠有效提升讀性能;
• 舉例：比如某個大 V 最近一年一直在漲粉，bgkv 支持查詢最近的 100 個粉絲，則不必讀出所有的百萬粉絲，
• 快取存盤有機結合：其作為 KV store 的快取層，提供快取管理的功能，支持快取加載、換出、快取和磁盤同步異步 sync 等復雜功能，

從上述描述可以看出，bgkv 的性能和記憶體使用效率是非常關鍵的，因此采用 C++ 撰寫，

3)磁盤存盤層(KV Cluster)

為了能夠提供海量存盤空間和較高的可靠性、可用性，資料必須最終落入磁盤，我們底層存盤是選擇了公司自研的分布式 KV store，

4)如何把圖存盤在 KV 資料庫中

上一小節，只是介紹了 ByteGraph 內部三層的關系，細心的讀者可能已經發現，ByteGraph 外部是圖介面，底層是依賴 KV 存盤，那么問題來了：如何把動輒百萬粉絲的圖資料存盤在一個 KV 系統上呢?

在位元組跳動的業務場景中，存在很多訪問熱度和“資料密度”極高的場景，比如抖音的大 V、熱門的文章等，其粉絲數或者點贊數會超過千萬級別;但作為 KV store，希望業務方的 KV 對的大小(Byte 數)是控制在 KB 量級的，且最好是大小均勻的：對于太大的 value，是會瞬間打滿 I/O 路徑的，無法保證線上穩定性;對于特別小的 value，則存盤效率比較低，事實上，資料大小不均勻這個問題困擾了很多業務團隊，在線上也會經常爆出事故，

對于一個有千萬粉絲的抖音大 V，相當于圖中的某個點有千萬條邊的出度，不僅要能存盤下來，而且要能滿足線上毫秒級的增刪查改，那么 ByteGraph 是如何解決這個問題的呢?

思路其實很簡單，總結來說，就是采用靈活的邊聚合方式，使得 KV store 中的 value 大小是均勻的，具體可以用以下四條來描述：

① 一個點(Vertex)和其所有相連的邊組成了一資料組(Group);不同的起點和及其終點是屬于不同的 Group，是存盤在不同的 KV 對的;比如用戶 A 的粉絲和用戶 B 的粉絲，就是分成不同 KV 存盤;

② 對于某一個點的及其出邊，當出度數量比較小(KB 級別)，將其所有出度即所有終點序列化為一個 KV 對，我們稱之為一級存盤方式(后面會展開描述);

③ 當一個點的出度逐漸增多，比如一個普通用戶逐漸成長為抖音大 V，我們則采用分布式 B-Tree 組織這百萬粉絲，我們稱之為二級存盤;

④ 一級存盤和二級存盤之間可以在線并發安全的互相切換，

一級存盤格式

一級存盤格式中，只有一個 KV 對，key 和 value 的編碼：

• key: 某個起點 id + 起點 type + 邊 type
• value: 此起點的所有出邊(Edge)及其邊上屬性聚合作為 value，但不包括終點的屬性

二級存盤(點的出度大于閾值)

如果一個大 V 瘋狂漲粉，則存盤粉絲的 value 就會越來越大，解決這個問題的思路也很樸素：拆成多個 KV 對，

但如何拆呢?ByteGraph 的方式就是把所有出度和終點拆成多個 KV 對，所有 KV 對形成一棵邏輯上的分布式 B-Tree，之所以說“邏輯上的”，是因為樹中的節點關系是靠 KV 中 key 來指向的，并非記憶體指標;B-Tree 是分布式的，是指構成這棵樹的各級節點是分布在集群多個實體上的，并不是單機索引關系，具體關系如下圖所示：

其中，整棵 B-Tree 由多組 KV 對組成，按照關系可以分為三種資料：

• 根節點：根節點本質是一個 KV 系統中的一個 key，其編碼方式和一級存盤中的 key 相同
  Meta 資料：

• Meta 資料本質是一個 KV 中的 value，和根節點組成了 KV 對;

• Meta 內部存盤了多個 PartKey，其中每個 PartKey 都是一個 KV 對中的 key，其對應的 value 資料就是下面介紹的 Part 資料，

Part 資料

對于二級存盤格式，存在多個 Part，每個 Part 存盤部分出邊的屬性和終點 ID，

每個 Part 都是一個 KV 對的 value，其對應的 key 存盤在 Meta 中，

從上述描述可以看出，對于一個出度很多的點和其邊的資料(比如大 V 和其粉絲)，在 ByteGraph 中，是存盤為多個 KV 的，面對增刪查改的需求，都需要在 B-Tree 上做二分查找，相比于一條邊一個 KV 對或者所有邊存盤成一個 KV 對的方式，B-Tree 的組織方式能夠有效的在讀放大和寫放大之間做一些動態調整，

但在實際業務場景下，粉絲會處于動態變化之中：新誕生的大 V 會快速新增粉絲，有些大 V 會持續掉粉;因此，存盤方式會在一級存盤和二級存盤之間轉換，并且 B-Tree 會持續的分裂或者合并;這就會引發分布式的并發增刪查改以及分裂合并等復雜的問題，有機會可以再單獨分享下這個有趣的設計，

ByteGraph 和 KV store 的關系，類似檔案系統和塊設備的關系，塊設備負責將存盤資源池化并提供 Low Level 的讀寫介面，檔案系統在塊設備上把元資料和資料組織成各種樹的索引結構，并封裝豐富的 POSIX 介面，便于外部使用，

4、一些問題深入探討

第三節介紹了 ByteGraph 的內在架構，現在我們更進一步，來看看一個分布式存盤系統，在面對位元組跳動萬億資料上億并發的業務場景下兩個問題的分析，

1)熱點資料讀寫解決

熱點資料在位元組跳動的線上業務中廣泛存在：熱點視頻、熱點文章、大 V 用戶、熱點廣告等等;熱點資料可能會出現瞬時出現大量讀寫，ByteGraph 在線上業務的實踐中，打磨出一整套應對性方案，

2)熱點讀

熱點讀的場景隨處可見，比如線上實際場景：某個熱點視頻被頻繁重繪，查看點贊數量等，在這種場景下，意味著訪問有很強的資料區域性，快取命中率會很高，因此，我們設計實作了多級的 Query Cache 機制以及熱點請求轉發機制;在 bgdb 查詢層快取查詢結果， bgdb 單節點快取命中讀性能 20w QPS 以上，而且多個 bgdb 可以并發處理同一個熱點的讀請求，則系統整體應對熱點度的“彈性”是非常充足的，

3)熱點寫

熱點讀和熱點寫通常是相伴而生的，熱點寫的例子也是隨處可見，比如：熱點新聞被瘋狂轉發， 熱點視頻被瘋狂點贊等等，對于資料庫而言，熱點寫入導致的性能退化的背后原因通常有兩個：行鎖沖突高或者磁盤寫入 IOPS 被打滿，我們分別來分析：

① 行鎖沖突高：目前 ByteGraph 是單行事務模型，只有記憶體結構鎖，這個鎖的并發量是每秒千萬級，基本不會構成寫入瓶頸，

② 磁盤 IOPS 被打滿：

IOPS(I/O Count Per Second)的概念：磁盤每秒的寫入請求數量是有上限的，不同型號的固態硬碟的 IOPS 各異，但都有一個上限，當上游寫入流量超過這個閾值時候，請求就會排隊，造成整個資料通路堵塞，延遲就會呈現指數上漲最終服務變成不可用，

Group Commit 解決方案：Group Commit 是資料庫中的一個成熟的技術方案，簡單來講，就是多個寫請求在 bgkv 記憶體中匯聚起來，聚成一個 Batch 寫入 KV store，則對外體現的寫入速率就是 BatchSize * IOPS，

對于某個獨立資料源來說，一般熱點寫的請求比熱點讀會少很多，一般不會超過 10K QPS，目前 ByteGraph 線上還沒有出現過熱點寫問題問題，

4)圖的索引

就像關系型資料庫一樣，圖資料庫也可以構建索引，默認情況下，對于同一個起點，我們會采用邊上的屬性(時間戳)作為主鍵索引;但為了加速查詢，我們也支持其他元素(終點、其他屬性)來構建二級的聚簇索引，這樣很多查找就從全部遍歷優化成了二分查找，使得查詢速度大幅提升，

ByteGraph 默認按照邊上的時間戳(ts)來排序存盤，因此對于以下請求，查詢效率很高：

• 查詢最近的若干個點贊
• 查詢某個指定時間范圍視窗內加的好友

方向的索引可能有些費解，舉個例子說明下：給定兩個用戶來查詢是否存在粉絲關系，其中一個用戶是大 V，另一個是普通用戶，大 V 的粉絲可達千萬，但普通用戶的關注者一般不會很多;因此，如果用普通用戶作為起點大 V 作為終點，查詢代價就會低很多，其實，很多場景下，我們還需要用戶能夠根據任意一個屬性來構建索引，這個也是我們正在支持的重要功能之一，

5、未來探索

過去的一年半時間里，ByteGraph 都是在有限的人力情況下，優先滿足業務需求，在系統能力構建方面還是有些薄弱的，有大量問題都需要在未來突破解決：

從圖存盤到圖資料庫：對于一個資料庫系統，是否支持 ACID 的事務，是一個核心問題，目前 ByteGraph 只解決了原子性和一致性，對于最復雜的隔離性還完全沒有觸碰，這是一個非常復雜的問題;另外，中國信通院發布了國內圖資料庫功能白皮書，以此標準，如果想做好一個功能完備的“資料庫”系統，我們面對的還是星辰大海;

標準的圖查詢語言：目前，圖資料庫的查詢語言業界還未形成標準(GQL 即將在 2020 年發布)，ByteGraph 選擇 Apache、AWS 、阿里云的 Gremlin 語言體系，但目前也只是支持了一個子集，更多的語法支持、更深入的查詢優化還未開展;

Cloud Native 存盤架構演進：現在 ByteGraph 還是構建與 KV 存盤之上，獨占物理機全部資源;從資源彈性部署、運維托管等角度是否有其他架構演進的探索可能，從查詢到事務再到磁盤存盤是否有深度垂直整合優化的空間，也是一個沒有被回答的問題;

現在 ByteGraph 是在 OLTP 場景下承載了大量線上資料，這些資料同時也會應用到推薦、風控等復雜分析和圖計算場景，如何把 TP 和輕量 AP 查詢融合在一起，具備部分 HTAP 能力，也是一個空間廣闊的藍海領域，

三、圖計算系統介紹與實踐

1、圖計算技術背景

1)圖計算簡介

圖資料庫重點面對 OLTP 場景，以事務為核心，強調增刪查改并重，并且一個查詢往往只是涉及到圖中的少量資料;而圖計算與之不同，是解決大規模圖資料處理的方法，面對 OLAP 場景，是對整個圖做分析計算，下圖(參考自 VLDB 2019 keynote 《Graph Processing: A Panaromic View and Some Open Problems》)描述了圖計算和圖資料庫的一些領域區分，

舉個圖計算的簡單例子，在我們比較熟悉的 Google 的搜索場景中，需要基于網頁鏈接關系計算每個網頁的 PageRank 值，用來對網頁進行排序，網頁鏈接關系其實就是一張圖，而基于網頁鏈接關系的 PageRank 計算，其實就是在這張圖上運行圖演算法，也就是圖計算，

對于小規模的圖，我們可以用單機來進行計算，但隨著資料量的增大，一般需要引入分布式的計算系統來解決，并且要能夠高效地運行各種型別的圖演算法，

2)批處理系統

大規模資料處理我們直接想到的就是使用 MapReduce / Spark 等批處理系統，位元組跳動在初期也有不少業務使用 MapReduce / Spark 來實作圖演算法，得益于批處理系統的廣泛使用，業務同學能夠快速實作并上線自己的演算法邏輯，

批處理系統本身是為了處理行式資料而設計的，其能夠輕易地將作業負載分散在不同的機器上，并行地處理大量的資料，不過圖資料比較特殊，天然具有關聯性，無法像行式資料一樣直接切割，如果用批處理系統來運行圖演算法，就可能會引入大量的 Shuffle 來實作關系的連接，而 Shuffle 是一項很重的操作，不僅會導致任務運行時間長，并且會浪費很多計算資源，

3)圖計算系統

圖計算系統是針對圖演算法的特點而衍生出的專用計算設施，能夠高效地運行圖演算法，因此隨著業務的發展，我們迫切需要引入圖計算系統來解決圖資料處理的問題，圖計算也是比較成熟的領域，在學術界和工業界已有大量的系統，這些系統在不同場景，也各有優劣勢，

由于面向不同的資料特征、不同的演算法特性等，圖計算系統在平臺架構、計算模型、圖劃分、執行模型、通信模型等方面各有取舍，下面，我們從不同角度對圖計算的一些現有技術做些分類分析，

① 分布架構

按照分布架構，圖計算可以分為單機或分布式、全記憶體或使用外存幾種，常見的各種圖計算系統如下圖所示，單機架構的優勢在于無需考慮分布式的通信開銷，但通常難以快速處理大規模的圖資料;分布式則通過通信或分布式共享記憶體將可處理的資料規模擴大，但通常也會引入巨大的額外開銷，

② 計算模型

按照計算物件，圖資料計算模型可以分為節點中心計算模型、邊中心計算模型、子圖中心計算模型等，

大部分圖計算系統都采用了節點中心計算模型(這里的節點指圖上的一個點)，該模型來自 Google 的 Pregel，核心思想是用戶編程程序中，以圖中一個節點及其鄰邊作為輸入來進行運算，具有編程簡單的優勢，典型的節點中心計算模型包括 Pregel 提出的 Pregel API 、 PowerGraph 提出的 GAS API 以及其他一些 API，

Pregel 創新性地提出了 “think like a vertex” 的思想，用戶只需撰寫處理一個節點的邏輯，即可被拓展到整張圖進行迭代運算，使用 Pregel 描述的 PageRank 如下圖所示：

def pagerank(vertex_id, msgs): 
    // 計算收到訊息的值之和 
    msg_sum = sum(msgs) 
    // 更新當前PR值 
    pr = 0.15 + 0.85 * msg_sum 
    // 用新計算的PR值發送訊息 
    for nr in out_neighbor(vertex_id): 
        msg = pr / out_degree(vertex_id) 
        send_msg(nr, msg) 
    // 檢查是否收斂 
    if converged(pr): 
        vote_halt(vertex_id) 

GAS API 則是 PowerGraph 為了解決冪律圖(一小部分節點的度數非常高)的問題，將對一個節點的處理邏輯，拆分為了 Gather、Apply、Scatter 三階段，在計算滿足交換律和結合律的情況下，通過使用 GAS 模型，通信成本從 |E| 降低到了 |V|，使用 GAS 描述的 PageRank 如下圖所示：

def gather(msg_a, msg_b): 
    // 匯聚訊息 
    return msg_a + msg_b 
 
def apply(vertex_id, msg_sum): 
    // 更新PR值 
    pr = 0.15 + 0.85 * msg_sum 
    // 判斷是否收斂 
    if converged(pr): 
        vote_halt(vertex_id) 
 
def scatter(vertex_id, nr): 
    // 發送訊息 
    return pr / out_degree(vertex_id) 

③ 圖劃分

對于單機無法處理的超級大圖，則需要將圖資料劃分成幾個子圖，采用分布式計算方式，因此，會涉及到圖劃分的問題，即如何將一整張圖切割成子圖，并分配給不同的機器進行分布式地計算，常見的圖劃分方式有切邊法(Edge-Cut)和切點法(Vertex-Cut)，其示意圖如下所示：

切邊法顧名思義，會從一條邊中間切開，兩邊的節點會分布在不同的圖磁區，每個節點全域只會出現一次，但切邊法可能會導致一條邊在全域出現兩次，如上左圖所示，節點 A 與節點 B 之間有一條邊，切邊法會在 A 和 B 中間切開，A 屬于圖磁區 1，B 屬于圖磁區 2，

切點法則是將一個節點切開，該節點上不同的邊會分布在不同的圖磁區，每條邊全域只會出現一次，但切點法會導致一個節點在全域出現多次，如上圖右圖所示，節點 A 被切分為 3 份，其中邊 AB 屬于磁區 2，邊 AD 屬于圖磁區 3，

圖劃分還會涉及到分圖策略，比如切點法會有各種策略的切法：按邊隨機哈希、Edge1D、Edge2D 等等，有些策略是可全域并行執行分圖的，速度快，但負載均衡和計算時的通信效率不理想;有些是需要串行執行的但負載均衡、通信效率會更好，各種策略需要根據不同的業務場景進行選擇，

④ 執行模型

執行模型解決的是不同的節點在迭代程序中，如何協調迭代進度的問題，圖計算通常是全圖多輪迭代的計算，比如 PageRank 演算法，需要持續迭代直至全圖所有節點收斂才會結束，

在圖劃分完成后，每個子圖會被分配到對應的機器進行處理，由于不同機器間運算環境、計算負載的不同，不同機器的運算速度是不同的，導致圖上不同節點間的迭代速度也是不同的，為了應對不同節點間迭代速度的不同，有同步計算、異步計算、以及半同步計算三種執行模型，

• 同步計算是全圖所有節點完成一輪迭代之后，才開啟下一輪迭代，因為通常每個節點都會依賴其他節點在上一輪迭代產生的結果，因此同步計算的結果是正確的，
• 異步計算則是每個節點不等待其他節點的迭代進度，在自己計算完一輪迭代后直接開啟下一輪迭代，所以就會導致很多節點還沒有完全拿到上一輪的結果就開始了下一輪計算，
• 半同步計算是兩者的綜合，其思想是允許一定的不同步，但當計算最快的節點與計算最慢的節點相差一定迭代輪數時，最快的節點會進行等待，同步計算和異步計算的示意圖如下圖：

同步計算和異步計算各有優劣，其對比如下表所示，半同步是兩者折中，多數圖計算系統都采用了同步計算模型，雖然計算效率比異步計算弱一些，但它具有易于理解、計算穩定、結果準確、可解釋性強等多個重要的優點，

⑤ 通信模型

為了實作拓展性，圖計算采用了不同的通信模型，大致可分為分布式共享記憶體、Push 以及 Pull，分布式共享記憶體將資料存盤在共享記憶體中，通過直接操作共享記憶體完成資訊互動;Push 模型是沿著出邊方向主動推送訊息;Pull 則是沿著入邊方向主動收訊息，三者優劣對比如下表格所示：

2、技術選型

由于位元組跳動要處理的是世界級的超大規模圖，同時還對計算任務運行時長有要求，因此主要考慮高性能、可拓展性強的圖計算系統，工業界使用比較多的系統主要有以下幾類：

1)Pregel & Giraph

Google 提出了 Pregel 來解決圖演算法在 MapReduce 上運行低效的問題，但沒有開源，Facebook 根據 Pregel 的思路發展了開源系統 Giraph，但 Giraph 有兩個問題：一是 Giraph 的社區不是很活躍;二是現實生活中的圖都是符合冪律分布的圖，即有一小部分點的邊數非常多，這些點在 Pregel 的計算模式下很容易拖慢整個計算任務，

2)GraphX

GraphX 是基于 Spark 構建的圖計算系統，融合了很多 PowerGraph 的思想，并對 Spark 在運行圖演算法程序中的多余 Shuffle 進行了優化，GraphX 對比原生 Spark 在性能方面有很大優勢，但 GraphX 非常費記憶體，Shuffle 效率也不是很高，導致運行時間也比較長，

3)Gemini

Gemini 是 16 年發表再在 OSDI 的一篇圖計算系統論文，結合了多種圖計算系統的優勢，并且有開源實作，作為最快的圖計算引擎之一，得到了業界的普遍認可，

正如《Scalability! But at what COST? 》一文指出，多數的圖計算系統為了拓展性，忽視了單機的性能，加之分布式帶來的巨大通信開銷，導致多機環境下的計算性能有時甚至反而不如單機環境，針對這些問題，Gemini 的做了針對性優化設計，簡單總結為：

• 圖存盤格式優化記憶體開銷：采用 CSC 和 CSR 的方式存盤圖，并對 CSC/CSR 進一步建立索引降低記憶體占用;
• Hierarchical Chunk-Based Partitioning：通過在 Node、Numa、Socket 多個維度做區域感知的圖切分，減少通信開銷;
• 自適應的 Push / Pull 計算：采用了雙模式通信策略，能根據當前活躍節點的數量動態地切換到稠密或稀疏模式，
• 兼顧單機性能和擴展性，使得 Gemini 處于圖計算性能最前沿，同時，Gemini 團隊也成立了商業公司專注圖資料的處理，

3、基于開源的實踐

Tencent Plato 是基于 Gemini 思想的開源圖計算系統，采用了 Gemini 的核心設計思路，但相比 Gemini 的開源版本有更加完善的工程實作，我們基于此，做了大量重構和二次開發，將其應用到生成環境中，這里分享下我們的實踐，

1)更大資料規模的探索

開源實作中有個非常關鍵的假設：一張圖中的點的數量不能超過 40 億個;但位元組跳動部分業務場景的資料規模遠超出了這個數額，為了支持千億萬億點的規模，我們將產生記憶體瓶頸的單機處理模塊，重構為分布式實作，

① 點 ID 的編碼

Gemini 的一個重要創新就是提出了基于 Chunk 的圖磁區方法，這種圖磁區方法需要將點 id 從 0 開始連續遞增編碼，但輸入的圖資料中，點 id 是隨機生成的，因此需要對點 id 進行一次映射，保證其連續遞增，具體實作方法是，在計算任務開始之前將原始的業務 id 轉換為從零開始的遞增 id，計算結束后再將 id 映射回去，如下圖所示：

在開源實作中，是假設圖中點的數量不可超過 40 億，40 億的 id 資料是可以存盤在單機記憶體中，因此采用比較簡單的實作方式：分布式計算集群中的每臺機器冗余存盤了所有點 id 的映射關系，然而，當點的數量從 40 億到千億級別，每臺機器僅 id 映射表就需要數百 GB 的記憶體，單機存盤方案就變得不再可行，因此需要將映射表分成 shard 分布式地存盤，具體實作方式如下：

我們通過哈希將原始業務點 id 打散在不同的機器，并行地分配全域從 0 開始連續遞增的 id，生成 id 映射關系后，每臺機器都會存有 id 映射表的一部分，隨后再將邊資料分別按起點和終點哈希，發送到對應的機器進行編碼，最終得到的資料即為可用于計算的資料，當計算運行結束后，需要資料需要映射回業務 id，其程序和上述也是類似的，

上面描述的僅僅是圖編碼部分，40 億點的值域限制還廣泛存在于構圖和實際計算程序中，我們都對此做了重構，另外在我們的規模下，也碰到了一些任務負載不均，不夠穩定，計算效率不高等問題，我們對此都做了部分優化和重構，

通過對開源實作的改造，位元組跳動的圖計算系統已經在線上支撐了多條產品線的計算任務，最大規模達到數萬億邊、數千億點的世界級超大圖，這是業內罕見的，同時，面對不斷增長的業務，并且我們還在持續擴大系統的邊界，來應對更大規模的挑戰，

2)自定義演算法實作

在常見圖計算演算法之外，位元組跳動多元的業務中，有大量的其他圖演算法需求以及現有演算法的改造需求，比如需要實作更適合二分圖的 LPA 演算法，需要改造 PageRank 演算法使之更容易收斂，

由于當前圖計算系統暴露的 API 還沒有非常好的封裝，使得撰寫演算法的用戶會直接感知到底層的內部機制，比如不同的通信模式、圖表示方式等，這固然方便了做圖計算演算法實作的調優，但也導致業務同學有一定成本;另外，因為涉及超大規模資料的高性能計算，一個細節(比如 hotpath 上的一個虛函式呼叫，一次執行緒同步)可能就對性能有至關重要的影響，需要業務同學對計算機體系結構有一定了解，基于上述兩個原因，目前演算法是圖計算引擎同學和圖計算用戶一起開發，但長期來看，我們會封裝常用計算算子并暴露 Python Binding ，或者引入 DSL 來降低業務的學習成本，

4、未來展望

面對位元組跳動的超大規模圖處理場景，我們在半年內快速開啟了圖計算方向，支持了搜索、風控等多個業務的大規模圖計算需求，取得了不錯的進展，但還有眾多需要我們探索的問題：

1)從全記憶體計算到混合存盤計算：為了支持更大規模的資料量，提供更加低成本的計算能力，我們將探索新型存盤硬體，包括 AEP / NVMe 等記憶體或外存設備，擴大系統能力;

2)動態圖計算：目前的系統只支持靜態圖計算，即對完整圖的全量資料進行計算，實際業務中的圖每時每刻都是在變化的，因此使用現有系統必須在每次計算都提供整張圖，而動態圖計算能夠比較好地處理增量的資料，無需對已經處理過的資料進行重復計算，因此我們將在一些場景探索動態圖計算;

3)異構計算：圖計算系統屬于計算密集型系統，在部分場景對計算性能有極高的要求，因此我們會嘗試異構計算，包括使用 GPU / FPGA 等硬體對計算進行加速，以追求卓越的計算性能;

4)圖計算語言：業務直接接觸底層計算引擎有很多弊端，比如業務邏輯與計算引擎強耦合，無法更靈活地對不同演算法進行性能優化，而通過圖計算語言對演算法進行描述，再對其編譯生成計算引擎的執行代碼，可以將業務邏輯與計算引擎解耦，能更好地對不同演算法進行自動地調優，將性能發揮到極致，

四、總結

隨著位元組跳動業務量級的飛速增長和業務需求的不斷豐富，我們在短時間內構建了圖存盤系統和圖計算系統，在實際生產系統中解決了大量的問題，但同時仍面臨著巨大的技術挑戰，我們將持續演進，打造業界頂尖的一堆疊式圖解決方案，未來已來，空間廣闊，希望更多有興趣的同學加入進來，用有趣的分布式技術來影響幾億人的互聯網生活，