圖數據庫發展綜述①

劉宇寧, 范冰冰

(華南師范大學 計算機學院, 廣州 510631)

數據庫是計算機最廣泛應用的技術, 傳統的關系型數據庫以“表格化結構”的方式, 對實際中的聯系進行建模, 從上世紀起一直占據著數據庫行業的主導地位[1]. 隨著數據量的快速增長, 數據類型的進一步擴展,部分研究指出, 非結構化數據占據了總數據量85%的比重[2]. 基于此, NoSQL數據庫憑借其無模式、可水平擴展的架構以及更為寬松的BASE原則等特點逐漸占據市場. 通常認為NoSQL數據庫分為4種類型, 包括:key-value數據庫、列式數據庫、文檔數據庫和圖數據庫. 隨著各行業在數據分析及深度挖掘數據間的內在聯系方面有了更多需求, 如金融行業嘗試在海量的賬目操作數據中進行欺詐行為檢測、社交網絡平臺對用戶之間關系進行深度關聯分析等. 關系型數據庫在處理關聯數據時, 復雜關聯情況會使得關系型數據庫表格之間的“外鍵”連接操作增加, 這使得其查詢復雜和高代價, 無法達到實際應用中快速響應的需求. 例如,在探究社交網絡多個用戶之間關系時, SQL語句的層級結構使用遞歸連接, 這導致了表格之間連接的高度復雜, 查詢效率低下. 在社交關系領域, 社交網絡可以看作是人與人之間密集關聯的網狀模型, 關系型數據庫的表格模型或者NoSQL數據庫的文檔、key-value存儲方式都難以表達它的結構特點. 而采用圖建模可以更好地表達其關系結構, 在進行實時關系查詢時, 通過圖算法能夠更加高效. 以“圖”為核心, 將“邊”視為數據庫的“一等公民”(即數據庫中最基本、最核心的概念)的圖數據庫在近十年的時間逐漸得到業界重視并快速發展[3].

根據中國信息通信研究院2019年12月發布的《圖數據庫白皮書》中信息, 圖數據庫的發展被劃分為兩個階段[4]: Graph1.0 (2007–2010年)小規模原生圖存儲階段, 圖數據庫主要以Neo4j的1.0版本為代表,采用了原生圖的底層存儲方式, 在復雜關聯數據的查詢性能上相對于關系型數據庫有了明顯提高. 《圖數據庫》[5]一書在5 000萬點和邊的數據規模下, 對比了Neo4j與關系型數據庫在關聯查詢的時間對比, 隨著關聯關系深度的增加, 關系型數據庫性能呈指數倍增長甚至無法運行. 該階段圖數據庫產品在架構設計上支持了單機部署, 在產品性能和業務擴展能力方面都有限; Graph2.0 (2010年至今)分布式架構的發展, 使得更多的圖數據庫產品支持分布式大規模圖存儲. 如JanusGraph允許使用多種后端存儲方式, OrientDB采用了原生圖存儲并擴展了分布式存儲模塊. 通過支持硬件上的水平擴展, 分布式圖數據庫進一步提升了在海量數據中對關聯數據的存儲以及實時查詢. 部分圖數據庫產品在全圖計算分析等復雜場景下需要結合圖處理引擎(如GraphX)進行離線計算和分析[6]. 近年來,發展勢頭迅速的TigerGraph[7]則將其產品定義為原生大規模并行圖處理的第三代圖數據庫, 通過內置豐富的算法庫和特有的數據存儲結構, 進一步提升圖數據庫在復雜場景下的查詢表現和可擴展性. 但目前業界對第三代圖數據庫產品還未有明確定義. 2019年初,Gartner數據與分析峰會上將圖列為2019年十大數據和分析趨勢之一, 并認為到2022年, 全球圖處理及圖數據庫應用都將以每年100%的速度增長.

本文第1節對圖數據庫概念、組成架構、特點以及和關系型數據庫對比4個部分進行介紹. 第2節對圖查詢語言、圖計算以及圖存儲3種圖數據庫關鍵技術進行比較分析. 第3節對比當前圖數據庫主流產品間的特點, 并介紹了各領域應用情況. 第4節對全文進行了總結, 并探索了未來的研究方向.

1 圖數據庫概念以及特點

1.1 圖數據庫概念

圖數據庫管理系統(以下簡稱圖數據庫)是一種經過優化的用于存儲、查詢和更新圖結構數據的數據庫管理系統[5], 它支持對圖數據模型的增、刪、查、改(CRUD)方法.

圖數據庫以數學中的圖論作為理論基礎, 以圖模型為特點進行數據存儲, 主流的圖模型有3種, 分別是屬性圖、RDF和超圖. 相對于RDF和超圖屬性圖模型目前被圖數據庫業界廣泛采用, 由圖數據管理領域學術界和工業界成員共同組成的關聯數據基準委員會(linked data benchmark council, LDBC)也正以屬性圖為基礎對圖數據模型和查詢語言進行標準化, 本文所討論的是以屬性圖為數據模型的圖數據庫研究.

屬性圖模型一般可以用以下四元組進行描述[6], 屬性圖表示為G, 包含節點集合V、屬性集合P、關系(邊)集合E, 標簽集合T組成,G=＜V,E,P,T＞.

節點: 用于表示圖中實體信息, 可以包含一個或多個屬性, 節點之間使用關系建立連接.

關系: 關系用于連接節點, 可以有一個或多個屬性(存儲為鍵值對key-value), 節點之間可以有多個甚至遞歸的關系.

屬性: 屬性是命名值, 其中名稱(或鍵)一般是字符串,屬性可以被索引和約束, 可以從多個屬性創建復合索引.

標簽: 標簽用于將節點分組, 一般而言一個節點可以具有多個標簽, 在圖數據庫中可以對標簽進行索引,用于提高查詢效率.

1.2 圖數據庫組成架構

當前圖數據庫的組成架構如圖1所示, 整體上采用了分層設計的模式[4–8], 由3層組成, 分別是: 接口層、計算層、存儲層.

圖1 圖數據庫組成架構

(1) 接口層

位于架構中的頂層, 負責對外提供服務, 包含了用戶使用圖數據庫所需要直接操作的接口及組件等, 提供了直觀的數據展示方法和友好的交互模式, 有以下幾種方式:

查詢語言接口: 提供除該圖數據庫原有查詢語言之外的, 如Cypher[9]、Gremlin[9]、GSQL[10]等主流圖查詢語言接口.

API: 提供ODBC、JDBC、RPC、RESTful等接口與應用端進行交互.

SDK: 在Python、Java、C++等主流編程語言中,通過庫函數的方式以調用圖數據庫的相關接口.

可視化組件: 通過圖形化界面的形式展示數據模型并且實現和用戶的交互操作.

(2) 計算層

作為中間層, 承擔上下層數據傳輸的橋梁, 提供對操作的處理和計算. 一般而言, 計算層實現了以下內容:

語法解析: 對輸入語法進行檢查, 進行語法解析并轉換成數據的具體操作內容.

查詢引擎: 為語法解析后的內容提供查詢等操作.

優化器: 對查詢或者計算內容提供優化操作.

事務管理: 用于保證事務的原子性和可串行性.

任務調度: 對多項任務進行調度管理, 保證查詢效率.

圖算法: 圖算法可能由圖數據庫產品自身實現, 也可能是提供圖處理引擎接口實現.

(3) 存儲層

圖數據庫以底層存儲方式的不同分為原生和非原生兩個類別, 存儲層提供圖數據結構、索引邏輯方面的管理.

1.3 圖數據庫特點

(1) 實際關系的建模方式

對于現實世界中的復雜實體關系, 圖模型的存儲和展示方式能夠更加直接地進行表達, 這有利于使用者對數據有更直觀的了解.

(2) 建模易擴展

圖數據庫提供了靈活的數據模式, 可以根據業務變化和場景需求, 對數據模型進行更改. 圖數據庫使用者無需在設計之初就把所有內容填充完畢, 在后續的使用中能夠對數據模型進行擴展, 免去了冗余的標準化時間成本.

(3) 針對關聯數據的快速查詢

屬性圖模型提供了內置的索引數據結構和對應的圖查詢算法進行針對性優化, 它無需針對給定查詢而加載或接觸無關的數據, 防止局部數據查詢引發的全局數據讀取. 在處理深度關聯數據時, 通過“點-邊-點”的連接方式能夠做到實時數據響應.

(4) 支持ACID事務完整性

圖數據庫在保證快速的數據訪問更新同時實現了數據的一致性保持 , 支持ACID事務管理, 能夠安全地進行數據管理.

1.4 圖數據庫對比關系型數據庫

(1) 建模方式

關系型數據庫以“表格化結構”的方式對實際中的聯系建模, 對結構化數據的處理起了重要的作用. 但其嚴格的建模約束, 使其難以適應動態變化的數據結構關系, 在處理“聯系”的具體問題上, 關系型數據庫需要通過“外鍵”連接的方式對表格進行操作, 這使得其查詢效率低下. 而圖數據庫采用“圖建模”的方式, 能夠更加貼切地表達現實世界中的實體及關系. 以社交圖關系為例, 分別采用關系型數據庫和圖數據庫建模方式進行建模, 如圖2, 圖3.

圖2 關系型數據庫社交關系建模

圖3 圖數據庫社交關系建模

可以發現, 針對于人與人密集關聯的網狀模型, 表格的方式并不能充分直觀地表達其關聯關系, 相反, 圖建模則能夠方便地表達這種網絡結構.

(2) 查詢效率

在查詢效率方面, 圖數據庫和關系型數據庫之間尚未形成統一的測試基準方法和數據集. Cheng等人提出一個兩者間的統一基準[11], 通過對圖數據和關系型數據之間的轉換方案, 來解決兩者間不同數據模型所帶來的影響, 將TPC-H和LDBC數據集進行擴展,使用不同的存儲引擎對比評估了關系型數據庫和圖數據庫之間性能指標. 實驗表明, 在主要由group by、sort、aggresgartion等操作構成的查詢中, 關系型數據庫更具優勢, 而在多表連接、路徑識別等查詢中, 圖數據庫有更優越的性能. 李金陽[1]以MySQL和Neo4j分別作為代表, 對比了在社交關系數據上實現多度查詢時的執行時間差異, 在面對大量且復雜的數據連接查詢時, 圖數據庫的響應時間呈線性增長, 遠低于關系型數據庫的響應時間. Macák等人[12]將數據導入到分布式版本數據庫中, 探索在擴展集群情況下查詢性能的差異, 針對連接、查詢過濾以及計算處理3類查詢分別進行對比. 實驗結果表明, 圖數據庫在前兩類查詢中更占優勢, 而關系型數據庫則在計算處理方面的查詢響應時間更短.

2 圖數據庫關鍵技術

2.1 圖查詢語言

目前, 圖數據庫領域沒有統一的圖查詢語言標準,2019年6月隸屬ISO/IEC的Joint Technical Comminttee1(JTC1, 聯合技術委員會1)通過圖查詢語言(graph query language)的標準提案, 將在未來為期48個月的指定工作, 這項工作旨在為屬性圖標準化圖查詢語言, 其關注重點是語法的表達能力和語義方面.而G-core研究、SQL/PGQ項目[13–16]也都在為圖查詢語言的標準化統一制定方案. 一般而言, 查詢語言分為命令式和聲明式兩種.

(1) 命令式查詢語言

命令式查詢語言是一種描述計算機所需作出的行為的編程范式, 系統需要順序依次執行用戶命令,這種方式有著較高的查詢效率但需要用戶具備一定的編程能力, 一般情況下命令式查詢語言是在需要對查詢等業務性能有著更高要求的情況下使用. 在圖數據庫技術中, Gremlin和Neo4j Java API包含了命令式功能[3].

(2) 聲明式查詢語言

聲明式查詢語言允許用戶表達檢索哪些數據, 剩下的由系統優化完成執行步驟, 這意味著用戶操作更加便捷. 聲明式查詢語言通常作為常規查詢語言, 提高圖數據的易用性. 在圖數據庫技術中, 主流的圖查詢語言, 如: Cypher、Gremlin、GSQL都是聲明式查詢語言.

接下來將上述3種圖查詢語言進行對比分析, 參考表1.

表1 圖查詢語言對比

圖算法屬于圖分析工具, 是分析關聯數據的有效方法. 基于圖論的數學原理, 圖算法利用節點之間的關系來推測復雜系統的組織形態和動態性. 圖數據庫的使用場景分為實時查詢及離線數據分析.

(1) 實時查詢

實時查詢一般是對數據進行局部查詢, 通過對圖數據進行遍歷搜索、過濾、迭代計算和統計等內容.圖數據庫為實時查詢提供了兩種常用的圖算法: 圖搜索算法和路徑發現算法.

圖搜索算法也被稱為圖遍歷算法, 指從一個點出發, 沿邊搜索其他頂點過程, 是實現圖查詢、更新的基礎. 這些算法目標是在圖上找出路徑, 但并不關心這些路徑在計算上是否最優. 常見的圖遍歷算法包括深度優先搜索和廣度優先搜索.

路徑發現算法基于圖搜索算法, 探索節點之間的路徑, 從某個節點開始遍歷關系, 直到目標節點, 這類算法往往在條件限定的情況下用來識別圖中的最優路徑, 常見的路徑發現算法包括: Dijkstra最短路徑算法、A*算法和最小生成樹等. 其中Dijkstra算法用于計算一對節點之間的最短(加權)路徑, 該算法首先查找從起始節點到與其直接連接的節點的最小權重關系, 并追蹤這些權重并移動至“最近”節點, 然后針對當前節點執行同一計算, 權重采用起始節點起算的累計值. 算法重復上述操作, 直至目標節點.Dijkstra算法的缺點是不支持負的權重, 且運行速度較慢.

為了加快查找速度, A*最短路徑算法在前者基礎上進行了改進, 在運行過程中, A*算法在主循環的每次迭代中都會判定要擴展哪些路徑, 通過估計到達目標節點剩余路徑的(啟發式)代價來完成該過程. A*算法的路徑選擇是要使式(1)最小化:

其中,g(n)是從起始節點到節點n的路徑代價.h(n)是節點n到目標節點的路徑代價估計, 通過啟發式函數計算.

A*算法中對估計路徑代價采用的啟發式方法需要根據不同情況制定, 如果在啟發式方法中高估路徑代價, 則可能導致跳過本該被計算的實際較短路徑, 導致錯誤結果. 此外, A*算法需要相對較高的內存存儲其使用數據. 研究者們通過對啟發式函數優化選擇以及其獲取方式的改進[17], 提出雙向A*算法、迭代A*算法等, 進一步提升了執行效率.

最小生成樹算法從給定節點開始, 查找其所有可達節點以及連接這些節點權重最小的關系集合. 它從任意已經過節點遍歷到下一位訪問節點的權重最小,從而避免了環的出現. 對比Dijkstra最短路徑算法, 它沒有在每個關系結束時都最小化總路徑長度, 而是將每個關系的長度分別最小化, 這使其可以計算帶有負權重的關系圖, 但該算法在圖沒有關系權重或者關系權重值相同情況下運行則沒有意義.

(2) 離線分析

除了實時查詢, 應用場景還經常需要對海量數據進行離線分析, 以便從中挖掘出有效信息. 相對而言,離線分析需要更長的時間完成, 算法也更加復雜, 一般通過解決問題的目的不同分為圖挖掘算法、中心性算法以及社區發現算法.

圖挖掘算法是基于圖的數據挖掘, 用來發現數據的模式, 可以幫助用戶或者上層應用更好地挖掘數據中的潛在信息. 典型的圖挖掘算法包括頻繁子圖、三角形計數等.

頻繁子圖算法用于枚舉在圖中所有出現次數超過設定閾值的子圖, 一般采用自底向上(即擴展圖規模)的挖掘策略, 包括基于Apriori的Apriori-Max-Graph算法、基于FP-增長的MARGIN算法等. 該類算法缺點在于挖掘過程中需經過多次迭代及多次子圖同構的判斷, 且子圖同構的判斷屬于NP完全問題,此外基于FP-增長的方法挖掘到的最大頻繁子圖集與頻繁子圖集相比只是減少了結果集的數量, 并不能降低挖掘難度. 研究者還提出基于深度優先搜索的gSpan算法, 能夠有效減少冗余候選子圖的生成, 提高挖掘效率.

三角形計數算法用于確定圖中經過每個節點的三角形數量, 該算法往往和聚類系數緊密相關, 用于估計群組穩定性以及圖中出現緊密相關的簇.

中心性算法用于理解圖中特定節點的角色及其對網絡的影響. 這些算法能夠識別最重要的節點, 并幫助我們了解群體動態, 例如可信度、可訪問性、事物傳播的速度以及子圖之間的連接點. 常見中心性算法包括度中心性算法、中介中心性算法、接近中性性算法和PageRank算法等.

度中心性算法用于度量節點擁有的關系數量, 可用來識別在線拍賣網站存在的普通用戶和詐騙分子群體, 后者加權中心度往往有著明顯的異常[18]. 接近中心性算法用于發現可通過子圖高效傳播信息的節點, 其衡量指標是該節點到其他各節點的平均距離(反距離),接近中心度得分高的節點與其他節點距離短. 其計算公式如下:

其中,u為節點,n為圖中節點總數,d(u,v)是另一個節點v和節點u之間最短距離. 通常會將該得分進行歸一化處理, 以此表示最短路徑的平均長度, 而非最短路徑之和, 歸一化后可以比較在不同規模圖中節點的接近中心性. 接近中心性歸一化公式如下:

Wasserman&Faust算法在接近中心性算法基礎上提出改進, 計算群組中可達節點數與到可達節點平均距離的比值, 對于檢測一個節點在整個圖(而非子圖)中的重要性更加有效.

中介中心性算法計算連通圖中沒對接點之間的最短(加權路徑), 每個節點的分值根據通過該節點的最短路徑數量確定. 對所有最短路徑, 將下面公式的結果相加以計算節點中介中心性得分:

其中,u為節點,p為節點s和t之間最短路徑總數,p(u)為s與t之間通過節點u的最短路徑數量.

PageRank算法度量節點的傳遞性(或方向性)的影響, 通過對節點輸入關系的數量和質量, 評估該節點的重要性, 最初用于網頁排序, 其算法公式如式(5):

假設頁面u中含有從第T1頁到Tn頁的引用,d是取值介于0–1的阻尼系數, 1–d是不考慮任何關系直接到達節點的概率,C(Tn)定義為節點T的出度.

PageRank算法的缺點是忽略了主題相關性, 導致查詢結果與主題的相關性降低; 另外, PageRank對新的鏈接不友好. 近年來, 研究者們針對PageRank算法在不同領域的使用進行了優化, Sayyadi等人[17]將時間因素整合到PageRank算法, 提出FutureRank算法. 華一雄等人[18]提出基于文本相似度及入出比的改進方案, 將其應用于文獻搜索領域. Yang等人[19]將時間反饋和主題相似度結合, 通過添加頁面更新率因子、主題相關因子來進行PageRank算法改進. Zhong等人[20]則提出一種基于資源分配的改進方案, 能夠在定向網絡中是被影響力更高的節點.

社區發現算法是基于網絡拓撲結構信息識別出的具有相似特征或起相同作用的節點的集合, 發現社團的一般性原則是社團成員在群組內部的關系要多于其與群組外部節點的關系. 近年來, 已有許多復雜網絡社區挖掘方法被提出, 依據原理可以被分為基于劃分、基于模塊度優化、基于標簽傳播的方法等.

基于劃分的社區去挖掘方法核心思想是先找出社區間的全部鏈接, 將其刪除, 最后每個連通分支對應著一個社區. 基于上述思想, GN算法[21]被提出, 該算法采用的啟發式規則是: 社區間鏈接的邊介數應大于社區內鏈接的邊介數, 其中每個鏈接的邊介數被定義為“網絡中經過該鏈接的任意兩點間最短路徑的條數”.GN算法的缺點是計算速度慢, 針對其不足, 研究者們引入統計方法[22]、鏈接聚類系數[23]、結構相似度[24]等關鍵技術進行改進.

模塊度Q作為一種社區發現指標, 將圖分割為更粗粒度的模塊, 然后度量分組強度, 模塊度采用矩陣形式表達為式(6)和式(7):

其中,k代表的是節點i的度,Aij為鄰接矩陣,S為每個節點所屬社區的one-hot表示,Sir=1表示第i個節點屬于第r個社區.

2004年Newman等人提出第一個基于模塊度優化的社團發現算法(FN算法)[25]. 該算法去初始化時,對候選解中每個社區僅包含一個節點, 迭代過程中,FN算法選擇使模塊性函數Q增加最大(或減小最少)的社區進行合并, 當候選集只對應一個社區時算法結束. 基于模塊度思想, 后續研究者結合譜圖理論[26]、局部優化和多層次聚類[27]技術等技術實現優化. 模塊度算法缺點在于多個分割選項出現相似模塊度時, 可能出現停滯, 形成局部極點阻礙進一步處理.

標簽傳播算法是一類啟發式算法, 其啟發式規則為“在具有社區結構的網絡中, 任一節點都應該與大多數鄰居在同一個社區”. 2007年, Raghavan等人提出著名的標簽算法(LPA算法)[28]. 其流程是初始化時, 每個節點被賦予唯一標簽, 在迭代過程中, 每個節點采用大多數鄰居的標簽來更新自身標簽, 當所有節點的標簽都與多數鄰居標簽相同時, 算法結束. 基于LPA算法,研究者們通過對目標函數修正[28]、多步層次貪婪算法[29]等進行性能提升.

針對社區發現的研究還處于發展階段, 社區發現算法的評價標準還未統一, 對于同一個網絡, 用不同社區發現算法會得到不同的社區結構, 不同評價標準也會得到不同的最優社區結構.

目前圖算法的研究仍處于發展階段, 不同領域針對同構、異構、動態網絡的圖特征挖掘有著不同的解決方案, 結合機器學習以及圖神經網絡技術的發展, 圖算法的效率在被進一步提升[30,31].

2.2 圖存儲

圖數據存儲被依據其底層實現原理劃分為原生圖存儲和非原生圖存儲. 原生圖存儲以圖為原型對數據進行組織管理, 是針對于圖數據定制化管理方式. 非原生圖存儲則采用了外部存儲引擎, 使用包括列式結構、key-value結構等存儲數據, 能夠兼容不同類型數據格式.

2.2.1 原生圖存儲

原生圖數據庫的代表是Neo4j和TigerGraph, 它提供原生的圖數據存儲、處理和檢索, 其原生圖存儲層使用了“無索引鄰接”[32], 該方法的特性是指, 每個頂點維護指向它的鄰接頂點的直接引用[3], 每個頂點可以看作是它的鄰接頂點的一個“局部索引”. 下面以Neo4j的物理存儲結構為例展示無索引鄰接的實現,Neo4j將屬性圖的頂點、邊、屬性和標簽保存在了不同的存儲文件中, 通過分離存儲方案, 提高了存儲和訪問效率. 圖4給出了Neo4j 2.2版本的頂點和邊的物理存儲邏輯結構, 其中頂點占用15字節, 邊記錄則占用34個字節, 頂點和邊記錄中各字節的詳細內容參考表2、表3.

圖4 Neo4j中頂點和邊的物理存儲結構

表2 Neo4j頂點記錄物理存儲結構中各字節作用

表3 Neo4j邊記錄物理存儲結構中各字節作用

2.2.2 非原生圖存儲

非原生圖數據庫在底層數據存儲的實現上沒有直接采用圖模型, 而是在此之上對圖進行封裝. 以Janus-Graph為例, 其存儲端采用了基于Google Bigtable[33]的KCV (key-column-value)的數據模式. 它的存儲方案中包含了兩種圖切割方法: 按邊切割(edge cut)和按節點切割(vertex cut). 在默認模式下, JanusGraph采用了按邊切割的方式[3]來進行圖切割存儲.

按邊切割: 根據邊進行切割, 以節點為中心, 每條邊存儲兩次, 源節點的領接列表存儲一次, 目標節點的領接鏈表存儲一次.

按節點切割: 根據點進行切割, 每個邊只存儲一次,節點對應的邊便會多一份該節點的存儲.

JanusGraph基于使用BigTable模型的存儲后端,完成存儲的邏輯結構, 如圖5所示.

圖5 JanusGraph的圖存儲整體結構

圖的存儲整體結構分為3個部分: vertex id、property、edge.

Vertex id: 對應節點的唯一id, 以使用HBase為例,則代表當前行的Rowkey, 代表某個節點.

Property: 代表節點的屬性.

Edge: 代表節點的對應的邊.

圖6則給出了Vertex id的存儲結構, 進行序列化存儲時, vertex id 共包含一個字節, 8位, 64 bit, 分為3個部分: partition id、count、ID padding. 前5位為partition id, partition是JanusGraph抽象出的概念, 通過其數量計算可以最終使數據均勻分配到多臺機器中.中間的count是流水號, 最高位固定為0, 其剩余位數足以生成2的55次冪(約30 000兆)個id, 滿足節點數量生成. 最后幾位bit是ID padding, 表示Vertex的類型, 具體位數長度會隨不同類型有所修改, 常用情況值為“000”.

圖6 JanusGraph中Vertex id的物理存儲結構

圖7給出了Edge和Property的邏輯結構, 均分別由column和value兩部分組成.

圖7 JanusGraph的節點和邊的物理存儲結構

在Edge的column中, 包含了label id、direction、sort key、adjacent vertex id和edge id. 其中, label id是邊類型代表的id. Direction是圖的方向, 用0和1來分別代表出和入. Sort key可以指定多個邊的屬性. Adjacent vertex id是目標節點id, 實際存儲的是目標節點id和源節點id的差值. Edge id則是邊的全局唯一id. Edge的value由signature key和other property組成, 前者用于提升edge的屬性的檢索速度, 后者則是存儲邊的其他屬性.

Property的column包含key id和property id, 前者用于存儲屬性label對應的id值, 后者則是指定屬性的唯一id. Value中只有property value用于保存屬性值.

基于上述整體的邏輯結構, 可以發現JanusGraph通過vertex id行保存了跟當前節點相關的所有邊, 在邊的邏輯結構中, 使用adjacent vertex id字段來獲取目標節點, 形成了由源節點指向目標節點的圖模式.

圖存儲方案作為圖數據庫底層數據管理基礎, 在原生和非原生存儲方案上各具優劣, 不同產品針對其優化也體現了各自優勢. 當前, Neo4j、TigerGraph和JanusGraph等主流圖數據庫研究人員針對其方案優化,仍需進一步探索.

3 圖數據庫產品及應用

3.1 圖數據庫產品

從DB-Engines中獲取的圖數據庫排名可知, 目前國內外對圖數據庫產品的研發投入越來越高, 各產品迭代更新也越來越快. 本節將選取Neo4j、TigerGraph、JanusGraph、ArangoDB、OrientDB這5款圖數據庫進行對比分析, 詳情參照表4.

表4 圖數據庫產品對比

3.1.1 原生圖數據庫

(1) Neo4j

Neo4J是目前業界最受歡迎和使用的原生圖數據庫, 其底層存儲采用了原生的屬性圖模型, 具有“無索引鄰接”的特性. Neo4j有著高擴展性支持存儲實現上億數量級的節點及關系內容, 提供了兩種運行模式, 分別是嵌入式模式和服務器模式. 在嵌入式模式下, Neo4j和應用程序運行于同一進程, 該模式的目標應用是硬件設備, 桌面應用程序和應用服務器的組件. 服務器模式是更為常用的方式, 每個服務器的核心是一個Neo4j的實例, 典型的訪問Neo4j的服務器的方式是使用REST API. Neo4j支持使用名為Cypher圖查詢語言,有著良好的表現力和較高的查詢效率.

(2) TigerGraph

TigerGraph是一款作為原生、實時和大規模并行處理(MPP)的圖數據庫, 其存儲通過底層原生屬性圖設計, 避免了從虛擬圖操作到物理存儲操作的轉換帶來的開銷. TigerGraph為用戶的快速訪問提供了便捷, 用戶可以在使用中設置參數來指定存儲于內存的圖大小, 如果圖不能整個在內存中進行操作,則多余的數據會放置在磁盤, 數據值會被壓縮保存,其采用C++編寫, 對內存進行細粒度管理, 內置壓縮因子隨著圖結構和數據的不同而變化, 提高存儲和查詢效率.

3.1.2 非原生圖數據庫

(1) ArangoDB

ArangoDB是一款多模型數據庫, 可以使用鍵值對(key-value)、文檔或者圖形的數據模型進行存儲.ArangoDB采用了試用于所有數據模型的統一內核和統一數據庫查詢語言. 因此, 用戶可以在單次查詢過程中混合使用多種模型, 這種混合多模型數據存儲方式增加了數據存儲的靈活性、簡化了性能擴展、提高了容錯能力以及降低了的存儲成本.

(2) OrientDB

OrientDB是一個多模型的開源數據庫, 支持文檔、圖形、鍵值對(key-value)和對象的數據模型, , 支持事務性和分布式體系結構, 數據庫的操作可以使用Java、SQL或者Gremlin來完成, 物理數據存儲可以在內存和磁盤上完成. OrrientDB使用文檔數據庫和面向對象功能來存儲物理頂點. 它支持分布式體系結構, 支持多尺度安全驗證和數據加密, 有著良好的數據安全性支持.

(3) JanusGraph

JanusGraph是一個開源的分布式圖數據庫, 是個有著良好的擴展性, 通過多機集群可以支持存儲和查詢數百億的頂點和邊圖數據. JanusGraph為數據持久化, 數據索引和客戶端訪問提供了強大的模塊化接口.它可以適配多種數據庫和索引, 數據庫方面包括大數據處理中常見的Apche Cassandra、Apache HBase、Google Bigtable、Oracle Berkeley. 索引方面, 為了加快并支持更復雜的查詢, 它支持Elasticsearch、Apache Solr、Apache Lucene等. 這種模塊化的設計能夠更好地增強分布式圖系統的功能, 提供了優化的磁盤表示形式, 以便更高效地存儲和更快的訪問速度. Janus-Graph還通過集成大數據平臺, 如Apache Spark、Apache Giraph、Apache Hadoop等, 支持全圖數據的分析、報表和ETL.

3.2 圖數據庫基準測試

圖數據庫暫無像關系型數據庫一般形成統一的基準測試標準, 國內外研究一般集中于數據加載、查詢性能和查詢可擴展性3個方面.

(1)數據加載

Deutsch等[7]對多款數據庫在數據加載的時間和占用磁盤容量兩個角度分別進行了比對分析. 在數據加載時間上, 采用初始數據批量操作方式, 得出在使用時間上: TigerGraph＜Neo4J＜ArangoDB＜JanusGraph的結論. 而在磁盤占用容量上, TigerGraph在測試中有明顯的優勢, 其內置的自動編碼和壓縮數據算法讓它在導入后的數據比原始數據所占空間更小, 而其他幾款產品加載后的數據空間占用程度都較于原始數據更高.

(2)查詢性能

針對基本查詢、圖遍歷以及最短路徑計算3個方面進行對比, JanusGraph的效率均高于Neo4j[30]. 而由Fernandes等人[32]提出的測試對比中, 在查詢響應時間方面ArangoDB更優于OrientDB和JanusGraph, 結合其在用戶體驗上的特性, 在綜合評分上ArangoDB＞JanusGraph＞OrientDB. 針對ArangoDB和Neo4j在查詢處理時間、內存利用率和CPU利用率上進行了對比, 與Neo4j相比, AranggoDB查詢時間上相對更占優勢且占用的CPU相對較少, 但主存耗費更多[11]. 針對K度查詢、弱聯通子圖查詢和圖算法PageRank的查詢實現進行對比測試中[15], 在K度路徑頂點計數查詢方面, 報告分1、2、3、6度4個梯度分別進行測試,在一度和二度查詢上, TigerGraph在兩個測試集上表現都為最佳, 而 Neo4j、JanusGraph則有著相對接近的查詢耗時, ArangoDB在這項測試中表現明顯低于其他幾項數據庫. 而在三度和多度這兩項深度查詢中, 除TigerGraph外其他幾款數據庫均出現超時或者內存耗盡的情況. 在弱聯通子圖和PageRank查詢中, 僅有TigerGraph和Neo4j在規定時間內完成了查詢.

(3)查詢可擴展性

在查詢的可擴展性方面, TigerGraph 能夠通過集群布置能夠顯著提升其查詢性能, Neo4j則因未提供對圖的切片處理而無法測試[15]. 而Cheng等人[11]通過使用多個節點部署的集群測試中, ArangoDB、JanusGraph、OrientDB均在多節點的情況下用時高于單節點, 有著較好的擴展性.

3.3 圖數據庫各領域應用研究

當前而言, 圖數據庫應用的領域和場景越來越多樣化, 許多著名的公司都開始使用圖數據庫來完成產業的發展和創新. Twitter、Facebook、Google等公司更是在圖數據庫出現的早期就開始了對其在社交網絡應用上的探索[34,35]. Neo4j和OrientDB的客戶包括安全公司、調查單位、媒體公司(Sky、Comcast、Warner)和貿易公司(Ebay或全球500強物流), 它們使用圖形數據庫為客戶提供實時的產品路線和交付[36]. 此外, 使用圖結構來表示生物醫學領域分子、藥物等模型能夠較高程度還原其真實性, 越來越多生物醫學行業研究采用圖數據庫來進行數據存儲[37–58]. 本文于2021年10月使用DBLP、中國知網數據庫、萬方數據知識服務平臺, 以“Graph database”“圖數據庫”作為主題檢索自2018年以來相關文獻, 共獲得以圖數據庫為基礎的應用共 145篇, 經人工統計, 應用分布比例如圖8. 知識圖譜是圖數據庫關聯最為緊密、應用范圍最廣的應用場景, 采用圖數據庫作為底層數據存儲方式, 實現了醫療、生物、金融、公文政策等多個領域的知識圖譜[59–66], 能夠幫助行業提高決策效率. 在社交網絡方面,使用圖數據庫存儲出行人員多維數據, 幫助挖掘可疑人員、密切接觸者等重點群體[67–70], 針對2019年所爆發的新冠疫情, 能夠快速找到確診病例和疑似病例的密切接觸者, 提高了分析效率. 圖數據庫運用在推薦系統領域, 包括的電影推薦、圖書推薦、醫生推薦等, 能夠進一步提升推薦的準確率[71–76]. 電力系統及智能物聯網領域通過圖數據庫對連接設備進行建模, 能夠直觀地反應電網拓撲結構、設備信息流通以及資源消耗情況, 幫助提高設備管理效率[77–91]. 金融行業通過圖數據庫, 利用多維交叉關聯信息深度刻畫申請和交易行為, 可以有效識別規模化、隱蔽性的欺詐網絡和洗錢網絡[92–100]. 使用圖數據庫產品以及豐富的圖分析算法, 結合NLP、CV等人工智能熱門領域技術, 情報科學領域在各類非結構化文檔實體關系提取以及視頻數據中人員關聯分析等應用也進一步發展[100–102]. 表5選取了圖數據庫近年來在各領域的代表性應用研究, 可以發現目前Neo4j憑借良好的開源性社區支持, 成為了廣大開發者使用首選.

表5 圖數據庫應用

圖8 圖數據庫應用統計分布

4 總結展望

目前, 圖數據庫的各項理論、方法、技術和系統處于快速發展和開發完善階段. 數據庫學術界和產業界對圖數據庫研發投入的成本不斷增加. 本文主要概述了圖數據庫基本特點, 并從圖查詢語言、圖計算、圖存儲3個方面對圖數據庫關鍵技術進行論述分析, 最后比對了市面上主流的圖數據庫產品以及應用場景. 從目前研究情況來看, 圖數據庫相關研究仍存在較大發展空間, 未來的研究方向主要包括以下幾點.

(1)統一的圖查詢語言和測試基準

目前圖查詢語言尚未有統一標準, 當前圖查詢語言(GQL)的標準還處于制定階段, 市面上多種查詢語言使用了不同的標準, 提高了用戶的學習成本. 在具體業務上, 不同產品的查詢語言表達方式使得在同樣的應用場景下, 所獲取的結果不一致. 在出現復雜閉環的圖中, 不同產品提供了不同的解決方案[7], 影響了用戶使用體驗. 統一圖查詢語言標準的制定, 能夠使GQL使用更加穩定和高效.

此外, 各公司所提供的實驗及數據都沒有形成統一的準則, 這讓用戶在不同產品之間的選擇變得困難,Cheng等人[11]提出供業界參考的測試基準, 但相對于已經被成熟使用的RDMS, 圖數據庫測試標準的制定是未來發展的一個主要方向.

(2)深度融合圖數據庫和圖處理引擎

目前, 不同圖數據庫產品在圖算法的提供上參差不齊, 部分圖數據庫無法獨立完成復雜的全圖迭代計算, 需要使用外部圖處理引擎完成任務. 這在一定程度上增加了額外的開銷, 加重了系統負擔. 而部分圖數據庫采取了分布式的設計方案, 這使得其處理的數據量規模得到了進一步提升, 同時通過優化提高了查詢能力. 圖數據庫和圖處理引擎的深度融合, 如采用內置圖算法庫以及圖處理引擎, 從而為用戶復雜的計算提供更簡單的內在操作是業界的研發方向.

(3)融合多模數據庫發展

多模數據庫對多種數據模型進行存儲, 其內置圖數據管理的方案存在差異, 建立適用于不同數據模型間轉換的圖數據接口能夠進一步提高數據間的轉換效率以及統一使用, 如Neo4j 4.0版本中提供了幫助用戶將關系型數據定制化轉換成圖數據模型的工具, 鄂海紅等也提出了從表格數據和RDF數據格式到圖數據的轉換方法[104,105]. 此外, 采取分布式架構實現底層數據存儲, 使用索引等技術方案, 可以進一步提高使用效率.

(4)軟硬件一體化

圖數據庫非規則訪問的特性對底層硬件的需求越發迫切, 將來可以通過軟硬件協同設計方案[6], 比如采用NVM 減少持久化存儲的開銷, 使用 RDMA 增強通信效率, 或者將事 務的部分要求交給硬件(例如 HTM)來控制、簡化軟件設計等將成為下一步研究方向.

(5)支持實時決策和人工智能應用

實時深度關聯分析使用戶能夠比以往更準確、更快速和更深入地探究、發現和預測關系. 使用圖數據庫對海量數據間關聯進行深度實時分析, 可以幫助企業完成人工智能創新應用, 提高用戶對海量數據的實時監控和挖掘分析.

隨著圖數據庫技術的不斷成熟, 其應用場景也將愈發豐富. 圖數據庫與圖處理引擎融合的圖系統帶來的強大的圖存儲和分析能力, 將會進一步推動圖數據庫在金融風控、社交網絡等典型應用場景的使用升級,也為智能物聯網等行業帶來了新的應用發展方向.