作者：孫宇熙

很多現實世界中的應用場景都可以用圖來表達，特別是應用數據可以以網絡化的模式來表達的時候，從交通道路網絡、電話交換網絡、電網、社交網絡到金融交易網絡。如果您沒有關注過相關的領域，您可能會驚詫于圖的技術得到了多么廣泛的應用。業界很多赫赫有名的公司都是基于圖技術而構建的，例如：

• 谷歌：PageRank 是一種大規模頁面（或鏈接）排序的算法，可以說，早期谷歌的核心技術就是一種淺層的并發圖計算技術。
• 臉書：臉書的技術框架的核心是它的 Social Graph，即朋友關聯朋友再關聯朋友。在任意兩個人之間通過 5 或 6 個人就可以建立聯系。臉書開源了很多東西，但是這個核心的圖計算引擎與架構從未開源過。
• 推特：推特它曾經在 2014 年短暫的在 Github 上面開源了 FlockDB 項目，但隨后就下線了，原因很簡單，圖計算是推特的商業與技術核心，開源模式沒有增加其商業價值——換句話說，任何商業公司的核心技術與機密如果構建在開源之上，其商業價值形同虛設。
• 領英（LinkedIn）：領英是專業職場社交網絡，特點是推薦距離你 2 層至 3 層的專家，提供這種推薦服務必須使用到圖計算引擎（或圖數據庫）。
• 高盛集團：在 2007-2008 年爆發的美國次貸危機中，萊曼兄弟公司破產，而高盛集團全身而退，背后的真實原因是高盛集團擁有強有力的圖數據庫系統—— SecDB，它成功計算并預測到即將發生的金融危機。
• Paypal、E-bay和許多其他金融或電子商務公司：圖計算可以幫助他們揭示出數據的內部關聯，而傳統的關系型數據庫或大數據技術實在是太慢了，它們在設計之初就不是用來處理數據間的深度關聯關系的。

Diagram-0：典型的社交網絡圖譜（實時生成的子圖）

上面這張配圖（Diagram-0）展示了一個典型的社交圖網絡的局部。它實際上是在一張大圖上進行的實時路徑查詢所生成的一張子圖。綠色的節點為初始頂點，紫色的節點為終止頂點，兩者間有 15 層間隔，并有 100 條關聯路徑，每條路徑上有不同類型的邊連接著相鄰的兩兩的頂點，其中不同類型（屬性）的邊以不同的色彩來渲染，以表達不同類型的社交關系（幫助、喜歡、愛情、合作、競爭等等）。

圖的數據結構大體包含 3 種類型的數據：

1. 頂點（vertex，復數：vertices），也被稱作點、節點（node），頂點可以有多個屬性，下面的邊也一樣，有鑒于此，某個類型的頂點的集合可以看作類似于傳統數據庫中的一張表，而頂點間的基于路徑或屬性的關聯操作則可看作是傳統關系型數據庫中的表連接（table-join）操作，區別在于圖上面的 join 操作的效率指數級高于 SQL;
2. 邊（edge），也稱作關系（relationship），一般情況下一條邊會連接兩個頂點，兩個點的排列順序可以表明邊的方向，而無向邊通常通過雙向邊來表達，所以 A-B = A↔B = A←B + B→A。而那種特殊類型的可以關聯多個（>=3）頂點的邊，一般都被拆解為兩兩頂點相連的多條邊來表達；
3. 路徑（path），表達的是一組相連的頂點與邊的組合，多條路徑可以構成一張網絡，也稱作子圖，多張子圖的全集合則構成了一張完整的圖數據集，我們稱之為“全圖”。很顯然，點和邊這兩大基礎數據類型的排列、組合就可以表達圖上面的全部數據模型。

圖中的數據類型的表達：

• 頂點：v, v, w, a, b, c…
• 邊：(u, v)
• 路徑：(u, v), (v, w), (w, a), (a, j)… …

注意，上面的邊的表達形式 (u, v) 通常代表有向邊，也就是說邊的方向是從 u 指向 v，我們也稱 u 為 out-node（出點），v 為 in-node（入點）。無向圖中的無向邊通常通過雙向有向邊來表達，在數據結構中不同的設計方案有不同的表達方式，例如在二維相鄰矩陣中，如果行、列相交的頂點中行 u 為出點，列 v 為入點，那么矩陣中的對應的交點表達的是從行出點 u 到列入點 v 的一條有向邊，另一條反方向的邊則是從行出點 v 到列入點 u 的有向邊。而在下面將要介紹到的相鄰哈希的數據結構中，這個表達相對更為簡易，(u, v, 1) 和 (v, u, -1) 分別表達了 u→v 和 v→u 兩條邊。在相鄰鏈表數據結構中，則從 u 出發存在最終指向 v 的某條鏈接（鏈路），反之亦然。之所以要表達反向邊的一個原因是如果不存在從 v 到 u 的邊，那么在圖上（路徑）查詢的時候，將不會找到從 v 出發可以直接到達 u 的任何邊，也就意味著圖的連通度受到了破壞——或者說數據結構的表達沒有反映出真實的頂點間的路網連接情況！

傳統意義上，表達圖的數據結構有兩類:

• 相鄰矩陣，源自英文 Adjacency Matrix
• 相鄰鏈表，英文 Adjacency List

簡單而言，相鄰矩陣是一個二維的矩陣，在計算機科學語境下，一個二維數組中的每個元素都代表了圖中是否存在著兩個頂點之間的一條邊。

相鄰鏈表用了一種迥然不同的方式來表達圖上的連接關系，如下圖（Diagram-1）所示，左側的有向（并帶權重的邊）圖用右側的相鄰鏈表表達，它包含了第一層的“數組”其中每個元素對應圖中的一個頂點，第二層則是每個頂點的邊所直接關聯的頂點構成的鏈表。注意，右側的相鄰表中只是表達了有向圖中的單向邊，如果從頂點 4 出發，只能抵達頂點 5，卻無從知道頂點 3 可以抵達頂點 4，除非用全圖遍歷的方式搜索，那樣的話效率會相當低下。當然，解決這一問題的另一種方式是在鏈表中也插入反向邊和頂點，類似于上文中提及的相鄰哈希中如何來表達反向邊。

Diagram-1：用相鄰鏈表來表達有向圖（單向邊）

如果 Diagram-1 中的有向圖用相鄰矩陣來表達，每條邊需要用矩陣中的一個元素來對應行、列中一個頂點，其中矩陣是 6x6 的，并且其中只有 7 個元素（7 條邊）是被賦值的。很顯然，這是一個相當稀疏的矩陣，占滿率只有 (7/36) < 20%，然而它所需要的最小存儲空間則為 36 字節（每個字節可以表達每條邊的權重）。如果是一張有 100 萬頂點的圖，其所需的存儲空間至少為 100GB（1M*1M = 1萬億字節），而這在工業界中只是屬于小圖的范疇的。

Diagram-2：用相鄰矩陣來表達有向圖

也許讀者會質疑以上相鄰矩陣的存儲空間的估算被夸大了，那么我們來探討一下：如果每個矩陣中的元素可以用 1 個比特位來表達 ，那么 100 萬頂點的全圖存儲空間可以降低到 125GB。然而，我們是假設用 1 個字節來表達邊的權重，如果這個權重的數值范圍超過 256，我們或許需要 2 個字節、4 個字節甚至 8 個字節，如果邊還有其它多個屬性，那么對于存儲空間就會有更大的甚至不可想象的需求。

現代的 GPU 是以善于處理矩陣運算而聞名的，不過通常二維矩陣的大小被限定在小于 32K（32,768）頂點。這是可以理解的，因為 32K 頂點的內存存儲空間已經達到 1GB+ 了，而這已經占到了 GPU 內存的 25-50%。換句話說，GPU 并不適合用做大圖上面的運算，除非使用極其復雜的圖上的 Map-Reduce 的方式來對大圖進行切割、分片來實現分而治之、串行的或并發的處理方式——但是你真的覺得這種分片、切圖的處理方式的效率會很高嗎？

存儲低效性或許是相鄰矩陣最大的敵人。這也許可以解釋為什么在學術界以外，尤其是工業界，很少用到真正意義上的相鄰矩陣來對真實世界的問題進行數據建模。盡管它有著 O(1) 的訪問時間復雜度。

相比而言，相鄰鏈表對于存儲空間的需求要小得多，在工業界中的應用也更為廣泛。例如臉書的社交圖譜（其底層的技術架構代碼為 Tao/Dragon）采用的就是相鄰鏈表的方式。鏈表中每個頂點表示一個人，而每個頂點下的鏈表表達的是這個人的朋友或關注者。這種設計方式很容易被理解，但是它可能會遇到熱點處理效率的問題，例如如果一個頂點有 1 萬個鄰居，那么鏈表的長度有 10,000 步，遍歷這個鏈表的時間復雜度用 Big-O Notation 來表達為 O(10,000)。在鏈表上的增刪改查的操作都是一樣的復雜度，更準確的說，平均復雜度為 O(5,000)。另一個角度來看，鏈表的并發能力很糟糕，你無法對于一個鏈表進行并發（寫）操作！

現在，讓我們思考一個方法，一種數據結構可以平衡兩件事情：

• 存儲空間：相對而言可控的、占用更小的存儲空間來存放更大量的數據  
• 訪問速度：低訪問延遲，并且對于并發訪問友好

在存儲維度，我們要盡量避免使用那種稀疏的，利用率低下的數據結構，因為大量的空數據占用了大量的空閑空間，以相鄰矩陣為例，它只適合用于那種拓撲結構非常密集的圖，例如全聯通圖（所謂全聯通指的是圖中任意兩個頂點都直接關聯）上面提到的 6 頂點的圖，如果全部聯通，則至少存在 30 條有向邊 = 2*6*5/2，如果還存在自己指向自己的邊，或頂點對間存在多條邊，則存在至少 36 條邊，那么用相鄰矩陣表達的是數據結構是節省存儲空間的。然而，實際應用場景中，絕大多數的圖都是非常稀疏的（我們用圖的密度 = (邊數/全聯通圖的邊數) * 100% 來衡量，大多數圖的密度遠低于 5%），因此相鄰矩陣就顯得很低效了。

相鄰鏈表在存儲空間上是大幅節省的，然而鏈表的設計存在訪問延遲大，并發訪問不友好等問題，因此突破點應該在于：如何取代鏈表為中心的數據結構設計方式。

在這里，我們設計并命名了一種新的數據結構：相鄰哈希（英文：Adjacency Hash 或 Adjacency Hash<*>）。它具有如下的特點：

• 定位圖中任意頂點的時耗恒定為 O(1)
• 定位圖中任意邊的延遲為 O(2)

以上時耗的復雜度假設可以通過某種哈希函數來實現，最簡單的例如通過數組下標訪問具體的點、邊元素來實現，對于邊而言僅需定位 out-node+in-node，時耗為 O(1+1)。

在 C++ 中，面向以上的特點的數據結構，最簡單粗暴的實現方式為，動態向量數組（Array of Vectors）：

// Array of vectors

Vector <pair<int,int>> a_of_v[n];   

動態向量數組可以實現極低的訪問延遲，并且有很低的存儲空間浪費，但是卻并不能解決另外的幾個問題：

• 并發訪問支持
• 數據刪除時的額外代價（例如存儲空白空間回填等）

在工業界中，典型的高性能哈希表的實現有例如谷歌的 SparseHash 庫，它實現了一種叫做 dense_hash_map 的哈希表。在 C++ 標準 11 中實現了 unordered_map，是一種鎖鏈式的哈希表，它通過犧牲一定的存儲空間來獲取快速尋址性能。但是以上兩種實現的問題是，他們都沒有和底層的硬件（CPU 內核）并發算力同步的擴張能力，換句話說是一種單線程哈希表實現，任何時刻只有單讀或單寫進程占據全部的表資源——這或許可以算作是對底層資源的一種浪費吧。

在高性能云計算環境下，通過并發計算可以獲得更高的系統吞吐率，通常這也意味著底層的數據結構是支持并發的（concurrent data structure），并且能利用多核 CPU、每核多線程，并能利用多機（無論是物理上還是邏輯上的）協同并發的針對一個邏輯上的大數據集進行并發處理。

傳統的哈希實現幾乎都是單線程、單任務的，意味著它們采用的是阻塞式設計，第二個線程或任務如果試圖訪問同一個資源池，它會被阻塞而等待，以至于無法（實時）完成任務。

從上面的單寫單讀向前進化，很自然的一個小目標是單寫多讀，我們稱之為 single-writer-multiple-reader 的并發哈希，它允許多個讀線程去訪問同一個資源池里的關鍵區域（critical section）。當然，這種設計中只允許任何時刻最多存在一個寫的線程。

單寫多讀的設計實現中通常會使用一些技術手段，例如：

• Versioning：中文稱為版本號記錄
• RCU (Read-Copy-Update)：中文稱為讀-拷貝-更新
• Open-Addressing：中文稱為開放式尋址

以 RCU 為例，Linux 操作系統的內核中首先使用了這種技術來支持多讀。在 MemC3/Cuckoo 哈希實現中則使用了開放尋址技術，如圖 Diagram-3 所示。

Diagram-3：Cuckoo 哈希的鍵被映射到了 2 個桶中以及使用了 1 個版本計數器

沿著上面的思路繼續向前迭代，我們當然希望可以實現多讀多寫的真正意義上的高并發數據結構。但是，這個愿景似乎與 ACID（數據強一致性）的要求相違背—在商用場景中，多個任務或線程在同一時間對同一個數據進行寫、讀等操作而可能造成的數據不一致而導致的混亂的問題。下面我們來把以上的挑戰和問題細化后逐一解決。

實現可擴展的高并發哈希數據結構需要克服我們在上面提到的幾個主要問題：

• 無阻塞或無鎖式設計（Non-blocking and Lock-Free）
• 精細顆粒度的訪問控制（Fine-granularity Access Control）

要突破并實現上面提到的兩條，兩者都和并發訪問控制高度相關，有如下的要點需要考量：

• 核心區域（訪問控制）：
  • 區域足夠小
  • 執行時間足夠短
• 通用數據訪問：
  • 避免不必要的訪問（Unnecessary）
  • 避免無意識的訪問（Unintentional）
• 并發控制：
  • 使用精細顆粒度的鎖實現，例如 lock-striping（條紋鎖）
  • 采用推測式上鎖機制，例如交易過程中的合并鎖機制（Transactional Lock Elision）

Diagram-4: 隨機放置vs.基于BFS的雙向集合關聯式哈希

對于一個高并發系統而言，它通常會至少包含如下三套機制協同工作才能實現充分的并發：

• 并發的基礎架構
• 并發的數據結構
• 并發的算法實現

以上三者，在圖數據庫、圖計算與存儲引擎系統的設計中更是缺一不可。

并發的基礎架構包含有硬件和軟件的基礎架構，例如英特爾的中央處理器的 TSX (Transactional Synchronization Extensions，交易同步擴展）功能是硬件級別的在英特爾 64 位架構之上的交易型內存支持。在軟件層面，應用程序可以把一段代碼聲明為一筆交易，而在這段代碼執行期間的操作為原子操作。像 TSX 這樣的功能可以實現平均達到 140% 的性能加速。這也是 Intel 推出的相對于其它 X86 架構處理器的一種競爭優勢。當然這種硬件功能對于代碼而言不完全是透明的，它在一定程度上也增加了編程的復雜度和程序的跨平臺遷移復雜度。

在軟件層面，更多的考量是操作系統本身對于高并發的支持，通常我們認為 Linux 操作系統在內核到庫級別對于并發的支持要好于 Windows 操作系統，盡管這個并不絕對，甚至是很多的底層實現，例如虛擬化、容器等的實現讓上層的應用程序對于底層的直接依賴性得以降低。 

另一方面，有了并發的數據結構，在代碼編程層面，你依然需要設計代碼邏輯、算法邏輯來充分的利用和釋放并發的數據處理能力。特別是對于圖數據集和圖數據結構而言，并發對于程序員而言是一種思路的轉變，充分的利用并發的能力，你可能可以獲得成百上千倍的性能提升，在同樣的硬件資源基礎上，在同樣的數據結構基礎上，在同樣的編程語言實現上，永遠不要忽略并發實現的意義和價值。

Diagram-5：嬴圖的基于高并發哈希實現的實時深度圖遍歷

上圖（Diagram-5）當中展示了在嬴圖之上，一款高性能、高并發實時圖數據庫服務器，通過高并發架構、數據結構以及圖算法實現的高性能K鄰操作的性能。

K鄰（英文 K-Hop）操作通常是通過 BFS（廣度優先搜索）的方式實現的。圖中的測試數據和結果是在一個常見的用于性能評測的圖數據集上（例如 Amazon 0601 數據集，有 340 萬條邊和 41 萬頂點）實現的，從任一頂點出發計算與它的最短距離為 K 步的鄰居的數量（和鄰居集合），直到找完圖中最深的鄰居后沒有新鄰居發現后返回。

注：在商用場景中圖的大小通常在百萬、千萬、億甚至十億以上的數量級，而學術界中用于發論文的圖數據集的數量級則經常在千、萬的數量級，兩者之間存在著由量變到引發質變的區別——特別對于算法復雜度和數據結構的并發駕馭能力而言，讀者需要對此注意區分和甄別。以 Dijkstra’s 最短路徑算法為例，它的原生算法完全是串行的，在小圖當中或許還可以通過對全圖進行全量計算來實現，在大圖之上則完全不具有可行性！

Diagram-6：K鄰并發算法

BFS 是相對于 DFS（深度優先搜索）或其它圖上算法（例如魯汶社區識別等）而言比較容易實現并發計算的，上圖（Diagram-6）中形象的解析了如何在圖中實現 BFS 算法并發。我們以 BFS 為例為讀者解讀如何實現高并發。

K鄰并發算法步驟如下：

1. 在圖中定位起始頂點（上圖中的綠色頂點），計算其直接關聯的具有唯一性的鄰居數量。如果 K=1，直接返回鄰居數量；否則，執行下一步。
2. K>=2, 確定參與并發計算的資源量，并根據第一步中返回的鄰居數量決定每個并發線程（任務）所需處理的任務量大小，進入第三步。
3. 每個任務進一步以分而治之的方式，計算當前面對的（被分配）頂點的鄰居數量，以遞歸的方式前進，直到滿足深度為K或者無新的鄰居頂點可以被返回而退出，結束。

基于以上的算法描述，我們再來回顧一下 Diagram-5 中的實現效果，當K鄰計算深度為 1-2 層的時候，內存計算引擎在微秒級內完成計算。從第 3 跳開始，返回的鄰居數量呈現指數級快速上漲（2-Hop 鄰居 ~200，3-Hop 鄰居 ~8000，4-Hop 鄰居接近 5 萬）的趨勢，這就意味著計算復雜度也等比上漲。但是，通過飽滿的并發操作，系統的延時保持在了相對低的水平，并呈現了線性甚至亞線性的增長趨勢（而不是指數級增長趨勢！），特別是在搜索深度第 6 層到第 17 層的區間內，系統時延幾乎穩定在 ~200ms 的范圍！

注：第 17 層（17-Hop）返回的鄰居數量為 0，因為此時全圖（聯通子圖）已經遍歷完畢，沒有找到任何深度達到 17 層的頂點鄰居，因此返回結果集合大小為 0。

如果我們做一個 1 比 1 的對標，同樣的數據集，在同樣的硬件配置的公有云服務器上用 Neo4j 來做同樣的K鄰操作，效果如下：

• 1-Hop：~200毫秒，比嬴圖慢了 1,000倍！
• 從 5-Hop 開始，幾乎無法實時返回（系統內存資源耗盡前未能返回結果）
• K鄰的結果默認情況下沒有去重。有大量重復鄰居頂點在結果集中。
• 隨著搜索深度的增加，返回時間和系統消耗呈現指數級（超線性）增長趨勢。
• 最大并發為 400%（4 線程并發），遠低于嬴圖的 6400% 并發規模。

Diagram-7：Neo4j 數據庫的圖遍歷性能

基于 Neo4j 的實驗，我們只進行到 7-Hop 后就不得不終止了，因為 7 跳的時候系統耗時超過 10 秒鐘，從 8 跳開始 Neo4J 幾乎不可能返回結果。而最大的問題是計算結果并不正確，這種不正確包含兩個維度：

• 重復頂點未被去重
• 頂點深度計算錯誤

K-hop 中返回的應該是最短路徑條件下的鄰居，那么如果第一層的直接鄰居中已經被返回的頂點，不可能也不應該出現在第二層或第三層或其它層級的鄰居列表中！很明顯 Neo4J，還有其它一些圖數據庫（例如騰訊的星圖）在 K-hop 的實現中沒有遵循 BFS 的原則（或者是實現算法錯誤），也沒有實現去重，甚至沒有辦法返回（任意深度）全部的鄰居。

注：在更大的數據集中，例如 Twitter 的 15 億條邊、4200 萬頂點、26GB 大小的社交數據集中，K-hop 的操作的挑戰更加巨大，我們已知的很多圖數據庫都無法在其上完成深度（>=3）的 K-hop 查詢，例如 Neo4J、JanusGraph、Titan、亞馬遜的Neptune、ArangoDB、百度的 HugeGraph 等。而在能完成的為數不多的幾個圖數據庫中，嬴圖也指數級快于其它玩家。具體指標參考下圖。

Diagram-8：性能評測對標 - 嬴圖 vs. Neo4J vs. Tiger Graph

如果讀者對于本文中提及的嬴圖的實現中所用到的 Adjacency Hash<*> 數據結構的設計與實現的細節感興趣，可以在國家知識產權局的數據庫中查詢嬴圖團隊提交的相關專利（專利號2020****5644）或聯系我們索取。

Diagram-9：嬴圖的二維和三維可視化

值得補充一點的是，盡管性能對于圖數據庫、圖計算而言甚為重要，可視化功能也不可忽略。因為相比于傳統的關系型數據庫的二維表中的行 vs. 列的結構，圖是高維度的、更直觀的、可解釋的，圖中的運算結果的可視化是非常必要、甚至是必須的。這也是為什么我們提出了一個觀點：白盒化 AI、可解釋 AI需要通過知識圖譜 + 圖數據庫來實現，前者本質上就是交互可視化，而它基于的是后者的算力突破！上圖中展示的是 嬴圖Manager（嬴圖數據庫集成的可視化前端操作界面&圖數據庫、圖譜管理平臺）中的對圖上實時計算的 2D 和 3D 可視化效果。

到這里，我們來總結一下圖數據結構的演化：更高的吞吐率可以通過更高的并發來實現，而這可以貫穿整個數據的全生命周期：

• 數據導入、加載（Data Ingestion）
• 數據轉換（Data Transformation）
• 數據計算（無論是K鄰還是路徑還是…）
• 基于批處理的操作、圖算法等

另外，內存消耗也是一個不可忽略的存儲要素，盡管我們這幾年都紛紛開始宣稱內存就是新的硬盤，它的性能指數級高于固態硬盤或磁盤，但是，它并不是沒有成本的，因此審慎的內存使用是必要的，例如以下的降低內存消耗的策略：

• 基于數據加速的數據建模（Data Modeling for Data Acceleration）
• 數據壓縮與數據去重（Data Compression & De-duplication）
• 算法實現與代碼編程中避免過多的數據膨脹、數據拷貝等操作

希望讀者能從本文中獲取一些有用的信息，那么我們最早決定寫這篇文章的目的就已經達到了。另外，我們克制了在文章中加入大量數學公式的沖動，目的只是為了讓你可以不必犧牲大量腦細胞的條件下讀懂本文。畢竟，數據結構和軟件工程不是博士們的專利。