期刊文献+

MapReduce模型中基于直方图的数据均衡算法 被引量:5

Data Balance Algorithm Based on Histogram in MapReduce
下载PDF
导出
摘要 MapReduce模型是一种典型的分布式计算模型,被广泛应用于大规模数据处理,其性能很大程度上依赖于数据分布状态。由于数据内容往往都是不均衡的,再加上存储的随机性,因此MapReduce模型在计算过程中容易出现数据倾斜的问题。针对该问题,通过改进的基于MapReduce的数据直方图并行构建算法,对数据块和整个文件分别建立数据直方图,根据数据块分布情况,判断每个存储节点的数据倾斜程度,并定义了文件均衡偏差值作为数据倾斜的度量标准,进而通过数据均衡算法来降低文件均衡偏差值。改进的基于MapReduce的数据直方图并行构建算法能够适应各种类型的数据应用场景,直方图构建过程中Map端向Reduce端只需要传输直方图统计信息,不需要传输文件内容,数据传输量几乎可以忽略不计;基于直方图的数据均衡算法采用了贪心策略,可以获得均衡分布最优解的一个比较好的近似解,经过不同数据多次实验验证,该算法与随机block分布算法相比,可以降低40%左右的文件均衡偏差值,具有更好的数据均衡效果。 MapReduce model is a typical distributed computing model,which is widely used in large-scale data processing,and its performance depends largely on the data distribution status.As the data content is often unbalanced,coupled with the storage of randomness,so MapReduce model prone to data skew problem in the calculation process.In order to solve this problem,this paper establishes a data histogram for the data block and the whole file through the improved parallel histogram parallelization algorithm based on MapReduce.According to the data block distribution,we can judge the data skew degree of each storage nodes and define the file equilibrium deviation value as the measure of data skew,and then the data balance algorithm is used to reduce the file equilibrium deviation value.The improved MapReduce-based data histogram parallel construction algorithm can adapt to various types of data application scenarios.In the process of building the histogram,the Map side only needs to transmit histogram statistics to the Reduce side without transmitting the contents of the file.The data transfer can be almost negligible.The data balance algorithm based on histogram employs greedy strategy,which can obtain a better approximate solution of the optimal solution of equilibrium distribution.After several experiments,compared with the random block distribution algorithm,the improved algorithm reduce about 40%of the file balance deviation value and achieves a better data balance performance.
作者 周渭博 钟勇 王阳 Zhou Weibo;Zhong Yong;Wang Yang(Chengdu Institute of Computer applications,Chinese Academy of Sciences,Chengdu 610041,China;University of Chinese Academy of Sciences,Beijing 100049,China;Chengdu ChongXin Big Data Services Co.,Ltd.Chengdu 611230,China)
出处 《西北工业大学学报》 EI CAS CSCD 北大核心 2018年第3期480-486,共7页 Journal of Northwestern Polytechnical University
基金 四川省科技支撑计划(2014GZ0013) 四川省科技支撑计划(2015GZ0088) 四川省青年软件创新工程(2014-063)资助
关键词 直方图 并行算法 数据倾斜 数据块 数据均衡 约束优化 实验设计 histogram parallel algorithm data skew block data balance constrained optimization design of experiments
  • 相关文献

参考文献4

二级参考文献80

  • 1周家帅,王琦,高军.一种基于动态划分的MapReduce负载均衡方法[J].计算机研究与发展,2013,50(S1):369-377. 被引量:11
  • 2韩蕾,孙徐湛,吴志川,陈立军.MapReduce上基于抽样的数据划分最优化研究[J].计算机研究与发展,2013,50(S2):77-84. 被引量:13
  • 3宁焕生,张瑜,刘芳丽,刘文明,渠慎丰.中国物联网信息服务系统研究[J].电子学报,2006,34(B12):2514-2517. 被引量:151
  • 4J Dean,S Ghemawat.MapReduce:Simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.
  • 5J L Wagener.High performance fortran[J].Computer Standards & Interfaces,Elsevier,1996,18(4):371-377.
  • 6W Gropp,E Lusk,et al.Using MPI:Portable Parallel Programming with the Message Passing Interface[M].Cambridge:MIT Press,1999.1-350.
  • 7A Geist,A Beguelin,et al.PVM:Parallel Virtual Machine:A Users' Guide and Tutorial for Networked Parallel Computing[M].Cambridge:MIT Press,1995.1-299.
  • 8A Verma,N Zea,et al.Breaking the mapreduce stage barrier .Proc of IEEE International Conference on Cluster Computing .Los Alamitos:IEEE Computer Society,2010.235-244.
  • 9H C Yang,A Dasdan,et al.Map-Reduce-Merge:Simplified relational data processing .Proc of ACM SIGMOD International Conference on Management of Data .New York:ACM,2007.1029-1040.
  • 10S V Valvag,D Johansen.Oivos:Simple and efficient distributed data processing .Proc of IEEE International Conference on High Performance Computing and Communications .Piscataway:IEEE,2008.113-122.

共引文献326

同被引文献46

引证文献5

二级引证文献22

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部