基于动态获取高频率键的MapReduce性能优化算法
Performance optimization algorithm for MapReduce based on obtaining frequent keys

在云计算技术领域中，MapReduce能够帮助人们快速处理海量数据，因此在学术界以及工业界越来越受到重视。但是MapReduce在处理以文本为中心的应用时，中间结果中数据重复较多。针对该情况，已有的高频率缓冲（frequency buffering，FB）算法提出在环形内存缓冲之前添加哈希表，并将高频率键存储在哈希表中。该算法通过采样来实现，有额外开销并且统计出的高频率键并不一定准确。该文提出一种基于动态获取高频率键的MapReduce性能优化算法，通过在环形内存缓冲之前增加计数Bloom过滤器（counting Bloom filter，CBF）和哈希表，将高频率键动态地存储在哈希表中。该算法获得的高频率键更准确，同时大大减少了数据排序和磁盘I/O的开销。实际测试结果表明：该算法明显提高了作业的执行速度，比原始MapReduce提高17.04%，比FB算法提高9.31%。
Abstract：MapReduce is getting much attention in academia and industry for use in cloud computing to quickly deal with huge amounts of data. However, when MapReduce deals with text-centric applications, the algorithm generates is large amount of duplicate data in the intermediate results that increases the run time. A frequency buffering (FB) algorithm was used to add a Hash table before the ring memory to store frequent keys in a Hash table. However, since the algorithm is implemented by sampling, the algorithm may not accurately estimate the overhead and the frequent keys. Therefore, this study added a performance optimization algorithm to MapReduce to obtain the frequent keys by adding a counting Bloom filter (CBF) and a Hash table to dynamically filter the frequent keys before storing them in the ring memory. This algorithm more accurately identifies the frequent keys and greatly reduces the data sorting overhead and the disk I/O. Tests show that this performance optimization algorithm for MapReduce for obtaining the frequent keys significantly improves the execution speed by 17.04% compared to the original MapReduce and 9.31% higher than the frequency buffering algorithm.