從擴(kuò)線查詢能力分析分布式圖數(shù)據(jù)庫Titan的設(shè)計(jì)改進(jìn)點(diǎn)

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

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

我們先來參考一下DB-Engines提供的數(shù)據(jù)庫趨勢信息：

從DB-Engines的數(shù)據(jù)庫趨勢信息來看，從13年至今，Graph DBMS是增長最快速的一類數(shù)據(jù)庫。而下圖給出了知名圖數(shù)據(jù)庫的數(shù)量以及在DB-Engines所收錄的341種數(shù)據(jù)庫中所占的比重：

盡管從實(shí)際的應(yīng)用現(xiàn)狀來看，圖數(shù)據(jù)庫依然還是一個(gè)相對小眾的數(shù)據(jù)庫，但從DB-Engines的趨勢信息反映了圖數(shù)據(jù)庫未來的巨***展?jié)摿Α?/p>

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

百度百科對圖數(shù)據(jù)庫的定義：

圖數(shù)據(jù)庫是NoSQL數(shù)據(jù)庫的一種，它應(yīng)用圖理論存儲實(shí)體之間的關(guān)系信息。最常見例子就是社會網(wǎng)絡(luò)中人與人之間的關(guān)系。關(guān)系型數(shù)據(jù)庫用于存儲“關(guān)系型”數(shù)據(jù)的效果并不好，其查詢復(fù)雜、緩慢、超出預(yù)期，而圖形數(shù)據(jù)庫的獨(dú)特設(shè)計(jì)恰恰彌補(bǔ)了這個(gè)缺陷。

如下內(nèi)容翻譯自維基百科：

圖數(shù)據(jù)庫以圖論為基礎(chǔ)，并以節(jié)點(diǎn)（頂點(diǎn)）、邊和屬性作為基本概念。

節(jié)點(diǎn)表示實(shí)體，如人、企業(yè)、賬戶或任何其他要表示的事物，大致相當(dāng)于關(guān)系數(shù)據(jù)庫中的記錄、關(guān)系或行，或文檔數(shù)據(jù)庫中的文檔。

邊，也稱為關(guān)系，是連接節(jié)點(diǎn)之間的線，表示它們之間的關(guān)系。邊是圖數(shù)據(jù)庫中的關(guān)鍵概念，代表了在其他系統(tǒng)中不能直接實(shí)現(xiàn)的關(guān)系的抽象。

屬性是節(jié)點(diǎn)（和邊）的重要關(guān)聯(lián)信息。例如，“維基百科”是一個(gè)節(jié)點(diǎn)，它的關(guān)聯(lián)信息可以是“網(wǎng)站”，或者“參考文獻(xiàn)”，或者是一個(gè)以“w”開頭的字母，這些信息都可以是這個(gè)節(jié)點(diǎn)的屬性。

圖其實(shí)是一種表達(dá)能力非常強(qiáng)的模型，如用來描述社交關(guān)系網(wǎng)絡(luò)，用戶與產(chǎn)品的推薦關(guān)系，通信網(wǎng)絡(luò)，交通網(wǎng)絡(luò)等等，這類數(shù)據(jù)的特點(diǎn)是各種實(shí)體間的關(guān)系錯(cuò)綜復(fù)雜，而實(shí)體自身還有屬性描述信息，而如果使用傳統(tǒng)的RDBMS來存儲這類數(shù)據(jù)，將使得RDBMS變得”沉重不堪”。這類數(shù)據(jù)其實(shí)廣泛存在于現(xiàn)實(shí)世界中，尤其是伴隨著不斷發(fā)展的人工智能技術(shù)，越來越多的復(fù)雜關(guān)系型\向量型數(shù)據(jù)被挖掘出來，圖數(shù)據(jù)庫將會成為一種基礎(chǔ)的數(shù)據(jù)庫技術(shù)。在區(qū)塊鏈領(lǐng)域，作為BlockChain 3.0的典型代表技術(shù)IOTA，它的核心技術(shù)其實(shí)已經(jīng)是圖技術(shù)。

圖數(shù)據(jù)庫與關(guān)系型數(shù)據(jù)庫

數(shù)十年來，開發(fā)者習(xí)慣了使用關(guān)系型數(shù)據(jù)庫處理關(guān)聯(lián)的、半結(jié)構(gòu)化的數(shù)據(jù)集。關(guān)系型數(shù)據(jù)庫設(shè)計(jì)之初是為了處理紙質(zhì)表格以及表格化結(jié)構(gòu)，它們試圖對這種實(shí)際中的特殊聯(lián)系進(jìn)行建模。然而關(guān)系型數(shù)據(jù)庫在處理“復(fù)雜關(guān)系”數(shù)據(jù)時(shí)卻顯得力不從心。

讓我們通過社交網(wǎng)絡(luò)領(lǐng)域中一些簡單的查詢來理解關(guān)系型數(shù)據(jù)庫中關(guān)系查詢的代價(jià)。下面是《Graph Databases》一書中提供的一個(gè)非常經(jīng)典的例子：

下圖展示了一個(gè)記錄朋友關(guān)系的簡單的連接表設(shè)計(jì)：

當(dāng)回答““who are Bob’s friends?”這個(gè)問題時(shí)很簡單。SQL語句如下：

基于這個(gè)示例數(shù)據(jù)，答案是Alice和Zach。這不是一個(gè)代價(jià)高昂或困難的查詢，因?yàn)樗褂昧薟HERE語句”WHERE p2.Person = ‘Bob’”，使得返回的行數(shù)是可預(yù)期的和受限的。

但如果要回答“who is friends with Bob?”，SQL語句則為：

這個(gè)查詢的答案是Alice。這個(gè)反向查詢在實(shí)現(xiàn)上也很簡單，但是數(shù)據(jù)庫端的花銷卻大了一些，因?yàn)樗械臄?shù)據(jù)行都在PersonFriend中。我們可以加入索引，然后仍會涉及代價(jià)高昂的間接層。

當(dāng)問題是“誰是Alice的朋友的朋友？”時(shí)查詢就更復(fù)雜了:

當(dāng)然基于RDBMS可以做到，而且這個(gè)查詢還是可能在合理的時(shí)間內(nèi)得到答案的。當(dāng)查詢延伸到第4層、第5層的朋友關(guān)系時(shí)，由于遞歸的JOIN查詢使得此時(shí)的時(shí)間空間復(fù)雜度變得非常高，從而使查詢的效率急劇惡化。

但利用圖數(shù)據(jù)庫，我們可以通過如下模型來描述上面的Person與PersonFriend兩個(gè)表中的數(shù)據(jù)：

在圖數(shù)據(jù)庫中，類似于”Bob的朋友”以及”Bob的朋友的朋友“這類查詢，我們稱之為“擴(kuò)線查詢”。如果需要查詢”Bob的朋友的朋友”，只需要從Bob這個(gè)節(jié)點(diǎn)出發(fā)，進(jìn)行2層擴(kuò)線查詢。不僅在數(shù)據(jù)模型的表達(dá)上更加直觀，查詢效率也會有質(zhì)的提升。

關(guān)于Titan

Titan有如下關(guān)鍵設(shè)計(jì)：

支持大規(guī)模圖數(shù)據(jù)存儲，Titan支持?jǐn)?shù)據(jù)分片

支持彈性和線性擴(kuò)展，高可用，高容錯(cuò)

支持Gremlin圖查詢語言

支持利用Hadoop計(jì)算框架對圖數(shù)據(jù)進(jìn)行分析

支持外部索引：ElasticSearch、Solr、Lucene

支持ACID和最終一致性

支持多儲存引擎：Cassandra、HBase、Berkeley DB和Immemory模式

基于Apache License 2.0

正是基于這些設(shè)計(jì)，Titan在2015年和2016年期間積累了一批用戶，因?yàn)楫?dāng)時(shí)并沒有多少開源圖數(shù)據(jù)庫可選。Titan項(xiàng)目原由Aurelius開發(fā)，但后來該公司被DataStax收購，Titan原來的開發(fā)團(tuán)隊(duì)轉(zhuǎn)向閉源圖數(shù)據(jù)庫產(chǎn)品的研發(fā)，因此，導(dǎo)致Titan項(xiàng)目停更。后來，由IBM領(lǐng)頭，在Linux社區(qū)開啟了JanusGraph項(xiàng)目（該項(xiàng)目直接從Titan項(xiàng)目Fork而來）來試圖讓停更的Titan復(fù)活。但從JanusGraph代碼的commits記錄來看，尚未見到有較大的改動(dòng)。

Titan擴(kuò)線查詢

下圖是基于Titan的三層擴(kuò)線過程詳解：

每一層查詢的輸入：

頂點(diǎn)集合VSet。第一層為用戶給定的頂點(diǎn)集合，后面的每一層為上一層查詢滿足條件的邊的頂點(diǎn)

頂點(diǎn)Label/頂點(diǎn)屬性的過濾條件ConditionA；

邊Label/邊屬性的過濾條件ConditionB。

每一層查詢的輸出：

VSet中滿足條件ConditionA的頂點(diǎn)及屬性集合ResultVSet

ResultVSet中與每一個(gè)頂點(diǎn)相關(guān)的滿足條件ConditionB的邊的集合

關(guān)于最后一次查詢：

最后一次擴(kuò)線查詢只查詢除了滿足ConditionB的邊，但與這些邊相關(guān)的頂點(diǎn)僅有頂點(diǎn)ID的信息，尚不包含任何屬性信息，更不確定是否滿足ConditionA，因此，需要再做一次屬性查詢。

查詢耗時(shí)估算方法：

假設(shè)，每一個(gè)頂點(diǎn)的出入度為M，屬性查詢耗時(shí)TP，邊查詢耗時(shí)TE，屬性與邊混合查詢耗時(shí)TR，理論上，從一個(gè)頂點(diǎn)擴(kuò)線總耗時(shí)約為：

TR+M＊TR+M＊M＊TR+M＊M＊M＊TP

因?yàn)閷傩耘c邊是融合在一個(gè)列族中的，因此，屬性查詢耗時(shí)與邊查詢耗時(shí)是相互有影響的。從HBase查詢原理上分析，TP/TE/TR的差別不是很明顯，尤其是數(shù)據(jù)都沒有命中緩存的情況下。

通過對Titan擴(kuò)線查詢能力的實(shí)際測試，得到如下一些結(jié)論：

當(dāng)點(diǎn)的平均出入度為20時(shí)（即一個(gè)頂點(diǎn)的關(guān)聯(lián)邊的數(shù)目有20個(gè)），從一個(gè)點(diǎn)出發(fā)，三層擴(kuò)線耗時(shí)在秒級別

當(dāng)點(diǎn)的平均出入度達(dá)到100，若無過濾條件，1個(gè)頂點(diǎn)三層擴(kuò)線的結(jié)果將達(dá)到將近100w點(diǎn)和100w邊，測試結(jié)果顯示，在沒有任何緩存的情況下，1個(gè)點(diǎn)的擴(kuò)線查詢耗時(shí)超過300秒

當(dāng)適當(dāng)?shù)脑O(shè)置過濾條件將三層擴(kuò)線的結(jié)果控制在10w級別，耗時(shí)在100s左右，50w級別耗時(shí)200s左右

從上面信息可以看出來，Titan的擴(kuò)線查詢效率是比較低的。下文中我們將結(jié)合Titan的數(shù)據(jù)結(jié)構(gòu)進(jìn)行相關(guān)分析。

Titan數(shù)據(jù)模型

在Titan中，對象實(shí)體被稱之為”頂點(diǎn)(Vertex)”，”Vertex”可以有表示其分類的Label信息，而Vertex的描述信息稱之為Property。”Vertex”與”Vertex”之間的關(guān)系，被稱之為”邊(Edge)”。一個(gè)”Edge”可以是單向的，也可以是雙向的。Edge有代表其分類的Label信息，Edge也可以有Property描述信息。

下面是Titan Document中提供的數(shù)據(jù)模型設(shè)計(jì)圖：

以HBase作為后端存儲引擎為例，我們簡單說明一下上圖中所提供的信息：

RowKey為vertex id

一個(gè)Vertex的Properties信息，以及與該Vertex相關(guān)的Edges，都以獨(dú)立的列存儲，而且被存成了一行數(shù)據(jù)

表示Edge的列中，包含了Label信息，Edge ID，相鄰Vertex信息，屬性等信息。

表示Vertex Perperty的列中，包含了Property的ID，以及Property的值

Titan有哪些待改進(jìn)點(diǎn)

問題1：頂點(diǎn)屬性和邊存儲在一行中，讀取時(shí)會相互影響性能

假設(shè)頂點(diǎn)有10個(gè)屬性，出邊和入邊總共100個(gè)，則在該頂點(diǎn)的一行數(shù)據(jù)中，會有110列（除用戶數(shù)據(jù)之外，還會有一些系統(tǒng)屬性，此處忽略），那么查詢該頂點(diǎn)的屬性時(shí)相當(dāng)于從110列中只取出10列，在效率上肯定慢于僅從10列中取10列數(shù)據(jù)，因?yàn)槎鄴呙枇艘恍o效數(shù)據(jù)。也就是說當(dāng)點(diǎn)的出入度越大時(shí)，屬性查詢耗時(shí)將會越大，在擴(kuò)線的最后一次查詢點(diǎn)屬性時(shí)，就會耗時(shí)越久。

問題2：存儲邊的列中，耦合了屬性(可能是多個(gè))以及Label等信息，屬性查詢和更新代價(jià)較大

從Titan的數(shù)據(jù)結(jié)構(gòu)可以看出，邊作為頂點(diǎn)中的一列存儲，邊的屬性也全部存儲在這一列中，那么更新其中某一個(gè)屬性時(shí)，需要先獲取整個(gè)邊的數(shù)據(jù)，修改完成后再寫回，效率較低。而且針對邊的屬性過濾，Titan的做法是將數(shù)據(jù)取回客戶端，在客戶端進(jìn)行過濾。所以對于擴(kuò)線場景，需要將所有的邊取回客戶端，然后再進(jìn)行邊的過濾，增加了網(wǎng)絡(luò)傳輸?shù)南摹?/p>

問題3：Titan支持多個(gè)后端存儲其實(shí)是一把雙刃劍

Titan支持Cassandra、HBase、Berkeley DB和Immemory模式，JanusGraph還增加了BigTable的支持，無疑可以滿足更多的用戶，但是為了支持多個(gè)后端存儲，就需要在軟件架構(gòu)上增加一個(gè)可以適配多個(gè)存儲的數(shù)據(jù)格式（StaticBuffer），數(shù)據(jù)無論是寫入還是讀取，都需要先轉(zhuǎn)化成中間格式，這里帶來了序列化和反序列化的一些性能損耗。當(dāng)數(shù)據(jù)量比較小時(shí)，性能損耗可能還不是特別明顯，但是當(dāng)點(diǎn)和邊到百萬級別，這個(gè)損耗值相當(dāng)可觀。

問題4：Titan把后端存儲當(dāng)做黑盒，幾乎純Client端的實(shí)現(xiàn)

以HBase為例，Titan完全可以基于HBase深度定制一些功能，例如可以利用HBase的Coprocessor能力，將計(jì)算過程下推到HBase端，還可以定制查詢過濾器，使得查詢更加高效。但Titan卻完全未利用這些能力。

在提出了這些問題之后，事實(shí)上也是為JanusGraph指明了關(guān)鍵的優(yōu)化方向。事實(shí)上，正是基于這些點(diǎn)，我們做過一些優(yōu)化嘗試，可以使得擴(kuò)線查詢有非常顯著的提升，這些我們將再后續(xù)文章中展開。

圖數(shù)據(jù)庫與圖引擎

很多人往往混淆了圖數(shù)據(jù)庫與圖引擎的概念，兩者其實(shí)有各自的聚焦點(diǎn):

圖數(shù)據(jù)庫：偏重于海量圖數(shù)據(jù)的實(shí)時(shí)存儲以及OLTP查詢能力，本文著重介紹了圖數(shù)據(jù)庫Titan/JanusGraph，另外一個(gè)非常典型的圖數(shù)據(jù)庫為Neo4j。

圖引擎：偏重于在海量圖數(shù)據(jù)中利用成熟的圖算法以及圖計(jì)算引擎進(jìn)行OLAP分析能力，如Pregel、Powergraph、GraphX等。

圖數(shù)據(jù)庫與圖引擎，是一種互補(bǔ)關(guān)系，未來會有大量的結(jié)合應(yīng)用場景。但在一個(gè)系統(tǒng)中，也完全可能融合這兩種能力。去年年底，網(wǎng)上一篇名為《從圖引擎平臺技術(shù)，看華為云EI的決心和野心》的文章介紹了華為自研的高性能圖引擎技術(shù)EYWA，能夠在百億邊規(guī)模的圖數(shù)據(jù)集中，提供秒級甚至是毫秒級的擴(kuò)線查詢能力，這是一個(gè)非常驚訝的結(jié)果，EYWA正是華為云已經(jīng)上線公測的圖引擎服務(wù)(GES)的核心技術(shù)，相信未來能在EYWA中看到融合了圖數(shù)據(jù)庫與圖引擎的一體化圖計(jì)算能力。

本文轉(zhuǎn)載自微信公眾號【Nosql漫談】。

NoSQL數(shù)據(jù)庫

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。