Azero一个大规模动态负载均衡图处理系统课件.pptx

1、目录v问题提出图处理系统性能制约因素现有系统存在问题主要贡献v空间向量划分算法v利用SVPA进行动态负载均衡vAzero系统架构、API及实现v待完成工作1问题背景v大规模图处理v计算模型BSP vs Mapreducev图的切分与存储2现有图处理系统vPregel(SIGMOD 2010)vGiraph(Hadoop Submit 2011)vMizan(EuroSys 2013)v3性能制约因素vWorker间网络通信Cross-edge，图切分算法vWorker的负载不均衡瓶颈节点算法行为图结构底层平台需要动态负载均衡4现有系统存在问题v系统性能受瓶颈Worker制约v图的切分未考虑图顶

2、点的连接关系大量Cross-edge的产生v负载均衡过程未保持图顶点连接的局部性v负载均衡算法开销大计算复杂度和网络开销顶点迁移时大量的数据传输5Motivationv寻找一个新的图处理负载均衡解决方案负载均衡同时保持图顶点连接局部性简单、高效6主要贡献vSVPA图切分算法v利用SVPA进行动态负载均衡的框架简单高效负载均衡同时保持图的局部性顶点低成本迁移、Superstep内负载均衡v新的大规模图处理系统Azero计算框架，API分布式索引，缓存策略等7SVPA算法算法part28图的切分vWorker集合W=w1,w2,，|W|=Nv图G=，v的后继元集+(v)v切分方案Ptt:VWwi上

3、顶点集合PPI(i)=Ptt-1wi跨边集CE=|EPtt(v1)Ptt(v2)切分均匀性：max(card(PPI(i)低切分局部性：card(CE)小9空间向量划分算法SVPA10CN(v)w1w211CN(v)12w1w2w3预切分方案Proposed Partitionv新图的PPI=v利用预切分方案计算CNvMETISv预切分方案和CN计算的分布式化网络开销(|E|/N)13划分向量p14SVPA15SVPAw1w2划分向量划分向量p16切分效果17利用利用SVPA进行动态负载均衡进行动态负载均衡part318负载均衡方案v六步负载均衡方案（Superstep结束）1.Master收

4、集Worker信息得到负载向量L2.Master计算新的划分向量new_p=LBF(old_p,L)3.Master将new_p发送给所有索引节点4.索引节点计算新的切分方案SVPnew_p5.索引节点计算顶点迁移方案M6.节点迁移（下一个Superstep开始）19负载均衡方案WorkerIndexWorkerIndexMaster1new p23new pttnew ptt4mig plnmig pln5620负载向量LvL=(load_w1,load_w2,load_wN)vload衡量指标worker运行总时间网络通信量21负载均衡函数LBFvnew_p=LBF(old_p,L)v将W

5、orker分为两类：Over-load和Under-loadv改变划分向量，使前者的顶点向后者迁移v使得新Superstep中各Worker负载近似相等v基于以下假设Worker中各顶点产生的负载近似相等顶点在相邻Superstep产生的负载近似相等22LBF两个版本vLBF_O基于Over-load针对性处理瓶颈WorkervLBF_U基于Under-load可用于Superstep内实时负载均衡*23伪代码LBF_O(old_p,L)average_load AverageValueOfArrayElements(L)delta_p 0delta_l 0for i 1 to N doLi

6、Li-average_loadfor i 1 to N doif Li 0 thennew_pi 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性能分析v顶点索引的空间复杂度(|V|*N)比正常索引(|V|)大备份简单（更新索引时只需备份p）v负载均衡

7、算法计算时间复杂度(N+|V|+|V|/N)=(|V|)v较大网络通信复杂度(N+N2)=(N2)v很小26顶点低成本迁移v两步迁移避免Message迁移v预复制输入图时将边缘顶点复制到多个Worker上顶点同时只有一个副本处于active状态v迁移/复制SVPA切分方案的一致性271 Vertex ReplicationComputableReceiving Messages状态机To be transferedTo be activeSleepingActive28两步迁移TBTTBASLPACTRP-1TBTTBASLPACTRP-2ACTTBTSLPTBATBTSLPTBAACTCom

8、putableReceiving MessagesComputableReceiving MessagesBefore MigrationStep 1Step 2Worker 1Worker 229Superstep内实时负载均衡30AZERO系统的设计与实现系统的设计与实现part431图处理流程Graph DataGraph PartitioningBSP modelWorkerWorkerWorkerManagerOutput32计算模型33Barrier SynchronizationLocal ComputingCommunacationw1w2w3w4w5v v顶点计算过程msgs

9、(v)mmmmmsgs(v)msgs(v”)Superstep k-1Superstep kSuperstep 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 sendM

10、essageToAllEdges(String message);public long getNumSuperSteps();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 VertexPr

11、ocessor public void compute(WorkerContext context)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()

12、30)long edges=v.getEdges.size();context.sendMessageToAllEdges(String.valueOf(v.getValue()/edges);else voteToHalt();36Distributed HashWorkerWorkerWorkerWorkerWorkerWorkerManagerAzeros Arichitecture37分布式索引v散列函数H:VWv顶点v的索引保存在节点H(v)上v三步顶点寻址方案计算H(v)向H(v)请求v的索引Ptt(v)向Ptt(v)发送消息38分布式索引39Distributed HashWor

13、kerWorkerWorkerWorkerWorkerWorkerH(v)Where is v?Ptt(v)Ptt(v)msgv索引Replication40索引Cachev将保存在Ptt(v)上v将缓存在wi上当PPI(i)对v的连续k次寻址结果相同时41流程图42寻址顶点找到？查询本地索引寻址失败查询本地缓存命中？查询H1(v)找到？查询H2(v)找到？更新本地缓存可缓存？寻址成功YNYYYYNNNNStorage LayerIndexManagerVertexAddressorLink LayerMessageReceiverMessageSenderAPI/ContextControllerVertexManagerUser FunctionNetworkLocal DiskAzero WorkerSVPA43实现细节vMessage发送方式计算时并行发送：节省时间计算后统一发送：Combiner优化v网络连接方式Netty：性能较好RMI：编程简洁v44待完成工作v测量顶点坐标分布与负载均衡灵活性切图结果均匀性与局部性动态负载均衡的实际效果与比较索引缓存策略的实际效果与比较系统可扩展性45THANKSQ&A46