陳巨集智:位元組跳動自研萬億級圖資料庫ByteGraph及其應用與挑戰

来源:https://www.cnblogs.com/datafuntalk/archive/2022/06/13/16370344.html
-Advertisement-
Play Games

導讀: 作為一種基礎的數據結構,圖數據的應用場景無處不在,如社交、風控、搜廣推、生物信息學中的蛋白質分析等。如何高效地對海量的圖數據進行存儲、查詢、計算及分析,是當前業界熱門的方向。本文將介紹位元組跳動自研的圖資料庫ByteGraph及其在位元組內部的應用和挑戰。 本文將圍繞以下五點展開: 瞭解圖資料庫 ...


file


導讀: 作為一種基礎的數據結構,圖數據的應用場景無處不在,如社交、風控、搜廣推、生物信息學中的蛋白質分析等。如何高效地對海量的圖數據進行存儲、查詢、計算及分析,是當前業界熱門的方向。本文將介紹位元組跳動自研的圖資料庫ByteGraph及其在位元組內部的應用和挑戰。

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

  • 瞭解圖資料庫
  • 適用場景介紹舉例
  • 數據模型和查詢語言
  • ByteGraph架構與實現
  • 關鍵問題分析
    --

01 瞭解圖資料庫

目前,位元組內部有如下表三款自研的圖數據產品。

file

1. 對比圖資料庫與關係資料庫

圖模型的基本元素包括點、邊和屬性。舉例:張三的好友所在的公司有多少名員工?傳統關係型資料庫需要多表join,而圖作為半結構化數據,在圖上進行遍歷和屬性的過濾會更加高效。

2. 什麼是圖資料庫?

近五年來,圖資料庫在領域內熱度上升趨勢非常明顯,各個大廠與開源社區都推出了自己的圖資料庫。用戶規模比較大、有一定影響力的查詢語言包括Cypher、Apache開源項目的Gremlin等。從集群規模來看,過往有單機資料庫,現在大多圖資料庫都具備分散式能力,這就需要考慮數據的防丟失問題、主副本之間的一致性、多台機器數據上的shard問題。

部分圖資料庫把圖資料庫與圖計算引擎二者合併在一起,目前位元組內部採用的暫時分離的兩套系統。

--

02 適用場景介紹舉例

1. ByteGraph適用的業務數據模型

ByteGraph初始立項是在2018年,主要目的是對頭條的用戶行為及好友關係進行存儲來替換Mysql;2019年6月承接對抖音用戶關係的數據存儲任務,接著在位元組內部各種微服務重承接了相關業務。

file

2. 已上線業務場景分類

目前有1.5萬台物理機,服務於600+業務集群。

file

--

03 數據模型和查詢語言

1. 有向屬性圖建模

目前來看,圖資料庫通常有兩大類,一種是屬性圖,另一種是RDF圖。屬性圖在節點和邊上有屬性表,從某種角度上講,它仍帶有關係資料庫的基本特性,類似表結構的形式,實際是採用Key-Value形式來存儲的,如用戶A關註了用戶B,用戶C點贊了某個視頻等,則會把關註的時間、點贊時間、評論的內容等以不同的有向邊存儲在屬性圖中,用圖來描述業務邏輯。

file

2. Gremlin查詢語言介面

選用Gremlin語言是考慮到之後方便對圖計算、圖資料庫二者進行融合,本身是圖靈完備的圖遍歷語言,相較於Cypher等類SQL語言,對於善用Python的數據分析師更容易上手。

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

file

--

04 ByteGraph架構與實現

1. ByteGraph整體架構

ByteGraph整體架構分為查詢引擎層(Graph Query Engine,下文簡稱GQ)、存儲引擎層(Graph Storage Engine,下文簡稱GS)和磁碟存儲層三層,整體上計算和存儲分離,每層由多個進程實例組成集群。

file

2. ByteGraph讀寫流程

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

file

3. ByteGraph實現:GQ

GQ同MySQL的SQL層一樣,負責查詢的解析和處理,其中的“處理”可以分為下述三個步驟:

  • Parser階段:利用遞歸下降解析器將查詢語言解析為一個查詢語法樹。
  • 生成查詢計劃:將Parser階段得到的查詢語法樹按照查詢優化策略(RBO&CBO)轉換為執行計劃。
  • 執行查詢計劃:理解GS數據分Partition的邏輯,找到相應數據並下推部分運算元,保證網路開銷不會太大,最後合併查詢結果,完成查詢計劃。

RBO主要基於Gremlin開源實現中的自帶優化規則、針對位元組應用中的運算元下推、自定義的運算元優化(fusion)三大規則。CBO本質上是對每個點的出入度做統計,把代價用方程量化表示。

file

對於不同支持場景使用不同策略,圖分區演算法的選擇與workload強相關,圖分區演算法能有效減少網路通信次數。

  • Brute force哈希分區:即根據起點和邊的類型進行一致性哈希分區,可以大部分查詢場景需求,尤其是一度查詢場景。
  • 知識圖譜場景:點、邊類型極多,但每種類型邊數量相對較少,此時根據邊類型進行哈希分區,將同種邊類型數據分佈在一個分區內。
  • 社交場景:更容易出現大V,利用facebook於2016年提出的social hash演算法,通過離線計算儘量將有關聯的數據放置在同一分片內,降低延遲。

4. ByteGraph實現:GS

file

  • 存儲結構

單個Partition定義為一個起點+一種特定的邊類型扇出的一跳鄰居。在GS中,將一個Partition按照排序鍵(可顯式設置或系統預設維護)組織成Btree。每棵Btree都有獨立的WAL序列,獨立維護自增logid。這種設計有利於支持GNN場景,做分散式採樣。

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

單機記憶體引擎整體採用hash map的結構,partition和page按需載入到記憶體中,根據LRU策略(Least Recent Used),swap到磁碟;某個page被修改後,WAL同步寫到磁碟,page會插入到dirty鏈表中,考慮當前機器狀態,非同步寫回。

file

  • 日誌管理:單個起點+邊類型組成一棵Btree,每個結點是一個KV對。

每棵Btree單一寫者,防止併發寫入導致不完整;每棵樹都有獨立的WAL日誌流,且寫入請求處理流程中只寫入WAL,並修改記憶體中數據,compaction時再將數據落盤,解決由於每個KV對可能由多條邊組成而導致的寫放大。即使記憶體數據丟失,仍可通過更新後的logid在磁碟上進行WAL的查詢並寫入。

  • 緩存實現:根據不同場景及當下cpu的開銷有不同策略。

圖原生緩存:相對於Memcached等直接緩存二進位數據而言,能更好的理解圖的語義,並支持一度查詢中的部分計算下推功能。

高性能LRU Cache:支持緩存逐出,且逐出的頻率和觸發閾值可調;採用numa aware和cpu cacheline aware設計,提高性能;支持Intel AEP等新硬體。

Write-through cache:支持多種與底層存儲同步數據的模式,可以每次寫入或定時落盤;支持定期與底層存儲校驗數據,防止數據過舊;支持負緩存等常見優化策略。

緩存與存儲分離:當數據規模不變、請求流量增大的情況下,緩存與存儲分離的模式可以快速擴容緩存以提高服務能力。

--

05 關鍵問題分析

1. 索引

  • 局部索引:給定一個起點和邊類型,對邊上的屬性構建索引
    特點:邊上元素皆可做索引項,能夠加速查詢,提高屬性過濾和排序性能;但會額外維護一份索引數據,與對應的原數據使用同一條日誌流,保證一致性。

  • 全局索引:目前只支持點的屬性全局索引,即指定一個屬性值查詢出對應的點。
    數據存儲在不同機器上,索引數據的一致性使用分散式事務解決。

2. 熱點讀寫

  • 熱點讀

場景舉例:某熱點視頻被頻繁刷新,查看其點贊數量。

應用機制:GQ層採用多個bgdb併發處理同一熱點的讀請求,單節點緩存命中讀性能可達20萬以上;GS層採用copy on write(即先拷貝,再寫入並替換)保證讀寫、讀讀均可併發。

  • 熱點寫

場景舉例:某熱點視頻短時間內被瘋狂轉發、點贊。

問題溯源:單機cpu使用率被拉高,磁碟寫入iops有上限,當客戶端寫入qps>磁碟iops時,就會發生請求排隊。

應對機制:採用group commit機制,即將多個寫入請求組合至一個batch寫入KV,再批量返回,降低磁碟層iops的上限。

file

3. 輕重查詢資源分配

將輕重查詢的資源池分離,輕查詢走light線程池,負責數量多的小查詢;重查詢則走heavy線程池,負責數量少的重查詢。當heavy線程池空閑時,輕查詢也可走。

file

4. 高可用

城域網雙機房,如國內的兩個機房,延遲較低。follow一寫多讀策略,備機房把寫流量轉入主機房,只有主機房會把WAL更新到KV存儲上。

廣域網容災部署,如新加坡和美國的兩台機器,延遲較高。follow了mysql的思想,每次寫入在本地寫入成功後,會被轉化為binlog,再發送給其他單元;並通過hybrid logical clock保證各單元對於一條邊的操作順序一致性。

file

5. 離線線上數據流融合

file

導入存量數據、寫入線上數據,將二者集成在公司內部數據平臺進行離線數據分析,具體流程如圖。


今天的分享就到這裡,謝謝大家。
本文首發於微信公眾號“DataFunTalk”。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • #region 輸入數字判斷是否是數字 #region 方法實現 /*不管是實參或形參,都在類型中開闢了空間的; 方法的功能一定要單一; 如GetMax(int n1,int n2); 方法中最忌諱的就是提示用戶輸入的字眼。 ///PS:最新版的沒有namespace這些,目前我想到的調用方法和類就 ...
  • #region 調用 /* 我們在main函數中調用Test()函數,我們管main函數稱為調用者, Test函數稱為被調用者. 如果被調用者想要得到調用者的值: 1) 傳遞參數; 2) 使用靜態欄位來模擬全局變數; 如果調用者想要得到被調用者的值: 1) 返回值; */ #endregion na ...
  • #region 複習 /* 常量:一旦賦值,不能被重新賦值; 枚舉:規範開發; 結構:為了一次性聲明多個不同類型的變數(實際為欄位); 數組:為了一次性聲明多個相同類型的變數 通過下標或索引訪問數組中元素 數組的取值和賦值 冒泡排序:兩個for迴圈 Array.Sort(nums);Array.Re ...
  • 鏡像下載、功能變數名稱解析、時間同步請點擊 阿裡雲開源鏡像站 1.先查看本機的系統信息 [[email protected] h0436 zlong]# cat /etc/redhat-release 2.進入yum.repos.d [[email protected] zlong]# cd /etc/yum.repos.d 3.查看 ...
  • 鏡像下載、功能變數名稱解析、時間同步請點擊 阿裡雲開源鏡像站 ifconfig 命令可以用於查看、配置、啟用或禁用指定的網路介面,還可以用來配置網卡的IP地址、掩碼、廣播地址、網關等,功能很豐富 功能雖然豐富,但是如果你沒有安裝呢? 嘿嘿嘿 如果沒有安裝ifconfig管理命令的話,直接運行ifconfig ...
  • 好消息!6月13日,騰訊雲資料庫三篇論文再次入選資料庫行業頂會SIGMOD,被SIGMOD 2022 Research Full Paper(研究類長文)收錄。 本次被收錄的研究成果中,新型數據結構設計、AI智能調參優化等均屬於業界首次提出。騰訊雲資料庫多次入選SIGMOD,表明騰訊雲資料庫在存儲、 ...
  • 本文將會和大家一起學習 SQL 的搜索條件中不可或缺的工具——謂詞(predicate)。SQL 謂詞就是返回值為 TRUE、FALSE 或 UNKNOWN 的表達式。 謂詞用於 WHERE 子句 和 HAVING 子句 的搜索條件中,還用於 FROM 子句的聯接條件以及需要布爾值的其他構造中。 本 ...
  • Apache ShardingSphere 助力噹噹 3.5 億用戶量級顧客系統重構,由 PHP+SQL Server 技術棧無縫轉型為 Java+ShardingSphere+MySQL,性能、可用性及維護性均得到顯著提升,是 ShardingSphere 異構遷移最佳實踐。 ...
一周排行
    -Advertisement-
    Play Games
  • 一、引言:什麼是 JSON JSON (Java Script Object Notation) 是一種很常用的數據格式,它常常用在 web 應用程式中。它可以表示結構化的數據。 下麵是常見的 JSON 文件結構 { "name": "Kamishiro Rize", "age": "22", "o ...
  • 前言 大家好,我是蝸牛,在上一篇中,我們介紹了不同版本的HTTP區別和發展背景,這篇文章我們來聊聊HTTP的缺點,HTTP缺點大致總結有以下三點: 通信使用明文(不加密),內容可能會被竊聽。 不驗證通信方的身份,因此有可能遭遇偽裝(客戶端和服務端都有可能) 無法證明報文的完整性,有可能會被篡改。 其 ...
  • resultMap處理欄位和屬性的映射關係 如果欄位名與實體類中的屬性名不一致,該如何處理映射關係? 第一種方法:為查詢的欄位設置別名,和屬性名保持一致 下麵是實體類中的屬性名: private Integer empId; private String empName; private Integ ...
  • 大家在看到這篇文章前,為了有一個舒適的c++IDE,一定感受到了Dev-c++的廉價感,Clion功能的多餘,VS的臃腫。他們也有自己的優點,但糟點太多,令人十分難受。而VS Code,可以取長補短。下麵的配置內容,可以讓你在刷題時,享受絲滑的動畫,體會集成終端的方便,讓你覺得Coding不再枯燥。 ...
  • 給定一個不含重覆數字的數組 nums ,返回其 所有可能的全排列 。你可以 按任意順序 返回答案。 示例 1: 輸入:nums = [1,2,3] 輸出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2: 輸入:nums = [0,1] 輸 ...
  • 設計模式的目的 編寫軟體過程中,程式員面臨著來自 耦合性,內聚性以及可維護性,可擴展性,重用性,靈活性 等多方面的 挑戰,設計模式是為了讓程式(軟體),具有更好 代碼重用性 (即:相同功能的代碼,不用多次編寫) 可讀性 (即:編程規範性, 便於其他程式員的閱讀和理解) 可擴展性 (即:當需要增加新的 ...
  • 本文講解了決策樹的創鍵的過程,包括熵,信息增益的計算,還有決策樹的創建,以及使用matplotlib讓決策樹可視化的詳細過程 ...
  • ♠ use C++11 倍數 若 $a,b,k \in \mathbb N$,且 $a \times k=b$,那麼 $b$ 是 $a$ 的倍數,稱 $a$ 整除 $b$,記作 $a \mid b$。 $[1,n]\in \mathbb N$ 中 $x \in \mathbb N$ 的倍數有 $\l ...
  • LinkList可以定義指向List的指針 1.當函數參數為LinkList L時,意味著只改變或操作List的內容,而不需要改變L這個指針 如 Status GetElem(LinkList L,int i,ElemType) 2.當參數為LinkList &L時,意味著需要改變或操作L這個指針本 ...
  • Spring 5框架 一、Spring概念 1、Spring是輕量級的JavaEE框架 2、Spring可以解決企業應用開發的複雜性 3、Spring有兩個核心部分:IOC和AOP ​ 1)IOC:控制反轉,把創建對象過程交給Spring進行管理 ​ 2)AOP:面向切麵,不修改源代碼進行功能增強 ...