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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Web數(shù)據(jù)共享（WDC）數(shù)據(jù)集由17億個(gè)頂點(diǎn)和640億條邊組成。在當(dāng)前主流服務(wù)器上存儲(chǔ)如此大規(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ū)為多個(gè)大數(shù)據(jù)系統(tǒng)。?

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

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

第一個(gè)問題：應(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ū)帶來了困難。一個(gè)頂點(diǎn)可以通過多條邊連接到許多其他頂點(diǎn)，其他頂點(diǎn)也可以通過它們的鄰邊連接到許多其他頂點(diǎn)。它就像網(wǎng)頁一樣，幾乎是相互鏈接的。那么對(duì)于一個(gè)圖形數(shù)據(jù)庫來說，應(yīng)該分區(qū)什么才能使語義直觀自然呢?(在RDBMS中，這相當(dāng)于當(dāng)表中有大量外鍵時(shí)如何對(duì)數(shù)據(jù)進(jìn)行分區(qū)。)當(dāng)然，也有一些自然的語義劃分方法。例如，在新冠疫情下，中國和其他國家的各種毒株傳播鏈?zhǔn)莾煞N不同的網(wǎng)絡(luò)結(jié)構(gòu)。 ?

然后，引入了第二個(gè)問題。?

第二個(gè)問題：如何保證在數(shù)據(jù)分區(qū)之后，每個(gè)分區(qū)的數(shù)據(jù)大致均衡。自然形成的圖符合冪次較低，即少數(shù)20%的頂點(diǎn)連接到其他80%的頂點(diǎn)，這些少數(shù)頂點(diǎn)稱為超級(jí)節(jié)點(diǎn)或密集節(jié)點(diǎn)。這意味著少數(shù)頂點(diǎn)與大多數(shù)其他頂點(diǎn)相關(guān)聯(lián)。因此，可以預(yù)期包含超級(jí)節(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ò)的視覺效果，其中超級(jí)網(wǎng)站（節(jié)點(diǎn)）是可見的。?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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