[發(fā)明專利]一種存儲優(yōu)化的分布式圖處理方法

有效

• 申請?zhí)枺?/td>: 201710301095.4
• 申請日: 2017-05-02
• 公開（公告）號: CN107122248B
• 公開（公告）日: 2020-01-21
• 發(fā)明（設(shè)計）人: 施展;馮丹;單玉祥;李君浩;毛艷;張蕓怡;方交鳳
• 申請（專利權(quán)）人: 華中科技大學(xué)
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/52;G06F9/54;G06F3/06
• 代理公司: 42201 華中科技大學(xué)專利中心
• 代理人: 張建偉;曹葆青

本發(fā)明公開了一種基于存儲優(yōu)化的分布式圖處理方法，屬于圖計算領(lǐng)域。本發(fā)明包括：數(shù)據(jù)預(yù)處理階段進行數(shù)據(jù)劃分；分發(fā)圖分區(qū)數(shù)據(jù)；開始數(shù)據(jù)迭代處理；更新消息傳遞；工作節(jié)點擴展決策；數(shù)據(jù)處理結(jié)束。本發(fā)明提出使用一致性哈希算法對圖數(shù)據(jù)進行分區(qū)和存儲，并設(shè)計實現(xiàn)了基于外存模式的分布式圖處理系統(tǒng)，利用動態(tài)存儲優(yōu)化的策略，根據(jù)負載調(diào)整圖的分區(qū)存儲，實現(xiàn)圖數(shù)據(jù)處理負載平衡，加快圖數(shù)據(jù)處理速度，解決現(xiàn)有技術(shù)存在的負載不平衡，在圖數(shù)據(jù)處理過程中造成熱點而引起的總體性能下降問題，從而提高圖處理的性能。

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

本發(fā)明屬于圖計算領(lǐng)域，更具體地，涉及一種存儲優(yōu)化的分布式圖處理方法。

背景技術(shù)

圖作為經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，通過點和邊來表達復(fù)雜的數(shù)據(jù)關(guān)系，已廣泛應(yīng)用于社會各領(lǐng)域，包括互聯(lián)網(wǎng)領(lǐng)域的社交數(shù)據(jù)分析與挖掘、化學(xué)領(lǐng)域的蛋白質(zhì)交互、醫(yī)學(xué)領(lǐng)域疾病暴發(fā)路徑的預(yù)測、學(xué)術(shù)領(lǐng)域中文獻的引用關(guān)系等，于是衍生出很多重要的算法，包括PageRank、最短路徑，連通分支，極大獨立集等。正因為圖數(shù)據(jù)具有重要的意義，又需要大量的計算，于是出現(xiàn)了各種各樣的圖處理系統(tǒng)。

首先是分布式內(nèi)存模式圖處理系統(tǒng)，包括Pregel、GraphLab等，這些系統(tǒng)先把圖的所有信息都放入到內(nèi)存中再開始處理，這種方式執(zhí)行速度快，但代價大、成本高，在規(guī)模繼續(xù)增大的圖應(yīng)用背景下，挑戰(zhàn)越來越顯著。且單一處理機可裝配內(nèi)存量較為有限，處理系統(tǒng)橫向擴展只能橫向補充處理機數(shù)量，這將不可避免地增加圖分區(qū)，更進一步增加切邊數(shù)量，增加處理機間通信壓力，加劇網(wǎng)絡(luò)IO延遲，由此將抵消橫向擴展所提供的并行優(yōu)勢，拖累圖處理性能。

在橫向擴展遭遇矛盾時，涌現(xiàn)出一批采取縱向擴展設(shè)計的單機外存模式圖處理技術(shù)系統(tǒng)，包括GraphChi、X-Stream等，其利用外存相對于內(nèi)存廉價且容量更易于擴展的優(yōu)點，將圖的大部分?jǐn)?shù)據(jù)駐留于外存，僅在計算有依賴時裝載少量數(shù)據(jù)進入內(nèi)存，圖的信息主要通過磁盤訪問的收益，減少對多機之間通信的依賴，并且可以實現(xiàn)在內(nèi)存等資源高度受限的普通機器上進行性能可以接受的圖處理，但是這種系統(tǒng)的性能嚴(yán)重受到磁盤IO的影響。

在大數(shù)據(jù)的時代，圖數(shù)據(jù)的規(guī)模越來越大，對擴展性、并行性要求越來越高。圖處理系統(tǒng)在結(jié)構(gòu)上無論是采取單機縱向擴展還是集群橫向擴展均面臨各自的限制。就單機而言，其資源擴展，無論是計算能力還是內(nèi)存資源、IO帶寬均有不足，反觀分布式架構(gòu)，圖的合理劃分早已成為經(jīng)典挑戰(zhàn)，盡管好的數(shù)據(jù)劃分能平衡計算負載、減少通信開銷，從而加速處理，但這種劃分本身是一個NP-hard問題，即使能實現(xiàn)近似算法，往往也要耗費大量的時間及資源進行預(yù)處理，得不償失，有鑒于此，現(xiàn)有技術(shù)仍然僅進行簡單的圖數(shù)據(jù)劃分，如Pregel的基于hash的劃分，Gemini的按段連續(xù)劃分。這種簡單的圖數(shù)據(jù)劃分在分布式圖處理過程中，難以避免負載不平衡的問題，造成動態(tài)變化的處理熱點，成為拖累整個圖迭代處理的短板，影響圖處理總體性能。

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

針對現(xiàn)有技術(shù)的以上缺陷，本發(fā)明提供一種存儲優(yōu)化的分布式圖處理方法，對圖數(shù)據(jù)進行分區(qū)存儲和IO平衡，實現(xiàn)圖數(shù)據(jù)處理負載平衡，加快圖數(shù)據(jù)處理速度，解決現(xiàn)有技術(shù)存在的負載不平衡，在圖數(shù)據(jù)處理過程中造成熱點而引起的總體性能下降問題。

為實現(xiàn)上述目的，本發(fā)明提供一種存儲優(yōu)化的分布式圖處理方法，包括如下步驟：

(1)初始化；將圖處理系統(tǒng)處理機節(jié)點劃分為一個主控節(jié)點和多個工作節(jié)點，各工作節(jié)點用于完成圖處理的基本過程，實現(xiàn)圖處理的計算模型；主控節(jié)點用于控制各個工作節(jié)點；

主控節(jié)點根據(jù)用戶初始的配置，可以是包含各個節(jié)點信息的文件，由這個文件來生成初始的消息路由表，所有工作節(jié)點保存所述消息路由表副本并與之同步更新；所述消息路由表用于記錄各工作節(jié)點間的路由信息；主控節(jié)點控制整個圖處理系統(tǒng)的執(zhí)行，工作節(jié)點完成圖處理的基本過程；所述路由信息，用于工作節(jié)點之間更新消息的傳遞和主控節(jié)點到各工作節(jié)點之間通信；