字節(jié)跳動(dòng)自研萬(wàn)億級(jí)圖數(shù)據(jù)庫(kù)ByteGraph及其應(yīng)用與挑戰(zhàn)

本文約3000字，建議閱讀6分鐘
本文將介紹字節(jié)跳動(dòng)自研的圖數(shù)據(jù)庫(kù)ByteGraph及其在字節(jié)內(nèi)部的應(yīng)用和挑戰(zhàn)。

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

• 了解圖數(shù)據(jù)庫(kù)
• 適用場(chǎng)景介紹舉例
• 數(shù)據(jù)模型和查詢語(yǔ)言
• ByteGraph架構(gòu)與實(shí)現(xiàn)
• 關(guān)鍵問(wèn)題分析

• Parser階段：利用遞歸下降解析器將查詢語(yǔ)言解析為一個(gè)查詢語(yǔ)法樹(shù)。
• 生成查詢計(jì)劃：將Parser階段得到的查詢語(yǔ)法樹(shù)按照查詢優(yōu)化策略（RBO&CBO）轉(zhuǎn)換為執(zhí)行計(jì)劃。
• 執(zhí)行查詢計(jì)劃：理解GS數(shù)據(jù)分Partition的邏輯，找到相應(yīng)數(shù)據(jù)并下推部分算子，保證網(wǎng)絡(luò)開(kāi)銷不會(huì)太大，最后合并查詢結(jié)果，完成查詢計(jì)劃。

• Brute force哈希分區(qū)：即根據(jù)起點(diǎn)和邊的類型進(jìn)行一致性哈希分區(qū)，可以大部分查詢場(chǎng)景需求，尤其是一度查詢場(chǎng)景。
• 知識(shí)圖譜場(chǎng)景：點(diǎn)、邊類型極多，但每種類型邊數(shù)量相對(duì)較少，此時(shí)根據(jù)邊類型進(jìn)行哈希分區(qū)，將同種邊類型數(shù)據(jù)分布在一個(gè)分區(qū)內(nèi)。
• 社交場(chǎng)景：更容易出現(xiàn)大V，利用facebook于2016年提出的social hash算法，通過(guò)離線計(jì)算盡量將有關(guān)聯(lián)的數(shù)據(jù)放置在同一分片內(nèi)，降低延遲。

• 存儲(chǔ)結(jié)構(gòu)

• 日志管理：單個(gè)起點(diǎn)+邊類型組成一棵Btree，每個(gè)結(jié)點(diǎn)是一個(gè)KV對(duì)。

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

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

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

• 熱點(diǎn)讀

• 熱點(diǎn)寫(xiě)

• 城域網(wǎng)雙機(jī)房，如國(guó)內(nèi)的兩個(gè)機(jī)房，延遲較低。follow一寫(xiě)多讀策略，備機(jī)房把寫(xiě)流量轉(zhuǎn)入主機(jī)房，只有主機(jī)房會(huì)把WAL更新到KV存儲(chǔ)上。
• 廣域網(wǎng)容災(zāi)部署，如新加坡和美國(guó)的兩臺(tái)機(jī)器，延遲較高。follow了mysql的思想，每次寫(xiě)入在本地寫(xiě)入成功后，會(huì)被轉(zhuǎn)化為binlog，再發(fā)送給其他單元；并通過(guò)hybrid logical clock保證各單元對(duì)于一條邊的操作順序一致性。