BHP：面向BSP模型的负载均衡Hash图数据划分

摘要：

图数据划分是基于BSP（bulk synchronous parallel）编程模型的大规模图处理系统中一个关键技术问题。传统的图划分技术需要多次迭代，时间复杂度过高，且划分结果不具有图顶点到分区的映射信息，因此这些算法并不适用于BSP模型下的数据划分。提出了一种新的面向BSP模型的负载均衡Hash数据划分算法（balanced Hash partition，BHP）。为了实现各个分区的出边数尽可能均衡，该算法引入了虚拟桶的概念，通过贪婪算法将虚拟桶重组为实际分区，保证了每个实际分区负载均衡，同时数据本地化策略使本分片上的数据尽可能地保留在本节点上，从而减小在数据加载时的数据迁移开销。从三个方面对比了BHP算法和经典Hash算法的性能，结果表明BHP算法能够提高作业的执行效率，减少消息发送的数量，有效解决了经典Hash算法的负载不均衡和分区间交互边过多的问题，当数据量变大时，效果尤为明显。

关键词：BSP模型、图划分、分布式系统、负载均衡、虚拟桶

分类号：TP311(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos.61033007,61173028;the Fundamental Research Funds for the Central Universities of China under Grant No. N100704001;the Ministry of Education of China and China Mobile Foundation under Grant No. MCM20125021

在线出版日期：2014-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：40-50