什么是分布式系統? ?

一般來說，分布式系統是一組計算機程序，它們在多臺獨立的服務器上協同工作以實現一個共同的目標。這些服務器指的是商用服務器，而不是大型機。這里用于跨服務器協作的硬件大多基于以太網設備或更高端的遠程直接數據存取（RMDA）設備。 ?

為什么需要采用分布式系統? ?

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

除了降低成本，分布式技術的另一個好處是它的可擴展性。通過在原有服務器數量的基礎上增加幾臺服務器，然后結合分布式系統的調度和分發能力，新增的服務器可以用來提供額外的服務。?

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

分布式系統的基本問題?

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

數據副本的問題?

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

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

數據分區問題?

單臺服務器的硬件、內存和CPU是有限的。如果數據太大，就不可能將所有數據存儲在一臺服務器上。因此，TB級甚至PB級的數據必須分布到多臺服務器上，將這一過程稱為數據分區。當一個請求要訪問多個數據分區時，分布式系統需要將請求分發到每個正確的數據分區，然后組合結果。?

圖形數據庫中的數據分區問題：圖形分區?

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

與關系數據庫和大數據系統中的分區問題相比，圖形分區問題更值得關注。?

以下來看一個靜態圖結構，例如CiteSeer數據集，它是一個由3312篇論文及其之間的引用組成的科學論文引用網絡，是一個可以存儲在單個服務器上的小規模數據集。?

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

Web數據共享（WDC）數據集由17億個頂點和640億條邊組成。在當前主流服務器上存儲如此大規模的數據集是困難的或是不可能的。?

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

數據分區有那么容易嗎? 并不是，在圖形數據庫領域，圖形分區問題是技術、產品和工程之間的權衡。?

圖形分區面臨的三個問題?

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

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

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

上圖為互聯網上網站的超鏈接形成的關聯網絡的視覺效果，其中超級網站（節點）是可見的。?

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

當然，還有許多其他細節需要考慮。本文盡量避免使用太多的專業術語。?

不幸的是，從技術角度來看，沒有解決圖形分區問題的靈丹妙藥，每個產品都必須做出權衡。?

以下是不同產品的權衡示例。?

不同圖形數據庫產品中的分區方法?

1.已經分布但未分區 ?

Neo4j3.5采用無分區分布式架構。 ?

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

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

此外，由于每臺服務器上的數據都是完整的，因此ACID事務相對容易實現。 ?

2.按用戶分布和分區 ?

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

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

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

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

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

在TigerGraph的解決方案中，頂點和邊在編碼之后分散在多個分區中。 ?

上述問題中的前兩個問題可以通過對頂點和邊進行編碼來部分解決。用戶可以決定是在分布式系統中還是在單臺服務器中讀取或計算數據。?

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

4.完全等效的分布式、分區和細粒度副本?

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

在這個解決方案中，明顯的特點是存儲層和計算層的分離設計，每一層都具有細粒度可擴展性的能力。?

數據在存儲層使用哈希或一致哈希解決方案進行分區。哈希是基于頂點或主鍵的ID執行的，這個解決方案只是解決了第一個問題。 ?

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

對于第三個問題，其解決方案是使用細粒度分區方法，以便可以執行某些分區的擴展。?

這種解決方案也被稱為分布式圖數據庫。?

以上提到的四種解決方案在產品和技術級別上進行了不同的權衡，重點放在合適的業務場景上。因此，這些解決方案都可以稱為分布式圖數據庫。?

原文標題：??Distribution and Partitioning in Graph Databases??，作者：Lisa liu