1. 圖狀結構數據廣泛存在
字節跳動的所有產品的大部分業務數據，幾乎都可以歸入到以下三種：
- 用戶信息、用戶和用戶的關係（關注、好友等）；
- 內容（視頻、文章、廣告等）；
- 用戶和內容的聯繫（點贊、評論、轉發、點擊廣告等）。
這三種數據關聯在一起，形成圖狀（Graph）結構數據。
為了滿足 social graph 的在線增刪改查場景，字節跳動自研了分佈式圖存儲系統——ByteGraph。針對上述圖狀結構數據，ByteGraph 支持有向屬性圖數據模型，支持 Gremlin 查詢語言，支持靈活豐富的寫入和查詢接口，讀寫吞吐可擴展到千萬 QPS，延遲毫秒級。目前，ByteGraph 支持了頭條、抖音、 TikTok、西瓜、火山等幾乎字節跳動全部產品線，遍佈全球機房。在這篇文章中，將從適用場景、內部架構、關鍵問題分析幾個方面作深入介紹。
ByteGraph 主要用於在線 OLTP 場景，而在離線場景下，圖數據的分析和計算需求也逐漸顯現。 2019 年年初，Gartner 數據與分析峰會上將圖列為 2019 年十大數據和分析趨勢之一，預計全球圖分析應用將以每年 100% 的速度迅猛增長，2020 年將達到 80 億美元。因此，我們團隊同時也開啟了在離線圖計算場景的支持和實踐。
下面會從圖數據庫和圖計算兩個部分，分別來介紹字節跳動在這方面的一些工作。
2. 自研圖數據庫（ByteGraph）介紹
從數據模型角度看，圖數據庫內部數據是有向屬性圖，其基本元素是 Graph 中的點（Vertex）、邊（Edge）以及其上附著的屬性；作為一個工具，圖數據對外提供的接口都是圍繞這些元素展開。
圖數據庫本質也是一個存儲系統，它和常見的 KV 存儲系統、MySQL 存儲系統的相比主要區別在於目標數據的邏輯關係不同和訪問模式不同，對於數據內在關係是圖模型以及在圖上游走類和模式匹配類的查詢，比如社交關係查詢，圖數據庫會有更大的性能優勢和更加簡潔高效的接口。
2.1 為什麼不選擇開源圖數據庫
圖數據庫在 90 年代出現，直到最近幾年在數據爆炸的大趨勢下快速發展，百花齊放；但目前比較成熟的大部分都是面對傳統行業較小的數據集和較低的訪問吞吐場景，比如開源的 Neo4j 是單機架構；因此，在互聯網場景下，通常都是基於已有的基礎設施定製系統：比如 Facebook 基於 MySQL 系統封裝了 Social Graph 系統 TAO，幾乎承載了 Facebook 所有數據邏輯；Linkedln 在 KV 之上構建了 Social Graph 服務；微博是基於 Redis 構建了粉絲和關注關係。
字節跳動的 Graph 在線存儲場景， 其需求也是有自身特點的，可以總結為：
- 海量數據存儲：百億點、萬億邊的數據規模；並且圖符合冪律分佈，比如少量大 V 粉絲達到幾千萬；
- 海量吞吐：最大集群 QPS 達到數千萬；
- 低延遲：要求訪問延遲 pct99 需要限制在毫秒級；
- 讀多寫少：讀流量是寫流量的接近百倍之多；
- 輕量查詢多，重量查詢少：90%查詢是圖上二度以內查詢；
- 容災架構演進：要能支持字節跳動城域網、廣域網、洲際網絡之間主備容災、異地多活等不同容災部署方案。
事實上，我們調研過了很多業界系統， 這個主題可以再單獨分享一篇文章。但是，面對字節跳動世界級的海量數據和海量併發請求，用萬億級分佈式存儲、千萬高併發、低延遲、穩定可控這三個條件一起去篩選，業界在線上被驗證穩定可信賴的開源圖存儲系統基本沒有滿足的了；另外，對於一個承載公司核心數據的重要的基礎設施，是值得長期投入並且深度掌控的。
因此，我們在 18 年 8 月份，開始從第一行代碼開始踏上圖數據庫的漫漫征程，從解決一個最核心的抖音社交關係問題入手，逐漸演變為支持有向屬性圖數據模型、支持寫入原子性、部分 Gremlin 圖查詢語言的通用圖數據庫系統，在公司所有產品體系落地，我們稱之為 ByteGraph。下面，會從數據模型、系統架構等幾個部分，由淺入深和大家分享我們的工作。
2.2 ByteGraph 的數據模型和 API
數據模型
就像我們在使用 SQL 數據庫時，先要完成數據庫 Schema 以及範式設計一樣，ByteGraph 也需要用戶完成類似的數據模型抽象，但圖的數據抽象更加簡單，基本上是把數據之間的關係“翻譯”成有向屬性圖，我們稱之為“構圖”過程。
比如在前面提到的，如果想把用戶關係存入 ByteGraph，第一步就是需要把用戶抽象為點，第二步把"關注關係”、“好友關係”抽象為邊就完全搞定了。下面，我們就從代碼層面介紹下點邊的數據類型。
- 點（Vertex）
點是圖數據庫的基本元素，通常反映的是靜態信息。在 ByteGraph 中，點包含以下字段：
<code>- 點的id(uint64_t): 比如用戶id作為一個點 - 點的type(uint32_t): 比如appID作為點的type - 點的屬性（KV 對）：比如 'name': string，'age': int, 'gender': male，等自定義屬性 - [id, type]唯一定義一個點/<code>
- 邊（Edge）
一條邊由兩個點和點之間的邊的類型組成，邊可以描述點之間的關係，比如用戶 A 關注了用戶 B ，可以用以下字段來描述：
<code>- 兩個點（Vertex）: 比如用戶A和用戶B - 邊的類型(string): 比如“關注” - 邊的時間戳(uint64_t)：這個t值是業務自定義含義的，比如可以用於記錄關注發生的時間戳 - 邊屬性（KV對）：比如'ts_us': int64 描述關係創建時間的屬性，以及其他用戶自定義屬性/<code>
- 邊的方向
在 ByteGraph 的數據模型中，邊是有方向的，目前支持 3 種邊的方向:
<code>- 正向邊：如 A 關注 B(A -> B) - 反向邊：如 B 被 A 關注(B B)/<code>
場景使用偽碼舉例
構圖完畢後，我們就可以把業務邏輯通過 Gremlin 查詢語言來實現了；為便於大家理解，我們列舉幾種典型的場景為例。
- 場景一：記錄關注關係 A 關注 B
<code>// 創建用戶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)/<code>- 場景二：查詢 A 關注的且關注了 C 的所有用戶
用戶 A 進入用戶 C 的詳情頁面，想看看 A 和 C 之間的二度中間節點有哪些，比如 A->B,B->C，B 則為中間節點。
<code>// 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)))/<code>- 場景三：查詢 A 的好友的好友（二度關係）
<code>// both("好友")相當於in("好友")和out("好友")的合集，
g.V().has("type", A.type).has("id", A.id).both("好友").both("好友").toSet()/<code>2.3 系統架構
前面幾個章節，從用戶角度介紹了 ByteGraph 的適用場景和對外使用姿勢。那 ByteGraph 架構是怎樣的，內部是如何工作的呢，這一節就來從內部實現來作進一步介紹。
下面這張圖展示了 ByteGraph 的內部架構，其中 bg 是 ByteGraph 的縮寫。
就像 MySQL 通常可以分為 SQL 層和引擎層兩層一樣，ByteGraph 自上而下分為查詢層 (bgdb)、存儲/事務引擎層（bgkv）、磁盤存儲層三層，每層都是由多個進程實例組成。其中 bgdb 層與 bgkv 層混合部署，磁盤存儲層獨立部署，我們詳細介紹每一層的關鍵設計。
查詢層(bgdb)
bgdb 層和 MySQL 的 SQL 層一樣，主要工作是做讀寫請求的解析和處理；其中，所謂“處理”可以分為以下三個步驟：
- 將客戶端發來的 Gremlin 查詢語句做語法解析，生成執行計劃；
- 並根據一定的路由規則（例如一致性哈希）找到目標數據所在的存儲節點（bgkv），將執行計劃中的讀寫請求發送給 多個 bgkv；
- 將 bgkv 讀寫結果彙總以及過濾處理，得到最終結果，返回給客戶端。
bgdb 層沒有狀態，可以水平擴容，用 Go 語言開發。
存儲/事務引擎層（bgkv)
bgkv 層是由多個進程實例組成，每個實例管理整個集群數據的一個子集（shard / partition)。
bgkv 層的實現和功能有點類似內存數據庫，提供高性能的數據讀寫功能，其特點是：
- 接口不同：只提供點邊讀寫接口；
- 支持算子下推：通過把計算(算子)移動到存儲（bgkv）上，能夠有效提升讀性能；舉例：比如某個大 V 最近一年一直在漲粉，bgkv 支持查詢最近的 100 個粉絲，則不必讀出所有的百萬粉絲。
- 緩存存儲有機結合：其作為 KV store 的緩存層，提供緩存管理的功能，支持緩存加載、換出、緩存和磁盤同步異步 sync 等複雜功能。
從上述描述可以看出，bgkv 的性能和內存使用效率是非常關鍵的，因此採用 C++ 編寫。
磁盤存儲層(KV Cluster)
為了能夠提供海量存儲空間和較高的可靠性、可用性，數據必須最終落入磁盤，我們底層存儲是選擇了公司自研的分佈式 KV store。
如何把圖存儲在 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 的編碼：
<code>- key: 某個起點 id + 起點 type + 邊 type - value: 此起點的所有出邊（Edge）及其邊上屬性聚合作為 value，但不包括終點的屬性/<code>
- 二級存儲（點的出度大於閾值）
如果一個大 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 接口，便於外部使用。
2.4 一些問題深入探討
第三節介紹了 ByteGraph 的內在架構，現在我們更進一步，來看看一個分佈式存儲系統，在面對字節跳動萬億數據上億併發的業務場景下兩個問題的分析。
熱點數據讀寫解決
熱點數據在字節跳動的線上業務中廣泛存在：熱點視頻、熱點文章、大 V 用戶、熱點廣告等等；熱點數據可能會出現瞬時出現大量讀寫。ByteGraph 在線上業務的實踐中，打磨出一整套應對性方案。
- 熱點讀
熱點讀的場景隨處可見，比如線上實際場景：某個熱點視頻被頻繁刷新，查看點贊數量等。在這種場景下，意味著訪問有很強的數據局部性，緩存命中率會很高，因此，我們設計實現了多級的 Query Cache 機制以及熱點請求轉發機制；在 bgdb 查詢層緩存查詢結果， bgdb 單節點緩存命中讀性能 20w QPS 以上，而且多個 bgdb 可以併發處理同一個熱點的讀請求，則系統整體應對熱點度的“彈性”是非常充足的。
- 熱點寫
熱點讀和熱點寫通常是相伴而生的，熱點寫的例子也是隨處可見，比如：熱點新聞被瘋狂轉發， 熱點視頻被瘋狂點贊等等。對於數據庫而言，熱點寫入導致的性能退化的背後原因通常有兩個：行鎖衝突高或者磁盤寫入 IOPS 被打滿，我們分別來分析：
- 行鎖衝突高：目前 ByteGraph 是單行事務模型，只有內存結構鎖，這個鎖的併發量是每秒千萬級，基本不會構成寫入瓶頸；
- 磁盤 IOPS 被打滿：IOPS（I/O Count Per Second）的概念：磁盤每秒的寫入請求數量是有上限的，不同型號的固態硬盤的 IOPS 各異，但都有一個上限，當上遊寫入流量超過這個閾值時候，請求就會排隊，造成整個數據通路堵塞，延遲就會呈現指數上漲最終服務變成不可用。Group Commit 解決方案：Group Commit 是數據庫中的一個成熟的技術方案，簡單來講，就是多個寫請求在 bgkv 內存中匯聚起來，聚成一個 Batch 寫入 KV store，則對外體現的寫入速率就是 BatchSize * IOPS。
對於某個獨立數據源來說，一般熱點寫的請求比熱點讀會少很多，一般不會超過 10K QPS，目前 ByteGraph 線上還沒有出現過熱點寫問題問題。
圖的索引
就像關係型數據庫一樣，圖數據庫也可以構建索引。默認情況下，對於同一個起點，我們會採用邊上的屬性（時間戳）作為主鍵索引；但為了加速查詢，我們也支持其他元素（終點、其他屬性）來構建二級的聚簇索引，這樣很多查找就從全部遍歷優化成了二分查找，使得查詢速度大幅提升。
ByteGraph 默認按照邊上的時間戳（ts）來排序存儲，因此對於以下請求，查詢效率很高：
- 查詢最近的若干個點贊
- 查詢某個指定時間範圍窗口內加的好友
方向的索引可能有些費解，舉個例子說明下：給定兩個用戶來查詢是否存在粉絲關係，其中一個用戶是大 V，另一個是普通用戶，大 V 的粉絲可達千萬，但普通用戶的關注者一般不會很多；因此，如果用普通用戶作為起點大 V 作為終點，查詢代價就會低很多。其實，很多場景下，我們還需要用戶能夠根據任意一個屬性來構建索引，這個也是我們正在支持的重要功能之一。
2.5 未來探索
過去的一年半時間裡，ByteGraph 都是在有限的人力情況下，優先滿足業務需求，在系統能力構建方面還是有些薄弱的，有大量問題都需要在未來突破解決：
- 從圖存儲到圖數據庫：對於一個數據庫系統，是否支持 ACID 的事務，是一個核心問題，目前 ByteGraph 只解決了原子性和一致性，對於最複雜的隔離性還完全沒有觸碰，這是一個非常複雜的問題；另外，中國信通院發佈了國內圖數據庫功能白皮書，以此標準，如果想做好一個功能完備的“數據庫”系統，我們面對的還是星辰大海；
- 標準的圖查詢語言：目前，圖數據庫的查詢語言業界還未形成標準（GQL 即將在 2020 年發佈），ByteGraph 選擇 Apache、AWS 、阿里雲的 Gremlin 語言體系，但目前也只是支持了一個子集，更多的語法支持、更深入的查詢優化還未開展；
- Cloud Native 存儲架構演進：現在 ByteGraph 還是構建與 KV 存儲之上，獨佔物理機全部資源；從資源彈性部署、運維託管等角度是否有其他架構演進的探索可能，從查詢到事務再到磁盤存儲是否有深度垂直整合優化的空間，也是一個沒有被回答的問題；
- 現在 ByteGraph 是在 OLTP 場景下承載了大量線上數據，這些數據同時也會應用到推薦、風控等複雜分析和圖計算場景，如何把 TP 和輕量 AP 查詢融合在一起，具備部分 HTAP 能力，也是一個空間廣闊的藍海領域。
3. 圖計算系統介紹與實踐
3.1 圖計算技術背景
圖計算簡介
圖數據庫重點面對 OLTP 場景，以事務為核心，強調增刪查改並重，並且一個查詢往往只是涉及到圖中的少量數據；而圖計算與之不同，是解決大規模圖數據處理的方法，面對 OLAP 場景，是對整個圖做分析計算，下圖（引用自 VLDB 2019 keynote 《Graph Processing: A Panaromic View and Some Open Problems》）描述了圖計算和圖數據庫的一些領域區分。
舉個圖計算的簡單例子，在我們比較熟悉的 Google 的搜索場景中，需要基於網頁鏈接關係計算每個網頁的 PageRank 值，用來對網頁進行排序。網頁鏈接關係其實就是一張圖，而基於網頁鏈接關係的 PageRank 計算，其實就是在這張圖上運行圖算法，也就是圖計算。
對於小規模的圖，我們可以用單機來進行計算。但隨著數據量的增大，一般需要引入分佈式的計算系統來解決，並且要能夠高效地運行各種類型的圖算法。
批處理系統
大規模數據處理我們直接想到的就是使用 MapReduce / Spark 等批處理系統，字節跳動在初期也有不少業務使用 MapReduce / Spark 來實現圖算法。得益於批處理系統的廣泛使用，業務同學能夠快速實現並上線自己的算法邏輯。
批處理系統本身是為了處理行式數據而設計的，其能夠輕易地將工作負載分散在不同的機器上，並行地處理大量的數據。不過圖數據比較特殊，天然具有關聯性，無法像行式數據一樣直接切割。如果用批處理系統來運行圖算法，就可能會引入大量的 Shuffle 來實現關係的連接，而 Shuffle 是一項很重的操作，不僅會導致任務運行時間長，並且會浪費很多計算資源。
圖計算系統
圖計算系統是針對圖算法的特點而衍生出的專用計算設施，能夠高效地運行圖算法。因此隨著業務的發展，我們迫切需要引入圖計算系統來解決圖數據處理的問題。圖計算也是比較成熟的領域，在學術界和工業界已有大量的系統，這些系統在不同場景，也各有優劣勢。
由於面向不同的數據特徵、不同的算法特性等，圖計算系統在平臺架構、計算模型、圖劃分、執行模型、通信模型等方面各有取捨。下面，我們從不同角度對圖計算的一些現有技術做些分類分析。
- 分佈架構
按照分佈架構，圖計算可以分為單機或分佈式、全內存或使用外存幾種，常見的各種圖計算系統如下圖所示。單機架構的優勢在於無需考慮分佈式的通信開銷，但通常難以快速處理大規模的圖數據；分佈式則通過通信或分佈式共享內存將可處理的數據規模擴大，但通常也會引入巨大的額外開銷。
- 計算模型
按照計算對象，圖數據計算模型可以分為節點中心計算模型、邊中心計算模型、子圖中心計算模型等。
大部分圖計算系統都採用了節點中心計算模型（這裡的節點指圖上的一個點），該模型來自 Google 的 Pregel，核心思想是用戶編程過程中，以圖中一個節點及其鄰邊作為輸入來進行運算，具有編程簡單的優勢。典型的節點中心計算模型包括 Pregel 提出的 Pregel API 、 PowerGraph 提出的 GAS API 以及其他一些 API。
Pregel 創新性地提出了 "think like a vertex" 的思想，用戶只需編寫處理一個節點的邏輯，即可被拓展到整張圖進行迭代運算，使用 Pregel 描述的 PageRank 如下圖所示：
<code>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)/<code>GAS API 則是 PowerGraph 為了解決冪律圖（一小部分節點的度數非常高）的問題，將對一個節點的處理邏輯，拆分為了 Gather、Apply、Scatter 三階段。在計算滿足交換律和結合律的情況下，通過使用 GAS 模型，通信成本從 |E| 降低到了 |V|，使用 GAS 描述的 PageRank 如下圖所示：
<code>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)/<code>- 圖劃分
對於單機無法處理的超級大圖，則需要將圖數據劃分成幾個子圖，採用分佈式計算方式，因此，會涉及到圖劃分的問題，即如何將一整張圖切割成子圖，並分配給不同的機器進行分佈式地計算。常見的圖劃分方式有切邊法（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 則是沿著入邊方向主動收消息。三者優劣對比如下表格所示：
3.2 技術選型
由於字節跳動要處理的是世界級的超大規模圖，同時還對計算任務運行時長有要求，因此主要考慮高性能、可拓展性強的圖計算系統。工業界使用比較多的系統主要有以下幾類：
- Pregel & Giraph
Google 提出了 Pregel 來解決圖算法在 MapReduce 上運行低效的問題，但沒有開源。Facebook 根據 Pregel 的思路發展了開源系統 Giraph，但 Giraph 有兩個問題：一是 Giraph 的社區不是很活躍；二是現實生活中的圖都是符合冪律分佈的圖，即有一小部分點的邊數非常多，這些點在 Pregel 的計算模式下很容易拖慢整個計算任務。
- GraphX
GraphX 是基於 Spark 構建的圖計算系統，融合了很多 PowerGraph 的思想，並對 Spark 在運行圖算法過程中的多餘 Shuffle 進行了優化。GraphX 對比原生 Spark 在性能方面有很大優勢，但 GraphX 非常費內存，Shuffle 效率也不是很高，導致運行時間也比較長。
- 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.3 基於開源的實踐
Tencent Plato 「鏈接」是基於 Gemini 思想的開源圖計算系統，採用了 Gemini 的核心設計思路，但相比 Gemini 的開源版本有更加完善的工程實現，我們基於此，做了大量重構和二次開發，將其應用到生成環境中，這裡分享下我們的實踐。
更大數據規模的探索
開源實現中有個非常關鍵的假設：一張圖中的點的數量不能超過 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 億點的值域限制還廣泛存在於構圖和實際計算過程中，我們都對此做了重構。另外在我們的規模下，也碰到了一些任務負載不均，不夠穩定，計算效率不高等問題，我們對此都做了部分優化和重構。
通過對開源實現的改造，字節跳動的圖計算系統已經在線上支撐了多條產品線的計算任務，最大規模達到數萬億邊、數千億點的世界級超大圖，這是業內罕見的。同時，面對不斷增長的業務，並且我們還在持續擴大系統的邊界，來應對更大規模的挑戰。
自定義算法實現
在常見圖計算算法之外，字節跳動多元的業務中，有大量的其他圖算法需求以及現有算法的改造需求，比如需要實現更適合二分圖的 LPA 算法，需要改造 PageRank 算法使之更容易收斂。
由於當前圖計算系統暴露的 API 還沒有非常好的封裝，使得編寫算法的用戶會直接感知到底層的內部機制，比如不同的通信模式、圖表示方式等，這固然方便了做圖計算算法實現的調優，但也導致業務同學有一定成本；另外，因為涉及超大規模數據的高性能計算，一個細節（比如 hotpath 上的一個虛函數調用，一次線程同步）可能就對性能有至關重要的影響，需要業務同學對計算機體系結構有一定了解。基於上述兩個原因，目前算法是圖計算引擎同學和圖計算用戶一起開發，但長期來看，我們會封裝常用計算算子並暴露 Python Binding ，或者引入 DSL 來降低業務的學習成本。
3.4 未來展望
面對字節跳動的超大規模圖處理場景，我們在半年內快速開啟了圖計算方向，支持了搜索、風控等多個業務的大規模圖計算需求，取得了不錯的進展，但還有眾多需要我們探索的問題：
- 從全內存計算到混合存儲計算：為了支持更大規模的數據量，提供更加低成本的計算能力，我們將探索新型存儲硬件，包括 AEP / NVMe 等內存或外存設備，擴大系統能力；
- 動態圖計算：目前的系統只支持靜態圖計算，即對完整圖的全量數據進行計算。實際業務中的圖每時每刻都是在變化的，因此使用現有系統必須在每次計算都提供整張圖。而動態圖計算能夠比較好地處理增量的數據，無需對已經處理過的數據進行重複計算，因此我們將在一些場景探索動態圖計算；
- 異構計算：圖計算系統屬於計算密集型系統，在部分場景對計算性能有極高的要求。因此我們會嘗試異構計算，包括使用 GPU / FPGA 等硬件對計算進行加速，以追求卓越的計算性能；
- 圖計算語言：業務直接接觸底層計算引擎有很多弊端，比如業務邏輯與計算引擎強耦合，無法更靈活地對不同算法進行性能優化。而通過圖計算語言對算法進行描述，再對其編譯生成計算引擎的執行代碼，可以將業務邏輯與計算引擎解耦，能更好地對不同算法進行自動地調優，將性能發揮到極致。
4. 總結
隨著字節跳動業務量級的飛速增長和業務需求的不斷豐富，我們在短時間內構建了圖存儲系統和圖計算系統，在實際生產系統中解決了大量的問題，但同時仍面臨著巨大的技術挑戰，我們將持續演進，打造業界頂尖的一棧式圖解決方案。未來已來，空間廣闊，希望更多有興趣的同學加入進來，用有趣的分佈式技術來影響幾億人的互聯網生活。
5. 參考文獻
- Bronson, Nathan, et al. "{TAO}: Facebook’s distributed data store for the social graph." Presented as part of the 2013 {USENIX} Annual Technical Conference ({USENIX}{ATC} 13). 2013.
- Malewicz, Grzegorz, et al. "Pregel: a system for large-scale graph processing." Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. 2010.
- Low, Yucheng, et al. "Distributed graphlab: A framework for machine learning in the cloud." arXiv preprint arXiv:1204.6078 (2012).
- Gonzalez, Joseph E., et al. "Powergraph: Distributed graph-parallel computation on natural graphs." Presented as part of the 10th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 12). 2012.
- Gonzalez, Joseph E., et al. "Graphx: Graph processing in a distributed dataflow framework." 11th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 14). 2014.
- Zhu, Xiaowei, et al. "Gemini: A computation-centric distributed graph processing system." 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 2016.
- Kyrola, Aapo, Guy Blelloch, and Carlos Guestrin. "Graphchi: Large-scale graph computation on just a {PC}." Presented as part of the 10th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 12). 2012.
- Roy, Amitabha, Ivo Mihailovic, and Willy Zwaenepoel. "X-stream: Edge-centric graph processing using streaming partitions." Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. 2013.
- Shun, Julian, and Guy E. Blelloch. "Ligra: a lightweight graph processing framework for shared memory." Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming. 2013.
- McSherry, Frank, Michael Isard, and Derek G. Murray. "Scalability! But at what {COST}?." 15th Workshop on Hot Topics in Operating Systems (HotOS {XV}). 2015.
- Aditya Auradkar, Chavdar Botev, Shirshanka Das. "Data Infrastructure at LinkedIn "2012 IEEE 28th International Conference on Data Engineering
