圖資料庫和圖計算系統有什麼區別？

對於廣大剛剛接觸“圖數據分析”的用戶而言，一個十分具有迷惑性的問題是：圖資料庫和圖計算系統有什麼區別？今天，我們就從技術層面來簡單地說一說兩者的不同之處。圖資料庫適合需要對子圖進行併發操作的場景；圖計算系統適合需要對全圖進行迭代式計算的場景。圖計算系統我們先從圖計算系統開始。圖計算系統面向的 ...

對於廣大剛剛接觸“圖數據分析”的用戶而言，一個十分具有迷惑性的問題是：圖資料庫和圖計算系統有什麼區別？今天，我們就從技術層面來簡單地說一說兩者的不同之處。

圖資料庫適合需要對子圖進行併發操作的場景；圖計算系統適合需要對全圖進行迭代式計算的場景。

圖計算系統

我們先從圖計算系統開始。

圖計算系統面向的場景主要是全圖分析類的任務，例如：計算每個頂點的PageRank；計算從某（幾）個頂點出發到其它所有頂點的最短路徑；獲悉整個圖包含了哪些連通分量；發現圖中包含的社區等等。這些任務背後的演算法需要對整個圖進行迭代式的處理，而計算過程中我們需要在每個頂點上維護一些狀態（變數），根據邊向鄰居頂點傳遞消息，並依據收到的消息再更新頂點的狀態。

由於這些計算面向的通常是靜態的拓撲結構，因此圖計算系統一般都會使用緊湊的表示方法來管理圖數據，例如使用稀疏矩陣表示中常見的CSR/CSC（Compressed Sparse Row/Column）等格式。這樣做的優勢很明顯：減少了讀取時需要訪問的數據量，且不必/不太需要考慮併發修改拓撲結構引入的開銷。誠然，這樣做會導致一個顯著的缺陷：無法/只能以高昂的代價來修改圖的拓撲結構。幸運的是，我們已知的大多數圖計算問題都不需要或者可以通過其它方式來避免修改圖的拓撲結構[1]。

[1]儘管有些分析過程如強連通分量、最小生成樹等，會在計算過程中刪除某些頂點/邊，但是這類操作可以通過標記的方式來提示相應對象的刪除，而無需真的修改圖的拓撲結構。

靜態的拓撲結構使得我們可以應用很多技術來優化圖計算的過程：例如，將一個大圖劃分成若幹較小的子圖並分配給不同的計算單元（節點/處理器/核/線程）進行並行處理；根據每一輪迭代的特點使用不同的方式來驅動計算/通信過程等等。當然，可選的技術細節較多也意味著最終的系統可能由於任何一個環節的拖累導致糟糕的性能；甚至很多原本的優化沒有產生良好的化學反應反倒變成了弱化[2]。

[2]圖的劃分就是一個簡單的例子：複雜的劃分策略有可能減少分散式計算過程中的通信量，但是帶來的代價是高昂的預處理開銷以及頂點映射表的維護和頻繁使用。PandaGraph使用的塊式劃分十分簡單，卻能有效地避免這些不必要的開銷。

圖資料庫

圖資料庫的主要職能是管理圖數據，因此需要支持高效的對頂點/邊的查詢與更新；為了方便用戶的使用，通常還需要增加對事務（transaction）的支持，從而保證併發操作下的正常運作。

持久化是所有資料庫的立足之本。由於圖的拓撲結構以及頂點/邊上依附的屬性數據可能會不斷發生改變，因此圖資料庫就不適合使用CSR/CSC之類的表示方法來管理圖數據了：即使它們的讀取效率非常高，但是寫入效率實在太低了（即使只修改一條邊，最壞情況下也可能需要改寫整個圖的數據）。因此，圖資料庫需要採用讀/寫效率更均衡的存儲結構，例如B+樹、LSM樹、鏈表、哈希表等。儘管這麼做會使得讀取效率在所難免地有一定下降，但換來的是高效得多的寫入性能。

基於使用的存儲結構，我們還需要在此之上構建完善的併發控制機制來管理對圖中頂點/邊的併發訪問。這使得我們不得不在每次操作中存儲一部分額外的信息（例如樂觀併發控制需要的讀寫集、多版本併發控制產生的多份數據）或是觸及一些需要競爭的資源（例如悲觀併發控制中的鎖），而這些都會或多或少地在訪問圖資料庫中的數據對象時引入一定開銷。

在圖資料庫中進行的分析通常都只涉及一小部分子圖的數據，例如從一個頂點出發找所有的幾度內鄰居，或是給定兩個頂點找出它們之間限定距離的最短路徑等等。這些任務都很輕量級，且可能會同時有大量請求併發進入系統。因此，使用單個線程處理單個任務是比較常見的做法，這樣能夠獲得更高的吞吐率，且避免了由並行處理的調度/同步引發的開銷[3]。這與圖計算系統對每個任務都使用並行處理的方式形成了鮮明的對比。又由於每個任務的處理時間可能很短，因此其它部分的開銷例如客戶端與伺服器端之間的通信效率等等也會變得十分重要（例如Restful的介面在有些場景下就會變成瓶頸）。

[3]隨著圖數據的增大，以及涉及子圖區域的增大，這類輕量級任務也會逐漸變得重量級，此時，使用並行處理的方式減少延遲也是十分重要的。LightGraph提供了對單個只讀事務進行並行處理的能力；對於時間消耗過長的任務，用戶也可以通過相應介面提前中止。

總結

圖計算系統面向的任務通常具有更高的複雜度，需要對整個圖進行反覆的訪問來完成計算；而圖資料庫，無論是更新還是分析，通常都只涉及一部分子圖的數據，且單個任務一般只需訪問一遍即可。因此，圖計算系統通常採用不可變（immutable）的數據佈局，使得讀取效率可以最大化，但是需要更精細地安排和組織並行的處理過程；圖資料庫則不得不選擇讀/寫性能更均衡的存儲方式來管理數據，並從併發控制、訪問介面等眾多角度儘可能地減少系統設計和實現引入的開銷。