目的
在圖數(shù)據(jù)庫(kù)領(lǐng)域一直存在著兩種遍歷引擎:分布式圖數(shù)據(jù)庫(kù)遍歷引擎和本地圖數(shù)據(jù)庫(kù)遍歷引擎斧吐。
簡(jiǎn)單來(lái)說(shuō),本地圖數(shù)據(jù)庫(kù)遍歷引擎通常用于將單機(jī)圖數(shù)據(jù)庫(kù)中圖數(shù)據(jù)的遍歷交惯,滿足用戶的實(shí)時(shí)圖遍歷需求浅妆。分布式圖數(shù)據(jù)庫(kù)遍歷引擎通常用于分布式數(shù)據(jù)庫(kù)中圖數(shù)據(jù)的遍歷,滿足用戶的批量圖遍歷需求壳嚎。
本地圖數(shù)據(jù)庫(kù)遍歷引擎和分布式圖數(shù)據(jù)庫(kù)遍歷引擎首先在應(yīng)用規(guī)模上是不同的桐智。
本地圖數(shù)據(jù)庫(kù)遍歷引擎
上圖即是一份圖數(shù)據(jù),數(shù)據(jù)存儲(chǔ)在單機(jī)圖數(shù)據(jù)庫(kù)中烟馅。我們對(duì)于圖的遍歷需求是
尋找出頂點(diǎn)1的好朋友的好朋友说庭,Gremlin遍歷路徑描述如下:
g.v(1).outE('friend').inV.outE('friend').inV
在本地圖數(shù)據(jù)庫(kù)遍歷引擎中,將遍歷路徑解析成執(zhí)行計(jì)劃郑趁,并實(shí)例化一個(gè)遍歷器(Traverser)刊驴,由這個(gè)遍歷器去對(duì)圖數(shù)據(jù)進(jìn)行遍歷并返回遍歷結(jié)果。
分布式數(shù)據(jù)庫(kù)遍歷引擎
分布式圖數(shù)據(jù)庫(kù)利用圖分割方法,將一個(gè)完整的圖數(shù)據(jù)分割后存在不同分區(qū)中捆憎。當(dāng)需要對(duì)這個(gè)圖進(jìn)行遍歷分析的時(shí)候舅柜,由于底層數(shù)據(jù)的分布式存儲(chǔ),一個(gè)遍歷實(shí)例往往是完成不了這種遍歷需求的躲惰。
這個(gè)時(shí)候往往需要用到分布式式數(shù)據(jù)庫(kù)遍歷引擎致份。分布式遍歷引擎會(huì)起多個(gè)遍歷器,這些遍歷器遍歷的數(shù)據(jù)是不同的础拨,它們是平行計(jì)算的氮块,但是它們之間會(huì)不斷的交換各自的計(jì)算結(jié)果,并將它傳給其它的遍歷器诡宗,這樣其它遍歷器得到這部分計(jì)算結(jié)果后與本地的遍歷數(shù)據(jù)進(jìn)行合并滔蝉,從而得到整個(gè)圖的遍歷結(jié)果。
如上圖是一份圖數(shù)據(jù)僚焦,假設(shè)這個(gè)圖的數(shù)據(jù)存儲(chǔ)在不同的圖數(shù)據(jù)庫(kù)分區(qū)上锰提,我們的需求是在這個(gè)圖中使用ranking算法,那么我們?cè)诿糠猪旤c(diǎn)數(shù)據(jù)的遍歷器中都需要運(yùn)行如下的代碼:
public void evaluateStep(int step) {
if(!this.inbox.isEmpty() && step < 1000) {
this.rank = this.rank + this.inbox.size();
for(Vertex vertex : this.adjacentVertices()) {
for(int i=0; i<this.inbox.size(); i++) {
this.sendMessage(vertex);
}
}
this.inbox.clear();
}
}