論文鏈接：

https://dl.acm.org/doi/pdf/10.1145/3626246.3653373

ps：可復(fù)制到瀏覽器打開

SIGMOD （ACM Special Interest Group on Management Of Data） 是數(shù)據(jù)庫(kù)三大國(guó)際頂級(jí)學(xué)術(shù)會(huì)議之一，也是數(shù)據(jù)庫(kù)領(lǐng)域影響力最大的頂級(jí)會(huì)議，中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）推薦的A類國(guó)際學(xué)術(shù)會(huì)議，今年的 SIGMOD 于 6 月 9 日到 14 日在南美洲的智利舉行。

每屆會(huì)議集中展示了當(dāng)前數(shù)據(jù)庫(kù)研究的前沿方向、工業(yè)界的最新技術(shù)和各國(guó)的研發(fā)水平，吸引了全球頂級(jí)研究機(jī)構(gòu)投稿。

其中來自字節(jié)跳動(dòng)基礎(chǔ)架構(gòu)圖團(tuán)隊(duì)的 《BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance》論文被 SIGMOD2024 收錄為 Industry Track 論文。

研究背景與動(dòng)機(jī)

ByteGraph 是字節(jié)自研的支持萬億級(jí)圖數(shù)據(jù)庫(kù)，目前 ByteGraph 已部署超過 1000+ 集群，支持今日頭條，抖音，西瓜視頻，火山，廣告，風(fēng)控等全系產(chǎn)品。典型的工作負(fù)載歸納如下:

• OLAP工作負(fù)載主要應(yīng)用于知識(shí)圖譜和風(fēng)控，讀取比例日常為 100%，數(shù)據(jù)導(dǎo)入時(shí)下降到 60%，整體吞吐量為數(shù)萬級(jí)，遍歷跳數(shù)為 3 到 5，寫入頻率為周期性，性能關(guān)注點(diǎn)包括延遲和錯(cuò)誤率。
• OLSP 工作負(fù)載適用于推薦、GNN 采樣和特征服務(wù)，讀取比例為 75% 至 90%，整體吞吐量為數(shù)億級(jí)遍歷跳數(shù)為 1 至 2，寫入頻率為實(shí)時(shí)，性能關(guān)注點(diǎn)包括吞吐量、延遲和錯(cuò)誤率。
• OLTP 工作負(fù)載主要應(yīng)用于電商和內(nèi)容記錄，讀取比例為 90% 至 99.9%，整體吞吐量為數(shù)千萬級(jí)，遍歷跳數(shù)為1，寫入頻率也為實(shí)時(shí)，性能關(guān)注點(diǎn)包括吞吐量、延遲和失敗率。

綜合分析表明，ByteGraph 系統(tǒng)所承擔(dān)的主要工作負(fù)載以讀操作為核心，其發(fā)生的頻次顯著高于寫操作。

尤其值得關(guān)注的是，圖結(jié)構(gòu)中最基本的讀取操作是對(duì)鄰接表的掃描，因此，對(duì)讀取性能的持續(xù)優(yōu)化，尤其是鄰接表掃描的性能，顯得至關(guān)重要。

盡管讀操作占主導(dǎo)地位，寫操作的重要性仍不容小覷，特別是在推薦場(chǎng)景中，ByteGraph 系統(tǒng)擁有海量的推薦場(chǎng)景集群，即使讀取比例超過 75%，寫入操作的規(guī)模也達(dá)到了千萬級(jí)，這常常成為影響整個(gè)集群成本的關(guān)鍵因素。

下面我們將先從 ByteGraph 前一代 2.0 架構(gòu)開始，介紹當(dāng)前遇到的問題。ByteGraph 2.0 系統(tǒng)架構(gòu)圖1所示：

ByteGraph 2.0 架構(gòu)整體劃分為三個(gè)層次：BGE 層負(fù)責(zé)處理圖查詢請(qǐng)求，BGS 層負(fù)責(zé)緩存圖的結(jié)構(gòu)和屬性數(shù)據(jù)，而分布式 KV 層則確保數(shù)據(jù)的持久化，三層可以各自獨(dú)立擴(kuò)展。

為了實(shí)現(xiàn)讀寫操作的均衡，ByteGraph 2.0 采用了 Edge Btree 來存儲(chǔ)鄰接表。通過在 KV 模型上構(gòu)建 Btree（每個(gè) Btree 的頁(yè)面作為一個(gè)KV單元存儲(chǔ)），ByteGraph 滿足了業(yè)務(wù)的基本需求。

更深入的 2.0 架構(gòu)細(xì)節(jié)可以在 ByteGraph 團(tuán)隊(duì) VLDB 2022 的論文《ByteGraph: A High-Performance Distributed Graph Database in ByteDance》中找到。

然而隨著業(yè)務(wù)規(guī)模的擴(kuò)大，以及基于圖的實(shí)時(shí)圖分析技術(shù)在社交網(wǎng)絡(luò)應(yīng)用中落地，我們發(fā)現(xiàn)上一代 ByteGraph 架構(gòu)在字節(jié)業(yè)務(wù)中遇到以下幾大痛點(diǎn)：

1. 基于 LSM-based 的分布式 KV 構(gòu)建系統(tǒng)，在字節(jié)圖數(shù)據(jù)庫(kù)的 Workload 下面存在一些劣勢(shì)，主要體現(xiàn)為以下幾個(gè)點(diǎn)

1. KV點(diǎn)查性能差：LSM-based 的 Key-Value 引擎，點(diǎn)查性能相比于 Btree 引擎不夠穩(wěn)定(無論 Compaction 策略采用 Level Compaction 還是 Size Tiered Compaction)，當(dāng) BGS 層出現(xiàn) Cache Miss 時(shí)，讀延遲不夠穩(wěn)定，而字節(jié)內(nèi)很多場(chǎng)景，如抖音點(diǎn)贊等業(yè)務(wù)，Workload 都是讀多寫少，對(duì)讀延遲有較高要求。
2. 寫入放大高：采取 Btree On LSM 的架構(gòu)，疊加了 Btree Page 寫入放大（每次修改 Page 中的一行記錄，都需要把 Page 寫入 KV 系統(tǒng)）和 LSM 內(nèi)部寫放大（一般采用 Level Compaction ），最終總體寫入放大較高。
3. 冗余的內(nèi)存層次：分布式 KV 內(nèi)部采用 RocksDB，當(dāng)發(fā)生 Cache Miss 后，一份數(shù)據(jù)會(huì)同時(shí)在 BGS 和RocksDB 的 Block Cache 中緩存，造成了內(nèi)存冗余，進(jìn)一步導(dǎo)致了整體服務(wù) TCO 上升。

2. 基于LSM的分布式KV底存儲(chǔ)在做垃圾回收的過程中采用兩種策略 (1) RocksDB 默認(rèn) KV 不分離，使用 Level Compaction 回收數(shù)據(jù) ，(2) TerarkDB 使用 KV 分離策略，Value 部分采用傳統(tǒng)的基于垃圾率的空間回收策略。以上兩者無法針對(duì) ByteGraph 業(yè)務(wù)上的冷熱訪問數(shù)據(jù)進(jìn)行針對(duì)性的優(yōu)化。
3. 隨著字節(jié)電商，支付等業(yè)務(wù)的快速發(fā)展，越來越多的圖計(jì)算，圖神經(jīng)網(wǎng)絡(luò)在圖數(shù)據(jù)上應(yīng)用，這些應(yīng)用要求更高的讀擴(kuò)展性，具體來說：當(dāng)新數(shù)據(jù)寫入ByteGraph 讀寫節(jié)點(diǎn)后，能在極短的時(shí)間內(nèi)穩(wěn)定的被只讀節(jié)點(diǎn)讀出。基于分布式 KV 的前一代 ByteGraph 實(shí)現(xiàn)的最終一致性，無法滿足 Time-bounded 主從一致性的要求。
4. 在字節(jié)的社交、推薦和風(fēng)控的圖查詢 Workload 中，會(huì)涉及到對(duì)點(diǎn)鄰居的復(fù)雜的計(jì)算模式，包括對(duì)鄰居打分排序，過濾等計(jì)算。在這類重計(jì)算的場(chǎng)景下，2.0 的行存儲(chǔ)引擎、執(zhí)行引擎對(duì)只需要分析部分邊屬性的掃描不友好，以及大批量邊的計(jì)算在基于行計(jì)算引擎中存在較高的解釋開銷。

解決方案

為了解決上述四大痛點(diǎn)，我們開發(fā)了 ByteGraph 的新一代架構(gòu)，命名為 ByteGraph 3.0（BG3）。

BG3 旨在從查詢引擎到存儲(chǔ)引擎全面更新，在查詢引擎引入向量化計(jì)算、MPP、AQE 等技術(shù)，同時(shí)構(gòu)建基于共享存儲(chǔ)的圖原生 Bw-tree 存儲(chǔ)引擎，來實(shí)現(xiàn)性能、成本的大幅優(yōu)化，本文將重點(diǎn)介紹圖存儲(chǔ)引擎部分。BG3 整體架構(gòu)如下所示：

如圖2所示，BG3 基于 Append-only 的共享云存儲(chǔ)系統(tǒng)構(gòu)建，在此之上我們構(gòu)建了一個(gè) Cloud Native Bw-tree 單機(jī)引擎，BG3 新架構(gòu)的存儲(chǔ)引擎主要有以下幾大創(chuàng)新點(diǎn)：

1.Space Optimized Bw-Tree Forest

如圖 3 所示，我們以抖音用戶點(diǎn)贊場(chǎng)景為例，用戶每點(diǎn)贊一條視頻，都會(huì)向 ByteGraph 插入一條用戶到視頻的邊。

假設(shè)A用戶是一個(gè)很活躍的用戶，每天都會(huì)點(diǎn)贊大量的視頻，而用戶B和C相比之下每天只點(diǎn)贊少量的視頻。

如果我們把所有用戶都存儲(chǔ)在一顆 Bw-tree 上，來自用戶 A，B，C 的邊有可能存儲(chǔ)在同一個(gè)葉子節(jié)點(diǎn)上，這樣由于A的點(diǎn)贊邊的頻繁插入葉子節(jié)點(diǎn)，會(huì)造成葉子節(jié)點(diǎn)的頻繁分裂和 Bw-tree 的沖突，這些都會(huì)引起用戶 B 和 C 沒有必要的讀寫延遲。

為了減少 Bw-tree 上的沖突，最理想的情況我們?yōu)槊恳粋€(gè)用戶的點(diǎn)贊邊被寫到一個(gè)獨(dú)立的 Bw-tree 中，但我們發(fā)現(xiàn)圖上存在明顯的 Power-Law 現(xiàn)象，80%用戶點(diǎn)贊頻率有限（可能只有幾十個(gè)贊），因?yàn)槊總€(gè) Bw-tree 都有一些元數(shù)據(jù)的開銷，如果每個(gè)用戶都單獨(dú)分配一顆Bw-tree會(huì)導(dǎo)致元數(shù)據(jù)的內(nèi)存和磁盤開銷過大。

因此我們提出了“Space Optimized Bw-tree Forest”，所有的用戶點(diǎn)贊邊會(huì)被首先寫入一顆統(tǒng)一的 Bw-tree(INIT)中，當(dāng)一個(gè)用戶的點(diǎn)贊邊數(shù)超過某個(gè)閾值，這個(gè)用戶的數(shù)據(jù)會(huì)被分裂到單獨(dú)的一個(gè)Bw-tree中（如圖3右邊的用戶A）。

2.Read Optimized Bw-Tree

Bw-tree 每次修改都會(huì)轉(zhuǎn)換為一次 Delta page 的寫入（如圖 4 左上所示），這樣設(shè)計(jì)的好處是寫入很快并且寫入放大低，但這種設(shè)計(jì)的缺點(diǎn)是讀入時(shí)有可能需要從磁盤上從不同位置讀取多個(gè) Delta 才能獲得 Base page 最新的鏡像（如圖 4 左下所示）。

字節(jié)內(nèi)大量業(yè)務(wù)對(duì) ByteGraph 的 Workload 都是寫少讀多，原始 Bw-tree 的寫入特性對(duì)讀性能有很大的影響，并且在存算分離的場(chǎng)景下會(huì)放大該問題，一次上層的 Cache Miss ，會(huì)造成大量下層的 IOPS 放大，多個(gè)Delta 導(dǎo)致的多次 IO 會(huì)導(dǎo)致讀取延遲不穩(wěn)定，對(duì)用戶影響較大，并且在共享存儲(chǔ)架構(gòu)下這個(gè)問題會(huì)更加明顯。

因此，BG3 提出了“Read Optimized Bw-tree”，如圖 4 右邊所示，我們?cè)诿看螌懭?Bw-tree 的時(shí)候，會(huì)把之前還未合并到Base page 的 Delta一并寫入，這樣設(shè)計(jì)的好處是當(dāng)我們需要讀取 Delta 獲得 Page 最新的鏡像時(shí)，我們可以只讀一次 Delta 數(shù)據(jù)。

雖然這種方法和原始 Bw-tree 對(duì)比增加了額外的寫入開銷，但我們?cè)谧止?jié)真實(shí)的 Workload 測(cè)試后發(fā)現(xiàn)（論文中也有對(duì)應(yīng)的評(píng)測(cè)），這部分寫入開銷可控的前提下大幅增加讀性能。

3.Workload-Aware Space Reclamation

為了持久化考慮，Bw-tree 的 Base page 和 Delta page 數(shù)據(jù)會(huì)被統(tǒng)一寫入Append-only的云存儲(chǔ)中。

傳統(tǒng)的 Bw-tree 的空間回收會(huì)維護(hù)一個(gè) Fifo 的隊(duì)列，新數(shù)據(jù)插入隊(duì)列頭部，每次空間回收都會(huì)從隊(duì)列的尾部開始掃描數(shù)據(jù)，把隊(duì)列尾仍然有效的數(shù)據(jù)重新寫入隊(duì)列頭，以達(dá)到回收已失效數(shù)據(jù)空間的目的。

傳統(tǒng) Bw-tree 的空間回收策略沒有考慮不同數(shù)據(jù)段的空間回收率，后臺(tái)的數(shù)據(jù)搬運(yùn)產(chǎn)生了大量的寫放大。

從空間回收的角度看，Base page 和 Delta page 的寫入 Pattern 不同。我們借鑒了 Arkdb[1] 的設(shè)計(jì)，把 Base/Delta 分別寫入不同 Stream，并把 Stream 內(nèi)數(shù)據(jù)劃分成相等大小 Extent的設(shè)計(jì)。與此同時(shí)，我們發(fā)現(xiàn)：

A. 以視頻點(diǎn)贊場(chǎng)景為例，圖數(shù)據(jù)的冪律分布特性使得視頻的熱度(喜歡，收藏，瀏覽)呈現(xiàn)出冷熱差別。同一個(gè)視頻，視頻剛發(fā)布時(shí)的點(diǎn)贊數(shù)的增長(zhǎng)率會(huì)遠(yuǎn)高于發(fā)布一個(gè)月后視頻的點(diǎn)贊數(shù)增長(zhǎng)率。點(diǎn)贊數(shù)增長(zhǎng)程度的不同傳導(dǎo)到下層存儲(chǔ)體現(xiàn)為不同視頻對(duì)應(yīng)的 Bw-tree 上各個(gè) Page 修改的頻率相差甚遠(yuǎn)。這進(jìn)一步造成了底層 Stream 中的 Extent 的空洞的變化率的不同。

B. 用戶對(duì)于事物的偏好往往隨著時(shí)間變化而變化，因此我們通常使用時(shí)間窗口來維護(hù)用戶最近的瀏覽歷史，搜索行為和視頻口味偏好等等。這就要求 ByteGraph 支持過期數(shù)據(jù)刪除的功能。這種基于 TTL 的過期刪除行為，在下層Extent 存儲(chǔ)時(shí)間到期后會(huì)產(chǎn)生批量刪除。

基于上面兩點(diǎn)觀察，我們提出了“Workload aware space reclamation”。每一塊 Extent 我們會(huì)有一個(gè)Extent usage tracking模塊，我們會(huì)記錄

1. LastTimestamp: 以 Extent中 最晚更新的一條數(shù)據(jù)的時(shí)間戳作為整個(gè)extent的時(shí)間戳。2. Fragmentation Rate. 我們通過記錄 Extent 的有效 Page 數(shù)和無效 Page 數(shù)，從而計(jì)算出 Extent 的空洞率。3.Update Gradient。Extent 每次更新我們會(huì)記錄更新時(shí)間以及當(dāng)前 Extent 中 Invalid Page 的總數(shù)。

如圖5所示，和傳統(tǒng)垃圾回收策略只選擇垃圾率最高的 Extent 回收不同，我們的策略會(huì)優(yōu)先選擇垃圾變化率 ( Update Gradient ) 最低（變化率最低意味著是冷數(shù)據(jù)，搬運(yùn)的都是有效的數(shù)據(jù)，這樣可以避免搬遷即將被刪除的數(shù)據(jù)，這樣對(duì)于全局是最優(yōu)的）的 Extent 進(jìn)行回收。

與此同時(shí)，當(dāng)我們發(fā)現(xiàn)一個(gè) Extent 設(shè)置了 TTL，在回收過程中我們會(huì)跳過這些 Extent，并在 TTL 到期后整體刪除數(shù)據(jù)，這樣可以避免因?yàn)槔厥债a(chǎn)生的沒必要的搬動(dòng)。

4.I/O Efficient Synchronization Mechanism

針對(duì)上一代 ByteGraph 的主從同步最終一致性的問題，ByteGraph 3.0 提出了 Write-Ahead Log based 的主從同步技術(shù)，同時(shí)為了節(jié)省成本，我們采取RW（讀寫節(jié)點(diǎn)）/ RO (只讀節(jié)點(diǎn)) Share Storage 的架構(gòu)，同時(shí) RO 通過 Replay WAL 來更新其內(nèi)存中的數(shù)據(jù)。

Share Storage 架構(gòu)的問題：為了提高 RO 緩存效率，RO 節(jié)點(diǎn)會(huì)根據(jù)自己的 Workload 進(jìn)行內(nèi)存頁(yè)(Bw-tree Page)的換入換出，然而如果不小心處理這里的細(xì)節(jié)，很容易導(dǎo)致 RO 節(jié)點(diǎn)上讀到不一致的數(shù)據(jù)，例如 RW 隨意 Flush Bw-tree的 Dirty Page，導(dǎo)致 RO 讀到了未來版本 Page ，具體同步問題可以參考論文原文圖6例子。

未來版本 Page 的問題本質(zhì)是因?yàn)?RO Replay WAL 更新內(nèi)存緩存的進(jìn)度 始終落后于始終 RW 最新寫入的 WAL，如果 RW 隨意 Flush Bw-Tree Page，可能會(huì)導(dǎo)致 RO 看到的磁盤數(shù)據(jù)比內(nèi)存更新。

其他系統(tǒng)解決方案：比如 Amazon Aurora / 火山引擎 VeDB 通過讀取特定 LSN 的 Page 來解決這個(gè)問題（存儲(chǔ)層提供多版本讀取接口），Aliyun PolarDB 通過延遲 Page 的 Flush 流程，直到 RO 將相關(guān)的數(shù)據(jù)更新到內(nèi)存中。不過這兩種都對(duì)存儲(chǔ)接口有一些特殊需求，工程實(shí)現(xiàn)較為復(fù)雜。

BG3 的解決方案：BG3 提出了Unified WAL Stream，通過維護(hù)數(shù)據(jù)的多個(gè)版本，并在日志流中寫入RW節(jié)點(diǎn)的Flush/Update Bw-tree Page Mapping 的操作（稱作后臺(tái)系統(tǒng)日志），將前臺(tái)用戶 WAL 和后臺(tái)系統(tǒng)日志寫到統(tǒng)一的物理日志流里面，RO 節(jié)點(diǎn)按順序回放，總是先回放內(nèi)存的數(shù)據(jù)，再看到磁盤更新，避免上文提高 Future Page 的問題，與此同時(shí)，我們針對(duì)生產(chǎn)環(huán)境下高 I/O 吞吐做了針對(duì)性的并行優(yōu)化。

通過這套設(shè)計(jì)，我們僅僅依賴一套通用的 Append Only Blob 存儲(chǔ)就解決了 Share Storage 架構(gòu)的問題，工程實(shí)現(xiàn)更加簡(jiǎn)潔，具體更多細(xì)節(jié)可以參考原論文。

5.Optimized Column-based Engine

上一代行引擎的性能問題：在字節(jié)的社交，推薦，風(fēng)控等領(lǐng)域會(huì)存儲(chǔ)用戶之間關(guān)系和與這些關(guān)系相關(guān)的屬性，業(yè)務(wù)會(huì)對(duì)這些屬性進(jìn)行較復(fù)雜的分析與計(jì)算。

如提取點(diǎn)贊關(guān)系中某些屬性排名 TOPN 的用戶的分析計(jì)算。使用行索引對(duì)這類分析型計(jì)算的列讀取 SCAN 不友好，會(huì)顯著增加訪存開銷。

另一方面，行執(zhí)行引擎執(zhí)行框架中的虛函數(shù)調(diào)用開銷和解釋開銷較高，為了解決這一問題，我們?cè)?3.0 中引入了列執(zhí)行引擎，以提升執(zhí)行效率。

然而，在實(shí)踐過程中，由于在圖查詢中會(huì)經(jīng)常涉及到對(duì)某些點(diǎn)的鄰居邊的各種分析查詢，如社交分析場(chǎng)景中會(huì)涉及到對(duì)某個(gè)頂點(diǎn)的每一個(gè)二度鄰居進(jìn)行子查詢分析，但是子查詢的執(zhí)行需要將所有的外層執(zhí)行結(jié)果按行輸入到子查詢中，這會(huì)使得執(zhí)行模式回退到了行執(zhí)行。

并且，圖上會(huì)存在不同類型的實(shí)體，常常業(yè)務(wù)期望在一條查詢內(nèi)能對(duì)多種類型實(shí)體進(jìn)行混合計(jì)算，如風(fēng)控領(lǐng)域中會(huì)存在大量的點(diǎn)類型實(shí)體的聯(lián)合分析， 這也會(huì)使得執(zhí)行回退到行執(zhí)行。

因此，需要在這兩種場(chǎng)景下對(duì)計(jì)算引擎進(jìn)行針對(duì)性的優(yōu)化。

針對(duì)以上兩點(diǎn)，BG3 設(shè)計(jì)了一套基于 Column 優(yōu)化的存儲(chǔ)布局 & 執(zhí)行引擎，具體更多細(xì)節(jié)可以期待 ByteGraph 團(tuán)隊(duì)的后續(xù)頂會(huì)論文，或者加入 ByteGraph 團(tuán)隊(duì)一起參與起來！

實(shí)驗(yàn)驗(yàn)證

本文選取了字節(jié)三個(gè)典型真實(shí)workload：抖音follow，風(fēng)控，抖音推薦對(duì)比了前一代ByteGraph2.0，BG3和Neptune的性能，實(shí)驗(yàn)結(jié)果可以看到，BG3在所有workload上都取得了最優(yōu)的性能。

論文中還從讀寫帶寬放大，垃圾回收策略，Bw-Tree Forest 分裂等多方面細(xì)粒度的對(duì)比了 BG3 提出的各個(gè)策略和傳統(tǒng)解法的對(duì)比，歡迎到家到原文中查看細(xì)節(jié)。

字節(jié)圖團(tuán)隊(duì)簡(jiǎn)介

我們是字節(jié)跳動(dòng)基礎(chǔ)架構(gòu)部門的圖團(tuán)隊(duì)，負(fù)責(zé)圖數(shù)據(jù)庫(kù)、圖計(jì)算、圖神經(jīng)網(wǎng)絡(luò)等圖相關(guān)技術(shù)方向，服務(wù)公司內(nèi)各大業(yè)務(wù)，包括 TT、抖音、頭條等核心業(yè)務(wù)場(chǎng)景。團(tuán)隊(duì)工作已發(fā)表 VLDB/SIGMOD/TKDE 頂會(huì)論文 5 篇。

團(tuán)隊(duì)廣泛參與業(yè)界標(biāo)準(zhǔn)制定相關(guān)工作，是 LDBC Council、大數(shù)據(jù)技術(shù)標(biāo)準(zhǔn)推進(jìn)委員會(huì)、圖智能計(jì)算分會(huì)等組織會(huì)員。

[1] Zhu Pang, Qingda Lu, Shuo Chen, Rui Wang, Yikang Xu, and Jiesheng Wu. 2021. ArkDB: a key-value engine for scalable cloud storage services. In Proceedings of the 2021 International Conference on Management of Data. 2570–2583