MapReduce中连接负载均衡优化研究

计算机工程与科学 ›› 2014, Vol. 36 ›› Issue (10): 1860-1865.

MapReduce中连接负载均衡优化研究

翟红敏，刘国华，赵威，刘源源,翟红坤

(1.东华大学计算机科学与技术学院，上海 201620;2.国网黑龙江省电力有限公司信息通信公司,黑龙江哈尔滨 150000)

收稿日期:2014-06-25 修回日期:2014-08-30 出版日期:2014-10-25 发布日期:2014-10-04
基金资助:
国家自然科学基金资助项目(61070032)

Optimizing load balancing of joins in MapReduce

ZHAI Hongmin,LIU Guohua,ZHAO Wei,LIU Yuanyuan,ZHAI Hongkun

(1.School of Computer and Science,Donghua University,Shanghai 201620;
2.State Grid Corporation of China Heilongjiang Electric Power Company Ltd.,
Information & Telecommunication Branch,Harbin 150000,China)

Received:2014-06-25 Revised:2014-08-30 Online:2014-10-25 Published:2014-10-04

摘要/Abstract

摘要：

数据分析和处理是大规模分布式数据处理应用中的重要任务。由于简单易用和具有灵活性, MapReduce编程模型逐渐成为大规模分布式数据处理系统（如Hadoop系统）的核心模型。由于所处理的数据可能不是均匀分布的,MapReduce编程模型在处理连接操作时,会出现数据倾斜问题。数据倾斜问题严重降低了MapReduce执行连接操作的效率。针对MapReduce中连接操作的数据倾斜问题,分析了造成MapReduce连接性能瓶颈的原因并建立负载均衡代价模型,提出了用范围分割方法控制连接过程中的数据倾斜问题实现负载均衡的策略。实验结果表明，所提方法明显提高了连接的效率。

关键词: MapReduce, 连接, 数据倾斜, 范围分割, 负载均衡

Abstract:

Data analysis and processing is one of the most important tasks in largescale distributed data processing applications.Due to its simplicity and scalability,MapReduce programming model has gradually become the crucial model for largescale distributed data processing systems (eg.Hadoop).Since the data may be uniformly distributed,data skew occurs when MapReduce programming model joins data,thus degrading the join performance severely.To solve data skew,its reason is analyzed,the load balancing cost model is established,and the rangepartitioner algorithm is proposed to control data skew so as to realize load balancing.Experimental results demonstrate that our method can obviously improve the efficiency of joins.

Key words: MapReduce, join, data skew, rangepartitioner, load balancing

翟红敏, 刘国华, 赵威, 刘源源, 翟红坤. MapReduce中连接负载均衡优化研究[J]. 计算机工程与科学, 2014, 36(10): 1860-1865.

ZHAI Hongmin, LIU Guohua, ZHAO Wei, LIU Yuanyuan, ZHAI Hongkun. Optimizing load balancing of joins in MapReduce [J]. Computer Engineering & Science, 2014, 36(10): 1860-1865.

参考文献［14］

［1］	Dean J, Ghemawat S. MapReduce:Simplified data processing on large clusters［J］. Communications of the ACM, 2008, 51(1):107113.
［2］	Blanas S, Patel J M, Ercegovac V, et al. A comparison of join algorithms for log processing in MapReduce［C］∥Proc of the 2010 ACM SIGMOD International Conference on Management of Data, 2010:975986.
［3］	Afrati F N,Ullman J D.Optimizing multiway joins in a MapReduce environment［J］. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(9):12821298.
［4］	Gufler B,Augsten N,Reiser A,et al.Load balancing in MapReduce based on scalable cardinality estimates［C］∥Proc of the International Conference on Data Engineering, 2012:522533.
［5］	Gufler B, Augsten N, Reiser A, et al. Handling data skew in MapReduce［C］∥ Proc of the 1st International Conference on Cloud Computing and Services Science, 2011:574583.
［6］	Yang H, Dasdan A, Hsiao R L, et al. Mapreducemerge:Simplified relational data processing on large clusters［C］∥Proc of the 2007 ACM SIGMOD International Conference on Management of Data, 2007:10291040.
［7］	Wang H, Qin X, Zhang Y, et al. LinearDB:A relational approach to make data warehouse scale like MapReduce［C］∥Proc of DASFAA’11, 2011:306320.
［8］	Dittrich J, QuianéRuiz J A, Jindal A, et al. Hadoop++:Making a yellow elephant run like a cheetah (without it even noticing)［J］. Proceedings of the VLDB Endowment, 2010, 3(12):515529.
［9］	Eltabakh M Y, Tian Y, zcan F, et al. CoHadoop:flexible data placement and its exploitation in Hadoop［J］. Proceedings of the VLDB Endowment, 2011, 4(9):575585.
［10］	Okcan A, Riedewald M. Processing thetajoins using MapReduce［C］∥Proc of the 2011 ACM SIGMOD International Conference on Management of Data, 2011:949960.
［11］	Lin Y, Agrawal D, Chen C, et al. Llama:Leveraging columnar storage for scalable join processing in the MapReduce framework［C］∥Proc of the 2011 ACM SIGMOD International Conference on Management of Data, 2011:961972.
［12］	Zhang X, Chen L, Wang M. Efficient multiway thetajoin processing using mapreduce［J］. Proceedings of the VLDB Endowment, 2012, 5(11):11841195.
［13］	Yan K, Zhu H. Two MRJs for multiway thetajoin in MapReduce［C］∥Proc of IDCS’13, 2013:321332.
［14］	Shi Bole Ding Baokang.Database Technology［M］.Beijing:Science Press,2002.(in Chinese)
［15］	Wbite T.Hadoop in action［M］.Californai:O’Reilly Media,2008.
	附中文参考文献：
［14］	施伯乐，丁宝康.数据库技术［M］.北京：科学出版社，2002.

[1]	厍向阳, 马亦骏. 改进的遥感图像语义分割算法[J]. 计算机工程与科学, 2023, 45(03): 504-511.
[2]	苏赋, 罗海波. 改进Stacking集成学习的指纹识别算法[J]. 计算机工程与科学, 2022, 44(12): 2153-2161.
[3]	王墨川, 何莉, 胡成雪, 陶健, 张德津. 基于曲率滤波和N-P准则的路面裂缝识别方法[J]. 计算机工程与科学, 2022, 44(10): 1822-1831.
[4]	杨春霞, 宋金剑, 姚思诚, . 基于深度BiLSTM和图卷积网络的方面级情感分析[J]. 计算机工程与科学, 2022, 44(10): 1893-1900.
[5]	喻明毫, 高建瓴. 轻量级水下目标检测器LUDet[J]. 计算机工程与科学, 2022, 44(09): 1638-1645.
[6]	李文佳, 史岚, 季航旭, 罗意彭. 面向Flink的负载均衡任务调度算法的研究与实现[J]. 计算机工程与科学, 2022, 44(07): 1141-1151.
[7]	徐浩桐, 黄山, 孙国璋, 贺菲莉, 段晓东, . 面向云环境的Flink负载均衡策略[J]. 计算机工程与科学, 2022, 44(05): 779-787.
[8]	罗晓霞, 王佳, 罗香玉, 李嘉楠 . 一种基于GN算法的动态图划分方法[J]. 计算机工程与科学, 2022, 44(02): 306-311.
[9]	张玉杰, 董蕊. 用于人体检测的YOLOv3改进及压缩算法的研究[J]. 计算机工程与科学, 2022, 44(02): 312-320.
[10]	李力, 汪硕, 黄韬, 刘韵洁, . 数据中心网络四层负载均衡技术综述[J]. 计算机工程与科学, 2022, 44(01): 48-59.
[11]	张逸风, 佟国香, 刘军, 屈亚宁. 基于蚁群遗传混合算法改进的连接查询研究[J]. 计算机工程与科学, 2021, 43(12): 2272-2280.
[12]	杜鹏, 李超, 石剑平, 姜麟. 基于阿当姆斯捷径连接的深度神经网络模型压缩方法[J]. 计算机工程与科学, 2021, 43(11): 2043-2048.
[13]	曹玉东, 蔡希彪. 基于并行小规模卷积神经网络的图像质量评价[J]. 计算机工程与科学, 2021, 43(10): 1810-1816.
[14]	黄山, 房六一, 徐浩桐, 段晓东, . 面向容器环境的Flink的任务调度优化研究[J]. 计算机工程与科学, 2021, 43(07): 1173-1184.
[15]	陈思琦, 黄汝维. 支持连接关键词搜索的属性加密方案研究[J]. 计算机工程与科学, 2021, 43(07): 1219-1225.