Azero一個(gè)大規(guī)模動(dòng)態(tài)負(fù)載均衡圖處理系統(tǒng)課件

1、目錄問題提出圖處理系統(tǒng)性能制約因素現(xiàn)有系統(tǒng)存在問題主要貢獻(xiàn)空間向量劃分算法利用SVPA進(jìn)行動(dòng)態(tài)負(fù)載均衡Azero系統(tǒng)架構(gòu)、API及實(shí)現(xiàn)待完成工作1問題背景大規(guī)模圖處理計(jì)算模型BSP vs Mapreduce圖的切分與存儲2現(xiàn)有圖處理系統(tǒng)Pregel (SIGMOD 2010)Giraph (Hadoop Submit 2011)Mizan (EuroSys 2013)3性能制約因素Worker間網(wǎng)絡(luò)通信Cross-edge，圖切分算法Worker的負(fù)載不均衡瓶頸節(jié)點(diǎn)算法行為圖結(jié)構(gòu)底層平臺需要?jiǎng)討B(tài)負(fù)載均衡4現(xiàn)有系統(tǒng)存在問題系統(tǒng)性能受瓶頸Worker制約圖的切分未考慮圖頂點(diǎn)的連接關(guān)系大量Cross

2、-edge的產(chǎn)生負(fù)載均衡過程未保持圖頂點(diǎn)連接的局部性負(fù)載均衡算法開銷大計(jì)算復(fù)雜度和網(wǎng)絡(luò)開銷頂點(diǎn)遷移時(shí)大量的數(shù)據(jù)傳輸5Motivation尋找一個(gè)新的圖處理負(fù)載均衡解決方案負(fù)載均衡同時(shí)保持圖頂點(diǎn)連接局部性簡單、高效6主要貢獻(xiàn)SVPA圖切分算法利用SVPA進(jìn)行動(dòng)態(tài)負(fù)載均衡的框架簡單高效負(fù)載均衡同時(shí)保持圖的局部性頂點(diǎn)低成本遷移、Superstep內(nèi)負(fù)載均衡新的大規(guī)模圖處理系統(tǒng)Azero計(jì)算框架，API分布式索引，緩存策略等7SVPA算法part28圖的切分Worker集合W=w1, w2, ，|W|=N圖G=，v的后繼元集+(v)切分方案Ptt: VWwi上頂點(diǎn)集合PPI(i)=Ptt-1wi跨邊集

3、CE=|EPtt(v1)Ptt(v2)切分均勻性：max(card(PPI(i)低切分局部性：card(CE)小9空間向量劃分算法SVPA10CN(v)w1w211CN(v)12w1w2w3預(yù)切分方案Proposed Partition新圖的PPI=利用預(yù)切分方案計(jì)算CNMETIS預(yù)切分方案和CN計(jì)算的分布式化網(wǎng)絡(luò)開銷(|E|/N)13劃分向量p14SVPA15SVPAw1w2劃分向量p16切分效果17利用SVPA進(jìn)行動(dòng)態(tài)負(fù)載均衡part318負(fù)載均衡方案六步負(fù)載均衡方案（Superstep結(jié)束）Master收集Worker信息得到負(fù)載向量LMaster計(jì)算新的劃分向量new_p=LBF(ol

4、d_p, L)Master將new_p發(fā)送給所有索引節(jié)點(diǎn)索引節(jié)點(diǎn)計(jì)算新的切分方案SVPnew_p索引節(jié)點(diǎn)計(jì)算頂點(diǎn)遷移方案M節(jié)點(diǎn)遷移（下一個(gè)Superstep開始）19負(fù)載均衡方案WorkerIndexWorkerIndexMaster1new p23new pttnew ptt4mig plnmig pln5620負(fù)載向量LL = (load_w1, load_w2, , load_wN)load衡量指標(biāo)worker運(yùn)行總時(shí)間網(wǎng)絡(luò)通信量21負(fù)載均衡函數(shù)LBFnew_p = LBF(old_p, L)將Worker分為兩類：Over-load和Under-load改變劃分向量，使前者的頂點(diǎn)向后者

5、遷移使得新Superstep中各Worker負(fù)載近似相等基于以下假設(shè)Worker中各頂點(diǎn)產(chǎn)生的負(fù)載近似相等頂點(diǎn)在相鄰Superstep產(chǎn)生的負(fù)載近似相等22LBF兩個(gè)版本LBF_O基于Over-load針對性處理瓶頸WorkerLBF_U基于Under-load可用于Superstep內(nèi)實(shí)時(shí)負(fù)載均衡*23偽代碼LBF_O(old_p, L)average_load AverageValueOfArrayElements(L)delta_p 0delta_l 0for i 1 to N doLi Li - average_loadfor i 1 to N doif Li 0 thennew_pi

6、 old_pi*average_load/(average_load+Li)delta_p delta_p + old_pi new_pidelta_l delta_l + Liif delta_l 0 thendelta -delta_p / delta_lfor i 1 to N doif Li 0 thennew_pi old_pi + delta * Lireturn new_p24遷出遷入遷移方案M25性能分析頂點(diǎn)索引的空間復(fù)雜度(|V|*N)比正常索引(|V|)大備份簡單（更新索引時(shí)只需備份p）負(fù)載均衡算法計(jì)算時(shí)間復(fù)雜度(N+|V|+|V|/N)= (|V|)較大網(wǎng)絡(luò)通信復(fù)雜度(N

7、+N2)=(N2)很小26頂點(diǎn)低成本遷移兩步遷移避免Message遷移預(yù)復(fù)制輸入圖時(shí)將邊緣頂點(diǎn)復(fù)制到多個(gè)Worker上頂點(diǎn)同時(shí)只有一個(gè)副本處于active狀態(tài)遷移/復(fù)制SVPA切分方案的一致性271 Vertex ReplicationComputableReceiving Messages狀態(tài)機(jī)To be transferedTo be activeSleepingActive28兩步遷移TBTTBASLPACTRP-1TBTTBASLPACTRP-2ACTTBTSLPTBATBTSLPTBAACTComputableReceiving MessagesComputableReceiving

8、 MessagesBefore MigrationStep 1Step 2Worker 1Worker 229Superstep內(nèi)實(shí)時(shí)負(fù)載均衡30Azero系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)part431圖處理流程Graph DataGraph PartitioningBSP modelWorkerWorkerWorkerManagerOutput32計(jì)算模型33Barrier SynchronizationLocal ComputingCommunacationw1w2w3w4w5vv頂點(diǎn)計(jì)算過程msgs(v)mmmmmsgs(v)msgs(v”)Superstep k-1Superstep kSuperst

9、ep k+134APIpublic interface VertexProcessor public void compute(WorkerContext context);public class WorkerContext public Vertex getCurrentVertex();public MapLong, List getMessages();public void sendMessage(long vid, String message);public void sendMessageToAllEdges(String message);public long getNum

10、SuperSteps();public long getNumVertexes();public void voteToHalt();public class Vertex public long getVID();public Object getValue();public void setValue(Object value);public Set getEdges();35PageRank Examplepublic class PageRank implements VertexProcessor public void compute(WorkerContext context)

11、Vertex v = context.getCurrentVertex();if (context.getNumSuperSteps() = 1) double sum = 0;for (List list : context.getMessages().values() sum += Double.valueOf(list.get(0);v.setValue(Double.valueOf(0.15/context.getNumVertexes+0.85*sum);if (context.getNumSuperSteps() 30) long edges = v.getEdges.size()

12、;context.sendMessageToAllEdges(String.valueOf(v.getValue()/edges); else voteToHalt();36Distributed HashWorkerWorkerWorkerWorkerWorkerWorkerManagerAzeros Arichitecture37分布式索引散列函數(shù)H: VW頂點(diǎn)v的索引保存在節(jié)點(diǎn)H(v)上三步頂點(diǎn)尋址方案計(jì)算H(v)向H(v)請求v的索引Ptt(v)向Ptt(v)發(fā)送消息38分布式索引39Distributed HashWorkerWorkerWorkerWorkerWorkerWorkerH(v)Where is v?Ptt(v)Ptt(v)msgv索引Replication40索引Cache將保存在Ptt(v)上將緩存在wi上當(dāng)PPI(i)對v的連續(xù)k次尋址結(jié)果相同時(shí)41流程圖42尋址頂點(diǎn)找到？查詢本地索引尋址失敗查詢本地緩存命中？查詢H1(v)找到？查詢H2(v)找到？更新本地緩存可緩存？尋址成功YNYYYYNNNNStorage LayerIndexManagerVertexAddressorLink LayerMessageReceiverMessageSenderAPI / ContextControllerVertexM