基于動態(tài)再劃分的分布式圖系統(tǒng)負載優(yōu)化機制研究.pdf

1、隨著計算機及網(wǎng)絡技術(shù)的飛速發(fā)展，越來越多的應用領(lǐng)域需要對大規(guī)模圖數(shù)據(jù)進行處理。傳統(tǒng)的單機處理模式不能有效地適應大規(guī)模圖數(shù)據(jù)計算，因此出現(xiàn)了許多分布式環(huán)境下的圖處理框架，如Pregel、Giraph、Graphlab等。圖劃分是分布式圖處理過程中的關(guān)鍵步驟，現(xiàn)有的分布式圖處理系統(tǒng)大多采用一次性靜態(tài)圖劃分技術(shù)來平衡各個計算節(jié)點的工作負載。由于在分布式圖處理的迭代過程中，不同特性的圖算法每次迭代計算所訪問的圖頂點數(shù)可能不同，其執(zhí)行過程中的運行

2、時負載是隨圖算法執(zhí)行行為而變化的。一次靜態(tài)圖劃分未考慮這種圖算法行為所產(chǎn)生的運行時負載不均衡對計算性能的影響，無法保證圖算法整個計算過程中的負載均衡，從而降低了圖處理的效率。
　　基于動態(tài)再劃分的負載優(yōu)化方法采用動態(tài)負載平衡技術(shù)，依據(jù)圖計算的行為特性監(jiān)測負載的運行時狀態(tài)，動態(tài)地將超載計算節(jié)點的負載轉(zhuǎn)移到未超載計算節(jié)點，從而減少圖算法行為對負載的不均衡影響，提高分布式圖處理的效率。主要研究內(nèi)容包括：提出基于圖算法行為特征的節(jié)點負載計

3、算方法，建立以活躍頂點、傳入消息數(shù)及遠程傳出消息為量化參數(shù)的節(jié)點負載計算模型；提出以局部節(jié)點負載為基礎，根據(jù)圖計算的行為變化平衡全局負載的兩階段負載動態(tài)再劃分方法；設計實現(xiàn)節(jié)點監(jiān)控程序以及以頂點為中心的負載遷移機制，在每次迭代最后階段將監(jiān)控到的節(jié)點負載發(fā)送到其它計算節(jié)點，由各節(jié)點協(xié)同地進行超載判定，確定負載并進行遷移。
　　針對多種圖算法，在大量數(shù)據(jù)集上對所提出的動態(tài)再劃分機制進行測試。測試結(jié)果表明，相比未采用動態(tài)再劃分機制的圖計