本文選自“字節(jié)跳動基礎(chǔ)架構(gòu)實(shí)踐”系列文章。

“字節(jié)跳動基礎(chǔ)架構(gòu)實(shí)踐”系列文章是由字節(jié)跳動基礎(chǔ)架構(gòu)部門各技術(shù)團(tuán)隊(duì)及專家傾力打造的技術(shù)干貨內(nèi)容，和大家分享團(tuán)隊(duì)在基礎(chǔ)架構(gòu)發(fā)展和演進(jìn)過程中的實(shí)踐經(jīng)驗(yàn)與教訓(xùn)，與各位技術(shù)同學(xué)一起交流成長。

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

1. 圖狀結(jié)構(gòu)數(shù)據(jù)廣泛存在

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 點(diǎn)（Vertex）

點(diǎn)是圖數(shù)據(jù)庫的基本元素，通常反映的是靜態(tài)信息。在 ByteGraph 中，點(diǎn)包含以下字段：

- 點(diǎn)的id(uint64_t): 比如用戶id作為一個點(diǎn)- 點(diǎn)的type(uint32_t): 比如appID作為點(diǎn)的type- 點(diǎn)的屬性（KV 對）：比如 'name': string，'age': int, 'gender': male，等自定義屬性- [id, type]唯一定義一個點(diǎn)

• 邊（Edge）

一條邊由兩個點(diǎn)和點(diǎn)之間的邊的類型組成，邊可以描述點(diǎn)之間的關(guān)系，比如用戶 A 關(guān)注了用戶 B ，可以用以下字段來描述：

- 兩個點(diǎn)（Vertex）: 比如用戶A和用戶B- 邊的類型(string): 比如“關(guān)注”- 邊的時間戳(uint64_t)：這個t值是業(yè)務(wù)自定義含義的，比如可以用于記錄關(guān)注發(fā)生的時間戳- 邊屬性（KV對）：比如'ts_us': int64 描述關(guān)系創(chuàng)建時間的屬性，以及其他用戶自定義屬性

• 邊的方向

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

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

場景使用偽碼舉例

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

• 場景一：記錄關(guān)注關(guān)系 A 關(guān)注 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)建關(guān)注關(guān)系 A -> B，其中addE("關(guān)注")中指定了邊的類型信息，from和to分別指定起點(diǎn)和終點(diǎn)，g.addE("關(guān)注").from(A.id, A.type).to(B.id, B.type).property("ts_us", now)

• 場景二：查詢 A 關(guān)注的且關(guān)注了 C 的所有用戶

用戶 A 進(jìn)入用戶 C 的詳情頁面，想看看 A 和 C 之間的二度中間節(jié)點(diǎn)有哪些，比如 A->B,B->C，B 則為中間節(jié)點(diǎn)。

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

• 場景三：查詢 A 的好友的好友（二度關(guān)系）

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

2.3 系統(tǒng)架構(gòu)

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

下面這張圖展示了 ByteGraph 的內(nèi)部架構(gòu)，其中 bg 是 ByteGraph 的縮寫。

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

查詢層(bgdb)

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

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

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

存儲/事務(wù)引擎層（bgkv)

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

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

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

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

磁盤存儲層(KV Cluster)

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

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

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

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

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

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

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

• 一級存儲格式

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

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

• 二級存儲（點(diǎn)的出度大于閾值）

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

但如何拆呢？ ByteGraph 的方式就是把所有出度和終點(diǎn)拆成多個 KV 對，所有 KV 對形成一棵邏輯上的分布式 B-Tree，之所以說“邏輯上的”，是因?yàn)闃渲械墓?jié)點(diǎn)關(guān)系是靠 KV 中 key 來指向的，并非內(nèi)存指針； B-Tree 是分布式的，是指構(gòu)成這棵樹的各級節(jié)點(diǎn)是分布在集群多個實(shí)例上的，并不是單機(jī)索引關(guān)系。具體關(guān)系如下圖所示：

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

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

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

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

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

2.4 一些問題深入探討

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

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

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

• 熱點(diǎn)讀

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

• 熱點(diǎn)寫

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

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

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

圖的索引

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

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

• 查詢最近的若干個點(diǎn)贊
• 查詢某個指定時間范圍窗口內(nèi)加的好友

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

2.5 未來探索

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

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

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

3.1 圖計(jì)算技術(shù)背景

圖計(jì)算簡介

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

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

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

批處理系統(tǒng)

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

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

圖計(jì)算系統(tǒng)

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

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

• 分布架構(gòu)

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

• 計(jì)算模型

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

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

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

def pagerank(vertex_id, msgs): // 計(jì)算收到消息的值之和 msg_sum = sum(msgs) // 更新當(dāng)前PR值 pr = 0.15 0.85 * msg_sum // 用新計(jì)算的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é)點(diǎn)的度數(shù)非常高）的問題，將對一個節(jié)點(diǎn)的處理邏輯，拆分為了 Gather、Apply、Scatter 三階段。在計(jì)算滿足交換律和結(jié)合律的情況下，通過使用 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)

• 圖劃分

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

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

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

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

• 執(zhí)行模型

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

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

同步計(jì)算是全圖所有節(jié)點(diǎn)完成一輪迭代之后，才開啟下一輪迭代，因?yàn)橥ǔＣ總€節(jié)點(diǎn)都會依賴其他節(jié)點(diǎn)在上一輪迭代產(chǎn)生的結(jié)果，因此同步計(jì)算的結(jié)果是正確的。

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

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

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

• 通信模型

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

3.2 技術(shù)選型

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

1. Pregel & Giraph

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

2. GraphX

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

3. Gemini

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

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

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

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

3.3 基于開源的實(shí)踐

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

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

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

• 點(diǎn) ID 的編碼

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

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

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

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

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

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

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

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

3.4 未來展望

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

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

4. 總結(jié)

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

5. 參考文獻(xiàn)

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 實(shí)踐

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

字節(jié)跳動基礎(chǔ)架構(gòu)團(tuán)隊(duì)

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

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

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

歡迎關(guān)注字節(jié)跳動技術(shù)團(tuán)隊(duì)