導讀：本次分享主題為圖數據庫存儲技術及實踐，將介紹創鄰科技在多年實踐和優化中對圖數據庫存儲技術的一些思考。主要包括以下幾大部分：

圖數據庫簡介

該章節我們主要介紹為什么需要圖數據庫？它能夠應用在什么場景，主要解決的問題是什么？以及什么是圖數據庫？

圖數據庫存儲核心目標

該章節主要介紹圖數據庫較傳統關系型數據庫的深鏈查詢優勢，以及圖數據庫存儲系統設計的核心目標。

圖數據庫存儲技術方案

該章節主要介紹了數組、鏈表、LSM樹三種存儲方式的優劣勢，在實際實現一個圖數據庫的過程中，應根據使用場景和設計理念去做取舍。

Galaxybase圖數據庫應用實踐

最后，該章節介紹原生分布式并行圖數據庫Galaxybase，涉及其優勢特點、存儲架構、性能優勢、生態和客戶案例等信息。

01圖數據庫簡介

1. 關聯是不可逆的趨勢

世界萬物是普遍聯系的，Internet帶來了信息的聯通，IoT帶來了設備的聯通，微信、微博、抖音、快手等APP將線下的社會關系轉移到了線上，形成更加廣泛的人際關系的聯通。隨著社交、零售、金融、電信、物流等行業的快速發展，在人們的生產生活中，每時每刻都產生著大量的數據，促使當今社會支起了一張龐大而復雜的關系網。隨著技術的發展，我們對這些數據的分析和使用，不再局限于從統計角度分析相關性，而是希望從關聯的角度，揭示數據的因果聯系。

2.關聯分析的場景

在社交網絡場景中，我們可以通過粉絲對KOL的關注、點贊、評論、轉發等多種關系，快速確定和品牌調性契合度較高的KOL，從而實現精準營銷。在好友推薦、輿情追蹤等場景也可以運用關聯分析的方法。

在金融場景中，我們可以使用關聯分析的方法來判斷信用卡欺詐團伙，具體方法是把和申請件相關的申請人、聯系人、推薦人，以及他們的手機地址、郵箱，還有申請件提交時使用的設備ip、cookie等信息，放到一張相互關聯的網絡中，就可以通過關聯分析來找到異常的欺詐網絡。在金融場景中，還有一種天然的網絡，就是賬號之間的轉賬網絡。過去如果想隱藏一筆資金的真實流向，最基本的操作就是把這筆資金分散成很多小的資金，然后通過賬號之間的多次轉手之后再匯總到目標帳戶，傳統的分析方法很難對這樣的轉賬操作進行高效的追蹤分析，而使用關聯分析的方法就可以把資金的流向分析得一目了然。

在零售環境中，我們可以通過構建商品知識圖譜，并加入用戶信息、用戶消費信息關聯商品知識圖譜，從而可以實現360度的用戶畫像、商品的實時推薦，以及反薅羊毛等業務場景。

在電力系統中，基于發電廠、變電站、線路段開關等電氣設備組成的天然的電網拓撲，可以實現電網調度的實施仿真，還有故障分析，降低由于研判時間較長帶來的停電時間，并可以計算出每一度使用的電當中，清潔能源和化石能源所占比例，為企業及時調整用電結構助力。

在電信場景中，電話號碼之間的主叫和被叫關系也是一張天然的網絡。通過分析不同呼叫方式的網絡模型，也可以非常容易地判斷出某次呼叫是一個正常通話還是一個騷擾電話，甚至是詐騙電話。因為壞人會頻繁更換號碼，所以通過黑名單的方式來攔截它的滯后性比較高，而通過網絡關聯分析的方法，可以迅速識別出不正常的呼叫形式。

在政企應用的場景中，可以通過關聯分析實現道路規劃、智能交通，還通過打通各個來源的數據信息，可以實現疫情的精準防控。

在制造業領域，可以通過建立實時的供應鏈網絡來進行供應鏈管理、物流優化、產品溯源。

在網絡安全領域，可以通過追蹤成千上萬個IP地址之間的調用關系，來尋找一次網絡攻擊的真正源頭，也可以分析調用鏈路上的薄弱環節，防患于未然。

世界萬物是普遍聯系的，如果能夠妥善地刻畫和分析這些聯系，我們就可以發現關聯分析幾乎能運用到生產生活的方方面面。前面列舉的只是關聯分析的一些常見場景，其應用遠遠不止這些，還有很多其他的場景，比如企業的股權穿透，公安的案情分析，生物醫藥領域的基因分析和新藥研發等。

3. 關聯分析的難題

前面提到的很多場景背后都涉及到數據量的問題。在以上場景中，我們遇到的數據量都非常巨大。比如一個典型的社交網絡中，光是自然人的數量就有十億數量級，再加發帖、評論、話題這些實體，總的實體數量很容易達到百億的規模，而這些實體之間關系的數量可以達到千億甚至萬億的規模。又比如轉賬網絡，賬戶實體數量可能在幾億至幾十億量級，但是賬戶間的轉賬關系可能是賬戶數量的幾百甚至上千倍，也能達到萬億規模。其他像零售場景，反映的是用戶每次瀏覽、咨詢、下單這些關聯的動作。電信網絡中要反映每次電話中的主叫和被叫的關系。不難想像，在這些場景中，我們所面對的數據量都是天文數字。處理這樣規模的數據肯定需要依靠專業產品，而不是簡單自己寫幾個程序就能解決的。

在這樣的大規模數據中，關聯分析通常還要處理較深的關聯跳數。在這里，跳數是指在網絡中從一個實體出發，要經過多少次找鄰居的操作才能到達目標實體。在不同的關聯分析場景中，由于數據模型不同，常見的關聯跳數也不同，少則5-6跳，多則20-30跳。在關系型數據庫，這樣的關聯操作是用Join操作來完成的。在關系代數中，Join的本質是做笛卡爾積。在這樣的大規模數據中進行Join操作，對系統資源的要求高，而查詢的響應時間通常會比較久。當然，我們有各種優化校驗的方式，比如建索引、排序合并和哈希Join等，然而在很多生產編碼規范中，都不允許對3張以上的表進行多表Join，也就無法進行3跳以上的關聯分析。

除了數據規模大，關聯跳數深以外，關聯分析還有一個特性就是實時要求高。比如電信欺詐問題，我們接到一個詐騙電話，最好是在幾秒內甚至是還正在響鈴還沒有接起電話時，就能進行詐騙預警。如果把這些呼叫數據拿出來，放到離線分析系統中跑批計算，得到結果可能已經是一周以后了，這樣起不到防范效果。又比如疫情精準防控，也是越快越準地定位密接人群，效果就越好。在這些數據規模大、關聯跳數深、實時要求高的場景中，傳統的數據存儲、查詢、分析、計算方式都不能很好地完成任務。

4. 圖數據庫基本概念

為解決以上問題，我們需要圖數據庫。按照維基百科的定義，圖數據庫是一個使用圖結構進行語義查詢的數據庫，它使用點、邊和屬性來表示和存儲數據。

這里的圖指的是圖論中的graph，由點和邊組成，G=（V，E）。在實際使用場景中，點用來表示實體，邊用來表示關系，可以是有向的，也可以是無向的。目前主流的圖數據庫使用的都是屬性圖模型（Property Graph Model），也就是除了點和邊以外，在點和邊上還可以附帶任意多數量的屬性。一個屬性可以理解為一個鍵值對。有了屬性之后，圖數據庫的表達能力大大增強了，幾乎可以描述現實場景中任何數據形態。

02圖數據庫存儲核心目標

接下來探討一下圖數據庫存儲的核心目標，也就是圖數據庫存儲需要解決的根本問題。

1. 圖查詢的核心語義

首先來回顧一下，數據規模大、關聯跳數深、實時要求高的場景下，完成一個圖查詢或者圖分析，要進行的核心操作是什么。單獨的訪問點和邊，以及上面的屬性并不是這里的關鍵。在關聯分析中，最核心的操作是鄰居的迭代遍歷。這也解釋了為什么關系型數據庫進行這個操作的時候性能不佳：因為在關系型數據庫中，邊（也就是實體之間的關系）并不是直接存儲的，而是以外鍵的形式來表示。從實現功能的角度，我們完全可以底層使用關系型數據庫，對外暴露一個具備圖語義的抽象接口，讓用戶能夠進行點邊和屬性的查詢，但是這樣做的性能是無法達到使用要求的，即便在主鍵和外鍵上都建立了索引，在面臨大規模數據的時候，或者查詢跳數比較深的時候，索引對性能的提升也是非常有限的。

2. 深鏈查詢性能對比

上表中用who-trust-whom公開數據集，對比了多關聯跳數在關系數據庫的查詢時間（不加索引、加索引）和圖數據庫的查詢時間。

首先對比加索引和不加索引的情況，可以看出，在2跳的時候，加索引是能夠明顯提升查詢速度的，3跳的時候提升就不多了，到4跳的時候加不加索引都已經變得很慢了。而使用圖數據庫，查詢性能可以一直保持在非常快的水平。

3. 免索引鄰接（Index Free Adjacency）

圖數據庫存儲的核心目標是實現免索引鄰接。

在寫入時，免索引鄰接可以保證一個點和與它直接相鄰的邊總是存儲在一起。因此查詢時迭代遍歷一個點的所有鄰居就可以直接進行，而不需要依賴其他索引類的數據結構。和依賴于一個全局索引相比，免索引鄰接會讓鄰居遍歷操作每一次迭代的時間復雜度降為O(1)，也就是說不需要任何其他操作就能直接進行迭代。因此迭代一個點的所有鄰居的時間，就是這個點的鄰居數量乘以O(1)，僅與這個點自己的鄰居數量有關，而與整個圖中全體的點邊數量是無關的。如果使用全局索引，那么每次定位都需要一個O(log(n))的時間復雜度。這里的n是參與全局索引的數據規模，可以理解為整體的邊數量。因此迭代一個點的所有鄰接的時間，就是這個點的鄰居數量乘以O(log(n))。

這樣我們從算法的時間度復雜度上看，O(log(n))已經是非常快的，但是當我們處理非常巨大的數據量時，這個值也會非常可觀。另外還需要注意的是，log(n)的值會隨著n的增大而不斷增大。假設圖中一個點只有一個鄰居，若使用全局索引，它也是會隨著圖中的總邊數增加而越來越慢。所以如果具備了免索引鄰接的能力，那么獲取這個鄰居的時間就是一個恒定值，而與全局的圖規模無關。這個特點就會帶來巨大的性能提升。所以我們可以明確，圖數據庫存儲的核心目標就是實現免索引鄰接。

03圖數據庫存儲技術方案

1. 使用數組存儲

首先最直接的方法就是用一個數組，把每一個點上面的所有邊，按照順序一起存儲。點文件就是一系列的點組成，每個點的存儲，包括點的ID、META信息，以及這個點的一系列屬性。每個邊文件中，按照起始點的順序存儲點上對應的邊。每條邊的存儲包括終止點ID、META信息，以及邊的屬性。META信息包括點邊類型、邊方向、實現事務的額外字段等。在這個存儲里，可以直接從起始點遍歷所有的邊數據，它的讀取性能非常高。

但是這樣的存儲方式也需要處理一個很棘手的問題，就是變長數組的問題。變長可能由很多因素導致，比如兩個點的屬性數量可能不一樣，屬性本身內容有可能不一樣，屬性值如果是字符串的話，字符串也是變長的，由于屬性長度不一樣導致每個點的存儲空間也是變長的。所以點文件和邊文件中都會面臨變長數組的問題。

解決思路有兩種，一是用額外的offset來記住存儲位置，另一個就是預先劃分好一些預留空間，用于后續的增長。

2. 使用鏈表存儲

為了徹底解決數組存儲的變長問題，可以改用鏈表方式來存儲。在鏈表的存儲方式中，點文件和邊文件里面存儲的全部都是ID，每個ID都是固定長度的，通過ID可以計算偏移量位置，通過偏移量位置直接讀取數據。因為它能夠通過位置計算ID，偏移量和ID是一一對應的，所以每個點也不用保存自身的ID。

我們再看一下在鏈表存儲中如何進行邊迭代。

首先從點A出發，在點文件中找到首個邊ID：α，去邊文件中找到α對應的偏移量，就能把整條邊數據讀出來。邊數據里，有起始點和終止點，比如這條邊的起始點A、終止點B。下一條邊的偏移量是θ，那么就再找到θ的位置。θ邊讀出來，它是從起始點C到終止點A。這時候點A是處于終止點的位置上，我們找對應終止點的下一條邊，是ω。然后再找ω的偏移量，讀出來，是一個A到D的邊，A在起始點的位置上，下一條邊是NULL，迭代遍歷結束。我們可以看到，鏈表存儲的方式很好地解決了變長的問題。

這看起來是個完美的解決方案，但其實仍存在問題。

在鏈表存儲下，每次迭代時offset的位置是隨機的，不是連續存儲的，因此會有大量的隨機讀操作。而磁盤對隨機讀操作是很不友好的，也就是說雖然時間復雜度是O(1)，但是這個O(1)的單位是磁盤隨機讀的時間。而前面數組方案中的O(1)的單位是磁盤順序讀的時間，這兩者在性能上差別非常大。所以使用鏈表的存儲方法，非常依賴一個高效實現的緩存機制。如果我們能把這個存儲結構在內存中緩存起來，那么在內存中進行隨機訪問的性能會非常高。

3. 使用LSM樹存儲

LSM樹存儲是一種基于順序寫盤、多層結構的KV存儲。

上圖展示了LSM樹讀寫操作的核心流程。一個寫請求進來時，直接寫入內存中的MemTable。如果這個MemTable沒滿，這個寫請求就直接返回了，所以寫請求性能是很高的。當這個MemTable滿了的時候，把它變成Immutable MemTable，同時生成一個新的MemTable供后續的寫請求使用。同時，把Immutable MemTable的內容寫到磁盤上，形成SSTable文件。內存中的MemTable和Immutable MemTable都是按Key排序的，所以SSTable也是按Key排序的。SSTable文件是分層組織的，直接從內存中寫出來的是第0層，當第0層數據達到一定大小之后，就把它跟第1層合并，類似歸并排序。合并出來的第1層文件也是順序寫排的，當第1層達到一定大小也會繼續和下層合并，以此類推。在合并的時候，會清除重復的數據或者被刪除的數據。

在讀取請求來的時候，首先去內存中的MemTable查找，查到就直接返回。沒查到就去第0層的文件中查找，第0層沒有再到第1層，這樣逐層查找。

因為在SSTable文件的存儲中，key是有序排列的，所以我們只要通過LSM樹實現免索引鄰接的能力。關鍵點在于合理地設計邊的Key，要讓一個點的所有邊在排序后是相鄰的。

上圖中例1，只要把邊Key的最高位放起始點ID，那么排序之后，從這個起點出發的邊自然就會排在一起。這里還可以有一個編號字段，加入編號字段就可以支持在兩點之間的同類型多條邊的共存。因為LSM樹是KV結構，所以如果只有起始點、終止點和META的話，那么兩點之間同類型的邊只有一個Key，所以只能存一條。對于像轉賬交易、訪問記錄這樣具有事件性質的邊來說，兩點之間肯定會有多條同類型的邊，在這樣的場景下，這個能力就是非常重要的。

在某些場景下邊的Key也可以不以起始點開始，比如例2的場景下。可以先放邊的類型，再放起始點ID。這樣做的目的是為了能夠通過邊類型直接做分片。因為在分布式環境下，做這樣的分片可能會有更好的性能。這樣雖然一個點的所有邊是分散存儲的，但是一個點某個類型的所有邊還是順序存儲在一起的。如果業務場景是邊查群總是按照類型分別迭代的，那么它也能提供很好的免索引鄰接的能力。

LSM樹也存在一些難點需要克服。

首先，SSTable文件是分層的，在查詢時的最壞情況下，需要找遍所有層才能知道找得到或者找不到，因此讀性能是沒有直接使用數組的方式那么高的。另外，Compaction對它的影響是很大的，Compaction是個后臺操作，會占用大量的磁盤IO，勢必對前臺讀寫性能造成影響。第三是，使用LSM方案通常都要依賴第三方存儲，對于一些特定的需求，必須要改動第三方存儲項目才能實現。

4. 優化之路

可以看到，幾種常見的實現免索引鄰接的存儲方式，都不是一勞永逸的方案，而是各有各的優勢和短板：

通過數組的方式讀取速度快，但寫入速度慢；通過LSM樹的方式寫入速度快，但是讀取速度慢。

通過鏈表的方式，讀取和寫入的速度都不占優，但卻是靈活性最高的方式。

在實際實現一個圖數據庫的過程中，要根據我們的設計理念去做取舍。

實現一個完整的圖數據庫產品，還有很多功能和性能的問題需要考慮。比如圖數據庫特有的反向邊一致性的問題，還有分布式條件下怎樣做分區分片，怎樣處理分布式事務，是否支持mvcc快照，實時副本怎么做，WAL怎么做，屬性索引怎么做，以及是否支持數據過期等。這些都是一個成熟的圖數據庫產品需要解決的問題。解決這些問題的同時，也要兼顧底層存儲的特性。

04Galaxybase 圖數據庫應用實踐

1. Galaxybase特點

Galaxybase是一個國產高性能分布式圖數據庫。它具有如下特點：

速度快：原生分布式并行圖存儲，毫秒級完成傳統方案無法實現的深鏈分析, 較同類技術百倍提升。

高擴展：完全分布式架構，動態在線擴容，高效支持萬億級超級大圖。

實時計算：內置豐富分布式圖算法、無ETL實現實時圖分析。

高效數據壓縮：優化資源利用，節省硬件和維護成本。

全自主可控、兼容國際開源生態與國產底層硬件。

2. 分布式圖存儲技術方案

Galaxybase數據庫使用的是業界領先的數據分片，加動態壓縮的分布式存儲技術。它支持屬性圖的存儲。在分布式部署環境中不同分區的文件可以根據計算出來的分布函數放在不同的集群機器上。備份數據也是以分區文件的形式，在集群不同機器之間進行同步。分區數據文件內部的點邊數據格式采用的是高壓縮比的動態壓縮技術，可以大幅節省存儲空間。Galaxybase原生圖存儲引擎是100%自研的，不依賴任何第三方存儲引擎。因此可以和圖查詢、圖計算功能做充分的整合優化，以實現非常好的產品性能。

3. Galaxybase性能優勢：打破圖數據處理規模世界紀錄

這是我們和中山大學攜手共建的一個國家重點研發圖計算項目。它依托國家超算廣州中心的環境，僅用50臺機器的集群就完成了5萬億規模交易數據的智能挖掘系統，實現了當前全球商業圖數據支持的最大規模圖數據處理。打破了之前用1000臺機器集群創造了1.2萬億規模的大圖處理的世界記錄。我們涵蓋的出入度，最大有超過1000萬的超級節點。六跳深鏈查詢平均耗時僅6.7秒。

4. 優異的查詢性能

LDBC SNB測試

模擬社交網絡圖，是迄今為止圖數據庫在模擬業務場景下最完整的基準測試。

測試詳情

Galaxybase圖數據庫具有優異的查詢性能。上圖是LDBC-SNB官方對Galaxybase進行測試的結果。測試由國外權威機構進行，首先進行了結果正確性驗證確保圖數據庫返回正確結果；隨后進行了系統穩定性、可用性、事務支持性和可恢復性驗證，均達到官方標準；最后進行了各項性能測試。Galaxybase表現優異，達到國際領先水平。在使用完全相同系統配置前置下，Galaxybase較LDBC之前公布的最高記錄吞吐量提升了70%，平均查詢性能達6倍以上提升，最高查詢性能提升72倍。

5. 豐富的圖算法支持

Galaxybase也提供了豐富的算法支持，提供了包括像圖遍歷、路徑發現、中心性分析、社群發現、相似度分析、子圖模式匹配等幾個大類的上百種圖算法。不久前率先通過了信通院圖計算平臺的一個產品基礎能力評測，涉及五個能力域，34個能力項的評測，全方位覆蓋了圖平臺的基本能力、兼容能力、管理能力、高可用和擴展能力。

6. 云啟創新生態

同時，我們也加入了騰訊云啟創新生態。我們創鄰和騰訊合作聯合推出了高性能的圖數據庫產品TGDB，已經在農行、交行、國家電網等超大型客戶場景中落地。TGDB當前在墨天輪的圖數據庫類目中排名第一。

7. 標桿用戶與合作伙伴

我們已經服務了金融、能源、教育、互聯網、政府多個行業中的頭部客戶。在農行、交行、民生、上農商、南電、國電、浙大、騰訊、公安都已經有落地進入實際生產的案例。我們的合作伙伴包括騰訊云、百度云、AWS等。歡迎大家來使用Galaxybase圖數據庫。