本文根據張威老師在〖2023 Gdevops全球敏捷運維峰會-北京站〗現場演講內容整理而成。
講師介紹
張威，字節跳動圖數據庫團隊架構師，從事圖數據庫研發，主要Focus存儲層，設計並研發第三代分佈式圖存儲層。
分享概要
一、ByteGraph簡介
二、ByteGraph 2.0架構介紹
三、ByteGraph 2.0當前問題
四、ByteGraph 3.0解決方案
五、ByteGraph 3.0架構介紹
六、ByteGraph未來展望
七、Q&A
一、ByteGraph簡介
1.可以做什麼
1）字節有哪些業務數據呢？
- 用戶信息、用戶關系
- 內容（視頻、文章、廣告等）
- 用戶和內容聯系（點贊、評論、轉發、點擊）
用戶與用戶、用戶與內容之間存在關系，用圖能夠清晰表達這些關系以及點贊、關註等場景。
2）使用圖表達業務場景的優勢
- 建模直觀簡潔
- 挖掘數據關聯
3）ByteGraph特點
- 高吞吐
- 低延遲
- 最終一致性
- 兼容Gremlin
產品ByteGraph自2018年開始自主研發，截至目前仍持續更新換代。前一代產品的相關論文已經發表在VLDB-2022，下一代的論文也正在路上，歡迎大傢關註。
2.查詢接口
查詢接口，即用戶怎麼使用數據庫。
1）Gremlin簡介
和SQL語言不同，使用數據庫時需要使用一種名為Gremlin的查詢語言，這是一種圖靈完備的圖遍歷語言。
相較Cypher等查詢語言，Gremlin的功能更全面，上手較為容易，使用更加廣泛。主流雲廠商圖數據庫都提供了Gremlin支持。
2）數據模型
- 有向屬性圖
- 點和邊上都可以攜帶多屬性，支持動態加減屬性列（體驗與MySQL的DDL語句較為類似）
舉個例子，寫一條用戶A所有一跳好友中滿足粉絲數量大於100的子集。
g.V(vertex(A.id, A.type)).out('好友').where(in('粉絲關註').count().is(gt(100))).toList()首先定位用戶A在圖中的點，其次求一跳查詢中的所有鄰居，判斷入度鄰居數量是否大於100，拉取滿足條件的所有用戶。在這個語句中，out是找到用戶好友；where是一個條件查詢，查詢該用戶的所有好友；in是粉絲數。這句話整體較為易懂。
2018年的業務發展比較迅猛，同時大傢偏向接受簡單的事務，Gremlin語言順應這種需求，所以在業務應用的規模逐漸變大。
3.業務介紹
- 抖音的用戶關系（點贊、粉絲等）
- 抖音推薦（好友在看、好友贊過等場景）
- 知識圖譜（搜索百科、教育、電商團隊進行實體推薦）
- 內部業務（微服務標準鏈路開發等）
除此之外，抖音的支付場景也比較多，所以也具備一些風控業務。比如產生一筆轉賬記錄，我們需要確認這位用戶是否套現，所以要根據該次請求去檢測環路，這個過程也應用了圖數據庫。
目前我們支持超過1000個業務集群，服務器規模已經達到上萬臺。
二、ByteGraph 2.0架構介紹
1.分層架構
當前架構從2018年左右開始搭建，如下圖所示分為三層。第一層是查詢層 GQ（Graph Query Engine），第二層是存儲引擎層GS（Graph Storage Engine），底層則是依賴分佈式KV。受到TiDB影響，這種架構在當時非常流行。
這套架構分為三層，這樣做的好處就是每一層都可以獨立擴展。
如果查詢語句比較復雜，則擴展最上面的查詢層；如果內存不足，則擴展內存層；如果存儲資源增多，則擴展最下層的分佈式KV。這個架構設計具備雲時代特征，彈性很好，但也存在層次較多等問題（後文會提到）。
2.模塊劃分
在查詢引擎方面，我們為用戶提供Gremlin語句。加入Gremlin後，整體與傳統數據庫類似，首先通過Parser轉為AST，然後生成物理計劃，最後通過執行器去執行。
由於ByteGraph是一個分佈式數據庫，所以分片策略在Graph Partition模塊，事務則與分佈式事務類似。
存儲引擎方面，存一張圖不外乎是存點或邊，所以將其抽象為兩種，一種是純點，一種是純邊。
3.執行引擎
執行流程示例：
g.V().has('id', 1).has('type', person).out('knows').has('age', gt(18)).values('name')整體語句的意思是找到用戶認識的超過十八歲的人，並得到他們的名字。這是一個典型的圖查詢。
4.存儲引擎
存儲引擎包括Vertex Storage（點存儲）和Edge Storage（邊存儲）。
點比較簡單，即使包括很多屬性，數據量也不大，所以將頂點和類型等屬性存儲在KV中。
邊則比較復雜，比如抖音大V這種具有幾百萬粉絲的用戶，將他幾百萬個粉絲的邊及其屬性存到KV顯然是不太可能的，會導致寫入放大或讀取放大，這種情況對KV很不友好。
所以將邊按鄰接表聚合成為Edge Stroage，再把Edge Stroage組織為Btree，有自己獨立的WAL，多個Edge stroage形成一個森林，這樣訪問不同的鄰接表的時候，無需做並發管理。
其它的部分和傳統的BTree存儲引擎一樣（例如InnoDB），共享全局的LRU負責緩存淘汰和Dirty List 負責刷臟。
三、ByteGraph 2.0當前問題
1.成本
依賴分佈式KV部署的帶來的成本開銷。
1）冗餘副本
目前都是3機房3/5副本。如果使用支持EC的池化存儲系統作為存儲底座，可以將副本數量降低為3機房2副本，節約30%-60%成本。
2）LSM Tree KV 存儲引擎本身的問題 （寫放大/Compaction造成的CPU消耗）
- 多層緩存冗餘：LSMT（BlockCache）和GS（BufferPool)）內部都有大容量緩存模塊，緩存了同一份熱數據，統一緩存資源能有較高的系統利用率和系統性能；
- 內存/CPU預留：基於LSM Tree帶來的BlockCache以及Share Nothing架構帶來的3份Compaction消耗導致存儲機型也需要預留CPU/Memory，導致無法使用高密度存儲機型，這進一步帶來了整體TCO放大；
- 磁盤預留寫放大高（40倍）：基於LSM Tree帶來寫放大開銷，在某些場景寫能到幾十倍，需要預留更多的磁盤資源，導致磁盤利用率低。
2.性能
- 分層過多：從上到下來看，Graph 整體為計算層 -> 內存層 -> KV-Proxy 層 -> KV-Server 層，數據寫入會穿透四層，cache miss 時數據查詢也會穿透四層，延遲和 CPU 開銷都難以優化到極致，業務要求更低的延遲；
- 多跳性能難以做到極致：隨著各種社交推薦、風控業務的發展，兩條以上的鄰居的召回需求增多，例如好友推薦（查詢好友的好友）、風險圖判斷等，當前計算和存儲解耦的設計導致在多跳查找中會有大量的RPC開銷，難以保障性能；
- Per Vertex級別的WAL：細粒度的分片導致分佈式事務無法做1PC優化，用戶需要優化分佈式事務的性能。
單跳/多跳查詢是ByteGraph的優勢場景，其Workload對於Scan One Hop能力尤其看重（也是線上典型場景）。ByteGraph的數據模型為屬性圖模型，邊上會有若幹屬性，最基礎的Get One Hop算子的物理計劃會 會拆解為讀取KV 若幹Page，然後掃描Page內部的若幹條邊。
典型的Scan請求經常是隻需要根據一列屬性過濾然後返回某幾列屬性，不需要掃描全部的屬性列，但是當前Page內是按行存儲的，即使隻需要部分列，也需要掃描全部的數據，內存訪問需要在page內隨機跳轉，導致內存延遲高，內存帶寬高，難以優化性能。
3.功能
- 延遲可控的主從同步：當前我們的主從機房的數據一致性為最終一致（通過轉發流量），我們需要有一個log based主從同步，為用戶提供延遲可控的主從一致性，甚至強一致性讀取（滿足一些業務寫後讀的需求）。
四、ByteGraph 3.0解決方案
1.成本
1）利用EC技術降低副本數量
延續Graph 2.0的 Shared storage設計，繼續擁抱彈性，替換KV -> DFS 池化存儲，利用低成本ByteStore 3AZ 兩副本技術（利用EC）取得成本收益，利用高密度存儲機型，進一步降低TCO。
LSMT -> BwTree 合並2.0 GS層Btree引擎/分佈式KV的LSMTree引擎，自研基於DFS的BwTree存儲引擎，減少寫放大，從幾十倍可以降低為 2~3倍，減少Compaction開銷。
基於Share Storage 架構，避免3份Compaction開銷，降低磁盤層開銷，彈性擴縮容。
2）利用DFS層簡單的Append Only Write API, 減少磁盤層預留的CPU和內存，使用高密度存儲機型，進一步降低TCO
2.性能
- 合並進程：合並查詢引擎和存儲引擎為一個進程，減少穿透層數，減少多跳查詢RPC開銷
- 減少分片數量：增大分片粒度，主推單分片一主多從架構，非必要不分片（利用Bare-Metal大內存機器來滿足性能），如果必須分片，采取Hash 分區的做法進行負載均衡，經過上述調整，事務的1PC比例大幅度增加。註意：在圖數據庫多跳查詢的場景，一定是分片越少（意味著網絡通信的大大降低），性能越高。
- Btree Page內列存，增強cache locality
- 自研新一代Pipeline執行引擎，減少通信拷貝開銷，感知Numa調度
3.功能
- 單分片Tablet級別WAL主從同步，減少2.0架構Vertex 粒度WAL帶來的，寫入QPS和寫流量轉發帶來的overhead
五、ByteGraph 3.0架構介紹
1.總體架構
3.0架構將查詢引擎和存儲引擎合並，類似於MySQL由SQL層和存儲引擎層構成。同時為了順應潮流，做了專門針對圖形的查詢語言GQL。
整體架構類似Amazon/PolarDB的shared storage架構，shared storage層是基於 byteStore 存儲構建，雖然架構相同，但是存儲引擎實現細節完全不同，BG3.0是基於DFS自研的BwTree，有更高的性能和更低的寫入放大。
數據分為若幹Tablet（一般情況默認就一個Tablet，非必要不分片），每個Tablet中存放一部分圖的hash分片，每個Tablet有RW和RO，通過共享的Journal 同步數據，數據持久化多副本交給Append Only Blob層解決，可用性通過上層 RW 和 RO 快速切換解決。
註意：這套架構裡面沒有Proxy，我們將Proxy內置在Tablet內部，第一是為了減少部署Proxy的開銷，第二我們可以一主多從模式下減少穿透層帶來的開銷，提供更高的性能。
2.並行執行引擎
- 新版的pipeline執行引擎將多個step合並成一個pipeline，減少基於channel的通信開銷；
- 單個Pipeline內部可以提供數據並行，啟動多個pipeline task進行運算，充分利用多核能力；
- 開發numa的piple line task調度器，增強數據局部性。
3.存儲引擎模塊劃分
存儲引擎模塊分為查詢引擎層和存儲引擎層（重點關註），整體存儲引擎是一個基於共享存儲的BwTree存儲引擎，支持主從同步。
- Journal Engine負責日志管理
- Mem Engine 整體功能和GS2類似，負責內存Btree 結構
- Page Engine負責磁盤Btree結構
4.存儲引擎流程介紹
Mem Engine大部分和2.0一樣，圖分為點和邊，邊按鄰接表聚合成為Edge Stroage，其它的部分和傳統的btree存儲引擎一樣，共享全局的LRU負責緩存淘汰和dirty list 負責刷臟。
不同點：
- WAL: 每個btree都有自己的WAL，現在多個Btree共享一條WAL，聚合寫入，增大1PC事務比例
- 點也會按hash規則，也存成若幹個btree，減少元數據開銷
- Flush帶寬優化：另外為了減少Flush的流量，我們每個Page上還會掛一個Delta，Flush的過程中對於Dirty Page我們會Base Delta輪轉下刷
- Page內列式存儲：為了提升GetOneHop Scan能力，我們會把點或者邊的上的屬性按列聚合存儲，增強內存訪問的locality，加強scan能力
Page Engine 整體分為 Page Index 和 Page Data 模塊，接受mem engine 的 page checkpoint流量。
- Page Index 作為索引，存儲 Page ID 到 Page 實際地址，支持增量落盤，默認情況下全內存緩存，讀取索引做到無IO，提供高效查詢。
- Page Data 存儲實際的Page Base/Delta數據，按更新頻率不同冷熱分離，分別寫入Page Base Stream / Page Delta Stream，各自獨立GC，目標是減少寫放大。
- 整體寫入流程：Memory Engine 的 Btree Page 在做Flush Dirty (Checkpoint)的時候，寫入Page Engine，進入到Page Engine內部後，根據是Base/Delta寫入不同的Stream的Active Blob，寫入成功後，得到BlobID和 Offset，然後更新Page Index 和對應的Blob的統計信息，Page Index/統計信息通過WAL保證持久化，整體完成後寫入返回
- 整體讀取流程：Memory Engine Cache Miss，讀取Page Engine，先查詢Page Index，得到該Page 對應的Base/Delta的地址(BlobID, Offset)，然後直接發起IO讀取對應Blob，保證至多兩個IO
- 主從復制流程：RW節點和RO節點基於共享存儲做主從同步，共享Page Index 和 Page Data，RO節點和RW節點的會有一定的延遲。（註意：Page Index WAL 和 Memory Engine WAL 共享一路Journal做RO同步，通過header來區分，方便統一按一條日志回放的邏輯，方便處理）
先進的reclaim策略：
- Base/Delta分離：Delta 更新比較快，Base更新慢，GC Delta 的時候沒必要搬運Base，因為Base 大概率是冷的沒有更新，分不同的Stream獨立GC可以減少整體寫放大
- 基於統計信息的Reclaim：我們為每個Blob維護BlobStatistic（包括Usage，Last Update Time，隨著寫入更新，定期checkpoint ）用來指導空間回收。Pick Blob時同時參考更新頻率和Usage兩個指標，進行加權，例如可以選擇Usage最低的Blob進行GC，或者選擇Usage 相對低，但是更新頻率低的Blob 進行GC (Min Decline GC)。
六、ByteGraph未來展望
1.業務收益
- 存儲成本降低30%-50%；
- 在單分片場景下，多跳召回場景上可提供數倍於原有系統的性能。
2.未來工作
- 補齊3.0功能，持續上量，持續優化內部業務&火山引擎的服務性能和使用體驗。
- 作為統一存儲底座，向上支撐圖數據庫查詢引擎，全圖計算引擎，圖訓練DataLoader等。
- 打造Single-Engine生態：提供一體化圖數據服務。隨著圖數據庫，GNN，圖計算越來越廣泛的使用，用戶對於“圖數據的統一存儲，處理，流動”有了更高的要求，ByteGraph 3.0 存儲層希望提供一套融合多種場景的存儲解決方案，通過統一的存儲格式，幫助用戶打通圖數據庫、GNN、圖計算系統以及Spark/Hadoop生態，真正做到一站式處理。
Q&A
Q1：我想問一下關於Bw-Tree的實現，這是參照微軟2013年那篇論文實現的嗎？
A1：不是微軟的Bw-Tree，大傢談到Bw-Tree一般會想到抓人眼球的Delta node。但我們的Bw-Tree聚焦點並不在此，主要借鑒其中的三項內容：第一個是內存設計；第二個是磁盤設備，微軟有一篇介紹配置如何存到磁盤上的論文，我們借鑒了磁盤設計並進行優化；第三個部分是內存中Delta的實現細節上可能不完全一樣。
Q2：演講中介紹到磁盤預留寫放大高有40倍左右，目前優化效果如何？主要受益於哪個措施？
A2：寫放大能做到兩三倍。比如Compaction是寫放大的原因，因為每一層都是上一層的10倍，如果有6層，那一次寫入推到最後一層就是60倍的情況。這是因為Compaction除了回收垃圾，還會做排序。
Q3：ByteGraph2.0到3.0的計劃中提到多跳場景下從 RPC調用，盡可能編程進程調用。我的理解是單機大類型的場景下，數據都在同一臺機器，成本確實會減少。但是如果機器很多，還是會產生開銷，請問是否進行將親和性比較強的數據放到同一臺機器上此類優化措施？
A3：這個問題很好，我們做圖數據庫主要是優化多跳的性能，否則就和SQL數據庫沒有區別了。你的問題在於親和性，比如將用戶和用戶的粉絲存儲在一起，這很好。但更常見的情況是粉絲群體高達幾百萬，不太可能都放在一臺機器上，還會可能產生流量不均勻等問題。
我們的優化手段秉持著大力出奇跡的理念，換大內存，將BTree的配置從行切成列，由此同一條邊的開銷占用內存會降低。總之，比起數據分佈，我們更希望使用工程優化手段。