一、RDF 和屬性圖

首先來介紹 RDF 和屬性圖。大家知道世界萬物是普遍聯系的，Internet 帶來了信息的連通，IoT 帶來了設備的連通，像微信、微博、抖音、快手這些 APP 帶來了人際關系的連通。隨著社交、零售、金融、電信、物流等行業的快速發展，當今社會支起了一張龐大而復雜的關系網，在人們的生產和生活過程中，每時每刻都產生著大量的數據。隨著技術的發展，我們對這些數據的分析和使用也不再局限于從統計的角度進行一些相關性的分析，而是希望從關聯的角度揭示數據的一些因果聯系。這里的關聯，指的是相互連接的 connectivity，而不是統計意義上的 correlation。

關聯分析的場景也非常多，覆蓋我們生活的方方面面。比如從社交網絡分析里，我們可以做精準營銷、好友推薦、輿情追蹤等等；金融領域可以做信用卡反欺詐的分析，資金流向識別；零售領域，我們可以做用戶 360 畫像做商品實時推薦，返薅羊毛；電力領域，可以做電網的調度仿真、故障分析、電臺因子計算；電信領域，可以做電信防騷擾，電信防詐騙；政企領域，可以做道路規劃、智能交通，還有疫情精準防控；在制造業，我們可以做供應鏈管理、物流優化、產品溯源等；網絡安全行業，可以做攻擊溯源、調用鏈分析等等。

以上只是列舉了一些常見的分析場景。事實上，關聯分析的應用遠遠不止于這些場景，還有很多其它場景。比如企業的股權穿透分析，公安的安全案情分析，還有生物醫藥領域的基因分類和新藥研發等等，這里就不一一贅述了。

在做關聯分析的時候，我們往往需要一個圖模型來描述。常見的圖模型分為 RDF 和屬性圖兩種。RDF 圖中用點來表示唯一標識的資源或者是字面量的值，邊則用來表示謂詞。點和邊之間組成一個 SPO 的三元組。屬性圖中，點表示實體，邊表示關系，屬性是點或邊上的一個鍵值對。

相比之下，RDF 的優勢是可以支持多值屬性，因為它的屬性也是一個點，所以一個點連出去，可以有多值的屬性。也可以通過四元組的方式前面加上一個圖的描述，來實現動態圖。并且 RDF 開始的比較早，所以有一個比較統一的標準。

屬性圖的優勢在于它兩點之間可以表示同類型的多條邊，因為它在邊上是可以有區分屬性的，邊上的屬性值也能讓邊上的表達能力更豐富。并且它支持復雜的屬性類型，比如 list、set、map 等。

隨著行業的發展，我們看到越來越多的可能。知識圖譜的表示在逐漸用屬性圖來完成。今年將正式投票、明年發布的 GQL 標準，也是基于屬性圖的一個查詢語言標準。當然也有少量的圖數據庫是用 RDF 模型來做的，但是未來更多的新型圖數據庫都會用屬性圖模型。

二、圖數據庫存儲的核心目標

不論是用 RDF 還是用屬性圖，作為一個圖數據庫，它的核心目標是什么？或者說數據庫存儲需要解決的一個根本問題是什么呢？那些需要用關聯分析的圖場景，往往是一些數據規模大、關聯跳數深、實時要求高的場景。

完成一個圖查詢或者圖分析的核心操作，就是鄰居的迭代遍歷。單獨的訪問點或者邊，或者上面的屬性并不是這里的關鍵。僅僅是單獨訪問，使用傳統的數據庫也可以提供很好的性能。在關聯分析當中，不論是從一個起始點若干跳數內的鄰域網絡進行分析，還是對全圖進行一些完整的計算，最核心的操作都是迭代遍歷某個點的所有邊，也就是所謂鄰居的迭代遍歷。在關系型數據庫中是依賴外鍵，通過建立索引等方式來完成的。

在圖數據庫中，會直接存儲邊數據，也就是所謂的實現 index-free adjacency。寫入的時候，保證一個點和它直接相連的邊總是存儲在一起。查詢的時候，迭代遍歷一個點的所有鄰居可以直接進行，不需要依賴于其它數據結構，從而可以大幅提升鄰居迭代遍歷的性能。

這里是跟關系型數據庫做的一個深點查詢的性能對比，用的是 who-trust-whom 的一個公開數據集，這個數據集也不是很大，約 7.5 萬點，50 萬邊。我們想知道一個信任的人這樣一個多跳關聯的查詢結果。使用關鍵性數據庫的時候，對比了加索引和不加索引的情況。可以看出 2 跳的時候加索引可以明顯提升關系型數據庫的查詢速度，到 3 跳的時候提升就不多了， 4 跳以上的時候加不加索引都會變得很慢。而使用圖數據庫，查詢性能一直會保持在一個非常快的水平。這就是圖數據庫的 index-free adjacency 的特性，能夠大幅提升鄰居查詢的速度。

根據實現免索引連接的方式，可以把圖數據庫分成三類。

第一類是使用原生圖存儲的方式，它的數據存儲層就直接實現了免索引連接。上面的處理計算層和業務層都是以完全圖的結構來描述，并且也不依賴于第三方存儲組件，所以這種實現免索引連接的性能是最高效的。

第二種方式是非原生存儲，數據存儲層使用的是一個第三方的開源存儲組件，但是它在處理過程中實現了近似免索引連接，在大多數情況下也能提供不錯的性能。它的問題是由于使用了第三方存儲組件，在某些場景下可能做得不是最優化。

第三種方式就是完全非原生的存儲，底下可能是一個關系型數據庫，或者是一個文檔型或者其它類型的數據庫，它的存儲層其實并不是真正地實現了免索引連接，而是處理成通過索引或者一些其它技術手段，向上表達了一個圖模型的查詢接口。這種其實只是在接口層上實現了圖的一個語義，而底下的存儲和計算層都不是完全地使用免索引連接，所以它的性能也會相對低一些。

三、圖數據庫存儲的主流技術方案

前文中已經明確了數據庫存儲的核心目標就是實現免索引連接。那么接下來就來看一些具體實現免索引連接的主流技術方案。這里主要介紹不同方案的設計思路，并不局限于某個產品的具體實現細節。

首先我們能想到的最直接的一個方案，就是用一個數組把每個點上的邊按照順序一起存儲。在這一存儲方案中，點文件就是由一系列的點數據組成的。每個點的存儲內容包括點的 ID、點的 Meta 信息，以及這個點的一系列屬性。在邊文件中，是按照起始點的順序存儲點上對應的邊，每條邊存儲的內容包括終止點 ID、邊的 Meta 信息、邊的一系列屬性。這里所謂的 Meta 信息包括點邊的類型、方向，還有一些為了實現事務的額外字段，這對于整體的存儲來說不是特別重要，在這里就不詳細展開了。在這個存儲方案中，可以直接從起始點開始遍歷相鄰邊的所有數據，讀取性能是非常高的。

這種存儲需要處理的一個比較棘手的問題，就是數組變長的情況。這里的變長是由很多因素導致，比如兩個點可能屬性數量不一樣，屬性本身如果是字符串，長度也會不一樣。屬性長度不一樣會導致每條邊的存儲空間也不一樣，這樣在邊文件中就不能用一個簡單的數組來進行尋址了。如果僅僅是屬性導致的變長，還是有比較簡單的解決方案的，比如可以把屬性單獨的再放到另一個存儲文件中，這樣點文件和邊文件里面的內容，是不是定長的呢？其實也不一定，因為每個點上邊的數量也是不一樣的，所以在邊文件里面，每個點觸發的邊序列的總長度也是不一樣的。所以還是要處理數組變長的問題。

解決思路一般是兩種，一種是使用額外的一個 offset 的記錄，相當于是用一個偏移量記錄，來記錄每一個點或者邊的起始位置。這個記錄本身就可以是定長的了，因為它是個 offset 值。或者是提前劃分好一些額外的區域，來預留給它增長的空間。

為了解決這種數組存儲變長的問題，我們自然也可以想到用類似鏈表的方式來存儲。在鏈表方式的存儲模式中，點和邊全部存的都是 ID，包括點 ID、邊 ID、屬性 ID 等等。通過屬性 ID ，可以在另外一個屬性存儲里面找到它的位置以及具體的值。因為存的都是 ID，所以每個點和每條邊的數據長度就是固定的了。通過 ID 可以直接計算出偏移量，然后用偏移量的位置去讀取數據。所以每個數據本身也不需要保存自身的ID，因為偏移量的位置是能夠反推出來自身 ID 的。

這是一個鏈表存儲下進行邊迭代的例子。

假設有一個起始點 A，需要迭代它的所有邊。首先在點文件中找到點 A 的首個邊，α。然后去邊文件中找到 α 對應偏移量的位置，就可以讀出這條邊的數據。可以看到，是一個從點 A 到點 B 的邊，A 是一個起始點，我們就去找起始點下一條邊的 ID，就找到邊 θ。然后去邊 θ 的位置，找到偏移量，就找到邊 θ。這里我們看到它是一個 C 到 A 的邊，A 是終止點。我們就去找終止點的下一條邊，是 ω。再去找到邊 ω 的位置，看到是起始點 A 終止點 D，通過這樣的方式就可以不斷地去迭代邊。

我們看到，用鏈表存儲的方式很好地解決了數組變長的問題，因為新增邊的時候，只需要新增固定長度的結構組成鏈表即可。每一次迭代也是在 O(1) 的時間內直接找到了下一條邊，也不依賴于外部的索引或者其它結構。

這看似是一個比較好的方案，但實際的使用中，也存在著一些問題。不要忘記，現在討論的是一個存儲格式，而不是一個內存結構。存儲格式意味著最終是要在磁盤 IO 上進行讀寫的。在鏈表存儲方案下，每一次邊迭代的時候，由于邊 offset 的位置是隨機的，所以會有大量的隨機讀操作。而磁盤對于隨機讀操作并不是很友好。所以雖然這里理論上的迭代鄰居找到下一條邊的復雜度是 O(1)，但 O(1) 的單位時間是磁盤隨機讀的時間，而不是順序讀的時間，這兩者在性能上是會有非常大的差別的。所以使用這種鏈表的存儲方式，通常來說會依賴一個非常高效實現的緩存機制，需要把大量的磁盤數據放到內存緩存中來讀，在內存中進行隨機訪問的性能就會提升很多。

除了基于數組和鏈表的方法，還有其它一些格式可以實現 O(1) 時間的邊迭代。比如，使用 LSM-Tree 的存儲結構，這個結構是一種順序寫盤多層結構的 KV 存儲。這里只簡單介紹一下它的工作原理。

這個圖忽略了像寫 WAL 這樣的細節，是 LSM 樹讀寫的核心操作流程。LSM 樹是一種常用的鍵值存儲結構，處理寫請求的性能很高。它的讀寫操作流程如下：當一個請求進來的時候，直接寫入內存中的一個 MemTable，如果 MemTable 沒寫滿，就直接返回請求。因此它處理寫請求的性能是很高的。當 MemTable 滿的時候，會生成一個不可寫的、只讀的 Immutable MemTable，同時生成新的可寫的 MemTable，以供后續使用。然后 Immutable MemTable 就會寫到磁盤上，形成一個 SST 文件。SST 文件在寫盤的時候，會根據 Key 排序，從而實現順序的邊迭代。其落盤結構的 SST 文件也是分層來組織的。從內存中直接寫出來的第 0 層達到一定數據量大小的時候，或者觸發某種條件的時候，就會進行一個歸并排序，歸并排序就是一個 Compaction 的過程。合并出來的第一層的 SST 文件，都是按照 Key 的順序寫排的。讀取的時候是先去內存中的 MemTable 查找，找到了就返回，如果沒有找到就去第 0 層的 SST 文件中查找，找不到再去第 1 層，這樣逐層查找，一直到找到需要讀取的 Key 為止。

使用 SST 文件進行存儲的一個關鍵就是設計邊的 Key。因為在 SST 文件中，Key 是有序排列的，所以我們需要通過 LSMTree 來實現免索引連接的能力。關鍵點就是合理地設計邊的 Key，使一個點所有邊在排序后是相鄰的。說起來比較拗口，其實實現起來并不難。

我們看一下這個例子。只要把邊 Key 的最高位放起始點 ID，那么后面無論是邊的其它什么信息，都可以讓從起始點 ID 出發的邊自然地排序排在一起。這里也可以加入一個編號的字段，因為兩點之間，起始點和終止點 Meta 這些是固定的，編號字段加入之后，就可以支持在兩點之間同類型的多條邊共存。因為這是一個 KV 結構。如果只有起始點、終止點和 Meta，兩點之間同類型的邊只能存在一條。所以比如轉賬交易或者是訪問記錄這些具有事件性質的邊要存多條，可以加一個編號。當然也不一定都是必須從起始點開始來做邊的 Key。

比如在例 2 中，把 type 邊類型放在高位。它就可以先以 type 進行劃分，后面才是起始點。這種方法也比較適合在分布式場景下按類型做分片，這樣同一類型的邊就會排在相鄰的分片中，有利于提高分布式查詢的性能。使用這個方式，有非常高的寫入性能，并且讀取的時候也能提供免索引連接的能力。

但是其實它也并不完美，也有很多問題需要克服。首先是讀性能，在讀的時候，如果內存沒有命中，下面是一個逐層的 SST 文件，去找 Key 的最壞情況，可能要把所有層的 SST 文件全部找完，才能找到合適的 Key。所以它的免索引連接是比較依賴于Compaction 操作的。只有在理想情況下，比如在一個完整的 Compaction 完成的情況下，它才能真正實現免索引連接，否則會在各個 SST 文件內部去查找。在整體上，它并沒有完整地達到不去利用其它結構就能夠進行快速的領域迭代。

而做 Compaction 又是一個有比較大的磁盤 IO 的操作，并且如果使用的是第三方的存儲結構，那么做 Compaction 的操作是不受圖數據庫本身控制的，可能是由一些其它的機制觸發的，比如是在前臺負載壓力比較大的情況下觸發了 Compaction，這樣實際在使用的時候會出現一些瓶頸，所以必須要對第三方存儲進行比較深度的改動，才能夠更好地優化。

可以看到，各種實現免索引連接的存儲方式都不是一勞永逸的，而是有各自的優勢和短板。通過數組的方式讀取速度快，但是寫入因為涉及到變長的問題，可能會比較慢。通過 LSM 樹的方式寫入速度快，但是讀的時候又依賴于 Compaction 操作，在 Compaction 沒有完成的情況下，它的讀取速度也比較慢。通過鏈表的方式讀取和寫入速度都不占優，但是它的靈活性卻最高，因為它是以 offset 形式的指針來實現的。

在實際商業圖數據庫的實現過程中，需要根據設計理念去做取舍。也可以結合兩種或者多種方案的優點，在不同的數據形式下，靈活地實現不同類型的存儲。還有一些其它的問題，比如分區分片、反向邊一致性、如何支持事務、數據索引怎么做、數據過期等等，都是要解決的問題，實現起來還是比較復雜的。

四、Galaxybase 圖數據庫應用實踐

接下來介紹 Galaxybase 圖數據庫的一些應用實踐。

Galaxybase 是創鄰研發的國產高性能分布式圖平臺，它的特點是速度快、高擴展、實時計算，支持一個知識中臺，并且安全自主可控。

使用原生分布式并行圖存儲，實現了存儲層的免索引連接，可以毫秒級完成傳統方案無法完成的深鏈分析，較同類技術有數百倍的提升。使用完全分布式的架構，支持動態在線擴容，高效支持萬億級超級大圖。也內置了非常豐富的圖算法，包括分布式圖算法和單機圖算法，不需要 ETL 就能實現實時圖分析。底層存儲包含數據壓縮的能力，可以優化資源利用，節省硬件和維護成本。有一個可視化交互的知識中臺，便于業務理解和操作，幫助數據價值快速變現。同時也是完全自主可控的，全面兼容國產底層軟硬件。

這是 Galaxybase 的架構圖，中間部分是整體的核心部分。底層使用了數據分片動態壓縮的分布式存儲技術，支持屬性圖的存儲模型，并且實現了原生圖存儲。

存儲層之上是計算層，實現了內置的圖計算引擎，包含了單機的圖算法和分布式圖算法，并且還可以由用戶來自定義一些定制化函數，來實現自己的高效算法。

再往上是接口層，支持 Java、Python、Go、Rest 的 API。并且可視化的模塊也可以以接口的方式嵌入到其它第三方頁面中。

左側可以看到，支持多源異構數據，比如傳統關系庫、CSV 文件、HDFS、實時流數據等等，都可以直接進行數據導入。

底層適配了各種操作系統，支持各種國產和非國產的主流操作系統。也支持國產的各種 CPU。

在上面可以構建一個圖智能中臺，包括圖工作流管理和可視化分析。在中臺之上，可以在各種的業務場景下提供不同的業務解決方案。

Galaxybase 的一個性能優勢，是能夠高效地進行分布式圖計算，并且實現了當前最大規模的圖數據處理，實現了 5 萬億超大規模的分布式圖存儲。在線查詢僅使用了 50 臺機器的集群，出入度最大有 1000 萬的超級節點，6 跳的平均查詢時間僅為 6.7 秒。這是與中山大學攜手共建的一個圖計算項目。

Galaxybase 還具備非常高效的查詢性能。在 LDBC 的 SNB 測試里面，去年我們做了一個官方的 Audit，打破了一項世界記錄，較之前的吞吐量提升 70%，平均查詢性能有 6 倍以上的提升，最高的 95 分位查詢性能提升達到 72 倍。

Galaxybase 支持非常豐富的圖算法，包括 57 種圖算法，其中 28 種已經支持了分布式，其它一些分布式算法也正在實現中。我們也是首家完成信通院圖計算評測的一個圖計算平臺。

我們的產品里面還包括一個圖智能中臺，主要是通過可視化界面的方式來進行交互式的探索，完成圖的一些定性分析，包括搜索頂點、點邊位置擴展、查找路徑，還有各種混合的布局。布局模式有各種方式混合的搭配，還可以和自定義的地圖進行匹配，支持時序演進分析等功能。

Galaxybase 是一款完全國產自主可控的產品。內核的存儲、計算、查詢的代碼完全都是自研的，不依賴于其它第三方開源框架。也完成了各種操作系統和 CPU 的國產信創適配認證，并且獲得了信創的一些相關獎項。

我們提供各種圖場景的解決方案，有很多合作伙伴，有很多已經在金融、能源、教育、互聯網、政府多個行業中的頭部客戶落地的使用場景，并且已經服務了幾年時間。

五、問答環節

Q1：針對大 value，比如大于 4K 的數據，隨機讀取的時候會非常耗 IO，這塊有什么優化嗎？

A1：一般來說，圖數據庫里如果是一個屬性值，單個屬性值大于 4K，其實我們不建議把它放到圖數據庫中來，因為圖數據庫主要是做點邊的關聯鄰居查找的。如果單個屬性大于 4K，可能是一個很長的文本。在這個上面做圖的分析，價值并不大。如果這個是要作為一個存儲放進來的話，最好是把它單獨放在一個另外的區域中，不要跟點邊正常的這些屬性來放在一起。

如果指的是點邊的結構，可能某一個點的鄰居特別多，會就這種超級節點的情況把它存在一起。針對鄰居存儲的數量非常大的情況，涉及到一個圖切分的概念。通常情況下我們更多使用的是一個邊切割，所以所有點的鄰居都會存在一起，這樣能更高效地來訪問一個點的所有鄰居。

當一個點的鄰居數量特別大的時候，這里可能都不只是 4K 量級，可能會有 400M 或者 4G 這樣的量級，這種情況下的切割就會形成單個非常大的文件。這種時候也可以考慮動態的點切割的方式，就是把一個點的鄰居，再切割成多個存儲文件，存儲文件可以在不同的分區里，可以在不同的分片下，這樣就可以實現并行迭代的方式。

當然這里的技術會更復雜，需要首先有對邊進行唯一定位的能力，有這個能力之后，就可以在這一個點的所有鄰居邊上，再進行進一步的切割，然后把大文件再分成不同的小文件。這也是常見的處理超級節點的一個方式。

Q2：在查詢路徑時，如果有超級節點，返回所有的路徑會不會有問題？一般怎么處理？

A2：這要結合業務需求查詢所有路徑。比如有的圖很大的時候，全部路徑的數量會是一個天文數字，那么返回所有路徑可能就沒有意義了。這時候更好的方式是，要了解我們要路徑去做什么。在路徑上可能要做一些計算，或者做一些聚合，做一些其它的操作。在做這些計算的時候，就不是簡單地返回路徑，而是把路徑上面的計算也一起做了，得到一個最后的計算結果。如果是路徑數量沒有那么大的情況下，也是可以逐條返回的。通常我們可以用寫輸出一個文件或者其它的方式，來返回所有路徑。

Q3：底層數據壓縮對圖性能的影響有多大？

A3：肯定是有影響的，因為壓縮畢竟也要占 CPU，所以這其實是個可選項，要看我們的需求是對讀寫性能更敏感，還是對磁盤空間更敏感。因為也有一些應用，不是實時的情況下，其實對延遲沒有那么敏感，但它的數據量可能很大。這時候我們可以通過底層數據壓縮的方式來節省磁盤空間。當然，如果是對實時性能要求比較高的情況下，肯定是不壓縮，直接讀寫性能更高。因此可以根據場景來決定。

Q4：怎么做無 ETL 的實時圖計算？如果直接從存儲層迭代出來的數據怎么解決一致性的問題？如果用 snapshot 就會有 ETL。

A4：可能要這樣解釋一下我們這個產品，它是存儲、計算都包含的，它是自帶了存儲層和計算層，所以用 snapshot 不需要 ETL 過程，相當于我們自己的計算引擎可以去加載存儲里面的數據，也不需要再做一個數據清理或者是轉換的過程。可以選擇你需要用的一些點邊類型或者屬性類型做篩選，去生成一個圖計算引擎。

一般我們在做一個圖計算的時候，其實都是在一個 snapshot 上做圖計算，不然整個計算結果也沒有一致性。所以我們會加載圖存儲的某一個時間切片的一個時間點的 snapshot 到圖計算引擎中，來做圖計算。