[發明專利]一種存儲優化的分布式圖處理方法

有效

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

1.一種存儲優化的分布式圖處理方法，其特征在于，包括如下步驟：

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

主控節點根據用戶初始的配置，生成初始的消息路由表，所有工作節點保存所述消息路由表副本并與之同步更新；所述消息路由表用于記錄各工作節點間的路由信息；主控節點控制整個圖處理系統的執行，工作節點完成圖處理的基本過程；所述路由信息，用于工作節點之間更新消息的傳遞和主控節點到各工作節點之間通信；

主控節點根據所述消息路由表劃分圖數據，按圖的結點id進行劃分；劃分塊數與消息路由表中工作節點數相同；分塊根據圖結點總數平均劃分；所述圖的所有結點形成一個環狀空間，圖結點id的最小值和圖結點id的最大值相鄰；經過劃分，各圖結點分區呈現兩種情況，一種分區是有連續的id，另一種分區是有兩段連續id；

(2)圖數據的分發；主控節點將步驟(1)劃分得到的各圖結點分區和該分區內的元數據根據一致性哈希算法發送到消息路由表中相應的工作節點，所述元數據包括全圖的邊數、全圖的結點數、圖的類型、各分區的邊數、各分區的id、各分區的起始的圖結點id、各分區結束的圖結點id和圖分區中點圖結點id；

(3)迭代次數判別；各工作節點在主控節點控制下開始圖數據迭代處理；迭代前，主控節點判別迭代次數是否達到迭代次數預設值，是則轉步驟(6)；否則，轉步驟(4)；

(4)更新消息傳遞，各工作節點執行MGA計算，包括：

首先，對圖分區的每條邊都執行一次Map操作，每一個圖結點在執行MAP操作的同時產生一個更新消息，發送給對應的目的地址；

其次，各圖結點執行一個Gather操作收集傳遞給該圖結點所有的更新消息；

第三，各圖結點執行一個Apply操作，用收集的更新消息來改變這個圖結點的數據；所述更新消息的發送僅僅發生在工作節點之間，更新消息根據消息路由表發送給對應的工作節點；

所述MGA計算即上述Map、Gather和Apply操作的簡稱，在圖處理一輪迭代中，每一個圖結點都要經歷這三個階段；

(5)擴展處理；主控節點根據所收集的工作節點運行狀態，判別各工作節點負載是否均衡：

是則，不進行分割和擴展，轉步驟(3)進行下一輪迭代；

否則對負載最大工作節點的圖分區數據進行分裂，即對處理的圖數據進行分割，然后橫向擴展，用以消除熱點，即處理數據耗時最長的那個節點，采用一致性哈希算法為工作節點分配圖分區數據，達到負載調控的目的；然后更新消息路由表，轉步驟(3)進行下一輪迭代；

(6)圖數據處理結束，同時輸出計算結果。

2.如權利要求1所述的方法，其特征在于，所述步驟(4)中MGA計算過程使用圖數據的流式讀取保證了對存儲器的順序訪問，從而保證了對外存IO的最大利用。

3.如權利要求1所述的方法，其特征在于，所述步驟(5)中收集的工作節點運行狀態包括磁盤IO、網絡IO以及計算消耗代價。

4.如權利要求1所述的方法，其特征在于，步驟(5)中所述熱點指一輪迭代中運行最慢的工作節點；

COST＝α|V|+|E|

其中，對于圖數據處理來說，α取圖的平均入度，α|V|代表一個圖分區所要接收的更新消息，|V|代表的是一個圖分區頂點的數目，|E|代表一個圖分區所要發送的更新消息，公式中COST衡量一個圖的負載；分裂的目的是在需要分裂的圖分區上找到一個圖結點，使該圖分區分裂成的兩段子分區的負載代價相當。