本文選自“字節(jié)跳動基礎架構實踐”系列文章。

“字節(jié)跳動基礎架構實踐”系列文章是由字節(jié)跳動基礎架構部門各技術團隊及專家傾力打造的技術干貨內容，和大家分享團隊在基礎架構發(fā)展和演進過程中的實踐經驗與教訓，與各位技術同學一起交流成長。

2019 年，Gartner 將圖列為 2019 年十大數(shù)據(jù)和分析趨勢之一，字節(jié)跳動在面對把海量內容推薦給海量用戶的業(yè)務挑戰(zhàn)中，也大量采用圖技術。本文將對字節(jié)跳動自研的分布式圖數(shù)據(jù)庫和圖計算專用引擎做深度解析和分享，展示新技術是如何解決業(yè)務問題，影響幾億互聯(lián)網用戶的產品體驗。

1. 圖狀結構數(shù)據(jù)廣泛存在

字節(jié)跳動的所有產品的大部分業(yè)務數(shù)據(jù)，幾乎都可以歸入到以下三種：

• 用戶信息、用戶和用戶的關系（關注、好友等）；
• 內容（視頻、文章、廣告等）；
• 用戶和內容的聯(lián)系（點贊、評論、轉發(fā)、點擊廣告等）。

這三種數(shù)據(jù)關聯(lián)在一起，形成圖狀（Graph）結構數(shù)據(jù)。

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

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

下面會從圖數(shù)據(jù)庫和圖計算兩個部分，分別來介紹字節(jié)跳動在這方面的一些工作。

2. 自研圖數(shù)據(jù)庫（ByteGraph）介紹

從數(shù)據(jù)模型角度看，圖數(shù)據(jù)庫內部數(shù)據(jù)是有向屬性圖，其基本元素是 Graph 中的點（Vertex）、邊（Edge）以及其上附著的屬性；作為一個工具，圖數(shù)據(jù)對外提供的接口都是圍繞這些元素展開。

圖數(shù)據(jù)庫本質也是一個存儲系統(tǒng)，它和常見的 KV 存儲系統(tǒng)、MySQL 存儲系統(tǒng)的相比主要區(qū)別在于目標數(shù)據(jù)的邏輯關系不同和訪問模式不同，對于數(shù)據(jù)內在關系是圖模型以及在圖上游走類和模式匹配類的查詢，比如社交關系查詢，圖數(shù)據(jù)庫會有更大的性能優(yōu)勢和更加簡潔高效的接口。

2.1 為什么不選擇開源圖數(shù)據(jù)庫

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

字節(jié)跳動的 Graph 在線存儲場景， 其需求也是有自身特點的，可以總結為：

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

事實上，我們調研過了很多業(yè)界系統(tǒng)， 這個主題可以再單獨分享一篇文章。但是，面對字節(jié)跳動世界級的海量數(shù)據(jù)和海量并發(fā)請求，用萬億級分布式存儲、千萬高并發(fā)、低延遲、穩(wěn)定可控這三個條件一起去篩選，業(yè)界在線上被驗證穩(wěn)定可信賴的開源圖存儲系統(tǒng)基本沒有滿足的了；另外，對于一個承載公司核心數(shù)據(jù)的重要的基礎設施，是值得長期投入并且深度掌控的。

因此，我們在 18 年 8 月份，開始從第一行代碼開始踏上圖數(shù)據(jù)庫的漫漫征程，從解決一個最核心的抖音社交關系問題入手，逐漸演變?yōu)橹С钟邢驅傩詧D數(shù)據(jù)模型、支持寫入原子性、部分 Gremlin 圖查詢語言的通用圖數(shù)據(jù)庫系統(tǒng)，在公司所有產品體系落地，我們稱之為 ByteGraph。下面，會從數(shù)據(jù)模型、系統(tǒng)架構等幾個部分，由淺入深和大家分享我們的工作。

2.2 ByteGraph 的數(shù)據(jù)模型和 API

數(shù)據(jù)模型

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

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

• 點（Vertex）

點是圖數(shù)據(jù)庫的基本元素，通常反映的是靜態(tài)信息。在 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值是業(yè)務自定義含義的，比如可以用于記錄關注發(fā)生的時間戳- 邊屬性（KV對）：比如'ts_us': int64 描述關系創(chuàng)建時間的屬性，以及其他用戶自定義屬性

• 邊的方向

在 ByteGraph 的數(shù)據(jù)模型中，邊是有方向的，目前支持 3 種邊的方向:

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

場景使用偽碼舉例

構圖完畢后，我們就可以把業(yè)務邏輯通過 Gremlin 查詢語言來實現(xiàn)了；為便于大家理解，我們列舉幾種典型的場景為例。

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

// 創(chuàng)建用戶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)// 創(chuàng)建關注關系 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 之間的二度中間節(jié)點有哪些，比如 A->B,B->C，B 則為中間節(jié)點。

// where()表示對于上一個step的每個執(zhí)行結果，執(zhí)行子查詢過濾條件，只保留關注了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()

2.3 系統(tǒng)架構

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

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

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

查詢層(bgdb)

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

1. 將客戶端發(fā)來的 Gremlin 查詢語句做語法解析，生成執(zhí)行計劃；
2. 并根據(jù)一定的路由規(guī)則（例如一致性哈希）找到目標數(shù)據(jù)所在的存儲節(jié)點（bgkv），將執(zhí)行計劃中的讀寫請求發(fā)送給 多個 bgkv；
3. 將 bgkv 讀寫結果匯總以及過濾處理，得到最終結果，返回給客戶端。

bgdb 層沒有狀態(tài)，可以水平擴容，用 Go 語言開發(fā)。

存儲/事務引擎層（bgkv)

bgkv 層是由多個進程實例組成，每個實例管理整個集群數(shù)據(jù)的一個子集（shard / partition)。

bgkv 層的實現(xiàn)和功能有點類似內存數(shù)據(jù)庫，提供高性能的數(shù)據(jù)讀寫功能，其特點是：

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

從上述描述可以看出，bgkv 的性能和內存使用效率是非常關鍵的，因此采用 C 編寫。

磁盤存儲層(KV Cluster)

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

如何把圖存儲在 KV 數(shù)據(jù)庫中

上一小節(jié)，只是介紹了 ByteGraph 內部三層的關系，細心的讀者可能已經發(fā)現(xiàn)，ByteGraph 外部是圖接口，底層是依賴 KV 存儲，那么問題來了：如何把動輒百萬粉絲的圖數(shù)據(jù)存儲在一個 KV 系統(tǒng)上呢？

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

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

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

1. 一個點（Vertex）和其所有相連的邊組成了一數(shù)據(jù)組（Group）；不同的起點和及其終點是屬于不同的 Group，是存儲在不同的 KV 對的；比如用戶 A 的粉絲和用戶 B 的粉絲，就是分成不同 KV 存儲；
2. 對于某一個點的及其出邊，當出度數(shù)量比較?。↘B 級別），將其所有出度即所有終點序列化為一個 KV 對，我們稱之為一級存儲方式（后面會展開描述）；
3. 當一個點的出度逐漸增多，比如一個普通用戶逐漸成長為抖音大 V，我們則采用分布式 B-Tree 組織這百萬粉絲，我們稱之為二級存儲；
4. 一級存儲和二級存儲之間可以在線并發(fā)安全的互相切換；

• 一級存儲格式

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

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

• 二級存儲（點的出度大于閾值）

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

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

其中，整棵 B-Tree 由多組 KV 對組成，按照關系可以分為三種數(shù)據(jù)：

• 根節(jié)點：根節(jié)點本質是一個 KV 系統(tǒng)中的一個 key，其編碼方式和一級存儲中的 key 相同
• Meta 數(shù)據(jù)：Meta 數(shù)據(jù)本質是一個 KV 中的 value，和根節(jié)點組成了 KV 對；Meta 內部存儲了多個 PartKey，其中每個 PartKey 都是一個 KV 對中的 key，其對應的 value 數(shù)據(jù)就是下面介紹的 Part 數(shù)據(jù)；
• Part 數(shù)據(jù)對于二級存儲格式，存在多個 Part，每個 Part 存儲部分出邊的屬性和終點 ID每個 Part 都是一個 KV 對的 value，其對應的 key 存儲在 Meta 中。

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

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

ByteGraph 和 KV store 的關系，類似文件系統(tǒng)和塊設備的關系，塊設備負責將存儲資源池化并提供 Low Level 的讀寫接口，文件系統(tǒng)在塊設備上把元數(shù)據(jù)和數(shù)據(jù)組織成各種樹的索引結構，并封裝豐富的 POSIX 接口，便于外部使用。

2.4 一些問題深入探討

第三節(jié)介紹了 ByteGraph 的內在架構，現(xiàn)在我們更進一步，來看看一個分布式存儲系統(tǒng)，在面對字節(jié)跳動萬億數(shù)據(jù)上億并發(fā)的業(yè)務場景下兩個問題的分析。

熱點數(shù)據(jù)讀寫解決

熱點數(shù)據(jù)在字節(jié)跳動的線上業(yè)務中廣泛存在：熱點視頻、熱點文章、大 V 用戶、熱點廣告等等；熱點數(shù)據(jù)可能會出現(xiàn)瞬時出現(xiàn)大量讀寫。ByteGraph 在線上業(yè)務的實踐中，打磨出一整套應對性方案。

• 熱點讀

熱點讀的場景隨處可見，比如線上實際場景：某個熱點視頻被頻繁刷新，查看點贊數(shù)量等。在這種場景下，意味著訪問有很強的數(shù)據(jù)局部性，緩存命中率會很高，因此，我們設計實現(xiàn)了多級的 Query Cache 機制以及熱點請求轉發(fā)機制；在 bgdb 查詢層緩存查詢結果， bgdb 單節(jié)點緩存命中讀性能 20w QPS 以上，而且多個 bgdb 可以并發(fā)處理同一個熱點的讀請求，則系統(tǒng)整體應對熱點度的“彈性”是非常充足的。

• 熱點寫

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

• 行鎖沖突高：目前 ByteGraph 是單行事務模型，只有內存結構鎖，這個鎖的并發(fā)量是每秒千萬級，基本不會構成寫入瓶頸；
• 磁盤 IOPS 被打滿：IOPS（I/O Count Per Second）的概念：磁盤每秒的寫入請求數(shù)量是有上限的，不同型號的固態(tài)硬盤的 IOPS 各異，但都有一個上限，當上游寫入流量超過這個閾值時候，請求就會排隊，造成整個數(shù)據(jù)通路堵塞，延遲就會呈現(xiàn)指數(shù)上漲最終服務變成不可用。Group Commit 解決方案：Group Commit 是數(shù)據(jù)庫中的一個成熟的技術方案，簡單來講，就是多個寫請求在 bgkv 內存中匯聚起來，聚成一個 Batch 寫入 KV store，則對外體現(xiàn)的寫入速率就是 BatchSize * IOPS。

對于某個獨立數(shù)據(jù)源來說，一般熱點寫的請求比熱點讀會少很多，一般不會超過 10K QPS，目前 ByteGraph 線上還沒有出現(xiàn)過熱點寫問題問題。

圖的索引

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

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

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

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

2.5 未來探索

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

• 從圖存儲到圖數(shù)據(jù)庫：對于一個數(shù)據(jù)庫系統(tǒng)，是否支持 ACID 的事務，是一個核心問題，目前 ByteGraph 只解決了原子性和一致性，對于最復雜的隔離性還完全沒有觸碰，這是一個非常復雜的問題；另外，中國信通院發(fā)布了國內圖數(shù)據(jù)庫功能白皮書，以此標準，如果想做好一個功能完備的“數(shù)據(jù)庫”系統(tǒng)，我們面對的還是星辰大海；
• 標準的圖查詢語言：目前，圖數(shù)據(jù)庫的查詢語言業(yè)界還未形成標準（GQL 即將在 2020 年發(fā)布），ByteGraph 選擇 Apache、AWS 、阿里云的 Gremlin 語言體系，但目前也只是支持了一個子集，更多的語法支持、更深入的查詢優(yōu)化還未開展；
• Cloud Native 存儲架構演進：現(xiàn)在 ByteGraph 還是構建與 KV 存儲之上，獨占物理機全部資源；從資源彈性部署、運維托管等角度是否有其他架構演進的探索可能，從查詢到事務再到磁盤存儲是否有深度垂直整合優(yōu)化的空間，也是一個沒有被回答的問題；
• 現(xiàn)在 ByteGraph 是在 OLTP 場景下承載了大量線上數(shù)據(jù)，這些數(shù)據(jù)同時也會應用到推薦、風控等復雜分析和圖計算場景，如何把 TP 和輕量 AP 查詢融合在一起，具備部分 HTAP 能力，也是一個空間廣闊的藍海領域。

3. 圖計算系統(tǒng)介紹與實踐

3.1 圖計算技術背景

圖計算簡介

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

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

對于小規(guī)模的圖，我們可以用單機來進行計算。但隨著數(shù)據(jù)量的增大，一般需要引入分布式的計算系統(tǒng)來解決，并且要能夠高效地運行各種類型的圖算法。

批處理系統(tǒng)

大規(guī)模數(shù)據(jù)處理我們直接想到的就是使用 MapReduce / Spark 等批處理系統(tǒng)，字節(jié)跳動在初期也有不少業(yè)務使用 MapReduce / Spark 來實現(xiàn)圖算法。得益于批處理系統(tǒng)的廣泛使用，業(yè)務同學能夠快速實現(xiàn)并上線自己的算法邏輯。

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

圖計算系統(tǒng)

圖計算系統(tǒng)是針對圖算法的特點而衍生出的專用計算設施，能夠高效地運行圖算法。因此隨著業(yè)務的發(fā)展，我們迫切需要引入圖計算系統(tǒng)來解決圖數(shù)據(jù)處理的問題。圖計算也是比較成熟的領域，在學術界和工業(yè)界已有大量的系統(tǒng)，這些系統(tǒng)在不同場景，也各有優(yōu)劣勢。

由于面向不同的數(shù)據(jù)特征、不同的算法特性等，圖計算系統(tǒng)在平臺架構、計算模型、圖劃分、執(zhí)行模型、通信模型等方面各有取舍。下面，我們從不同角度對圖計算的一些現(xiàn)有技術做些分類分析。

• 分布架構

按照分布架構，圖計算可以分為單機或分布式、全內存或使用外存幾種，常見的各種圖計算系統(tǒng)如下圖所示。單機架構的優(yōu)勢在于無需考慮分布式的通信開銷，但通常難以快速處理大規(guī)模的圖數(shù)據(jù)；分布式則通過通信或分布式共享內存將可處理的數(shù)據(jù)規(guī)模擴大，但通常也會引入巨大的額外開銷。

• 計算模型

按照計算對象，圖數(shù)據(jù)計算模型可以分為節(jié)點中心計算模型、邊中心計算模型、子圖中心計算模型等。

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

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

def pagerank(vertex_id, msgs): // 計算收到消息的值之和 msg_sum = sum(msgs) // 更新當前PR值 pr = 0.15 0.85 * msg_sum // 用新計算的PR值發(fā)送消息 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 為了解決冪律圖（一小部分節(jié)點的度數(shù)非常高）的問題，將對一個節(jié)點的處理邏輯，拆分為了 Gather、Apply、Scatter 三階段。在計算滿足交換律和結合律的情況下，通過使用 GAS 模型，通信成本從 |E| 降低到了 |V|，使用 GAS 描述的 PageRank 如下圖所示：

def gather(msg_a, msg_b): // 匯聚消息 return msg_a msg_bdef 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): // 發(fā)送消息 return pr / out_degree(vertex_id)

• 圖劃分

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

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

切點法則是將一個節(jié)點切開，該節(jié)點上不同的邊會分布在不同的圖分區(qū)，每條邊全局只會出現(xiàn)一次，但切點法會導致一個節(jié)點在全局出現(xiàn)多次。如上圖右圖所示，節(jié)點 A 被切分為 3 份，其中邊 AB 屬于分區(qū) 2，邊 AD 屬于圖分區(qū) 3。

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

• 執(zhí)行模型

執(zhí)行模型解決的是不同的節(jié)點在迭代過程中，如何協(xié)調迭代進度的問題。圖計算通常是全圖多輪迭代的計算，比如 PageRank 算法，需要持續(xù)迭代直至全圖所有節(jié)點收斂才會結束。

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

同步計算是全圖所有節(jié)點完成一輪迭代之后，才開啟下一輪迭代，因為通常每個節(jié)點都會依賴其他節(jié)點在上一輪迭代產生的結果，因此同步計算的結果是正確的。

異步計算則是每個節(jié)點不等待其他節(jié)點的迭代進度，在自己計算完一輪迭代后直接開啟下一輪迭代，所以就會導致很多節(jié)點還沒有完全拿到上一輪的結果就開始了下一輪計算。

半同步計算是兩者的綜合，其思想是允許一定的不同步，但當計算最快的節(jié)點與計算最慢的節(jié)點相差一定迭代輪數(shù)時，最快的節(jié)點會進行等待。 同步計算和異步計算的示意圖如下圖：

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

• 通信模型

為了實現(xiàn)拓展性，圖計算采用了不同的通信模型，大致可分為分布式共享內存、Push 以及 Pull。分布式共享內存將數(shù)據(jù)存儲在共享內存中，通過直接操作共享內存完成信息交互；Push 模型是沿著出邊方向主動推送消息；Pull 則是沿著入邊方向主動收消息。三者優(yōu)劣對比如下表格所示：

3.2 技術選型

由于字節(jié)跳動要處理的是世界級的超大規(guī)模圖，同時還對計算任務運行時長有要求，因此主要考慮高性能、可拓展性強的圖計算系統(tǒng)。工業(yè)界使用比較多的系統(tǒng)主要有以下幾類：

1. Pregel & Giraph

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

2. GraphX

GraphX 是基于 Spark 構建的圖計算系統(tǒng)，融合了很多 PowerGraph 的思想，并對 Spark 在運行圖算法過程中的多余 Shuffle 進行了優(yōu)化。GraphX 對比原生 Spark 在性能方面有很大優(yōu)勢，但 GraphX 非常費內存，Shuffle 效率也不是很高，導致運行時間也比較長。

3. Gemini

Gemini 是 16 年發(fā)表再在 OSDI 的一篇圖計算系統(tǒng)論文，結合了多種圖計算系統(tǒng)的優(yōu)勢，并且有開源實現(xiàn)，作為最快的圖計算引擎之一，得到了業(yè)界的普遍認可。

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

• 圖存儲格式優(yōu)化內存開銷：采用 CSC 和 CSR 的方式存儲圖，并對 CSC/CSR 進一步建立索引降低內存占用；
• Hierarchical Chunk-Based Partitioning：通過在 Node、Numa、Socket 多個維度做區(qū)域感知的圖切分，減少通信開銷；
• 自適應的 Push / Pull 計算：采用了雙模式通信策略，能根據(jù)當前活躍節(jié)點的數(shù)量動態(tài)地切換到稠密或稀疏模式。

兼顧單機性能和擴展性，使得 Gemini 處于圖計算性能最前沿，同時，Gemini 團隊也成立了商業(yè)公司專注圖數(shù)據(jù)的處理。

3.3 基于開源的實踐

Tencent Plato 「鏈接」是基于 Gemini 思想的開源圖計算系統(tǒng)，采用了 Gemini 的核心設計思路，但相比 Gemini 的開源版本有更加完善的工程實現(xiàn)，我們基于此，做了大量重構和二次開發(fā)，將其應用到生成環(huán)境中，這里分享下我們的實踐。

更大數(shù)據(jù)規(guī)模的探索

開源實現(xiàn)中有個非常關鍵的假設：一張圖中的點的數(shù)量不能超過 40 億個；但字節(jié)跳動部分業(yè)務場景的數(shù)據(jù)規(guī)模遠超出了這個數(shù)額。為了支持千億萬億點的規(guī)模，我們將產生內存瓶頸的單機處理模塊，重構為分布式實現(xiàn)。

• 點 ID 的編碼

Gemini 的一個重要創(chuàng)新就是提出了基于 Chunk 的圖分區(qū)方法。這種圖分區(qū)方法需要將點 id 從 0 開始連續(xù)遞增編碼，但輸入的圖數(shù)據(jù)中，點 id 是隨機生成的，因此需要對點 id 進行一次映射，保證其連續(xù)遞增。具體實現(xiàn)方法是，在計算任務開始之前將原始的業(yè)務 id 轉換為從零開始的遞增 id，計算結束后再將 id 映射回去，如下圖所示：

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

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

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

通過對開源實現(xiàn)的改造，字節(jié)跳動的圖計算系統(tǒng)已經在線上支撐了多條產品線的計算任務，最大規(guī)模達到數(shù)萬億邊、數(shù)千億點的世界級超大圖，這是業(yè)內罕見的。同時，面對不斷增長的業(yè)務，并且我們還在持續(xù)擴大系統(tǒng)的邊界，來應對更大規(guī)模的挑戰(zhàn)。

自定義算法實現(xiàn)

在常見圖計算算法之外，字節(jié)跳動多元的業(yè)務中，有大量的其他圖算法需求以及現(xiàn)有算法的改造需求，比如需要實現(xiàn)更適合二分圖的 LPA 算法，需要改造 PageRank 算法使之更容易收斂。

由于當前圖計算系統(tǒng)暴露的 API 還沒有非常好的封裝，使得編寫算法的用戶會直接感知到底層的內部機制，比如不同的通信模式、圖表示方式等，這固然方便了做圖計算算法實現(xiàn)的調優(yōu)，但也導致業(yè)務同學有一定成本；另外，因為涉及超大規(guī)模數(shù)據(jù)的高性能計算，一個細節(jié)（比如 hotpath 上的一個虛函數(shù)調用，一次線程同步）可能就對性能有至關重要的影響，需要業(yè)務同學對計算機體系結構有一定了解?；谏鲜鰞蓚€原因，目前算法是圖計算引擎同學和圖計算用戶一起開發(fā)，但長期來看，我們會封裝常用計算算子并暴露 Python Binding ，或者引入 DSL 來降低業(yè)務的學習成本。

3.4 未來展望

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

1. 從全內存計算到混合存儲計算：為了支持更大規(guī)模的數(shù)據(jù)量，提供更加低成本的計算能力，我們將探索新型存儲硬件，包括 AEP / NVMe 等內存或外存設備，擴大系統(tǒng)能力；
2. 動態(tài)圖計算：目前的系統(tǒng)只支持靜態(tài)圖計算，即對完整圖的全量數(shù)據(jù)進行計算。實際業(yè)務中的圖每時每刻都是在變化的，因此使用現(xiàn)有系統(tǒng)必須在每次計算都提供整張圖。而動態(tài)圖計算能夠比較好地處理增量的數(shù)據(jù)，無需對已經處理過的數(shù)據(jù)進行重復計算，因此我們將在一些場景探索動態(tài)圖計算；
3. 異構計算：圖計算系統(tǒng)屬于計算密集型系統(tǒng)，在部分場景對計算性能有極高的要求。因此我們會嘗試異構計算，包括使用 GPU / FPGA 等硬件對計算進行加速，以追求卓越的計算性能；
4. 圖計算語言：業(yè)務直接接觸底層計算引擎有很多弊端，比如業(yè)務邏輯與計算引擎強耦合，無法更靈活地對不同算法進行性能優(yōu)化。而通過圖計算語言對算法進行描述，再對其編譯生成計算引擎的執(zhí)行代碼，可以將業(yè)務邏輯與計算引擎解耦，能更好地對不同算法進行自動地調優(yōu)，將性能發(fā)揮到極致。

4. 總結

隨著字節(jié)跳動業(yè)務量級的飛速增長和業(yè)務需求的不斷豐富，我們在短時間內構建了圖存儲系統(tǒng)和圖計算系統(tǒng)，在實際生產系統(tǒng)中解決了大量的問題，但同時仍面臨著巨大的技術挑戰(zhàn)，我們將持續(xù)演進，打造業(yè)界頂尖的一棧式圖解決方案。未來已來，空間廣闊，希望更多有興趣的同學加入進來，用有趣的分布式技術來影響幾億人的互聯(lián)網生活。

5. 參考文獻

1. 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.
2. 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.
3. Low, Yucheng, et al. "Distributed graphlab: A framework for machine learning in the cloud." arXiv preprint arXiv:1204.6078 (2012).
4. 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.
5. 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.
6. Zhu, Xiaowei, et al. "Gemini: A computation-centric distributed graph processing system." 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 2016.
7. 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.
8. 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.
9. 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.
10. McSherry, Frank, Michael Isard, and Derek G. Murray. "Scalability! But at what {COST}?." 15th Workshop on Hot Topics in Operating Systems (HotOS {XV}). 2015.
11. Aditya Auradkar, Chavdar Botev, Shirshanka Das. "Data Infrastructure at LinkedIn "2012 IEEE 28th International Conference on Data Engineering

更多分享

字節(jié)跳動 EB 級 HDFS 實踐

字節(jié)跳動如何優(yōu)化萬級節(jié)點 HDFS平臺

---

字節(jié)跳動基礎架構團隊

字節(jié)跳動基礎架構團隊是支撐字節(jié)跳動旗下包括抖音、今日頭條、西瓜視頻、火山小視頻在內的多款億級規(guī)模用戶產品平穩(wěn)運行的重要團隊，為字節(jié)跳動及旗下業(yè)務的快速穩(wěn)定發(fā)展提供了保證和推動力。

公司內，基礎架構團隊主要負責字節(jié)跳動私有云建設，管理數(shù)以萬計服務器規(guī)模的集群，負責數(shù)萬臺計算/存儲混合部署和在線/離線混合部署，支持若干 EB 海量數(shù)據(jù)的穩(wěn)定存儲。

文化上，團隊積極擁抱開源和創(chuàng)新的軟硬件架構。我們長期招聘基礎架構方向的同學，具體可參見 job.bytedance.com，感興趣可以聯(lián)系郵箱 arch-graph@bytedance.com 。

歡迎關注字節(jié)跳動技術團隊