什么是分布式系統(tǒng)? ?

一般來說，分布式系統(tǒng)是一組計算機(jī)程序，它們在多臺獨(dú)立的服務(wù)器上協(xié)同工作以實現(xiàn)一個共同的目標(biāo)。這些服務(wù)器指的是商用服務(wù)器，而不是大型機(jī)。這里用于跨服務(wù)器協(xié)作的硬件大多基于以太網(wǎng)設(shè)備或更高端的遠(yuǎn)程直接數(shù)據(jù)存取（RMDA）設(shè)備。 ?

為什么需要采用分布式系統(tǒng)? ?

構(gòu)建分布式系統(tǒng)的主要原因是采用軟件技術(shù)和廉價的硬件設(shè)備來取代成本高昂的硬件設(shè)備。特別是在大多數(shù)私有服務(wù)器機(jī)房，而不是采用公共云或超級計算機(jī)條件下，采購成本是業(yè)務(wù)決策的重要依據(jù)。?

除了降低成本，分布式技術(shù)的另一個好處是它的可擴(kuò)展性。通過在原有服務(wù)器數(shù)量的基礎(chǔ)上增加幾臺服務(wù)器，然后結(jié)合分布式系統(tǒng)的調(diào)度和分發(fā)能力，新增的服務(wù)器可以用來提供額外的服務(wù)。?

與購買多臺相同數(shù)量的服務(wù)器或購買高配置的服務(wù)器相比，分布式技術(shù)可以按需購買服務(wù)器，這樣降低了過度配置的風(fēng)險，并提高了硬件資源的利用率。?

分布式系統(tǒng)的基本問題?

在分布式技術(shù)中，由于數(shù)據(jù)存儲和計算需要在多個獨(dú)立的服務(wù)器上實現(xiàn)，因此必須涉及一系列底層技術(shù)。在本文只討論兩個問題：一個是數(shù)據(jù)復(fù)制或副本問題，另一個是如何將大型數(shù)據(jù)的存儲和計算分配給獨(dú)立的服務(wù)器。?

數(shù)據(jù)副本的問題?

商用服務(wù)器的硬件可靠性和維護(hù)能力遠(yuǎn)低于大型機(jī)。因為在服務(wù)器機(jī)房中，網(wǎng)線松動、硬盤損壞、電源故障幾乎每小時都會發(fā)生。解決或避免這些硬件問題是分布式軟件系統(tǒng)的基本問題。一種常見的解決方案是在多臺服務(wù)器上復(fù)制數(shù)據(jù)。一旦部分?jǐn)?shù)據(jù)副本丟失，系統(tǒng)仍然可以使用剩余的數(shù)據(jù)副本提供服務(wù)。?

而且，當(dāng)系統(tǒng)的訪問負(fù)載過大時，還可以通過增加副本來提供更多的服務(wù)。此外，還需要一些技術(shù)來確保數(shù)據(jù)副本彼此一致；也就是說，不同服務(wù)器上的每個副本的數(shù)據(jù)是相同的。對于圖形數(shù)據(jù)庫，也存在數(shù)據(jù)復(fù)制問題。解決這個問題的方法類似于關(guān)系數(shù)據(jù)庫或大數(shù)據(jù)系統(tǒng)中解決數(shù)據(jù)復(fù)制問題的方法。?

數(shù)據(jù)分區(qū)問題?

單臺服務(wù)器的硬件、內(nèi)存和CPU是有限的。如果數(shù)據(jù)太大，就不可能將所有數(shù)據(jù)存儲在一臺服務(wù)器上。因此，TB級甚至PB級的數(shù)據(jù)必須分布到多臺服務(wù)器上，將這一過程稱為數(shù)據(jù)分區(qū)。當(dāng)一個請求要訪問多個數(shù)據(jù)分區(qū)時，分布式系統(tǒng)需要將請求分發(fā)到每個正確的數(shù)據(jù)分區(qū)，然后組合結(jié)果。?

圖形數(shù)據(jù)庫中的數(shù)據(jù)分區(qū)問題：圖形分區(qū)?

在圖形數(shù)據(jù)庫中，分布過程被形象地稱為圖形分區(qū)。一個大圖被劃分為多個小圖，每個小圖的存儲和計算都存儲在不同的服務(wù)器上。?

與關(guān)系數(shù)據(jù)庫和大數(shù)據(jù)系統(tǒng)中的分區(qū)問題相比，圖形分區(qū)問題更值得關(guān)注。?

以下來看一個靜態(tài)圖結(jié)構(gòu)，例如CiteSeer數(shù)據(jù)集，它是一個由3312篇論文及其之間的引用組成的科學(xué)論文引用網(wǎng)絡(luò)，是一個可以存儲在單個服務(wù)器上的小規(guī)模數(shù)據(jù)集。?

Twitter2010數(shù)據(jù)集是Twitter用戶的社交網(wǎng)絡(luò)，由1271萬個頂點(diǎn)和2.3億條邊組成。將這一數(shù)據(jù)集存儲在2022年生產(chǎn)的單一主流服務(wù)器上相對容易。然而，這可能需要采購價格非常昂貴的高端服務(wù)器。 ?

Web數(shù)據(jù)共享（WDC）數(shù)據(jù)集由17億個頂點(diǎn)和640億條邊組成。在當(dāng)前主流服務(wù)器上存儲如此大規(guī)模的數(shù)據(jù)集是困難的或是不可能的。?

另一方面，由于人類的數(shù)據(jù)增長速度快于摩爾定律，并且數(shù)據(jù)之間的連接或關(guān)系的數(shù)量以指數(shù)形式高于數(shù)據(jù)生產(chǎn)的速度，因此數(shù)據(jù)分區(qū)問題似乎是圖形數(shù)據(jù)庫系統(tǒng)不可避免的問題。這聽起來與主流分布式技術(shù)中數(shù)據(jù)的分區(qū)或散列方式并沒有什么不同。畢竟，數(shù)據(jù)被分區(qū)為多個大數(shù)據(jù)系統(tǒng)。?

數(shù)據(jù)分區(qū)有那么容易嗎? 并不是，在圖形數(shù)據(jù)庫領(lǐng)域，圖形分區(qū)問題是技術(shù)、產(chǎn)品和工程之間的權(quán)衡。?

圖形分區(qū)面臨的三個問題?

第一個問題：應(yīng)該分區(qū)什么?在大數(shù)據(jù)或關(guān)系數(shù)據(jù)庫系統(tǒng)中，根據(jù)記錄或字段進(jìn)行行分區(qū)或列分區(qū)，或者根據(jù)數(shù)據(jù)ID進(jìn)行分區(qū)，這些在語義和技術(shù)上都是直觀的。但是，圖形數(shù)據(jù)結(jié)構(gòu)的強(qiáng)連通性給圖形數(shù)據(jù)的分區(qū)帶來了困難。一個頂點(diǎn)可以通過多條邊連接到許多其他頂點(diǎn)，其他頂點(diǎn)也可以通過它們的鄰邊連接到許多其他頂點(diǎn)。它就像網(wǎng)頁一樣，幾乎是相互鏈接的。那么對于一個圖形數(shù)據(jù)庫來說，應(yīng)該分區(qū)什么才能使語義直觀自然呢?(在RDBMS中，這相當(dāng)于當(dāng)表中有大量外鍵時如何對數(shù)據(jù)進(jìn)行分區(qū)。)當(dāng)然，也有一些自然的語義劃分方法。例如，在新冠疫情下，中國和其他國家的各種毒株傳播鏈?zhǔn)莾煞N不同的網(wǎng)絡(luò)結(jié)構(gòu)。 ?

然后，引入了第二個問題。?

第二個問題：如何保證在數(shù)據(jù)分區(qū)之后，每個分區(qū)的數(shù)據(jù)大致均衡。自然形成的圖符合冪次較低，即少數(shù)20%的頂點(diǎn)連接到其他80%的頂點(diǎn)，這些少數(shù)頂點(diǎn)稱為超級節(jié)點(diǎn)或密集節(jié)點(diǎn)。這意味著少數(shù)頂點(diǎn)與大多數(shù)其他頂點(diǎn)相關(guān)聯(lián)。因此，可以預(yù)期包含超級節(jié)點(diǎn)的分區(qū)的負(fù)載和熱點(diǎn)與包含其他頂點(diǎn)的其他分區(qū)的負(fù)載和熱點(diǎn)相比要高得多。 ?

上圖為互聯(lián)網(wǎng)上網(wǎng)站的超鏈接形成的關(guān)聯(lián)網(wǎng)絡(luò)的視覺效果，其中超級網(wǎng)站（節(jié)點(diǎn)）是可見的。?

第三個問題：隨著圖形網(wǎng)絡(luò)的增長，原有的分區(qū)方法逐漸過時，圖形的分布和連接模式發(fā)生變化，如何評估和執(zhí)行重新分區(qū)?上圖展示了人類大腦中860億個神經(jīng)元之間連接的視覺效果。隨著人們的學(xué)習(xí)、鍛煉、睡眠和衰老，神經(jīng)元連接每周都在不斷變化。原來的分區(qū)方法可能根本無法跟上這些變化。 ?

當(dāng)然，還有許多其他細(xì)節(jié)需要考慮。本文盡量避免使用太多的專業(yè)術(shù)語。?

不幸的是，從技術(shù)角度來看，沒有解決圖形分區(qū)問題的靈丹妙藥，每個產(chǎn)品都必須做出權(quán)衡。?

以下是不同產(chǎn)品的權(quán)衡示例。?

不同圖形數(shù)據(jù)庫產(chǎn)品中的分區(qū)方法?

1.已經(jīng)分布但未分區(qū) ?

Neo4j3.5采用無分區(qū)分布式架構(gòu)。 ?

使用分布式系統(tǒng)的原因是確保在多個副本中寫入數(shù)據(jù)的一致性和可用性。這意味著所有的圖形數(shù)據(jù)都存儲在每臺服務(wù)器上，并且數(shù)據(jù)的大小不能超過單臺服務(wù)器的內(nèi)存和硬盤的容量?？梢酝ㄟ^添加多個寫副本來保證數(shù)據(jù)寫入過程中單臺服務(wù)器的故障，并且可以通過添加多個讀副本來提高讀性能(寫性能沒有提高)。 ?

這種解決方案可以避免上面提到的圖形數(shù)據(jù)分區(qū)的三個問題，理論上，將這樣的解決方案稱為分布式圖數(shù)據(jù)庫并沒有什么錯。?

此外，由于每臺服務(wù)器上的數(shù)據(jù)都是完整的，因此ACID事務(wù)相對容易實現(xiàn)。 ?

2.按用戶分布和分區(qū) ?

按用戶進(jìn)行分布式和分區(qū)的架構(gòu)通常由Neo4j 4.x Fabric表示。根據(jù)用戶的業(yè)務(wù)案例，用戶可以指定子圖可以放在(一組)服務(wù)器上。例如，在一個集群中，產(chǎn)品E的子圖放在服務(wù)器E上，產(chǎn)品N的子圖放在服務(wù)器N上(當(dāng)然，為了服務(wù)本身的可用性，這些服務(wù)器也可以放在上圖中提到的因果集群中)。在這一過程中，對于寫和讀操作，用戶都需要指定一臺或一組服務(wù)器進(jìn)行操作。 ?

這個解決方案把上面提到的三個問題留給用戶在產(chǎn)品層面上進(jìn)行決策。因此，這樣的解決方案也被稱為分布式圖數(shù)據(jù)庫。?

此外，該解決方案可以保證服務(wù)器E中的ACID事務(wù)，但是由于服務(wù)器E中的頂點(diǎn)與其他服務(wù)器中的頂點(diǎn)之間存在一定數(shù)量的邊連接，因此從技術(shù)上無法保證這些邊的ACID事務(wù)。 ?

3.非等效的分布式、分區(qū)和粗粒度副本 ?

該解決方案允許多個副本和圖形數(shù)據(jù)分區(qū)，這兩個過程需要少量的用戶參與。?

在TigerGraph的解決方案中，頂點(diǎn)和邊在編碼之后分散在多個分區(qū)中。 ?

上述問題中的前兩個問題可以通過對頂點(diǎn)和邊進(jìn)行編碼來部分解決。用戶可以決定是在分布式系統(tǒng)中還是在單臺服務(wù)器中讀取或計算數(shù)據(jù)。?

但是，這樣的一組分區(qū)必須以完全相同的副本進(jìn)行復(fù)制(因此向外擴(kuò)展的粒度是整個圖表而不分區(qū))，這需要更大的存儲空間。 ?

4.完全等效的分布式、分區(qū)和細(xì)粒度副本?

還有一些解決方案的架構(gòu)設(shè)計目的是將圖形的可擴(kuò)展性或彈性相對地置于整個系統(tǒng)設(shè)計的最高優(yōu)先級。假設(shè)數(shù)據(jù)的生成速度快于摩爾定律，數(shù)據(jù)之間的相互作用和關(guān)系比數(shù)據(jù)生成速度呈指數(shù)級增長。因此，有必要能夠處理如此爆炸性增長的數(shù)據(jù)并快速提供服務(wù)。?

在這個解決方案中，明顯的特點(diǎn)是存儲層和計算層的分離設(shè)計，每一層都具有細(xì)粒度可擴(kuò)展性的能力。?

數(shù)據(jù)在存儲層使用哈?；蛞恢鹿＝鉀Q方案進(jìn)行分區(qū)。哈希是基于頂點(diǎn)或主鍵的ID執(zhí)行的，這個解決方案只是解決了第一個問題。 ?

為了處理超級節(jié)點(diǎn)和負(fù)載平衡問題(第二個問題)，引入了另一層B-樹數(shù)據(jù)結(jié)構(gòu)。它將超級節(jié)點(diǎn)分割為多個處理單元，在線程之間平衡數(shù)據(jù)，并向外擴(kuò)展計算層。 ?

對于第三個問題，其解決方案是使用細(xì)粒度分區(qū)方法，以便可以執(zhí)行某些分區(qū)的擴(kuò)展。?

這種解決方案也被稱為分布式圖數(shù)據(jù)庫。?

以上提到的四種解決方案在產(chǎn)品和技術(shù)級別上進(jìn)行了不同的權(quán)衡，重點(diǎn)放在合適的業(yè)務(wù)場景上。因此，這些解決方案都可以稱為分布式圖數(shù)據(jù)庫。?

原文標(biāo)題：??Distribution and Partitioning in Graph Databases??，作者：Lisa liu