圖數(shù)據(jù)庫技術(shù)發(fā)展趨勢研究

(中國信息通信研究院云計算與大數(shù)據(jù)研究所，北京100191)

0 引言

當(dāng)前，互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、金融等領(lǐng)域中積累了海量的數(shù)據(jù)，數(shù)據(jù)間的關(guān)聯(lián)可以產(chǎn)生重要的價值。隨著大數(shù)據(jù)技術(shù)的不斷發(fā)展，如何匯集各個領(lǐng)域數(shù)據(jù)、通過數(shù)據(jù)間的關(guān)聯(lián)與分析挖掘海量數(shù)據(jù)的價值成為了各行業(yè)關(guān)注的重點。在技術(shù)的探索中，圖處理技術(shù)為數(shù)據(jù)賦能提供了新的方式，可驅(qū)動行業(yè)更好地發(fā)展。

圖數(shù)據(jù)通過將實體與關(guān)系點變化的方式將知識結(jié)構(gòu)化保存，是一種基于事務(wù)關(guān)聯(lián)關(guān)系的模型表達，具有數(shù)據(jù)天然可解釋性，備受學(xué)術(shù)界和工業(yè)界推崇。在數(shù)據(jù)的關(guān)聯(lián)分析中，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫需要進行大量的關(guān)聯(lián)操作，在小規(guī)模數(shù)據(jù)的情況下這樣的操作還可以接受，但是當(dāng)數(shù)據(jù)規(guī)模逐漸增大，關(guān)聯(lián)操作會造成性能呈指數(shù)級下降。圖數(shù)據(jù)庫相較于傳統(tǒng)關(guān)系型數(shù)據(jù)庫和NoSQL數(shù)據(jù)庫，其豐富完整的關(guān)系表達提供了高效的關(guān)聯(lián)查詢和完備的實體信息。

大型互聯(lián)網(wǎng)公司很早便開始創(chuàng)建自己專有的圖處理技術(shù)及圖數(shù)據(jù)庫系統(tǒng)，用于社交關(guān)系挖掘、網(wǎng)頁檢索與排序、推薦系統(tǒng)等，并獲得了巨大的商業(yè)成功。目前，通信、互聯(lián)網(wǎng)、電子商務(wù)、社交網(wǎng)絡(luò)和物聯(lián)網(wǎng)等領(lǐng)域中積累了大量的圖數(shù)據(jù)，其規(guī)模巨大并且不斷增長：Facebook的社交網(wǎng)絡(luò)規(guī)模在2011年已超過8億頂點；而騰訊QQ的社交網(wǎng)絡(luò)目前在10億個頂點的規(guī)模；在電信行業(yè)中，廣州市僅一個月內(nèi)由電話呼叫方和被呼叫方組成的圖的規(guī)模就超過4.5千萬個頂點、1.5億條邊；而ClueWeb[1]數(shù)據(jù)包含海量的網(wǎng)頁，其于2012年公布的數(shù)據(jù)集已經(jīng)達到10億個頂點、425億條邊的規(guī)模，僅是存儲邊的列表文件就超過400 GB。

但是，相比其他的數(shù)據(jù)庫技術(shù)，目前圖數(shù)據(jù)庫還處于起步階段，各方面的技術(shù)概念還未統(tǒng)一，應(yīng)用場景仍在探索，選型實施資料較少。本文將首先圍繞圖數(shù)據(jù)庫技術(shù)給出圖數(shù)據(jù)庫相關(guān)定義，從技術(shù)路線和性能進行圖數(shù)據(jù)庫與傳統(tǒng)關(guān)系型數(shù)據(jù)庫的對比研究；然后，介紹國內(nèi)外圖數(shù)據(jù)庫產(chǎn)業(yè)發(fā)展現(xiàn)狀與應(yīng)用場景；最后，根據(jù)產(chǎn)業(yè)現(xiàn)狀給出圖數(shù)據(jù)庫的一些未來發(fā)展趨勢研判。

1 圖數(shù)據(jù)庫概述

圖數(shù)據(jù)庫以圖論為理論基礎(chǔ)，使用圖模型，將關(guān)聯(lián)數(shù)據(jù)的實體作為頂點存儲，關(guān)系作為邊存儲，解決了數(shù)據(jù)復(fù)雜關(guān)聯(lián)帶來的嚴重隨機訪問問題。在分類上，圖數(shù)據(jù)庫可歸類為NoSQL數(shù)據(jù)庫。

1.1 圖模型

圖是一組對象的集合，由頂點和邊構(gòu)成，頂點表示實體或?qū)嵗?，如人、賬號、組織、業(yè)務(wù)等，它們可以類比于關(guān)系型數(shù)據(jù)庫里的記錄或行，或文檔數(shù)據(jù)庫里的文檔；邊是連接頂點的線，表示頂點之間的關(guān)聯(lián)關(guān)系。邊是圖數(shù)據(jù)庫中的關(guān)鍵概念，在關(guān)系型數(shù)據(jù)庫或文檔存儲數(shù)據(jù)庫中，沒有對邊的抽象概念進行直接實現(xiàn)。圖模型主要包含屬性圖、資源描述框架(Resource Description Framework, RDF)圖兩種(見圖1)。

圖1 圖模型示意圖

1.2 圖數(shù)據(jù)庫定義

圖數(shù)據(jù)庫基于圖模型，對圖數(shù)據(jù)進行存儲、操作和訪問，與關(guān)系型數(shù)據(jù)庫中的聯(lián)機事務(wù)處理(Online Transactional Processing，OLTP)數(shù)據(jù)庫是類似的, 支持事務(wù)、可持久化等特性。圖數(shù)據(jù)庫根據(jù)底層存儲實現(xiàn)的不同，可分為原生圖數(shù)據(jù)庫和非原生圖數(shù)據(jù)庫兩種。

(1)原生圖數(shù)據(jù)庫：使用圖模型進行數(shù)據(jù)存儲，可以針對圖數(shù)據(jù)做優(yōu)化，從而帶來更好的性能，例如Neo4j。

(2)非原生圖數(shù)據(jù)庫：底層存儲使用非圖模型進行存儲，在存儲之上封裝圖的語義，進行圖處理，其優(yōu)點是易于開發(fā)，適合產(chǎn)品眾多的大型公司，形成相互配合的產(chǎn)品棧，例如Titan、JanusGraph底層采用KV存儲非圖模型。

相較關(guān)系型數(shù)據(jù)庫，圖數(shù)據(jù)庫基于圖模型存儲和處理的方式主要有以下優(yōu)勢。

(1)萬物互聯(lián)，圖數(shù)據(jù)可以更直觀地表達數(shù)據(jù)之間的關(guān)聯(lián)關(guān)系。

(2)圖數(shù)據(jù)有強兼容性，可以更容易地存儲、擴展多種類型的數(shù)據(jù)。

(3)對關(guān)系數(shù)據(jù)的處理效率是關(guān)系型數(shù)據(jù)庫的2～3個數(shù)量級。

Ian Robinson等[2]曾經(jīng)在5000萬點和邊的數(shù)據(jù)規(guī)模下，對比了Neo4j與關(guān)系型數(shù)據(jù)庫在關(guān)聯(lián)查詢的時間消耗(見表1)，隨著關(guān)聯(lián)查詢深度的增加，關(guān)系型數(shù)據(jù)庫性能消耗呈指數(shù)倍增長甚至無法執(zhí)行。

表1 Neo4j與某關(guān)系型數(shù)據(jù)庫在關(guān)聯(lián)查詢的性能對比

1.3 圖數(shù)據(jù)庫技術(shù)架構(gòu)

當(dāng)前，市場上主流的圖數(shù)據(jù)庫主體架構(gòu)如圖2所示，分為存儲層、計算層和接口層。

圖2 圖數(shù)據(jù)庫系統(tǒng)架構(gòu)

(1)存儲層：圖數(shù)據(jù)庫有原生和非原生兩種存儲方式，這些數(shù)據(jù)通過圖存儲引擎進行圖數(shù)據(jù)結(jié)構(gòu)、索引邏輯上的管理。例如，原生圖數(shù)據(jù)庫中常使用鏈表或者B+樹、LSM樹(Log-Structured Merge-Tree，日志結(jié)構(gòu)合并樹)等樹狀結(jié)構(gòu)存儲圖數(shù)據(jù)；而非原生圖數(shù)據(jù)庫一般復(fù)用外部NoSQL數(shù)據(jù)庫進行數(shù)據(jù)存儲，然后通過存儲引擎將實際的數(shù)據(jù)以圖數(shù)據(jù)的邏輯進行管理。

(2)計算層：提供對操作的處理和計算，主要工作是基礎(chǔ)圖算法的實現(xiàn)，其次也包括數(shù)據(jù)庫通用的語法解析、任務(wù)調(diào)度、事務(wù)管理、優(yōu)化器等組件。目前，大多數(shù)圖數(shù)據(jù)庫只能提供基礎(chǔ)圖算法，復(fù)雜的全圖分析可能需要圖處理引擎對接進行。

(3)接口層：提供了查詢語言接口、API、SDK、可視化組件等對外提供服務(wù)。當(dāng)前，圖數(shù)據(jù)庫沒有統(tǒng)一的查詢語言，因此圖數(shù)據(jù)庫產(chǎn)品在提供其原有查詢語言外，也可能會提供Cypher、Gremlin等主流查詢語言接口便于用戶使用。此外，圖數(shù)據(jù)的天然可解釋性使得大多數(shù)圖數(shù)據(jù)庫產(chǎn)品也會提供一定的可視化能力，在數(shù)據(jù)庫層面直觀地為用戶展現(xiàn)數(shù)據(jù)間的關(guān)聯(lián)情況。

2 圖數(shù)據(jù)庫的計算

圖數(shù)據(jù)庫的使用場景主要為實時查詢，包括本地查詢、鄰居查詢和局部遍歷。用戶通過圖查詢語言在圖上進行遍歷、過濾和統(tǒng)計等操作，以滿足實時的需求。

此外，用戶常常會提出比實時查詢更為復(fù)雜的分析需求以挖掘圖數(shù)據(jù)中的潛在價值。在圖算法的實現(xiàn)上，最理想化的選擇是在圖數(shù)據(jù)庫上直接實現(xiàn)圖算法，但由于圖數(shù)據(jù)庫更側(cè)重于高并發(fā)和海量存儲，全圖算法更側(cè)重于迭代計算，因此目前更為常見的選擇是提供另外的圖處理引擎與圖數(shù)據(jù)庫集成(見圖3)：從圖數(shù)據(jù)庫對接或?qū)霐?shù)據(jù)到圖處理引擎中進行離線分析，結(jié)合其更為強大的計算能力對全圖進行迭代計算，尋找某種特定模式(社區(qū)發(fā)現(xiàn)或欺詐模式)或者路徑，滿足數(shù)據(jù)挖掘的應(yīng)用需求。

圖3 圖數(shù)據(jù)庫實時查詢與離線分析

2.1 實時查詢

數(shù)據(jù)庫為實時查詢提供了兩類常用的圖算法。

(1)圖遍歷：也被稱為圖搜索，是指訪問圖中每個頂點的過程，對圖的訪問和更新都以圖遍歷為基礎(chǔ)。圖遍歷常見算法包括廣度優(yōu)先搜索和深度優(yōu)先搜索。

(2)路徑發(fā)現(xiàn)：用以識別最符合大型網(wǎng)絡(luò)中兩點之間某些條件下的最短路徑。路徑發(fā)現(xiàn)常見算法包括最短路徑、最小權(quán)重生成樹和兩兩最短路徑。

2.2 離線分析

離線分析需要較長的時間來完成，分析的算法也相對復(fù)雜，可根據(jù)解決問題的目的不同分為以下幾類。

(1)中心性：是社交網(wǎng)絡(luò)分析中常用的一個概念，用以表達社交網(wǎng)絡(luò)中一個點或者一個人在整個網(wǎng)絡(luò)中所在中心的程度。通過知道一個頂點的中心性，可以用來了解和判斷該頂點在網(wǎng)絡(luò)中所占據(jù)的重要性。中心性常見算法包括佩奇排名、中介中心性、緊密度中心性和調(diào)和中心性。

(2)社群發(fā)現(xiàn)：用以劃分復(fù)雜網(wǎng)絡(luò)的社群結(jié)構(gòu)。在復(fù)雜網(wǎng)絡(luò)的研究中，如果網(wǎng)絡(luò)的頂點可以被容易地分組成頂點集，且使得每組頂點在內(nèi)部密集連接，則稱網(wǎng)絡(luò)具有社群結(jié)構(gòu)。這意味著社群內(nèi)的點的連接更為緊密，社群間的連接較為稀疏。社群發(fā)現(xiàn)常見算法包括Louvain算法和標簽傳播算法。

(3)圖挖掘：是基于圖的數(shù)據(jù)挖掘，用來發(fā)現(xiàn)數(shù)據(jù)的模式。通過分析圖數(shù)據(jù)，發(fā)現(xiàn)有趣、意外、有用的模式是非常必要的，可以用來幫助理解數(shù)據(jù)或作出決策，在社交網(wǎng)絡(luò)、醫(yī)藥化學(xué)、交通運輸網(wǎng)絡(luò)等諸多領(lǐng)域中有著重要意義。常用的圖挖掘算法包括頻繁子圖和數(shù)三角形。

隨著人工智能技術(shù)的發(fā)展，機器學(xué)習(xí)、深度學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)等算法也可通過圖處理引擎分析圖數(shù)據(jù)庫中的數(shù)據(jù)價值。當(dāng)前國際主流的圖處理引擎包括GraphX、GraphLab、Giraph等(見表2)。

表2 3類圖處理引擎

3 國內(nèi)外圖數(shù)據(jù)庫產(chǎn)業(yè)發(fā)展現(xiàn)狀

根據(jù)第三方機構(gòu)db-engines.com[3]的統(tǒng)計數(shù)據(jù)，近年來各類別數(shù)據(jù)庫中圖數(shù)據(jù)庫受歡迎程度可謂是水漲船高，在學(xué)術(shù)界和工業(yè)界均是討論熱點。

在工業(yè)界，自2007年第一款圖數(shù)據(jù)庫Neo4j問世開始，圖數(shù)據(jù)庫技術(shù)便不斷更新迭代并涌現(xiàn)了大批競爭者，到如今發(fā)展不過短短十余年，就已經(jīng)歷了底層存儲、架構(gòu)等技術(shù)方面的重大變革，由最初的單機圖數(shù)據(jù)庫向分布式大規(guī)模圖數(shù)據(jù)庫發(fā)展。

(1)Graph 1.0：小規(guī)模原生圖存儲

Graph 1.0時代(2007—2010年)，以Neo4j為代表，采用原生圖的方式實現(xiàn)圖存儲，獲得了比關(guān)系型數(shù)據(jù)庫快得多的復(fù)雜關(guān)聯(lián)數(shù)據(jù)查詢性能。然而，當(dāng)時在軟件架構(gòu)設(shè)計上只支持單機部署，圖數(shù)據(jù)庫產(chǎn)品性能和業(yè)務(wù)擴展能力有限。

(2)Graph 2.0：分布式大規(guī)模圖存儲

Graph2.0時代(2010年至今)，隨著大數(shù)據(jù)和物聯(lián)網(wǎng)的蓬勃發(fā)展，數(shù)據(jù)本身的豐富程度增加，數(shù)據(jù)之間的關(guān)聯(lián)性增多，擴展性成為數(shù)據(jù)庫行業(yè)共同的痛點，分布式架構(gòu)的興起催生了很多的分布式圖數(shù)據(jù)庫項目。在這一發(fā)展階段，支持分布式大規(guī)模圖存儲是關(guān)注的重點，圖存儲是否以原生的方式實現(xiàn)，不再是那么重要的問題，例如OrientDB選擇了支持原生圖存儲，自研了分布式圖數(shù)據(jù)存儲模塊，而JanusGraph則是在其他數(shù)據(jù)庫(Cassandra、HBase等)之上封裝實現(xiàn)圖的語義。通過支持在通用硬件上進行水平擴展，分布式圖數(shù)據(jù)庫具備了在海量關(guān)聯(lián)關(guān)系數(shù)據(jù)的存儲與實時深度查詢上絕佳的性能，但是在全圖分析等需要迭代計算的場景下仍需要結(jié)合圖處理引擎進行離線計算與分析。

目前，國外圖數(shù)據(jù)庫市場上開源、商用圖數(shù)據(jù)庫并駕齊驅(qū)，其中開源圖數(shù)據(jù)庫有Neo4j、JanusGraph、ArangoDB等，商用圖數(shù)據(jù)庫有Neptune(亞馬遜)、Cosmos(微軟)、TigerGraph等。而我國圖數(shù)據(jù)庫產(chǎn)業(yè)發(fā)展也隨著時代的更替而蓬勃發(fā)展，產(chǎn)品形態(tài)豐富?？傮w來看，國內(nèi)數(shù)據(jù)庫產(chǎn)品在大數(shù)據(jù)時代起步發(fā)展，有向分布式發(fā)展的需求與趨勢，強調(diào)對實時復(fù)雜圖查詢的性能要求，多使用自研的查詢語言，部分產(chǎn)品支持Cypher或Gremlin等查詢語言。

經(jīng)中國信息通信研究院的詳細調(diào)研及初步估計，當(dāng)前國內(nèi)的圖數(shù)據(jù)庫已有20余款產(chǎn)品，主要由4類研發(fā)主體發(fā)起，其特點如下。

(1)各大高校實驗室、研究所在圖數(shù)據(jù)庫發(fā)展初期研究開發(fā)的數(shù)據(jù)庫產(chǎn)品，主要聚焦于支持RDF圖模型的圖數(shù)據(jù)庫。

(2)大型互聯(lián)網(wǎng)企業(yè)由于自身積累的海量數(shù)據(jù)以及業(yè)務(wù)需求，催生了相關(guān)的數(shù)據(jù)庫產(chǎn)品。這些產(chǎn)品考慮到企業(yè)原有數(shù)據(jù)系統(tǒng)的情況，結(jié)合原有數(shù)據(jù)系統(tǒng)而開發(fā)的非原生圖數(shù)據(jù)庫不在少數(shù)，但絕大多數(shù)使用分布式架構(gòu)以供企業(yè)內(nèi)部使用，產(chǎn)品迭代較快，當(dāng)前也有部分產(chǎn)品實現(xiàn)了商業(yè)化。

(3)新興創(chuàng)業(yè)公司的圖數(shù)據(jù)庫產(chǎn)品，其最大特點是完全自主研發(fā)，強調(diào)高性能與數(shù)據(jù)庫的事務(wù)性，但是產(chǎn)品版本更新迭代相對較少，目前也在往分布式架構(gòu)發(fā)展。

(4)傳統(tǒng)IT服務(wù)商在圖數(shù)據(jù)庫的發(fā)展浪潮下，也加快了圖數(shù)據(jù)庫產(chǎn)品的研發(fā)步伐，并且通常與企業(yè)已有的其它產(chǎn)品(例如知識圖譜工具)一同對外輸出。

4 圖數(shù)據(jù)庫發(fā)展趨勢

目前，圖數(shù)據(jù)庫正處于飛速發(fā)展的狀態(tài)，隨著概念的普及、需求的變化，圖數(shù)據(jù)庫正在向如下方向發(fā)展。

4.1 查詢語言統(tǒng)一化

目前，圖數(shù)據(jù)庫市場查詢語言不一，有使用Gremlin、Cypher、SPARQL的，也有使用自己開發(fā)定義的查詢語言。用戶在業(yè)務(wù)中使用圖數(shù)據(jù)庫時學(xué)習(xí)成本高，對圖數(shù)據(jù)庫產(chǎn)品的推廣帶來一定的阻礙。同時，國際上ISO/IEC的GQL制定耗時4年，與當(dāng)前圖數(shù)據(jù)庫市場的發(fā)展速度嚴重不匹配。如何解決這一問題已是廠商與用戶共同關(guān)注的問題。

4.2 圖數(shù)據(jù)庫與圖處理引擎融合化

現(xiàn)今圖數(shù)據(jù)庫只能提供較簡單的圖算法進行實時查詢，不能獨立完成復(fù)雜的全圖迭代計算，需要與圖處理引擎結(jié)合，增加了額外的處理過程，加重了系統(tǒng)負擔(dān)。當(dāng)前，分布式圖數(shù)據(jù)庫支持了更大規(guī)模的數(shù)據(jù)，同時通過優(yōu)化保證了查詢的高性能，未來與圖處理引擎深度融合從而為用戶提供更簡單、更復(fù)雜的計算能力是圖數(shù)據(jù)庫廠商的研發(fā)方向。此外，圖神經(jīng)網(wǎng)絡(luò)理論與技術(shù)的飛速發(fā)展也值得關(guān)注。

4.3 軟硬件一體化

圖數(shù)據(jù)庫數(shù)據(jù)非規(guī)則訪問的特性一直是性能提升的重要瓶頸，隨著圖切分、圖算法的不斷提升，圖數(shù)據(jù)庫對底層硬件的需求愈加迫切，將來可以通過軟硬件協(xié)同設(shè)計的方式，比如采用NVM(非易失性存儲器)減少持久化存儲的開銷，使用RDMA(遠程直接數(shù)據(jù)存取)增強通信效率，或者將事務(wù)的部分要求交給硬件(例如HTM)來控制、簡化軟件設(shè)計等。

5 結(jié)束語

本文給出了圖數(shù)據(jù)庫的基本定義和通用架構(gòu)，介紹了圖數(shù)據(jù)庫的數(shù)據(jù)處理方式和相關(guān)算法，通過調(diào)研對國內(nèi)外圖數(shù)據(jù)庫產(chǎn)業(yè)發(fā)展進行了梳理和闡述，同時提出了產(chǎn)業(yè)側(cè)未來的一些發(fā)展趨勢?，F(xiàn)在，圖數(shù)據(jù)庫產(chǎn)品還在起步初期，技術(shù)能力還在飛速變革，應(yīng)用市場也在不斷的探索擴展。當(dāng)前，圖數(shù)據(jù)庫在知識圖譜、社交網(wǎng)絡(luò)、金融領(lǐng)域等均有不俗表現(xiàn)，隨著5G時代的到來，萬物互聯(lián)的概念越發(fā)深入人心，圖數(shù)據(jù)正是這種關(guān)聯(lián)方式最直接的表達。但是，圖數(shù)據(jù)庫產(chǎn)業(yè)的發(fā)展仍需要標準化工作來找尋正確的方向，普及觀點、規(guī)范產(chǎn)品能力依然是產(chǎn)業(yè)當(dāng)前的重中之重。