作者：孫宇熙 & 陳俊文

（本篇摘譯自 Designing Highly Scalable Graph Database Systems without Exponential Performance Degradation - Understanding Distributed Native Graph Processing 一文，該文被 ACM Digital Library 美國計算機學會數字圖書館收錄。）

當今圖數據庫系統面臨的一個主要挑戰，就是怎樣才能兼顧存儲與計算兩方面性能。很多圖系統廠商選擇了犧牲查詢速度來獲得存儲的可擴展性，得到的系統雖然能使用眾多實例存儲大量數據，但無法提供足夠的圖計算能力來實時深入地對動態圖數據進行穿透。像K鄰搜索、全圖最短路徑這類計算，表面上直觀易懂，實則牽涉大量針對圖數據的深度遍歷，放在一個典型的 BSP（Bulky Synchronous Processing）系統上運行會引發多個分布實例之間的大規模數據交換，從而導致嚴重的的延遲。

真實世界中的圖數據往往要么非常密集、含有超級節點（例如金融交易數據），要么數據量巨大，需要分區、分片進行水平擴展，同時不能以性能的指數級下降為代價。上面舉例的分布式圖系統顯然不是為了真實世界的需求而設計的，它們“只能存不能算”，我們稱其所達到的可擴展性是無效的。

如何才能獲得有效可擴展的圖系統呢？這需要先了解圖數據庫可擴展性的發展歷程。圖1展示了圖數據庫從單機實例到水平可擴展的分布式集群的進化路徑。

圖1：分布式（圖）系統的發展

我們將真正稱得上有效可擴展的圖系統架構分為三類，分別介紹它們的特性。

第一類：分布式共識 & HTAP

第一類分布式圖系統可以從分布式共識集群談起。分布式共識集群支持RAFT協議，并且為了便于選出集群leader，通常含有3個或更多奇數個實例。例如，Neo4j的Enterprise Edition v4.x支持原始的RAFT協議，只用一個主實例處理工作負載，而其他兩個實例僅同步來自主實例的數據。

一種較實用的處理工作負載的方法是使用增強的RAFT協議，讓所有實例以負載均衡的方式工作。例如，讓主導實例處理讀寫操作，其他實例除了同步數據之外還可以處理讀操作，仍然保證了整個集群的數據一致性。

一種更復雜的方法是HTAP（混合事務和分析處理），集群leader處理TP操作和AP操作，而follower處理各種AP操作（圖算法、路徑查詢等）。圖2所示的就是嬴圖的HTAP圖系統架構。

圖2：嬴圖的HTAP架構

分布式共識系統的利弊總結如下：

• 硬件使用量低
• 數據一致性好
• 復雜、深層查詢高性能
• 僅限于垂直可擴展性

第二類：Grid

第二類分布式圖系統包含多個集群，由name server擔任客戶端和服務器端之間的代理角色，在實例間對查詢進行分配、對數據進行轉發與聚合，實現針對多實例的聯邦查詢（Query-Federation）。這類分布式圖系統的圖分割工作通常是基于時間序列（水平分割）或業務邏輯（垂直分割）人為地進行的。

例如，將一年之內發生的信用卡交易數據（邊）按月劃分為12個圖集，再將這些圖集存儲到不同的集群（3個實例）中。這種按時間劃分邊數據的邏輯是由數據庫管理員事先定義好的，通過切點（node-cut）的方式進行圖分割，是一種基于時間序列、同時又支持絕大多數業務邏輯（按月計算）的分割方式。在不涉及跨集群計算時（即不會發生數據遷移），該類圖系統與HTAP系統具有同樣良好的查詢性能。

圖3展示了一種Grid體系架構，相比于圖2所示HTAP架構，該架構額外增加了name server和meta server兩個組成部分。從設計上，所有查詢都由name server進行代理，同時name server與meta server協同工作以確保整個系統的彈性。各集群則在很大程度上與HTAP架構相同。

圖3：Grid體系架構（Cluster、Name Server、Meta Server）

值得注意的是，由于會受到數據遷移的影響（類似于map reduce的工作原理），Grid系統在進行圖算法等跨集群操作時的性能并不盡如人意。

我們將Grid架構設計的利弊概括為：

• 保留了HTAP體系結構的所有優缺點
• 同時兼顧了可擴展性與性能
• 需要管理員（DBA）干預圖分割
• 絕大多數業務邏輯需首先在各集群上執行得到臨時結果，發送給name server進行聚合后再返回到客戶端
• 業務邏輯必須與圖分割、圖查詢的邏輯相適配

第三類：Shard

第三類分布式圖系統延用了第二類系統中的name server和meta server，但其數據分割的方式并非人為制定，而是由name server根據自動收集的統計信息（Automatic Statistics Collection）進行判斷，并根據系統的使用情況做出實時調整。

此類架構的終極目標是放棄對name server算力的依賴，讓每個分片（shard server）將充分擔負起計算任務。該架構在數據遷移方面以最小I/O成本為原則進行優化，在跨分片計算時讓少量數據向大量數據遷移，只在name server上進行最少的數據整合。

圖4展示了一種分片體系結構。在這種對等（peer-to-peer）的體系結構中，shard server和name server都具有計算能力，同時shard server還負擔了分區存儲。

圖4：Shard體系架構（Shard Server、Name Server、Meta Server）

針對圖數據展開應用的Shard系統具有以下特征：

• 無限可擴展
• I/O性能高
• 跨分片的查詢性能低（指數級）
• 圖查詢的調度（計劃和優化）復雜

應用場景

為真實的商業場景設計分布式圖系統時，需進行有針對性的優化以獲得令人滿意的性能。下面表格給出了以上3種分布式圖系統的特征及其具體要求。

表：三種分布式圖系統及其業務場景

一個真正能勝任的分布式圖系統還需要考慮很多因素，如成本、主觀偏好、設計理念、商業邏輯、復雜性容忍度、服務能力等。我們很難籠統的說一種架構絕對優于另一種架構。但長遠來看，圖體系架構的發展方向顯然是從上面所介紹的第一類到第二類、最終到第三類；只是就目前來看，前兩類體系已經能滿足絕大多數客戶場景的需求，并且人類的智力水平（DBA干預）暫時足以幫助實現性能和可擴展性之間的平衡（第二、三類）。

（更多信息請點擊閱讀原論文。）