圖數(shù)據(jù)庫中的”分布式”和“切圖”
今天，我試著簡要綜述幾類不同的圖數(shù)據(jù)庫的分布式與切圖的設(shè)計，希望可以幫助大家了解不同項目、產(chǎn)品的設(shè)計差異。如果有理解不對的地方，歡迎留言討論。
什么是分布式系統(tǒng)
一般來說，分布式系統(tǒng)是一組計算機程序的集合，這些程序利用跨多個獨立節(jié)點的資源來實現(xiàn)共同的目標；這里的獨立節(jié)點，硬件上大多是指商用服務(wù)器(Commodity Servers)而不是大型主機（Mainframe）；這里的跨節(jié)點協(xié)同，硬件上大多是基于以太網(wǎng)設(shè)備或者更高端的 RMDA 設(shè)備。
為什么我們需要分布式系統(tǒng)？
使用分布式技術(shù)的主要目的，本質(zhì)上是用軟件技術(shù)+廉價硬件來換取昂貴硬件設(shè)備（比如主機）的成本；特別是在大多數(shù)私有機房環(huán)境——而不是公有云端或者超算條件下，此時采購成本是商業(yè)決策的重要依據(jù)。
除了降低硬件成本外，分布式技術(shù)帶來的另一個好處是其“擴展性”，通過在原有商用服務(wù)器的數(shù)量基礎(chǔ)上，增加幾臺服務(wù)器，再結(jié)合分布式軟件的調(diào)度和分發(fā)能力，使得新加入的這幾臺服務(wù)器也再額外提供更多的服務(wù)；
相比于每次擴容都要 1 比 1 采購更多的等數(shù)量服務(wù)器，或者購買更高配置的服務(wù)器；分布式技術(shù)這一方面使得采購計劃可以按需擴容，降低了一次性的大額資本支出；另一方面也使得業(yè)務(wù)容量可以更加容易規(guī)劃。
分布式系統(tǒng)的基礎(chǔ)問題
在分布式技術(shù)中，由于數(shù)據(jù)的存儲和計算需要跨多個獨立節(jié)點來實現(xiàn)，因此不得不涉及到一系列基礎(chǔ)技術(shù)。在本文中我們只討論兩個：一是提供數(shù)據(jù)（和服務(wù)）的拷貝或者副本的問題；二是對于那些龐大數(shù)據(jù)的存儲和計算該如何分發(fā)到各個獨立節(jié)點上完成？
一、數(shù)據(jù)的副本問題
由于是商用服務(wù)器，其硬件上的可靠性和維護遠遠低于主機，網(wǎng)線松動、硬盤損壞、電源故障在大型機房中幾乎每小時都在發(fā)生，是常態(tài)；處理屏蔽這些硬件問題是分布式軟件系統(tǒng)要解決的基本問題。一個常用的方式是為數(shù)據(jù)（和其服務(wù)）提供更多的拷貝或者副本，這些副本存在于多臺商用服務(wù)器上，當一些副本發(fā)生故障時，由正常的副本繼續(xù)提供服務(wù)；并且當訪問壓力增加時，還可以增加更多的副本來增加服務(wù)能力。此外，還需要通過一定的技術(shù)手段來保證這些副本的”一致性”，也就是每個服務(wù)器上各個副本的數(shù)據(jù)是一樣的。當然，在圖數(shù)據(jù)庫中，副本問題也存在；其處理方式和大多數(shù)大數(shù)據(jù)、RDBMS 會較為類似。
二、是數(shù)據(jù)的切分問題
單臺服務(wù)器的硬盤、內(nèi)存、CPU 都是有限的，TB、PB 級別的數(shù)據(jù)通過一定的辦法分發(fā)到各個服務(wù)器上，這稱為”切片”。當一些請求要訪問多個切片時，分布式系統(tǒng)要能夠?qū)⑦@些請求拆散分發(fā)到各個正確的分片上，并將各分片的返回重新“拼裝”成完整的結(jié)果。
圖數(shù)據(jù)中的切分問題：切圖
在圖數(shù)據(jù)庫中，這個分發(fā)過程被形象的稱為”切圖”：就是把一個大圖切成很多的小圖，把對于這些小圖的存儲或者計算再放置在不同的服務(wù)器上。相比大數(shù)據(jù)、RDBMS 的大多數(shù)方案，值得一些特別的說明。
我們先考慮一個靜態(tài)的（不會發(fā)生變化的）圖結(jié)構(gòu)，比如“CiteSeer數(shù)據(jù)集”，這里面記錄了 3312 篇論文，以及這些論文之間的引用關(guān)系；這是一個很小規(guī)模的數(shù)據(jù)集，因此工程上，我們可以基本相信對于這個數(shù)據(jù)集的處理，基本可以交給單個服務(wù)器。
再對于 twitter2010 這個數(shù)據(jù)集，其中有 1271 萬個頂點和 2.3 億條邊，對于今天(2022)的主流服務(wù)器來說，相對可以輕松處理；但對于 10 年前的服務(wù)器來說，可能就需要選購非常昂貴的高端服務(wù)器才行。
但對于 WDC 數(shù)據(jù)集(Web Data Commons)，其中有 17 億個頂點和 640 億條邊，這樣規(guī)模的計算這對于當前單臺主流服務(wù)器來說也相當困難了。
另一方面，由于人類社會數(shù)據(jù)產(chǎn)生的速度快于摩爾定律，而數(shù)據(jù)之間的交互與關(guān)系又指數(shù)級高于數(shù)據(jù)產(chǎn)生的速度；“切圖”似乎是一個不可避免的問題；但這聽上去似乎和各種主流分布式技術(shù)里面的數(shù)據(jù)分片和散列的方式?jīng)]啥區(qū)別。畢竟那么多大數(shù)據(jù)系統(tǒng)，不都要”切”嗎
等等——圖真的那么好”切”嗎？
遺憾的是，并不是。圖領(lǐng)域里面，”切圖”是一個在技術(shù)、產(chǎn)品和工程上需要仔細權(quán)衡的問題。
切圖面臨的三個問題
第一個問題，切在哪里？在大數(shù)據(jù)或者 RDBMS 中，我們根據(jù)記錄或者字段來進行 行切 row-based 或者 列切 column-based，也可以根據(jù) ID 規(guī)則進行切分；這些在語義和技術(shù)都比較直觀?？墒菆D的特點是它的強連通性，一個點通過一些邊，關(guān)聯(lián)上了另外一些點，這些點又通過它們的鄰邊關(guān)聯(lián)上了更多的點，就像全世界的 web 網(wǎng)頁，幾乎都通過超鏈接關(guān)聯(lián)在一起，那對于圖來說，切在哪里才是語義上直觀與自然的。(如果用RDBMS的術(shù)語，相當于有大量的外鍵情況下，如何切分)。當然，也存在一些天然語義上的圖切片方式，例如在新冠疫情下，各種毒株在中國的傳染鏈條和國外的鏈條已經(jīng)天然是兩個不同的網(wǎng)絡(luò)結(jié)構(gòu)。但此時，引入了第二個問題。
第二個問題，如何保證切了之后，各分片的負載是大致均衡的？天然形成的圖符合冪率定律——20% 的少數(shù)節(jié)點連接了 80% 的其他節(jié)點，這些少數(shù)節(jié)點也稱為“超級節(jié)點”或者“稠密點”。這意味著少數(shù)超級節(jié)點關(guān)聯(lián)了大多數(shù)其他的平平無奇的節(jié)點。因此可以預(yù)計含有超級節(jié)點的分片（服務(wù)器）的負載和熱點會遠遠大于其他不含超級節(jié)點的分片。
互聯(lián)網(wǎng)上網(wǎng)站通過超鏈接形成的關(guān)聯(lián)網(wǎng)絡(luò)可視效果，其中的超級網(wǎng)站（節(jié)點）清晰可見
第三個問題，當圖網(wǎng)絡(luò)逐漸演化增長，圖的分布和連通性也逐漸發(fā)生了改變，原有的切分方法逐漸失效，該如何評估和進行重分布。下圖是人類大腦 860 億個神經(jīng)元之間的連接可視圖，隨著學習、鍛煉、睡眠、衰老，神經(jīng)元連接甚至在周級別就會發(fā)生顯著的變化；原先得到的切片方式可能完全跟不上變化。
當然還有其他很多要考慮的問題細節(jié)，本文也盡量避免引入太多的技術(shù)術(shù)語。
遺憾的是，雖然有這些問題（當然其實還有更多），在技術(shù)角度并沒有一個通用的最優(yōu)方案，各個產(chǎn)品針對其重點不得不進行取舍，下面是一些舉例。
不同圖數(shù)據(jù)庫的切圖方式
1. “分布式”但不”切圖”
這種思路的典型做法是 Neo4j 3.5 雖然采用了分布式的架構(gòu)，但不進行圖切分
采用分布式的目的，是為了保證寫入的多副本一致性和讀負載能力。
也就是說每個服務(wù)器中都保留了”全量”的圖數(shù)據(jù)，因此圖數(shù)據(jù)不能大于單機的內(nèi)存和硬盤容量；而通過增加寫副本，可以保證寫入過程中單機失效問題；通過增加讀副本，可以提供更多的讀請求能力（不能提高寫請求的能力）。
可以看到對于前面的三個問題，這種方案在產(chǎn)品層面直接避免。但是理論上，這樣的方案稱為“分布式”并沒有什么問題。
多說一句，由于是單機，數(shù)據(jù)庫意義上的 ACID 在技術(shù)上較為簡單。
Neo4j 3.5 的因果集群架構(gòu)
2. 分布式，由用戶來”切圖”
這個典型的代表是 Neo4j 4.x Fabric。根據(jù)業(yè)務(wù)情況，用戶指定將每個部分的子圖放在一個(組)服務(wù)器上,例如在一個集群內(nèi)，E號產(chǎn)品的圖放在 E號服務(wù)器上，N號產(chǎn)品的圖放在N號服務(wù)器上。(當然，為了服務(wù)本身的可用性，這些服務(wù)器還可以采用上文中 Causal Cluster 的方案。)在這個過程中，不論是查詢還是寫入，都需要用戶指定要訪問哪個服務(wù)。 Fabric 輔助用戶代理路由。這個方案和 RDBMS 的分表非常類似，用戶在使用過程中自己指定要使用那個分區(qū)或者分表，”切分”這個動作，用戶是有著完全的掌控。
可以看到對于前面的三個問題，這種方案在產(chǎn)品層面完全交給了用戶來決定。當然，這樣的方案也可以稱為“分布式”。
多說一句，雖然可以保證E服務(wù)器內(nèi)部的 ACID。但因為存在一定數(shù)量的邊”橫跨”兩個服務(wù)器，技術(shù)上不保證這些”橫跨”邊操作的 ACID。
Neo4j Fabric 架構(gòu)
3. 非對等分布式，”切圖”， 粗顆粒度的副本
在這種方案中，既有多副本，也有“切圖”，這兩個過程也都需要少量用戶的介入。
描述已自動生成
Tigergraph 的切圖方案
在 TigerGraph 的方案中，點和邊（在編碼后），會分散到多個分片上。
上面的三個問題，第 1 和 2 可以通過編碼部分的技巧來部分緩解，并將部分查詢或者計算的決策（單機還是分布式模型）交給用戶決定來實現(xiàn)權(quán)衡。
描述已自動生成
描述已自動生成
TigerGraph 的單機查詢模式和并行計算模式
多說一句，這樣一組分片必需要完整并一模一樣的復(fù)制多份（因此擴容顆粒度是整個圖，而不是某個分片）。相對擴容時的單次支出較大。
4. 全對等分布式，”切圖”，細顆粒度的副本
還有一些方案的架構(gòu)設(shè)計目的中，相對把圖的擴展性/彈性排在整個系統(tǒng)設(shè)計最高的優(yōu)先級。其假設(shè)是數(shù)據(jù)產(chǎn)生的速度快于摩爾定律，而數(shù)據(jù)之間的交互與關(guān)系又指數(shù)級高于數(shù)據(jù)產(chǎn)生的速度。因此必須要能夠處理這樣爆炸增長的數(shù)據(jù)，并快速提供服務(wù)。
在這種架構(gòu)中，通常的顯著特點是把存儲層和計算層物理上分開，各自實現(xiàn)細顆粒度的擴容能力；
數(shù)據(jù)分片由存儲層負責，通常用 hash 或者一致性 hash 的方案進行切分，根據(jù)點的 ID 或者主鍵進行散列。（回答第一個問題）
圖形用戶界面, 應(yīng)用程序
Nebula Graph 的架構(gòu)
Wu, Min, et al. "Nebula Graph: An open source distributed graph database." arXiv preprint arXiv:2206.07278 (2022).
Li C, Chen H, Zhang S, et al. ByteGraph: A High-Performance Distributed Graph Database in ByteDance[J].
為了處理超級節(jié)點和負載均衡(第二個問題)，再引入一層數(shù)據(jù)結(jié)構(gòu)(B+tree)，將大的超級節(jié)點拆分成更多小的處理單元。并（工程上）實現(xiàn)線程間的負載切換，和獨立擴容計算層。對于第三個問題，通過引入細顆粒度的切片，單獨實現(xiàn)部分切片的擴容
中度可信度描述已自動生成
當然，這種方案也可以稱為“分布式”。
以上四種方案，在產(chǎn)品和技術(shù)層面做了不同的權(quán)衡，各種側(cè)重以適合各自的用戶業(yè)務(wù)場景。但它們都可以稱為“分布式”。
關(guān)于“偽分布式”(Pseudo-Distrubuted Mode)
一般來說，這是用單服務(wù)器上的運行模擬在多個服務(wù)器的運行；特別適合于學習或者調(diào)試。
- 關(guān)于圖領(lǐng)域的綜述
Sahu, S., Mhedhbi, A., Salihoglu, S., Lin, J., ¨Ozsu, M.T.: The ubiquity of large graphs and surprising challenges of graph processing: extended survey. VLDB J. 29(2-3), 595–618 (2020)
Sakr, S., Bonifati, A., Voigt, H., Iosup, A., Ammar, K., Angles, R., Yoneki: The future is big graphs: a community view on graph processing systems. Communications of the ACM 64(9), 62–71 (2021)
Disclaimer
1.以上提到的技術(shù)方案，是作者的理解和分享，如有錯誤歡迎指出，并沒有商業(yè)競爭目的。
2.為了降低讀者理解難度,做了很大程度的簡化，并不表示原方案是如此簡單。
