MapReduce模型中基于直方图的数据均衡算法

MapReduce模型是一种典型的分布式计算模型,被广泛应用于大规模数据处理,其性能很大程度上依赖于数据分布状态。由于数据内容往往都是不均衡的,再加上存储的随机性,因此MapReduce模型在计算过程中容易出现数据倾斜的问题。针对该问题,通过改进的基于MapReduce的数据直方图并行构建算法,对数据块和整个文件分别建立数据直方图,根据数据块分布情况,判断每个存储节点的数据倾斜程度,并定义了文件均衡偏差值作为数据倾斜的度量标准,进而通过数据均衡算法来降低文件均衡偏差值。改进的基于MapReduce的数据直方图并行构建算法能够适应各种类型的数据应用场景,直方图构建过程中Map端向Reduce端只需要传输直方图统计信息,不需要传输文件内容,数据传输量几乎可以忽略不计;基于直方图的数据均衡算法采用了贪心策略,可以获得均衡分布最优解的一个比较好的近似解,经过不同数据多次实验验证,该算法与随机block分布算法相比,可以降低40%左右的文件均衡偏差值,具有更好的数据均衡效果。