Hadoop任务分配策略的改进

计算机应用 ›› 2013, Vol. 33 ›› Issue (08): 2158-2162.

Hadoop任务分配策略的改进

黄承真,王雷,刘小龙,况亚萍

中国科学技术大学自动化系，合肥 230027

收稿日期:2013-03-05 修回日期:2013-04-12 出版日期:2013-08-01 发布日期:2013-09-11
通讯作者: 王雷
作者简介:黄承真(1987-)，男，重庆人，硕士研究生，主要研究方向：云计算、大数据、Hadoop;
王雷(1972-)，男，安徽宿州人，副教授，博士，主要研究方向：计算机网络、媒体处理、云计算与云存储;
刘小龙(1989-)，男，重庆人，硕士研究生，主要研究方向：流媒体、网络传播与控制;
况亚萍(1991-)，女，安徽淮北人，硕士研究生，主要研究方向：云计算、虚拟化、网络传播与控制。
基金资助:
中央高校基本科研业务费专项资金资助项目

Tasks assignment optimization in Hadoop

HUANG Chengzhen,WANG Lei,LIU Xiaolong,KUANG Yaping

Department of Automation, University of Science and Technology of China, Hefei Anhui 230027, China

Received:2013-03-05 Revised:2013-04-12 Online:2013-09-11 Published:2013-08-01
Contact: WANG Lei

摘要/Abstract

摘要： Hadoop广泛应用于大数据的并行处理，其现有的任务分配策略多面向同构环境，或者没有充分利用集群的全局信息，或者在异构环境下无法兼顾执行效率与算法复杂度。针对这些问题，提出异构环境下的任务分配算法λ-Flow算法，将原先一次完成的任务分配过程划分成多轮，每轮基于当前集群状态，以及上轮任务的执行情况，动态进行任务分配，直至全部任务分配结束，以期达到最优执行效率。通过与其他算法对比实验表明，λ-Flow算法能够更好地适应集群的动态变化，有效减少作业执行时间。

关键词: Hadoop, MapReduce, 任务分配, 异构环境, 最小费用最大流

Abstract: Hadoop has been widely used in large data parallel processing. The existing tasks assignment strategies are almost oriented to a homogenous environment, but ignore the global cluster state, or not take into account the efficiency of the implementation and the complexity of the algorithm in a heterogeneous environment. To solve these problems, a new tasks assignment algorithm named λ-Flow which was oriented to a heterogeneous environment was proposed. In λ-Flow, the tasks assignment was divided into several rounds. In each round, λ-Flow collected the cluster states and the execution result of the last round dynamically, and assigned tasks in accordance with these states and the result. The comparative experimental result shows that the λ-Flow algorithm performs better in a dynamic changing cluster than the existing algorithms, and reduces the execution time of a job effectively.

Key words: Hadoop, MapReduce, tasks assignment, heterogeneous environment, min cost max flow

中图分类号:

黄承真王雷刘小龙况亚萍. Hadoop任务分配策略的改进[J]. 计算机应用, 2013, 33(08): 2158-2162.

HUANG Chengzhen WANG Lei LIU Xiaolong KUANG Yaping. Tasks assignment optimization in Hadoop[J]. Journal of Computer Applications, 2013, 33(08): 2158-2162.

参考文献

［1］ARMBRUST M, FOX A, GRIFFITH R, et al. Above the clouds: a Berkeley view of cloud computing ［J］. Communications of the ACM, 2010, 53(4): 50-58.

［2］DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters［J］.Communications of the ACM,2008,51(1):107-113.

［3］ISARD M, BUDIU M, YU Y, et al. Dryad: distributed data-parallel programs from sequential building blocks［C］// EuroSys 07: Proceedings of the 2007 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems. New York: ACM, 2007: 59-72.

［4］Hadoop［EB/OL］. ［2012-12-27］. http://hadoop.apache.org/.

［5］THUSOO A, SHAO Z, ANTHONY S, et al. Data warehousing and analytics in-frastructure at Facebook ［C］// SIGMOD 10: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2010:1013-1020.

［6］WHITE T. Hadoop: the definitive guide［M］. Sebastopol, CA, USA: OReilly Media, 2009.

［7］Fair Scheduler for Hadoop ［EB/OL］. ［2012-12-10］. http://Hadoop.apache.org/common/docs/current/Fair_scheduler.html.

［8］ZAHARIA M, BORTHAKUR D, SARMA J S, et al. Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling ［C］// EuroSys 10: Proceedings of the 5th European Conference on Computer Systems. New York: ACM, 2010: 265-278.

［9］Capacity scheduler for Hadoop［EB/OL］. ［2012-12-13］. http://Hadoop.apache.org/common/docs/current/Capacity_scheduler.html.

［10］ZAHARIA M, KONWINSKI A, JOSEPH A D, et al. Improving MapReduce performance in heterogeneous environments ［C］// OSDI08: Proceedings of The 8th USENIX Conference on Operating Systems Design and Implementation. Berkeley: USENIX Association, 2008:29-42.

［11］FISCHER M J, SU X Y, YIN Y T. Assigning tasks for efficiency in Hadoop: extended abstract ［C］// SPAA 10: Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures. New York: ACM, 2010:30-39.

［12］SASTRY G. FlowScheduler: towards efficient task assignment for Hadoop ［EB/OL］. (2011-05-02) [2012-12-08]. http://girishsastry.com/papers/writeup.pdf.

［13］JIN J H, LUO J Z, SONG A B, et al. BAR: an efficient data locality driven task scheduling algorithm for cloud computing ［C］// CCGRID 11: Proceedings of the 2011 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Washington, DC: IEEE Computer Society, 2011: 295-304.

［14］ORMEN T H, LEISERSON C E, RIVEST R L, et al. 算法导论［M］. 殷建平,徐云, 王刚,等译.北京:机械工业出版社, 2006:396-408.

［15］段凡丁.关于最短路径的SPFA快速算法［J］. 西南交通大学学报,1994,29(2):207-212.

[1]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 计算机应用, 2021, 41(8): 2232-2241.
[2]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[3]	杨玮, 李然, 张堃. 基于变邻域模拟退火算法的多自动导引车任务分配优化[J]. 计算机应用, 2021, 41(10): 3056-3062.
[4]	余敦辉, 袁旭, 张万山, 王晨旭. 基于动态阈值的时空众包在线分配算法[J]. 计算机应用, 2020, 40(3): 658-664.
[5]	韩俊樱, 张振宇, 孔德仕. 移动群智感知中面向用户区域的分布式多任务分配方法[J]. 计算机应用, 2020, 40(2): 358-362.
[6]	董聪, 张晓, 程文迪, 石佳. 基于新型存储器件的分布式文件系统性能优化[J]. 计算机应用, 2020, 40(12): 3594-3603.
[7]	秦海燕, 章永龙, 李斌. 社会网络下分配众包任务的真实机制[J]. 计算机应用, 2020, 40(10): 3019-3024.
[8]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
[9]	李耘书, 滕飞, 李天瑞. 基于微操作的Hadoop参数自动调优方法[J]. 计算机应用, 2019, 39(6): 1589-1594.
[10]	张兴盛, 余敦辉, 张万山, 王晨旭. 时空众包环境下时效均衡的在线任务分配算法[J]. 计算机应用, 2019, 39(5): 1357-1363.
[11]	陈友玲, 左丽丹, 牛禹霏, 王龙. 基于知识相似度的产品开发任务分配方法[J]. 计算机应用, 2019, 39(2): 323-329.
[12]	李鑫滨, 章寿涛, 闫磊, 韩松. 基于鲁棒Restless Bandits模型的多水下自主航行器任务分配策略[J]. 计算机应用, 2019, 39(10): 2795-2801.
[13]	刘鹏飞, 毛莺池, 王龙宝. 基于云雾协作模型的任务分配方法[J]. 计算机应用, 2019, 39(1): 8-14.
[14]	郭方方, 潮洛蒙, 朱建文. 基于相似连接的多源数据并行预处理方法[J]. 计算机应用, 2019, 39(1): 57-60.
[15]	郑振涛, 赵卓峰, 王桂玲, 徐垚. 面向港口停留区域识别的船舶停留轨迹提取方法[J]. 计算机应用, 2019, 39(1): 113-117.