導(dǎo)讀：本文由香港中文大學(xué)James Cheng教授團(tuán)隊(duì)貢獻(xiàn)，James Cheng教授長(zhǎng)期從事分布式系統(tǒng)、分布式計(jì)算、圖計(jì)算與圖數(shù)據(jù)管理等方向的研究工作。曾與阿里巴巴、華為、騰訊、字節(jié)跳動(dòng)等多家公司在大數(shù)據(jù)計(jì)算系統(tǒng)、存儲(chǔ)系統(tǒng)、調(diào)度系統(tǒng)、深度學(xué)習(xí)系統(tǒng)等方向上展開(kāi)項(xiàng)目合作，曾獲得香港青年科學(xué)家稱號(hào)，ATC'21最佳論文獎(jiǎng)。

接下來(lái)，大家一起來(lái)了解下圖數(shù)據(jù)庫(kù)技術(shù)發(fā)展的前世今生吧：

一、背景介紹

圖（Graph）是一種由點(diǎn)（Vertex）和邊（Edge）及其屬性（Property）構(gòu)成的通用數(shù)據(jù)結(jié)構(gòu)，以表達(dá)自然世界中實(shí)體間的關(guān)聯(lián)關(guān)系，被廣泛應(yīng)用于知識(shí)圖譜、社交網(wǎng)絡(luò)、金融網(wǎng)絡(luò)、生物蛋白質(zhì)分析等各種垂直領(lǐng)域。隨著各行各業(yè)生產(chǎn)的數(shù)據(jù)規(guī)模增長(zhǎng)，大規(guī)模圖數(shù)據(jù)管理在近十年來(lái)受到了越來(lái)越多的重視，圖數(shù)據(jù)庫(kù)系統(tǒng)也正在被廣泛的開(kāi)發(fā)和研究，以實(shí)現(xiàn)高效的圖狀數(shù)據(jù)存儲(chǔ)和查詢。為了存儲(chǔ)圖數(shù)據(jù)，一些圖數(shù)據(jù)庫(kù)利用傳統(tǒng)的數(shù)據(jù)庫(kù)模型（如關(guān)系型數(shù)據(jù)庫(kù)，文檔數(shù)據(jù)庫(kù)，列存數(shù)據(jù)庫(kù)）來(lái)轉(zhuǎn)換圖數(shù)據(jù)；而還有一些圖原生的數(shù)據(jù)庫(kù)（比如Neo4j、TigerGraph等），則專門(mén)為圖數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)了高效的存儲(chǔ)格式。

與傳統(tǒng)數(shù)據(jù)庫(kù)相比，圖數(shù)據(jù)庫(kù)的本質(zhì)區(qū)別在于可以更高效的存儲(chǔ)和查詢圖數(shù)據(jù)。不同的存儲(chǔ)模型導(dǎo)致了不同的查詢執(zhí)行策略和對(duì)圖的具體操作行為，這將最終導(dǎo)致各種性能。例如，在原生的圖數(shù)據(jù)庫(kù)中，可以通過(guò)掃描無(wú)索引的鄰接列表來(lái)執(zhí)行遍歷操作，在基于關(guān)系型表而設(shè)計(jì)的圖數(shù)據(jù)庫(kù)中，則需要通過(guò)對(duì)多個(gè)表的Join操作來(lái)執(zhí)行。隨著遍歷跳數(shù)的增加，對(duì)于冪律分布的圖數(shù)據(jù)來(lái)說(shuō)，用于Join的表的大小可能呈指數(shù)級(jí)增長(zhǎng)，這將導(dǎo)致嚴(yán)重的性能瓶頸。而另一方面，關(guān)聯(lián)型的數(shù)據(jù)以Table的形式存儲(chǔ)在關(guān)系型數(shù)據(jù)庫(kù)中，可以實(shí)現(xiàn)更好的數(shù)據(jù)平衡和定位。對(duì)于一些原生的圖數(shù)據(jù)庫(kù)來(lái)說(shuō)，由于圖結(jié)構(gòu)的不規(guī)則性，不規(guī)則的數(shù)據(jù)模式導(dǎo)致了較差的數(shù)據(jù)局部性，并為數(shù)據(jù)檢索帶來(lái)了額外的開(kāi)銷(xiāo)。

本文將梳理圖數(shù)據(jù)庫(kù)發(fā)展的歷史脈絡(luò)與技術(shù)演進(jìn)，并簡(jiǎn)單討論筆者認(rèn)為圖數(shù)據(jù)庫(kù)今后的發(fā)展方向。

二、圖數(shù)據(jù)庫(kù)的發(fā)展歷史

從Google分別于2003、2004、2006年在SOSP'03、OSDI'04、OSDI'06發(fā)表經(jīng)典三駕馬車(chē)（GFS，MapReduce，BigTable）論文開(kāi)始，以Hadoop開(kāi)源生態(tài)為中心的大數(shù)據(jù)體系得到了蓬勃的發(fā)展，數(shù)據(jù)模型逐步由以表（Table）的主流形式來(lái)存儲(chǔ)和查詢關(guān)系型數(shù)據(jù)慢慢發(fā)展到以鍵值、寬列、文檔、圖等各種形式來(lái)存儲(chǔ)和查詢海量數(shù)據(jù)的NoSQL體系。

日益膨脹和快速發(fā)展的各類(lèi)應(yīng)用所產(chǎn)生的數(shù)據(jù)使得NoSQL體系對(duì)數(shù)據(jù)存儲(chǔ)與查詢的要求變得多種多樣：高吞吐、高可用、低時(shí)延、強(qiáng)一致等等。因此在大數(shù)據(jù)時(shí)代下，各類(lèi)組件百花齊放，迭代升級(jí)也非常迅速。圖數(shù)據(jù)存儲(chǔ)作為NoSQL體系中的一種數(shù)據(jù)建模方式，主要用以表達(dá)現(xiàn)實(shí)世界中實(shí)體間的關(guān)聯(lián)關(guān)系；圖數(shù)據(jù)庫(kù)則是與之對(duì)應(yīng)的存儲(chǔ)系統(tǒng)，用以存儲(chǔ)和管理（增刪改查）圖狀數(shù)據(jù)。

圖數(shù)據(jù)庫(kù)是一種非關(guān)系型數(shù)據(jù)庫(kù)，以解決現(xiàn)有關(guān)系數(shù)據(jù)庫(kù)的局限性。圖模型明確地列出了數(shù)據(jù)節(jié)點(diǎn)之間的依賴關(guān)系，而關(guān)系模型和其他NoSQL數(shù)據(jù)庫(kù)模型則通過(guò)隱式連接來(lái)鏈接數(shù)據(jù)。圖數(shù)據(jù)庫(kù)從設(shè)計(jì)上，就是可以簡(jiǎn)單快速地檢索難以在關(guān)系系統(tǒng)中建模的復(fù)雜層次結(jié)構(gòu)的。圖數(shù)據(jù)庫(kù)的底層存儲(chǔ)機(jī)制可能各有不同。有些依賴于關(guān)系引擎并將圖數(shù)據(jù)“存儲(chǔ)”到表中（雖然表是一個(gè)邏輯元素，但是這種方法在圖數(shù)據(jù)庫(kù)、圖數(shù)據(jù)庫(kù)管理系統(tǒng)和實(shí)際存儲(chǔ)數(shù)據(jù)的物理設(shè)備之間施加了另一層抽象）。另一些則使用鍵值存儲(chǔ)或文件導(dǎo)向的數(shù)據(jù)庫(kù)進(jìn)行存儲(chǔ)，使它們具有固有的NoSQL結(jié)構(gòu)。大多數(shù)基于非關(guān)系存儲(chǔ)引擎的圖數(shù)據(jù)庫(kù)還添加了標(biāo)記或?qū)傩缘母拍睿@些標(biāo)記或?qū)傩员举|(zhì)上是具有指向另一個(gè)文檔的指針的關(guān)系。這樣就可以對(duì)數(shù)據(jù)元素進(jìn)行分類(lèi)，以便于集中檢索。

圖片來(lái)源自：https://k21academy.com/dba-to-cloud-dba/nosql-database-service-in-oracle-cloud/

從大約2010年開(kāi)始，各種構(gòu)建于NoSQL體系或者關(guān)系型數(shù)據(jù)庫(kù)之上的圖數(shù)據(jù)庫(kù)便涌現(xiàn)而出，比如：Titan, JanusGraph, RedisGraph, Sparksee, AgensGraph, OrientDB 等等, 當(dāng)然同一時(shí)間也出現(xiàn)了Neo4j這種為圖數(shù)據(jù)而專門(mén)設(shè)計(jì)的圖原生存儲(chǔ)數(shù)據(jù)庫(kù)，其現(xiàn)今已經(jīng)發(fā)展成為了圖數(shù)據(jù)庫(kù)領(lǐng)域商業(yè)化的領(lǐng)頭羊。我們下面將根據(jù)存儲(chǔ)模型的不同對(duì)這些圖數(shù)據(jù)庫(kù)做一個(gè)簡(jiǎn)單的歸類(lèi)和討論。但由于篇幅有限，詳細(xì)的分析和性能對(duì)比不會(huì)在本文展開(kāi)，我們今后將會(huì)在arXiv上提交一篇Experimental Track的學(xué)術(shù)論文來(lái)系統(tǒng)性地分析這些圖數(shù)據(jù)庫(kù)的設(shè)計(jì)方案和性能測(cè)試報(bào)告。

1、圖數(shù)據(jù)庫(kù)的存儲(chǔ)設(shè)計(jì)?

如何存儲(chǔ)圖數(shù)據(jù)以實(shí)現(xiàn)高效查詢和更新是圖數(shù)據(jù)庫(kù)的一個(gè)重要問(wèn)題。對(duì)于一個(gè)圖模型G，應(yīng)該考慮的存儲(chǔ)數(shù)據(jù)包括點(diǎn)（V）、邊（E）、頂點(diǎn)屬性（VP）和邊屬性（EP）。一個(gè)圖通常又可以用三種常見(jiàn)的方法來(lái)表示：鄰接表、鄰接矩陣和邊列表。鄰接表通常將一個(gè)頂點(diǎn)的所有鄰居作為一個(gè)數(shù)組來(lái)存儲(chǔ)。因此，一條邊從兩個(gè)方向上會(huì)出現(xiàn)在兩個(gè)不同頂點(diǎn)的鄰接表中。鄰接矩陣選擇用一個(gè)矩陣來(lái)表示兩個(gè)頂點(diǎn)之間是否有一條邊，而邊表會(huì)獨(dú)立存儲(chǔ)所有的邊集合，并使用指針讓每個(gè)頂點(diǎn)記錄它與自己鄰居的關(guān)系。

2、圖原生數(shù)據(jù)庫(kù)

（1）Neo4j

Neo4j定制化的分別將四種對(duì)象（即點(diǎn)、邊、點(diǎn)屬性和邊屬性）作為記錄來(lái)存儲(chǔ)，并利用指針將它們連接起來(lái)。圖1展示了Neo4j如何在物理存儲(chǔ)上組織所有對(duì)象。一個(gè)頂點(diǎn)/邊的所有屬性都以鏈表的形式連接起來(lái)，其頭部由相關(guān)頂點(diǎn)/邊的實(shí)例的指針指向。與屬性類(lèi)似，一個(gè)頂點(diǎn)所有相鄰的邊也被連接在一起，但用雙鏈接列表來(lái)呈現(xiàn)。每個(gè)邊的實(shí)例將只存儲(chǔ)一次，但由兩個(gè)鄰接表連接。因此，要找到邊的實(shí)例，唯一的方法就是遍歷頂點(diǎn)上的雙向鏈表，這就會(huì)產(chǎn)生對(duì)邊集的掃描開(kāi)銷(xiāo)。然而，Neo4j中的遍歷可以通過(guò)雙鏈表的形式來(lái)加速。具體來(lái)說(shuō)，考慮到?jīng)]有頂點(diǎn)屬性訪問(wèn)的兩跳遍歷，Neo4j需要：1）從起始頂點(diǎn)開(kāi)始遍歷雙向鏈表，找到第一條邊；2）迭代步驟（1）中找到的所有邊上連接的其他雙向鏈表，完成下一跳。這種兩跳遍歷可以擺脫在兩個(gè)步驟之間加載頂點(diǎn)記錄，以減少磁盤(pán)I/O。

圖1 - Neo4j的存儲(chǔ)模型

圖2說(shuō)明了Neo4j如何將所有記錄存儲(chǔ)在磁盤(pán)上。我們可以看到，每條記錄都有自己固定大小的塊，相同類(lèi)型的記錄被連續(xù)地存儲(chǔ)在一起，形成一張表。因此，表中的每條記錄都可以根據(jù)其偏移量進(jìn)行有效定位，其中偏移量是根據(jù)記錄的ID計(jì)算的。對(duì)于屬性值，如果它的長(zhǎng)度大于一個(gè)記錄塊的默認(rèn)長(zhǎng)度，那么Neo4j將把這個(gè)屬性值的超出部分存儲(chǔ)在另一個(gè)由若干固定大小的槽組成的分離數(shù)據(jù)塊中。

圖2 - Neo4j不同類(lèi)型的數(shù)據(jù)記錄在磁盤(pán)上的組織形式

（2）RedisGraph

RedisGraph是一個(gè)基于Redis的圖存儲(chǔ)，Redis是一個(gè)基于內(nèi)存的鍵值存儲(chǔ)系統(tǒng)。然而，RedisGraph沒(méi)有將圖數(shù)據(jù)建模為適合Redis存儲(chǔ)模型的鍵值存儲(chǔ)，而是利用鄰接矩陣設(shè)計(jì)了自己的存儲(chǔ)模型，只利用了Redis的內(nèi)存分配和索引管理。這就是我們將RedisGraph列為圖原生存儲(chǔ)數(shù)據(jù)庫(kù)的原因。

圖2展示了RedisGraph是如何建模和存儲(chǔ)圖的。點(diǎn)和邊的屬性被存儲(chǔ)到一個(gè)頂點(diǎn)/邊緣容器的數(shù)組中。每個(gè)頂點(diǎn)/邊容器都有一個(gè)header來(lái)記錄當(dāng)前容器的元數(shù)據(jù)，包括存儲(chǔ)的頂點(diǎn)/邊的數(shù)量，容器的容量，以及使用的內(nèi)存大小。對(duì)于每個(gè)頂點(diǎn)/邊，其屬性被存儲(chǔ)在一個(gè)鏈表中，鏈表里的每個(gè)節(jié)點(diǎn)是一個(gè)具有固定大小的數(shù)據(jù)塊。屬性的鍵值對(duì)被按順序存儲(chǔ)在數(shù)據(jù)塊中。當(dāng)前一個(gè)數(shù)據(jù)塊滿了之后，一個(gè)新的數(shù)據(jù)塊將被追加到鏈表的尾部。此外，RedisGraph將具有相同標(biāo)簽的頂點(diǎn)/邊放到同一個(gè)容器中，以獲得更好的數(shù)據(jù)局部性。由于RedisGraph需要為每個(gè)頂點(diǎn)/邊和數(shù)據(jù)塊從Redis存儲(chǔ)層調(diào)用內(nèi)存分配，它根據(jù)容器的容量預(yù)先分配了容器所需的所有內(nèi)存，以避免頻繁且昂貴的內(nèi)存分配調(diào)用。

RedisGraph中的所有邊都以鄰接矩陣的格式存儲(chǔ)。如果兩個(gè)頂點(diǎn)之間存在一條邊，就會(huì)在鄰接矩陣的對(duì)應(yīng)位置上存儲(chǔ)一個(gè)指向該邊實(shí)例的指針，否則就不存儲(chǔ)。由于圖的性質(zhì)，鄰接矩陣大多是一個(gè)稀疏矩陣。因此，RedisGraph選擇使用了壓縮稀疏行（CSR）的格式來(lái)實(shí)現(xiàn)對(duì)矩陣的存儲(chǔ)。而多跳遍歷可以通過(guò)RedisGraph中的矩陣乘法來(lái)計(jì)算。然而，在CSR格式下，圖拓?fù)浣Y(jié)構(gòu)的變化對(duì)CSR的更新是很昂貴的，而且會(huì)給遍歷操作帶來(lái)嚴(yán)重的開(kāi)銷(xiāo)。

圖3 - RedisGraph的存儲(chǔ)Layout設(shè)計(jì)

（3）Sparksee

Sparksee以前被稱作DEX，也是一個(gè)圖數(shù)據(jù)庫(kù)。它利用基于位圖的索引bitmap來(lái)減少存儲(chǔ)開(kāi)銷(xiāo)，并通過(guò)基于位（bit）的邏輯操作來(lái)加速與圖相關(guān)的工作負(fù)載。

為了存儲(chǔ)一個(gè)圖，Sparksee首先將所有的數(shù)據(jù)分為不同的值集（value set）。具體來(lái)說(shuō)，一個(gè)值集是由以下一種鍵值對(duì)組成的：1.（頂點(diǎn)/邊ID，Label）；2.（邊ID, 頭/尾頂點(diǎn)ID）; 3.（頂點(diǎn)/邊ID, 屬性鍵的屬性值）。對(duì)于每個(gè)值集，Sparksee用兩個(gè)map來(lái)存儲(chǔ)所有的對(duì)：一個(gè)map記錄每個(gè)對(duì)象（即頂點(diǎn)/邊）到一個(gè)值（即Label、頭/尾頂點(diǎn)或?qū)傩灾担?，而另一個(gè)map則是將不同的值映射到一個(gè)位圖（如圖4所示）。因此，圖的拓?fù)湫畔⑹且赃吜斜砗袜徑颖恚次粓D）的形式存儲(chǔ)在值集中的。

位圖結(jié)構(gòu)是一個(gè)具有可變長(zhǎng)度的bits序列，它由第一個(gè)和最后一個(gè)非零元素定義。位圖中的每個(gè)位都與一個(gè)對(duì)象的標(biāo)識(shí)符oid相關(guān)（即頂點(diǎn)/邊ID）。如果該對(duì)象有相關(guān)的值，相應(yīng)的位置就被設(shè)置為1，否則為0。通過(guò)使用位圖結(jié)構(gòu)，Sparksee可以將一些基于圖的操作轉(zhuǎn)化為位運(yùn)算操作。由于位圖的長(zhǎng)度是由第一個(gè)和最后一個(gè)非零元素定義的，所以位圖不可避免地會(huì)變得很大，這就造成了數(shù)據(jù)檢索的開(kāi)銷(xiāo)。為了壓縮位圖，Sparksee將一個(gè)位圖分割成多個(gè)長(zhǎng)度為32位的子序列。每個(gè)子序列都與一個(gè)給定的ID配對(duì)，并存儲(chǔ)在一個(gè)排序的樹(shù)中。為了減少空間的使用，只有非零的子序列會(huì)被存儲(chǔ)并被排序樹(shù)索引。由于bits是以連續(xù)的方式分割的，Sparksee可以在數(shù)據(jù)檢索時(shí)快速定位到某個(gè)bits的子序列ID。

圖4：Sparksee中的值集與位圖

3、基于RDBMS構(gòu)建的圖數(shù)據(jù)庫(kù)?

由于關(guān)系型數(shù)據(jù)庫(kù)有相對(duì)成熟的技術(shù)和性能優(yōu)化，許多圖數(shù)據(jù)庫(kù)都是建立在RDBMS或關(guān)系型數(shù)據(jù)模型之上的（比如SQLGraph, AgensGraph, etc.）。AgensGraph就是一個(gè)構(gòu)建于PostgreSQL之上的圖數(shù)據(jù)庫(kù)，Oracle Spatial and Graph則是Oracle中支持圖數(shù)據(jù)存儲(chǔ)的一個(gè)組件。為了在關(guān)系數(shù)據(jù)庫(kù)中建立圖數(shù)據(jù)模型，頂點(diǎn)和邊通常被存儲(chǔ)為表中的記錄，其中的每一列代表一種屬性。除屬性外，邊記錄還將其源點(diǎn)和目標(biāo)點(diǎn)作為兩個(gè)外鍵存儲(chǔ)，以支持遍歷操作，這可以通過(guò)表的Join來(lái)完成。而連續(xù)的Join會(huì)嚴(yán)重?fù)p害多跳遍歷的性能，特別是當(dāng)表內(nèi)有大量頂點(diǎn)時(shí)。

（1）AgensGraph

我們以AgensGraph為例來(lái)介紹在關(guān)系型數(shù)據(jù)庫(kù)中存儲(chǔ)圖數(shù)據(jù)的方案。由于頂點(diǎn)/邊的屬性在圖中并不總是有固定的Schema，AgensGraph用基于JSON的表來(lái)存儲(chǔ)屬性，所有的屬性都以JSON格式存儲(chǔ)在一列。具體來(lái)說(shuō)，AgensGraph表中的一行記錄，對(duì)于頂點(diǎn)是按照（VertexID, Label, Properties in JSON）的格式來(lái)存儲(chǔ)的，對(duì)于邊則是按照（EdgeID, Source VertexID, Destination VertexID, Properties in JSON）的格式存儲(chǔ)的。圖5顯示了AgensGraph是如何管理磁盤(pán)上的表數(shù)據(jù)的。表文件首先被切成具有固定大小的多個(gè)頁(yè)。每頁(yè)的頁(yè)頭存儲(chǔ)了本頁(yè)的元數(shù)據(jù)，包括存儲(chǔ)的記錄數(shù)和這一頁(yè)的使用空間。為了更好地在頁(yè)中進(jìn)行順序掃描，每條記錄都有一個(gè)固定大小的指針塊，包含相關(guān)記錄數(shù)據(jù)的偏移量和長(zhǎng)度。指針塊以正向方式從頁(yè)頭開(kāi)始存儲(chǔ)，而記錄數(shù)據(jù)則以反向方式從頁(yè)尾開(kāi)始存儲(chǔ)。

圖5 - AgensGraph中圖數(shù)據(jù)在Table中以頁(yè)的方式的存儲(chǔ)格式

4、基于文檔構(gòu)建的圖數(shù)據(jù)庫(kù)?

文檔存儲(chǔ)的基本單元是一個(gè)以某種標(biāo)準(zhǔn)格式（如JSON、XML或BSON等二進(jìn)制格式）編碼的文檔。通過(guò)這些半結(jié)構(gòu)化的格式，文檔可以靈活地以鍵值對(duì)的形式存儲(chǔ)頂點(diǎn)/邊的屬性，且沒(méi)有固定的Schema。因此，在基于文檔的圖數(shù)據(jù)庫(kù)中，一組頂點(diǎn)/邊被存儲(chǔ)為一個(gè)文檔。為了連接頂點(diǎn)和與之關(guān)聯(lián)的鄰接邊，頂點(diǎn)文檔會(huì)包含該點(diǎn)的鄰接表，其以一組嵌套的鍵值來(lái)表示，對(duì)應(yīng)的值是一個(gè)List或者是一組記錄了label的鍵值對(duì)。

（1）OrientDB

OrientDB是一個(gè)典型的基于文檔的圖數(shù)據(jù)庫(kù)。圖6展示了OrientDB是如何存儲(chǔ)頂點(diǎn)和邊文件的。頂點(diǎn)和邊首先被它們的標(biāo)簽分離成類(lèi)。一個(gè)類(lèi)可以為存儲(chǔ)的文檔定義一個(gè)屬性集。雖然一個(gè)文檔不一定包含所有定義的屬性，但類(lèi)仍然可以幫助在訪問(wèn)實(shí)際數(shù)據(jù)前對(duì)不存在的屬性進(jìn)行預(yù)過(guò)濾。每個(gè)類(lèi)可以進(jìn)一步分割成多個(gè)cluster，以便根據(jù)CPU核數(shù)實(shí)現(xiàn)并行數(shù)據(jù)訪問(wèn)。每個(gè)頂點(diǎn)/邊分配了一個(gè)唯一的RID，以便快速定位，RID由類(lèi)ID、Cluster ID和在Cluster中的位置構(gòu)成。

除了RID和屬性，頂點(diǎn)文件還存儲(chǔ)了兩種不同格式的鄰接表（即regular Edgelist和lightweight Edgelist）。Regular Edgelist存儲(chǔ)了相鄰邊的RID，而Lightweight Edgelist包含了入向頂點(diǎn)的RID。因此在遍歷時(shí)，如果查詢不需要訪問(wèn)邊屬性，OrientDB可以使用Lightweight Edgelist來(lái)直接獲得目標(biāo)頂點(diǎn)。否則，OrientDB將通過(guò)RID找到邊文檔來(lái)訪問(wèn)邊屬性，最后獲得存儲(chǔ)在邊文檔中的頂點(diǎn)RID（即源點(diǎn)和目標(biāo)點(diǎn)）。

圖6 - OrientDB的數(shù)據(jù)存儲(chǔ)格式

5、基于寬列構(gòu)建的圖數(shù)據(jù)庫(kù)?

寬列存儲(chǔ)是由表組成的，表是行的集合。與關(guān)系型數(shù)據(jù)庫(kù)不同，寬列存儲(chǔ)沒(méi)有要求固定的Schema。每一列的名稱因行而異，每一行的鍵值對(duì)都存儲(chǔ)在這一列中。因此，寬列存儲(chǔ)也可以被視為二維鍵值存儲(chǔ)。Google的BigTable和Hadoop生態(tài)體系下的HBase就是典型的寬列存儲(chǔ)。其表中的每一行都包含任意數(shù)量的單元格，每個(gè)單元格都存儲(chǔ)一個(gè)鍵值對(duì)。利用寬列模型來(lái)存儲(chǔ)圖數(shù)據(jù)的典型圖數(shù)據(jù)庫(kù)有Titan和JanusGraph。

（1）JanusGraph

JanusGraph的底層存儲(chǔ)就是HBase, 在HBase中每一行都是一個(gè)由ID唯一識(shí)別的頂點(diǎn)。如圖7(a)所示，JanusGraph將點(diǎn)的每個(gè)屬性和鄰接邊都存儲(chǔ)到行中的一個(gè)單元格中。為了快速檢索，屬性按屬性ID排序，邊按邊的標(biāo)簽排序。圖7(b)顯示了JanusGraph中邊和屬性存儲(chǔ)的詳細(xì)格式。一條邊的key是由label和direction的復(fù)合ID、排序鍵、相鄰頂點(diǎn)ID和邊ID組成的。排序鍵可以由邊的label和其他邊的屬性來(lái)組成，以便加快遍歷。

由于JanusGraph沒(méi)有將邊組織成Row，所有的屬性都被序列化并存儲(chǔ)在表示邊的列單元中。為了避免在屬性過(guò)濾時(shí)對(duì)屬性列單元中的值進(jìn)行頻繁的反序列化，JanusGraph存儲(chǔ)了signature key，其包括了所有的屬性ID，以便快速檢查屬性是否存在。屬性列單元的結(jié)構(gòu)比邊列單元相對(duì)簡(jiǎn)單，屬性單元的key字段只存儲(chǔ)一個(gè)由屬性key編碼的ID，而value字段包含一個(gè)為每個(gè)屬性鍵和屬性值分配的唯一ID。

圖7 - JanusGraph的圖數(shù)據(jù)存儲(chǔ)格式

三、圖數(shù)據(jù)庫(kù)的現(xiàn)狀

隨著大數(shù)據(jù)基礎(chǔ)設(shè)施的不斷發(fā)展與完善， 數(shù)據(jù)庫(kù)產(chǎn)品的研發(fā)方向也正在從不斷提升經(jīng)典存儲(chǔ)系統(tǒng)的性能與穩(wěn)定性逐步轉(zhuǎn)向?yàn)獒槍?duì)各種垂直類(lèi)場(chǎng)景的特定性能要求而定制化設(shè)計(jì)。例如，隨著物聯(lián)網(wǎng)時(shí)代的到來(lái)，各類(lèi)傳感器、汽車(chē)、基站等端設(shè)備產(chǎn)生的數(shù)據(jù)規(guī)模正不斷增大，該場(chǎng)景具有典型的存量數(shù)據(jù)大、新增數(shù)據(jù)多（采集頻率高、設(shè)備量多）的特點(diǎn)，對(duì)數(shù)據(jù)庫(kù)的實(shí)時(shí)性能要求也比較高，通常需支持千萬(wàn)級(jí)QPS的寫(xiě)入，以及毫秒級(jí)的查詢響應(yīng)時(shí)間。傳統(tǒng)的數(shù)據(jù)庫(kù)架構(gòu)很難再滿足這種特定場(chǎng)景下的讀寫(xiě)需求，用戶已不再考慮一招能解決所有問(wèn)題（one-size-fits-all）的方案，而逐漸轉(zhuǎn)向針對(duì)不同工作負(fù)載給出特定數(shù)據(jù)庫(kù)選型方案的思路。由此，各種垂直類(lèi)型的數(shù)據(jù)庫(kù)不斷被提出，例如圖數(shù)據(jù)庫(kù)、時(shí)序數(shù)據(jù)庫(kù)、流式數(shù)據(jù)庫(kù)、向量數(shù)據(jù)庫(kù)等等。

圖數(shù)據(jù)庫(kù)的架構(gòu)和性能需求也在不斷與時(shí)俱進(jìn)，進(jìn)入"2.0時(shí)代"。一方面圖數(shù)據(jù)的規(guī)模越來(lái)越大，一套成熟的分布式高可用方案已經(jīng)變成對(duì)圖數(shù)據(jù)庫(kù)的基本需求，另一方面對(duì)圖數(shù)據(jù)的查詢復(fù)雜度也在進(jìn)一步提升，人們?cè)絹?lái)越想從高階的多跳查詢（>3跳）中挖掘出關(guān)聯(lián)關(guān)系數(shù)據(jù)的深層價(jià)值。而圖數(shù)據(jù)本來(lái)天生就具有數(shù)據(jù)傾斜的特點(diǎn)，出入度大的點(diǎn)往往占比很少，而與之相關(guān)聯(lián)的查詢卻需要訪問(wèn)很大比例的全圖數(shù)據(jù)才能返回最終結(jié)果，因此需要更多的算力。然而，在圖上對(duì)度數(shù)大的點(diǎn)的訪問(wèn)是很難預(yù)測(cè)的，如何在不影響吞吐的情況下，降低查詢的平均延時(shí)以保證服務(wù)的P99能滿足在線要求？單是這一點(diǎn)就是件挑戰(zhàn)力十足的事情。

而隨著圖數(shù)據(jù)的價(jià)值不斷被認(rèn)可，越來(lái)越多的應(yīng)用場(chǎng)景也開(kāi)始使用圖模型來(lái)表達(dá)業(yè)務(wù)數(shù)據(jù)（例如，金融網(wǎng)絡(luò)中的反洗錢(qián)、反套現(xiàn)，電商交易網(wǎng)絡(luò)中的商品推薦，短視頻中的點(diǎn)贊關(guān)注記錄等）。數(shù)據(jù)從產(chǎn)出之初，就被業(yè)務(wù)寫(xiě)入到了圖數(shù)據(jù)庫(kù)中，并期望可以做到寫(xiě)后的實(shí)時(shí)可見(jiàn)，因此在高可用的前提下，圖數(shù)據(jù)庫(kù)對(duì)數(shù)據(jù)的一致性、事務(wù)性也開(kāi)始有了要求。新一代的圖數(shù)據(jù)庫(kù)架構(gòu)在時(shí)間和業(yè)務(wù)需求的催化下，被自然衍生了出來(lái)。圖數(shù)據(jù)庫(kù)的熱度也一路水漲船高，如DB-Engines網(wǎng)站所示，從2013年開(kāi)始至今，圖數(shù)據(jù)庫(kù)的流行趨勢(shì)變化是所有垂類(lèi)數(shù)據(jù)庫(kù)中最高的，且看趨勢(shì)至少未來(lái)5年也依然會(huì)保持最高。2023年，圖數(shù)據(jù)庫(kù)的標(biāo)準(zhǔn)查詢語(yǔ)言GQL也會(huì)發(fā)布，各種類(lèi)型的圖數(shù)據(jù)庫(kù)查詢語(yǔ)言（e.g., Gremlin, Cypher, GSQL, nGQL）相信終將迎來(lái)統(tǒng)一，這可以進(jìn)一步促進(jìn)圖數(shù)據(jù)庫(kù)生態(tài)的發(fā)展。

接下來(lái)，本文將盤(pán)點(diǎn)近幾年有代表性的若干個(gè)現(xiàn)代圖數(shù)據(jù)庫(kù)的架構(gòu)設(shè)計(jì)，簡(jiǎn)單講解下圖數(shù)據(jù)庫(kù)2.0時(shí)代對(duì)高可用性和高性能的業(yè)界實(shí)現(xiàn)方案。

1、NebulaGraph

NebulaGraph是一款開(kāi)源的高性能分布式圖數(shù)據(jù)庫(kù)，一個(gè)完整的 Nebula 部署集群包含三個(gè)服務(wù)，Query Service， Storage Service 和 Meta Service， 如圖8所示：

圖8 - NebulaGraph的系統(tǒng)架構(gòu)

圖片來(lái)源自：https://www.nebula-graph.com.cn/posts/nebula-graph-architecture-overview

Meta Service集群基于raft協(xié)議保證了數(shù)據(jù)的一致性和高可用。Meta Service不僅負(fù)責(zé)存儲(chǔ)和提供圖數(shù)據(jù)的meta信息，如schema、partition信息等，還同時(shí)負(fù)責(zé)指揮數(shù)據(jù)遷移及 leader 的變更等運(yùn)維操作。左側(cè)主要服務(wù)采用了存儲(chǔ)與計(jì)算分離的架構(gòu)，虛線以上為計(jì)算，以下為存儲(chǔ)。計(jì)算層和存儲(chǔ)層可以根據(jù)各自的情況彈性擴(kuò)容、縮容，也使水平擴(kuò)展成為可能。此外，存儲(chǔ)計(jì)算分離使得 Storage Service 可以為多種類(lèi)型的計(jì)算層或者計(jì)算引擎提供服務(wù)。

Nebula的每個(gè)計(jì)算節(jié)點(diǎn)都運(yùn)行著一個(gè)無(wú)狀態(tài)的查詢計(jì)算引擎，而節(jié)點(diǎn)彼此間無(wú)任何通信關(guān)系。計(jì)算節(jié)點(diǎn)從Meta Service讀取meta信息然后將請(qǐng)求發(fā)送到對(duì)應(yīng)的Storage Service實(shí)例上。這樣設(shè)計(jì)使得計(jì)算層更容易使用 K8s 管理或部署在云上。每個(gè)查詢計(jì)算引擎都能接收客戶端的請(qǐng)求，解析查詢語(yǔ)句，生成抽象語(yǔ)法樹(shù)（AST）并將 AST 傳遞給執(zhí)行計(jì)劃器和優(yōu)化器，最后再交由執(zhí)行器執(zhí)行。

Storage Service采用shared-nothing的分布式架構(gòu)設(shè)計(jì)，每個(gè)存儲(chǔ)節(jié)點(diǎn)都有多個(gè)本地 KV 存儲(chǔ)實(shí)例作為物理存儲(chǔ)。Nebula同樣用Raft來(lái)保證這些 KV 存儲(chǔ)之間的一致性，并在KV語(yǔ)義之上封裝了一層圖語(yǔ)義層，用于將圖操作轉(zhuǎn)換為下層的KV操作。圖數(shù)據(jù)（點(diǎn)和邊）通過(guò)Hash的方式存儲(chǔ)在不同Partition中，這些Partition分布在所有的存儲(chǔ)節(jié)點(diǎn)上，分布信息則存儲(chǔ)在Meta Service中。

2、ByteGraph

ByteGraph是字節(jié)跳動(dòng)基礎(chǔ)架構(gòu)團(tuán)隊(duì)自研的分布式圖數(shù)據(jù)庫(kù)產(chǎn)品，并在字節(jié)內(nèi)部的近一百條業(yè)務(wù)線上得到了廣泛的落地，包括抖音上的好友關(guān)系，用戶-視頻點(diǎn)贊關(guān)系等。ByteGraph的架構(gòu)（如圖9所示）整體上跟Nebula較為類(lèi)似，也采用計(jì)算-存儲(chǔ)分離的架構(gòu)，不同的地方在于ByteGraph的存儲(chǔ)層進(jìn)一步劃分成了內(nèi)存存儲(chǔ)層和磁盤(pán)存儲(chǔ)層。

圖9 - ByteGraph的系統(tǒng)架構(gòu)

圖片來(lái)源自：https://zhuanlan.zhihu.com/p/109401046

ByteGraph的查詢層同樣沒(méi)有狀態(tài)，可以水平擴(kuò)容，主要工作是做讀寫(xiě)請(qǐng)求的解析和處理（將數(shù)據(jù)請(qǐng)求基于一致性哈希規(guī)則分發(fā)給存儲(chǔ)層實(shí)例并收集返回的請(qǐng)求結(jié)果）。內(nèi)存存儲(chǔ)層的實(shí)現(xiàn)和功能有點(diǎn)類(lèi)似內(nèi)存數(shù)據(jù)庫(kù)，提供高性能的數(shù)據(jù)讀寫(xiě)功能，具體提供點(diǎn)邊的讀寫(xiě)接口并支持算子下推：通過(guò)把計(jì)算(算子)移動(dòng)到存儲(chǔ)層實(shí)例上執(zhí)行，以有效提升讀性能。內(nèi)存存儲(chǔ)層整體上作為了磁盤(pán)存儲(chǔ)層的緩存，提供緩存管理的功能，支持緩存加載、換出、緩存和磁盤(pán)同步異步sync等功能。磁盤(pán)存儲(chǔ)層是一個(gè)單獨(dú)部署的分布式鍵值對(duì)存儲(chǔ)服務(wù)，將圖數(shù)據(jù)以KV pairs的形式持久化存儲(chǔ)在磁盤(pán)上。

ByteGraph針對(duì)熱點(diǎn)數(shù)據(jù)訪問(wèn)做了自己的存儲(chǔ)優(yōu)化，從系統(tǒng)角度當(dāng)然希望存儲(chǔ)在KVS中的KV pairs大小控制在KB量級(jí)且大小均勻。其將頂點(diǎn)的所有出度鄰居平均拆分成多個(gè)KV對(duì)，所有KV對(duì)形成一棵邏輯上的B-Tree，數(shù)據(jù)結(jié)構(gòu)如下圖所示。值得一提的是，ByteGraph在今年的VLDB'22 Industrial Track上發(fā)表了一篇論文，對(duì)其設(shè)計(jì)動(dòng)機(jī)和性能分析都做了比較詳細(xì)的描述，具體可參考論文地址：

https://vldb.org/pvldb/vol15/p3306-li.pdf

圖片來(lái)源自：https://zhuanlan.zhihu.com/p/109401046

3、EasyGraph

EasyGraph是騰訊TEG數(shù)據(jù)平臺(tái)部自研的分布式圖數(shù)據(jù)庫(kù)產(chǎn)品，目前已在騰訊內(nèi)部如企業(yè)微信、微信支付、王者榮耀、和平精英、QQ、廣告等諸多關(guān)鍵產(chǎn)品線落地，并且作為騰訊云KonisGraph圖數(shù)據(jù)庫(kù)對(duì)外輸出。

圖片來(lái)源自：https://zhuanlan.zhihu.com/p/450584880

EasyGraph整體上采用存儲(chǔ)計(jì)算分離架構(gòu)，在KV存儲(chǔ)組件上適配了開(kāi)源的TiKV及內(nèi)部分布式KV；TiKV基于rocksdb實(shí)現(xiàn)了分區(qū)和副本管理，并在TiDB上有成熟的解決方案，適配TiKV可以實(shí)現(xiàn)存儲(chǔ)層的可擴(kuò)展性，TiKV基于Raft算法實(shí)現(xiàn)了數(shù)據(jù)多副本之間的一致性。EasyGraph也自研了圖可視化分析引擎，在可視化效果及規(guī)模上都有明顯的提升，支持幾十萬(wàn)級(jí)點(diǎn)邊渲染分析，以及用戶級(jí)靈活的布局展示和可視化分析。

EasyGraph也支持AngelGraph圖計(jì)算引擎，其包括幾十種傳統(tǒng)圖算法、Embedding及GNN算法，如社區(qū)發(fā)現(xiàn)、標(biāo)簽傳播、隨機(jī)游走等算法，這些算法進(jìn)一步提升對(duì)圖數(shù)據(jù)的挖掘分析能力。

4、Neo4j latest?

最新版本的Neo4j已經(jīng)支持了分布式模式以完善對(duì)高可用性和可擴(kuò)展性的支持，其通過(guò)多副本的方式來(lái)防止數(shù)據(jù)丟失，如下圖所示：

圖片來(lái)源自：https://neo4j.com/docs/operations-manual/current/clustering/introduction/

Neo4j通過(guò)Primary Mode將一份數(shù)據(jù)備份到多個(gè)servers上并通過(guò)raft協(xié)議來(lái)保證一致性。與之相對(duì)應(yīng)地，一次寫(xiě)入需要保證至少在(N/2+1）個(gè)副本上寫(xiě)成功才可以返回成功，因此在primary mode下服務(wù)實(shí)例數(shù)量越多，寫(xiě)性能就越差。而為了實(shí)現(xiàn)可擴(kuò)展性，Neo4j也支持了Secondary mode，即支持對(duì)多個(gè)只讀副本的部署以提高集群整體的讀能力，只讀副本是功能齊全的Neo4j數(shù)據(jù)庫(kù)，能夠完成任意（只讀）圖數(shù)據(jù)查詢和過(guò)程。只讀副本是通過(guò)事務(wù)日志shipping來(lái)完成對(duì)主副本的數(shù)據(jù)異步同步的。

Neo4j也支持了數(shù)據(jù)科學(xué)（Graph Data Science）庫(kù)，其包含了許多圖分析算法，比如社區(qū)發(fā)現(xiàn)，路徑搜索等，甚至也支持了少量的圖神經(jīng)網(wǎng)絡(luò)算法（比如GraphSage， Node2Vec）。這些算法統(tǒng)一集成在了Neo4j的Cypher語(yǔ)言體系下，以提供給用戶統(tǒng)一的圖查詢/圖分析體驗(yàn)。

5、TigerGraph?

TigerGraph如今已經(jīng)發(fā)展成為了一個(gè)商業(yè)化程度僅次于Neo4j的圖數(shù)據(jù)庫(kù)產(chǎn)品，但由于其是一個(gè)閉源產(chǎn)品，很多技術(shù)實(shí)現(xiàn)我們無(wú)從知曉。從TigerGraph網(wǎng)站上的官方技術(shù)博客描述來(lái)看，TigerGraph 是一款分布式MPP圖數(shù)據(jù)庫(kù)，同時(shí)支持在線事務(wù)處理（OLTP）和在線分析查詢（OLAP），也集成了基于PyG的圖神經(jīng)網(wǎng)絡(luò)訓(xùn)練功能。

從架構(gòu)上看，TigerGraph集成了較為完善的數(shù)據(jù)導(dǎo)入功能，可以在系統(tǒng)在線的情況下，將關(guān)系型數(shù)據(jù)或其他格式的半結(jié)構(gòu)化數(shù)據(jù)導(dǎo)入到TigerGraph系統(tǒng)中。TigerGraph的Graph Storage Engine（GSE）負(fù)責(zé)了對(duì)數(shù)據(jù)的壓縮和存儲(chǔ)，其將數(shù)據(jù)編碼、轉(zhuǎn)換成一種對(duì)MPP處理友好的圖原生存儲(chǔ)格式后加載至Graph Processing Engine（GPE），而GPE則是具體負(fù)責(zé)響應(yīng)查詢請(qǐng)求和圖計(jì)算分析的執(zhí)行引擎。TigerGraph還包含一個(gè)可視化的客戶端以及 REST API，并集成了很多企業(yè)數(shù)據(jù)基礎(chǔ)設(shè)施服務(wù)。TigerGraph使用Apache Kafka讓GSE與GPE進(jìn)行數(shù)據(jù)同步，邏輯上GPE可以理解為一個(gè)內(nèi)存存儲(chǔ)層，而GSE是一個(gè)圖原生的持久化存儲(chǔ)層；數(shù)據(jù)的更新將先反應(yīng)到GPE層，然后通過(guò)Kafka將Transaction Log交給GSE消費(fèi)并完成持久化更新。

圖片來(lái)源自：https://docs.tigergraph.com/tigergraph-server/current/intro/internal-architecture

在OLTP功能上，TigerGraph支持完整的ACID特性，支持最高的serializability事務(wù)隔離級(jí)別。TigerGraph支持垂直擴(kuò)展和水平擴(kuò)展，且可以對(duì)集群中的圖數(shù)據(jù)自動(dòng)分區(qū)。從這點(diǎn)來(lái)看，TigerGraph對(duì)大規(guī)模圖數(shù)據(jù)的存儲(chǔ)支持得比Neo4j要友好很多。TigerGraph使用自定義的GSQL語(yǔ)言來(lái)表達(dá)查詢邏輯，GSQL將SQL風(fēng)格的查詢語(yǔ)法與Cypher風(fēng)格的圖遍歷語(yǔ)法結(jié)合在了一起，并支持用戶自定義函數(shù)。

四、圖數(shù)據(jù)庫(kù)的未來(lái)

圖數(shù)據(jù)庫(kù)在經(jīng)歷了最近幾年的蓬勃發(fā)展之后，無(wú)論是系統(tǒng)性能還是穩(wěn)定性都得到了大幅提升，那接下來(lái)Graph Database Community再會(huì)往哪些方向發(fā)展呢？

筆者認(rèn)為，一方面統(tǒng)一圖數(shù)據(jù)庫(kù)的查詢語(yǔ)言標(biāo)準(zhǔn)（GQL）是一件迫在眉睫的事情，標(biāo)準(zhǔn)的制定將有利于降低用戶的學(xué)習(xí)門(mén)檻，并使得圖數(shù)據(jù)庫(kù)的查詢優(yōu)化技術(shù)可以得到更充分的發(fā)展，比如根據(jù)圖數(shù)據(jù)分布往往不均勻的特點(diǎn)提出定制化的基于規(guī)則和基于代價(jià)的優(yōu)化策略，還比如可以將如今在OLAP領(lǐng)域大紅大紫的向量化執(zhí)行技術(shù)和代碼生成技術(shù)引入到圖查詢引擎中，以提升Graph OLAP的執(zhí)行效率。而另一方面，筆者認(rèn)為圖數(shù)據(jù)庫(kù)之所以能在最近幾年大火的另一個(gè)原因是源于圖計(jì)算技術(shù)和圖AI技術(shù)的崛起。而這些技術(shù)能夠同時(shí)引起各界學(xué)者和工程師的關(guān)注也是因?yàn)閳D狀數(shù)據(jù)的獨(dú)特之處 -- 特別是在這個(gè)數(shù)據(jù)互聯(lián)的時(shí)代，需要盡可能在低成本、短時(shí)間的前提下從海量數(shù)據(jù)中挖掘出關(guān)聯(lián)最深，價(jià)值最大的信息，圖就是非常理想的解決方案。除此以外，我們很難從其他種類(lèi)的NoSQL模型、大數(shù)據(jù)框架或關(guān)系型數(shù)據(jù)庫(kù)中找到隱式數(shù)據(jù)關(guān)聯(lián)的解決辦法。

隨著算力的提升和大數(shù)據(jù)生態(tài)的日漸成熟，我們的目標(biāo)正在從存儲(chǔ)系統(tǒng)的效率轉(zhuǎn)變?yōu)閺拇鎯?chǔ)系統(tǒng)包含的數(shù)據(jù)中提取價(jià)值。圖數(shù)據(jù)庫(kù)需要與圖計(jì)算系統(tǒng)、圖AI系統(tǒng)，乃至流圖系統(tǒng)緊密地聯(lián)動(dòng)起來(lái)，才能讓圖數(shù)據(jù)的價(jià)值在用戶手中得到充分的釋放。而如何打造一套可以讓不同目標(biāo)的圖系統(tǒng)都集成到一起，提供統(tǒng)一DDL并簡(jiǎn)單易用的graph infrastructure呢？我們能看到各個(gè)廠商和初創(chuàng)公司正在給出自己的答案...