Data Balance Algorithm Based on Histogram in MapReduce

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

¹ 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

Received: 10 April 2017

Abstract

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.

摘要

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