[發(fā)明專利]一種基于分布式圖數(shù)據(jù)庫的圖遍歷算法

有效

• 申請?zhí)枺?/td>: 202210452638.3
• 申請日: 2022-04-27
• 公開（公告）號: CN114817262B
• 公開（公告）日: 2023-03-28
• 發(fā)明（設(shè)計(jì)）人: 段翰聰;李林;張建;王書涵;陳鐸汝;李世豪;鄒濤;李濤
• 申請（專利權(quán)）人: 電子科技大學(xué)
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/27
• 代理公司: 成都行之智信知識產(chǎn)權(quán)代理有限公司 51256
• 代理人: 徐驥

本發(fā)明公開了一種基于分布式圖數(shù)據(jù)庫的圖遍歷算法，屬于分布式存儲索引技術(shù)領(lǐng)域，解決了傳統(tǒng)技術(shù)中需要依賴計(jì)算節(jié)點(diǎn)來保持圖遍歷的中間結(jié)果，通信開銷較高的技術(shù)問題，其包括步驟A：計(jì)算節(jié)點(diǎn)向主節(jié)點(diǎn)發(fā)送圖遍歷請求，主節(jié)點(diǎn)向其余從節(jié)點(diǎn)廣播該圖遍歷請求；步驟B：主節(jié)點(diǎn)和從節(jié)點(diǎn)收到圖遍歷請求后，從符合條件的起始節(jié)點(diǎn)開始遍歷自身存儲的所有節(jié)點(diǎn)，得到主節(jié)點(diǎn)和從節(jié)點(diǎn)符合篩選條件的NodeIDs，如果沒有符合條件的起始節(jié)點(diǎn)，則該存儲節(jié)點(diǎn)的本地任務(wù)完成等步驟，實(shí)現(xiàn)了將圖遍歷請求下推至存儲層，降低圖遍歷過程中存儲層與計(jì)算層之間的網(wǎng)絡(luò)通信開銷的技術(shù)效果。

技術(shù)領(lǐng)域

本發(fā)明涉及分布式存儲索引技術(shù)領(lǐng)域，具體涉及一種基于分布式圖數(shù)據(jù)庫的圖遍歷算法。

背景技術(shù)

隨著各種互聯(lián)網(wǎng)應(yīng)用的蓬勃發(fā)展，大規(guī)模數(shù)據(jù)下的復(fù)雜關(guān)系給傳統(tǒng)的關(guān)系型數(shù)據(jù)庫帶來了巨大的挑戰(zhàn)。在傳統(tǒng)的關(guān)系型數(shù)據(jù)庫領(lǐng)域，查詢同某個(gè)實(shí)體的相關(guān)聯(lián)的其它實(shí)體，或繼續(xù)以此向外延伸，數(shù)據(jù)庫使用者需要編寫冗長的SQL語句，同時(shí)數(shù)據(jù)庫系統(tǒng)通常會進(jìn)行復(fù)雜的多表join操作，查詢性能并不理想。這類數(shù)據(jù)之間關(guān)聯(lián)性查詢，成為了關(guān)系型數(shù)查詢。圖數(shù)據(jù)庫的出現(xiàn)，能夠很好的解決關(guān)系型數(shù)據(jù)庫所面臨的實(shí)體關(guān)聯(lián)類查詢的性能瓶頸，推動數(shù)據(jù)庫系統(tǒng)領(lǐng)域的發(fā)展。

在目前的分布式圖數(shù)據(jù)庫中，有多種不同架構(gòu)的方案。為了讓計(jì)算節(jié)點(diǎn)和存儲節(jié)點(diǎn)可以根據(jù)實(shí)際的業(yè)務(wù)需求，靈活地橫向擴(kuò)展，通常的方案都是計(jì)算節(jié)點(diǎn)與存儲節(jié)點(diǎn)分離。與此同時(shí)，分布式圖數(shù)據(jù)庫的網(wǎng)絡(luò)通信成本也隨之增大(副作用)，每次查詢需要從存儲節(jié)點(diǎn)拉取大量的數(shù)據(jù)到計(jì)算節(jié)點(diǎn)進(jìn)行計(jì)算，計(jì)算節(jié)點(diǎn)與存儲節(jié)點(diǎn)之間的網(wǎng)絡(luò)I/O效率成為了分布式圖數(shù)據(jù)庫的性能瓶頸之一。

現(xiàn)有技術(shù)中，圖遍歷被劃分成NodesFilter算子和Expand算子的組合，這意味著需要依賴計(jì)算節(jié)點(diǎn)來保持圖遍歷的中間結(jié)果，中間結(jié)果的序列化、反序列化以及網(wǎng)絡(luò)I/O的開銷對圖遍歷的性能影響較大。

發(fā)明內(nèi)容

本發(fā)明提供了一種基于分布式圖數(shù)據(jù)庫的圖遍歷算法，解決圖遍歷過程對計(jì)算節(jié)點(diǎn)依賴性較大，開銷較高的問題。

本發(fā)明通過下述技術(shù)方案實(shí)現(xiàn)：

一種基于分布式圖數(shù)據(jù)庫的圖遍歷算法，包括以下步驟：

步驟A：計(jì)算節(jié)點(diǎn)向主節(jié)點(diǎn)發(fā)送圖遍歷請求，主節(jié)點(diǎn)向其余從節(jié)點(diǎn)廣播該圖遍歷請求；

步驟B：從節(jié)點(diǎn)收到圖遍歷請求后，從符合條件的起始節(jié)點(diǎn)開始遍歷自身存儲的所有節(jié)點(diǎn)，得到本從節(jié)點(diǎn)符合篩選條件的NodeIDs，如果沒有符合條件的起始節(jié)點(diǎn)，則該從節(jié)點(diǎn)的JobMaster本地任務(wù)完成；

步驟C：在上述步驟B中，如果遍歷出存儲于其他從節(jié)點(diǎn)的節(jié)點(diǎn)，則將該節(jié)點(diǎn)存儲至圖遍歷路由表，并將圖遍歷路由表發(fā)送至目標(biāo)節(jié)點(diǎn)，得到該從節(jié)點(diǎn)中符合篩選條件的NodeIDs；如果沒有遍歷出儲存于其他存儲節(jié)點(diǎn)的節(jié)點(diǎn)，則該從節(jié)點(diǎn)向上級的Root匯報(bào)完成信息。

步驟D：Root收到完成信息后，本Root任務(wù)完成，并向JobMaster匯報(bào)，JobMaster收到全部Root任務(wù)，且本地遍歷任務(wù)全部完成，向計(jì)算節(jié)點(diǎn)匯報(bào)任務(wù)執(zhí)行完畢。

采用上述方案，能夠讓圖遍歷操作下沉至存儲層，減少計(jì)算層在查詢過程中和存儲層頻繁的網(wǎng)絡(luò)通信的開銷，通過該種完整的跨存儲節(jié)點(diǎn)的圖遍歷算法，能夠很好地支撐存儲節(jié)點(diǎn)內(nèi)的本地執(zhí)行和存儲節(jié)點(diǎn)間的請求轉(zhuǎn)發(fā)，不需要依賴于計(jì)算節(jié)點(diǎn)的同步，有效降低計(jì)算節(jié)點(diǎn)中的開銷。

所述步驟A的具體步驟為：

步驟A1：主節(jié)點(diǎn)收到計(jì)算節(jié)點(diǎn)的圖遍歷請求后創(chuàng)建TraversalTask對象，并將TraversalTask對象的類型設(shè)定為JobMaster，并創(chuàng)建與從節(jié)點(diǎn)內(nèi)Partition數(shù)量對應(yīng)的用于進(jìn)行圖遍歷的Worker。

步驟A2：上述JobMaster向其他的從節(jié)點(diǎn)廣播圖遍歷請求：