DataFunTalk導(dǎo)讀：作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，圖數(shù)據(jù)的應(yīng)用場景無處不在，如社交、風(fēng)控、搜廣推、生物信息學(xué)中的蛋白質(zhì)分析等。如何高效地對海量的圖數(shù)據(jù)進(jìn)行存儲、查詢、計算及分析，是當(dāng)前業(yè)界熱門的方向。本文將介紹字節(jié)跳動自研的圖數(shù)據(jù)庫ByteGraph及其在字節(jié)內(nèi)部的應(yīng)用和挑戰(zhàn)。

本文將圍繞以下五點展開：

了解圖數(shù)據(jù)庫

適用場景介紹舉例

數(shù)據(jù)模型和查詢語言

ByteGraph架構(gòu)與實現(xiàn)

關(guān)鍵問題分析

01了解圖數(shù)據(jù)庫

目前，字節(jié)內(nèi)部有如下表三款自研的圖數(shù)據(jù)產(chǎn)品。

1. 對比圖數(shù)據(jù)庫與關(guān)系數(shù)據(jù)庫

圖模型的基本元素包括點、邊和屬性。舉例：張三的好友所在的公司有多少名員工？傳統(tǒng)關(guān)系型數(shù)據(jù)庫需要多表join，而圖作為半結(jié)構(gòu)化數(shù)據(jù)，在圖上進(jìn)行遍歷和屬性的過濾會更加高效。

2. 什么是圖數(shù)據(jù)庫？

近五年來，圖數(shù)據(jù)庫在領(lǐng)域內(nèi)熱度上升趨勢非常明顯，各個大廠與開源社區(qū)都推出了自己的圖數(shù)據(jù)庫。用戶規(guī)模比較大、有一定影響力的查詢語言包括Cypher、Apache開源項目的Gremlin等。從集群規(guī)模來看，過往有單機數(shù)據(jù)庫，現(xiàn)在大多圖數(shù)據(jù)庫都具備分布式能力，這就需要考慮數(shù)據(jù)的防丟失問題、主副本之間的一致性、多臺機器數(shù)據(jù)上的shard問題。

部分圖數(shù)據(jù)庫把圖數(shù)據(jù)庫與圖計算引擎二者合并在一起，目前字節(jié)內(nèi)部采用的暫時分離的兩套系統(tǒng)。

02適用場景介紹舉例

1. ByteGraph適用的業(yè)務(wù)數(shù)據(jù)模型

ByteGraph初始立項是在2018年，主要目的是對頭條的用戶行為及好友關(guān)系進(jìn)行存儲來替換Mysql；2019年6月承接對抖音用戶關(guān)系的數(shù)據(jù)存儲任務(wù)，接著在字節(jié)內(nèi)部各種微服務(wù)重承接了相關(guān)業(yè)務(wù)。

2. 已上線業(yè)務(wù)場景分類

目前有1.5萬臺物理機，服務(wù)于600+業(yè)務(wù)集群。

03數(shù)據(jù)模型和查詢語言

1. 有向?qū)傩詧D建模

目前來看，圖數(shù)據(jù)庫通常有兩大類，一種是屬性圖，另一種是RDF圖。屬性圖在節(jié)點和邊上有屬性表，從某種角度上講，它仍帶有關(guān)系數(shù)據(jù)庫的基本特性，類似表結(jié)構(gòu)的形式，實際是采用Key-Value形式來存儲的，如用戶A關(guān)注了用戶B，用戶C點贊了某個視頻等，則會把關(guān)注的時間、點贊時間、評論的內(nèi)容等以不同的有向邊存儲在屬性圖中，用圖來描述業(yè)務(wù)邏輯。

2. Gremlin查詢語言接口

選用Gremlin語言是考慮到之后方便對圖計算、圖數(shù)據(jù)庫二者進(jìn)行融合，本身是圖靈完備的圖遍歷語言，相較于Cypher等類SQL語言，對于善用Python的數(shù)據(jù)分析師更容易上手。

舉例：寫一條用戶A所有一跳好友中滿足粉絲數(shù)量大于100的子集。首先定位用戶A在圖中的點，其次求一跳查詢中的所有鄰居，判斷入度鄰居整體數(shù)量是否大于100，拉取滿足條件的所有用戶。

04ByteGraph架構(gòu)與實現(xiàn)

1. ByteGraph整體架構(gòu)

ByteGraph整體架構(gòu)分為查詢引擎層（Graph Query Engine，下文簡稱GQ）、存儲引擎層（Graph Storage Engine，下文簡稱GS）和磁盤存儲層三層，整體上計算和存儲分離，每層由多個進(jìn)程實例組成集群。

2. ByteGraph讀寫流程

拿“讀流程”舉例，請求獲取用戶A的一跳鄰居。首先一個查詢進(jìn)來后，從client端隨機挑選一個查詢層響應(yīng)，對應(yīng)到GQ2上，獲取對應(yīng)的數(shù)據(jù)存放的位置是哪一臺機器，接著把請求給到GS1，檢查數(shù)據(jù)是否在該層以及是否為最新數(shù)據(jù)，如果不在則去KV store把所需數(shù)據(jù)拉取至GS1 緩存中。

3. ByteGraph實現(xiàn)：GQ

GQ同MySQL的SQL層一樣，負(fù)責(zé)查詢的解析和處理，其中的“處理”可以分為下述三個步驟：

Parser階段：利用遞歸下降解析器將查詢語言解析為一個查詢語法樹。

生成查詢計劃：將Parser階段得到的查詢語法樹按照查詢優(yōu)化策略（RBO&CBO）轉(zhuǎn)換為執(zhí)行計劃。

執(zhí)行查詢計劃：理解GS數(shù)據(jù)分Partition的邏輯，找到相應(yīng)數(shù)據(jù)并下推部分算子，保證網(wǎng)絡(luò)開銷不會太大，最后合并查詢結(jié)果，完成查詢計劃。

RBO主要基于Gremlin開源實現(xiàn)中的自帶優(yōu)化規(guī)則、針對字節(jié)應(yīng)用中的算子下推、自定義的算子優(yōu)化（fusion）三大規(guī)則。CBO本質(zhì)上是對每個點的出入度做統(tǒng)計，把代價用方程量化表示。

對于不同支持場景使用不同策略，圖分區(qū)算法的選擇與workload強相關(guān)，圖分區(qū)算法能有效減少網(wǎng)絡(luò)通信次數(shù)。

Brute force哈希分區(qū)：即根據(jù)起點和邊的類型進(jìn)行一致性哈希分區(qū)，可以大部分查詢場景需求，尤其是一度查詢場景。

知識圖譜場景：點、邊類型極多，但每種類型邊數(shù)量相對較少，此時根據(jù)邊類型進(jìn)行哈希分區(qū)，將同種邊類型數(shù)據(jù)分布在一個分區(qū)內(nèi)。

社交場景：更容易出現(xiàn)大V，利用facebook于2016年提出的social hash算法，通過離線計算盡量將有關(guān)聯(lián)的數(shù)據(jù)放置在同一分片內(nèi)，降低延遲。

4. ByteGraph實現(xiàn)：GS

存儲結(jié)構(gòu)

單個Partition定義為一個起點+一種特定的邊類型扇出的一跳鄰居。在GS中，將一個Partition按照排序鍵（可顯式設(shè)置或系統(tǒng)默認(rèn)維護(hù)）組織成Btree。每棵Btree都有獨立的WAL序列，獨立維護(hù)自增logid。這種設(shè)計有利于支持GNN場景，做分布式采樣。

Edge Page、Meta Page分別是位于Btree中的葉子結(jié)點、非葉子結(jié)點（充當(dāng)index作用），分別用于存儲圖中的邊數(shù)據(jù)和指向子節(jié)點的Key。Meta page長度是固定的，但是一個meta page會放多少edge page是可配的，通常配置為2000一片。如上圖，Partition在磁盤中將每個page都存儲為一個獨立的鍵值對（下文簡稱KV対）。meta page的key是起點＋邊類型，edge page的key存在meta page中實現(xiàn)對特定edge page的查找。

單機內(nèi)存引擎整體采用hash map的結(jié)構(gòu)，partition和page按需加載到內(nèi)存中，根據(jù)LRU策略（Least Recent Used），swap到磁盤；某個page被修改后，WAL同步寫到磁盤，page會插入到dirty鏈表中，考慮當(dāng)前機器狀態(tài)，異步寫回。

日志管理：單個起點+邊類型組成一棵Btree，每個結(jié)點是一個KV對。

每棵Btree單一寫者，防止并發(fā)寫入導(dǎo)致不完整；每棵樹都有獨立的WAL日志流，且寫入請求處理流程中只寫入WAL，并修改內(nèi)存中數(shù)據(jù)，compaction時再將數(shù)據(jù)落盤，解決由于每個KV對可能由多條邊組成而導(dǎo)致的寫放大。即使內(nèi)存數(shù)據(jù)丟失，仍可通過更新后的logid在磁盤上進(jìn)行WAL的查詢并寫入。

緩存實現(xiàn)：根據(jù)不同場景及當(dāng)下cpu的開銷有不同策略。

圖原生緩存：相對于Memcached等直接緩存二進(jìn)制數(shù)據(jù)而言，能更好的理解圖的語義，并支持一度查詢中的部分計算下推功能。

高性能LRU Cache：支持緩存逐出，且逐出的頻率和觸發(fā)閾值可調(diào)；采用numa aware和cpu cacheline aware設(shè)計，提高性能；支持Intel AEP等新硬件。

Write-through cache：支持多種與底層存儲同步數(shù)據(jù)的模式，可以每次寫入或定時落盤；支持定期與底層存儲校驗數(shù)據(jù)，防止數(shù)據(jù)過舊；支持負(fù)緩存等常見優(yōu)化策略。

緩存與存儲分離：當(dāng)數(shù)據(jù)規(guī)模不變、請求流量增大的情況下，緩存與存儲分離的模式可以快速擴(kuò)容緩存以提高服務(wù)能力。

05關(guān)鍵問題分析

1. 索引

局部索引：給定一個起點和邊類型，對邊上的屬性構(gòu)建索引

特點：邊上元素皆可做索引項，能夠加速查詢，提高屬性過濾和排序性能；但會額外維護(hù)一份索引數(shù)據(jù)，與對應(yīng)的原數(shù)據(jù)使用同一條日志流，保證一致性。

全局索引：目前只支持點的屬性全局索引，即指定一個屬性值查詢出對應(yīng)的點。

數(shù)據(jù)存儲在不同機器上，索引數(shù)據(jù)的一致性使用分布式事務(wù)解決。

2. 熱點讀寫

熱點讀

場景舉例：某熱點視頻被頻繁刷新，查看其點贊數(shù)量。

應(yīng)用機制：GQ層采用多個bgdb并發(fā)處理同一熱點的讀請求，單節(jié)點緩存命中讀性能可達(dá)20萬以上；GS層采用copy on write（即先拷貝，再寫入并替換）保證讀寫、讀讀均可并發(fā)。

熱點寫

場景舉例：某熱點視頻短時間內(nèi)被瘋狂轉(zhuǎn)發(fā)、點贊。

問題溯源：單機cpu使用率被拉高，磁盤寫入iops有上限，當(dāng)客戶端寫入qps>磁盤iops時，就會發(fā)生請求排隊。

應(yīng)對機制：采用group commit機制，即將多個寫入請求組合至一個batch寫入KV，再批量返回，降低磁盤層iops的上限。

3. 輕重查詢資源分配

將輕重查詢的資源池分離，輕查詢走light線程池，負(fù)責(zé)數(shù)量多的小查詢；重查詢則走h(yuǎn)eavy線程池，負(fù)責(zé)數(shù)量少的重查詢。當(dāng)heavy線程池空閑時，輕查詢也可走。

4. 高可用

城域網(wǎng)雙機房，如國內(nèi)的兩個機房，延遲較低。follow一寫多讀策略，備機房把寫流量轉(zhuǎn)入主機房，只有主機房會把WAL更新到KV存儲上。

廣域網(wǎng)容災(zāi)部署，如新加坡和美國的兩臺機器，延遲較高。follow了mysql的思想，每次寫入在本地寫入成功后，會被轉(zhuǎn)化為binlog，再發(fā)送給其他單元；并通過hybrid logical clock保證各單元對于一條邊的操作順序一致性。

5. 離線在線數(shù)據(jù)流融合

導(dǎo)入存量數(shù)據(jù)、寫入在線數(shù)據(jù)，將二者集成在公司內(nèi)部數(shù)據(jù)平臺進(jìn)行離線數(shù)據(jù)分析，具體流程如圖。