ImageVerifierCode 换一换
格式:PPTX , 页数:46 ,大小:790KB ,
文档编号:3376599      下载积分:25 文币
快捷下载
登录下载
邮箱/手机:
温馨提示:
系统将以此处填写的邮箱或者手机号生成账号和密码,方便再次下载。 如填写123,账号和密码都是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

优惠套餐
 

温馨提示:若手机下载失败,请复制以下地址【https://www.163wenku.com/d-3376599.html】到电脑浏览器->登陆(账号密码均为手机号或邮箱;不要扫码登陆)->重新下载(不再收费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  
下载须知

1: 试题类文档的标题没说有答案,则无答案;主观题也可能无答案。PPT的音视频可能无法播放。 请谨慎下单,一旦售出,概不退换。
2: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
3: 本文为用户(三亚风情)主动上传,所有收益归该用户。163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

1,本文(Azero一个大规模动态负载均衡图处理系统课件.pptx)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!

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

侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|