論文鏈接：

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

ps：可復制到瀏覽器打開

SIGMOD （ACM Special Interest Group on Management Of Data） 是數據庫三大國際頂級學術會議之一，也是數據庫領域影響力最大的頂級會議，中國計算機學會（CCF）推薦的A類國際學術會議，今年的 SIGMOD 于 6 月 9 日到 14 日在南美洲的智利舉行。

每屆會議集中展示了當前數據庫研究的前沿方向、工業界的最新技術和各國的研發水平，吸引了全球頂級研究機構投稿。

其中來自字節跳動基礎架構圖團隊的 《BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance》論文被 SIGMOD2024 收錄為 Industry Track 論文。

研究背景與動機

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

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

綜合分析表明，ByteGraph 系統所承擔的主要工作負載以讀操作為核心，其發生的頻次顯著高于寫操作。

尤其值得關注的是，圖結構中最基本的讀取操作是對鄰接表的掃描，因此，對讀取性能的持續優化，尤其是鄰接表掃描的性能，顯得至關重要。

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

下面我們將先從 ByteGraph 前一代 2.0 架構開始，介紹當前遇到的問題。ByteGraph 2.0 系統架構圖1所示：

ByteGraph 2.0 架構整體劃分為三個層次：BGE 層負責處理圖查詢請求，BGS 層負責緩存圖的結構和屬性數據，而分布式 KV 層則確保數據的持久化，三層可以各自獨立擴展。

為了實現讀寫操作的均衡，ByteGraph 2.0 采用了 Edge Btree 來存儲鄰接表。通過在 KV 模型上構建 Btree（每個 Btree 的頁面作為一個KV單元存儲），ByteGraph 滿足了業務的基本需求。

更深入的 2.0 架構細節可以在 ByteGraph 團隊 VLDB 2022 的論文《ByteGraph: A High-Performance Distributed Graph Database in ByteDance》中找到。

然而隨著業務規模的擴大，以及基于圖的實時圖分析技術在社交網絡應用中落地，我們發現上一代 ByteGraph 架構在字節業務中遇到以下幾大痛點：

1. 基于 LSM-based 的分布式 KV 構建系統，在字節圖數據庫的 Workload 下面存在一些劣勢，主要體現為以下幾個點

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

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

解決方案

為了解決上述四大痛點，我們開發了 ByteGraph 的新一代架構，命名為 ByteGraph 3.0（BG3）。

BG3 旨在從查詢引擎到存儲引擎全面更新，在查詢引擎引入向量化計算、MPP、AQE 等技術，同時構建基于共享存儲的圖原生 Bw-tree 存儲引擎，來實現性能、成本的大幅優化，本文將重點介紹圖存儲引擎部分。BG3 整體架構如下所示：

如圖2所示，BG3 基于 Append-only 的共享云存儲系統構建，在此之上我們構建了一個 Cloud Native Bw-tree 單機引擎，BG3 新架構的存儲引擎主要有以下幾大創新點：

1.Space Optimized Bw-Tree Forest

如圖 3 所示，我們以抖音用戶點贊場景為例，用戶每點贊一條視頻，都會向 ByteGraph 插入一條用戶到視頻的邊。

假設A用戶是一個很活躍的用戶，每天都會點贊大量的視頻，而用戶B和C相比之下每天只點贊少量的視頻。

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

為了減少 Bw-tree 上的沖突，最理想的情況我們為每一個用戶的點贊邊被寫到一個獨立的 Bw-tree 中，但我們發現圖上存在明顯的 Power-Law 現象，80%用戶點贊頻率有限（可能只有幾十個贊），因為每個 Bw-tree 都有一些元數據的開銷，如果每個用戶都單獨分配一顆Bw-tree會導致元數據的內存和磁盤開銷過大。

因此我們提出了“Space Optimized Bw-tree Forest”，所有的用戶點贊邊會被首先寫入一顆統一的 Bw-tree(INIT)中，當一個用戶的點贊邊數超過某個閾值，這個用戶的數據會被分裂到單獨的一個Bw-tree中（如圖3右邊的用戶A）。

2.Read Optimized Bw-Tree

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

字節內大量業務對 ByteGraph 的 Workload 都是寫少讀多，原始 Bw-tree 的寫入特性對讀性能有很大的影響，并且在存算分離的場景下會放大該問題，一次上層的 Cache Miss ，會造成大量下層的 IOPS 放大，多個Delta 導致的多次 IO 會導致讀取延遲不穩定，對用戶影響較大，并且在共享存儲架構下這個問題會更加明顯。

因此，BG3 提出了“Read Optimized Bw-tree”，如圖 4 右邊所示，我們在每次寫入 Bw-tree 的時候，會把之前還未合并到Base page 的 Delta一并寫入，這樣設計的好處是當我們需要讀取 Delta 獲得 Page 最新的鏡像時，我們可以只讀一次 Delta 數據。

雖然這種方法和原始 Bw-tree 對比增加了額外的寫入開銷，但我們在字節真實的 Workload 測試后發現（論文中也有對應的評測），這部分寫入開銷可控的前提下大幅增加讀性能。

3.Workload-Aware Space Reclamation

為了持久化考慮，Bw-tree 的 Base page 和 Delta page 數據會被統一寫入Append-only的云存儲中。

傳統的 Bw-tree 的空間回收會維護一個 Fifo 的隊列，新數據插入隊列頭部，每次空間回收都會從隊列的尾部開始掃描數據，把隊列尾仍然有效的數據重新寫入隊列頭，以達到回收已失效數據空間的目的。

傳統 Bw-tree 的空間回收策略沒有考慮不同數據段的空間回收率，后臺的數據搬運產生了大量的寫放大。

從空間回收的角度看，Base page 和 Delta page 的寫入 Pattern 不同。我們借鑒了 Arkdb[1] 的設計，把 Base/Delta 分別寫入不同 Stream，并把 Stream 內數據劃分成相等大小 Extent的設計。與此同時，我們發現：

A. 以視頻點贊場景為例，圖數據的冪律分布特性使得視頻的熱度(喜歡，收藏，瀏覽)呈現出冷熱差別。同一個視頻，視頻剛發布時的點贊數的增長率會遠高于發布一個月后視頻的點贊數增長率。點贊數增長程度的不同傳導到下層存儲體現為不同視頻對應的 Bw-tree 上各個 Page 修改的頻率相差甚遠。這進一步造成了底層 Stream 中的 Extent 的空洞的變化率的不同。

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

基于上面兩點觀察，我們提出了“Workload aware space reclamation”。每一塊 Extent 我們會有一個Extent usage tracking模塊，我們會記錄

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

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

與此同時，當我們發現一個 Extent 設置了 TTL，在回收過程中我們會跳過這些 Extent，并在 TTL 到期后整體刪除數據，這樣可以避免因為垃圾回收產生的沒必要的搬動。

4.I/O Efficient Synchronization Mechanism

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

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

未來版本 Page 的問題本質是因為 RO Replay WAL 更新內存緩存的進度 始終落后于始終 RW 最新寫入的 WAL，如果 RW 隨意 Flush Bw-Tree Page，可能會導致 RO 看到的磁盤數據比內存更新。

其他系統解決方案：比如 Amazon Aurora / 火山引擎 VeDB 通過讀取特定 LSN 的 Page 來解決這個問題（存儲層提供多版本讀取接口），Aliyun PolarDB 通過延遲 Page 的 Flush 流程，直到 RO 將相關的數據更新到內存中。不過這兩種都對存儲接口有一些特殊需求，工程實現較為復雜。

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

通過這套設計，我們僅僅依賴一套通用的 Append Only Blob 存儲就解決了 Share Storage 架構的問題，工程實現更加簡潔，具體更多細節可以參考原論文。

5.Optimized Column-based Engine

上一代行引擎的性能問題：在字節的社交，推薦，風控等領域會存儲用戶之間關系和與這些關系相關的屬性，業務會對這些屬性進行較復雜的分析與計算。

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

另一方面，行執行引擎執行框架中的虛函數調用開銷和解釋開銷較高，為了解決這一問題，我們在 3.0 中引入了列執行引擎，以提升執行效率。

然而，在實踐過程中，由于在圖查詢中會經常涉及到對某些點的鄰居邊的各種分析查詢，如社交分析場景中會涉及到對某個頂點的每一個二度鄰居進行子查詢分析，但是子查詢的執行需要將所有的外層執行結果按行輸入到子查詢中，這會使得執行模式回退到了行執行。

并且，圖上會存在不同類型的實體，常常業務期望在一條查詢內能對多種類型實體進行混合計算，如風控領域中會存在大量的點類型實體的聯合分析， 這也會使得執行回退到行執行。

因此，需要在這兩種場景下對計算引擎進行針對性的優化。

針對以上兩點，BG3 設計了一套基于 Column 優化的存儲布局 & 執行引擎，具體更多細節可以期待 ByteGraph 團隊的后續頂會論文，或者加入 ByteGraph 團隊一起參與起來！

實驗驗證

本文選取了字節三個典型真實workload：抖音follow，風控，抖音推薦對比了前一代ByteGraph2.0，BG3和Neptune的性能，實驗結果可以看到，BG3在所有workload上都取得了最優的性能。

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

字節圖團隊簡介

我們是字節跳動基礎架構部門的圖團隊，負責圖數據庫、圖計算、圖神經網絡等圖相關技術方向，服務公司內各大業務，包括 TT、抖音、頭條等核心業務場景。團隊工作已發表 VLDB/SIGMOD/TKDE 頂會論文 5 篇。

團隊廣泛參與業界標準制定相關工作，是 LDBC Council、大數據技術標準推進委員會、圖智能計算分會等組織會員。

[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