Storm环境下基于权重的任务调度算法

doi:10.11772/j.issn.1001-9081.2017082125

计算机应用 ›› 2018, Vol. 38 ›› Issue (3): 699-706.DOI: 10.11772/j.issn.1001-9081.2017082125

Storm环境下基于权重的任务调度算法

鲁亮¹, 于炯^1,2, 卞琛², 英昌甜^2,3, 师康利², 蒲勇霖²

1. 新疆大学信息科学与工程学院, 乌鲁木齐 830046;
2. 新疆大学软件学院, 乌鲁木齐 830008;
3. 新疆大学电气工程学科博士后科研流动站, 乌鲁木齐 830047

收稿日期:2017-08-31 修回日期:2017-11-07 出版日期:2018-03-10 发布日期:2018-03-07
通讯作者: 鲁亮
作者简介:鲁亮(1990-),男,湖南湘潭人,博士研究生,CCF会员,主要研究方向:分布式计算、内存计算;于炯(1964-),男,北京人,教授,博士生导师,博士,CCF会员,主要研究方向:网格计算、分布式计算;卞琛(1981-),男,江苏南京人,副教授,博士,CCF会员,主要研究方向:分布式计算、内存计算;英昌甜(1989-),女,新疆乌鲁木齐人,博士,主要研究方向:内存计算、绿色存储;师康利(1990-),女,河南许昌人,硕士研究生,主要研究方向:分布式计算、内存计算;蒲勇霖(1991-),男,山东淄博人,硕士研究生,主要研究方向:内存计算、绿色计算。
基金资助:
国家自然科学基金资助项目（61462079，61562086）；新疆维吾尔自治区自然科学基金资助项目（2017D01A20）；新疆维吾尔自治区高校科研计划项目（XJEDU2016S106）；新疆维吾尔自治区研究生科研创新项目（XJGRI2016028）。

Task scheduling algorithm based on weight in Storm

LU Liang¹, YU Jiong^1,2, BIAN Chen², YING Changtian^2,3, SHI Kangli², PU Yonglin²

1. School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China;
2. School of Software, Xinjiang University, Urumqi Xinjiang 830008, China;
3. Postdoctoral Research Station of Electrical Engineering, Xinjiang University, Urumqi Xinjiang 830047, China

Received:2017-08-31 Revised:2017-11-07 Online:2018-03-10 Published:2018-03-07
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61462079, 61562086), the Natural Science Foundation of Xinjiang Uygur Autonomous Region of China (2017D01A20), the Educational Research Program of Xinjiang Uygur Autonomous Region of China (XJEDU2016S106), the Graduate Research and Innovation Project of Xinjiang Uygur Autonomous Region of China (XJGRI2016028).

摘要/Abstract

摘要： 大数据流式计算平台Apache Storm默认采用轮询的方式进行任务调度，未考虑到拓扑中各任务计算开销的差异以及任务之间不同类型的通信模式，在负载均衡和通信开销方面存在较大的优化空间。针对这一问题，提出一种Storm环境下基于权重的任务调度算法（TSAW-Storm）。该算法首先根据各任务的CPU资源占用情况以及任务间的数据流大小，分别确定拓扑的点权和边权；并利用最大化边权增益的思想，逐步构建起各工作节点中承载的任务集合，在保证集群负载均衡的同时，尽可能将边权较大的节点间数据流转化为节点内数据流，从而降低网络传输开销。实验结果表明，在包含有8个工作节点的WordCount基准测试中，TSAW-Storm的系统延迟和节点间数据流大小相比Storm默认调度算法分别降低了30.0%和32.9%，且各工作节点的CPU负载标准差仅为Storm默认调度算法的25.8%；此外，在与在线调度算法的对比实验中，TSAW-Storm在系统延迟、节点间数据流大小和CPU负载标准差方面分别降低了7.76%、11.8%和5.93%，且算法的执行开销明显降低，有效提高了Storm系统的运行效率。

关键词: 大数据, 流式计算, Storm, 权重, 任务调度, 负载均衡, 通信开销

Abstract: Apache Storm, a typical platform for big data stream computing, uses a round-robin scheduling algorithm as the default scheduler, which does not consider the fact that differences of computational and communication cost are ubiquitous among different tasks and different data streams in one topology. Hence optimization is needed in terms of load balance and communication cost. To solve this problem, a Task Scheduling Algorithm based on Weight in Storm (TSAW-Storm) was proposed. In the algorithm, CPU occupation was taken as the weight of a task in a specific topology, and similarly tuple rate between a pair of tasks was taken as the weight of a data stream. Then tasks were assigned to the most suitable work node gradually by maximizing the gain of weight of data streams via transforming inter-node data streams into intra-node ones as many as possible with load balance ensured in order to reduce network overhead. Experimental results show that TSAW-Storm can reduce latency and inter-node tuple rate by about 30.0% and 32.9% respectively, and standard deviation of CPU load of work nodes is only 25.8% when compared to Storm default scheduling algorithm in WordCount benchmark with 8 work nodes. Additionally, online scheduler is deployed in contrast experiment. Experimental results show that TSAW-Storm can reduce latency, inter-node tuple rate and standard deviation of CPU load by about 7.76%, 11.8% and 5.93% respectively, which needs only a bit of executive overhead compared to online scheduler. Therefore, the proposed algorithm can reduce communication cost as well as improve load balance effectively, which makes a great contribution to the efficient operation of Apache Storm.

Key words: big data, stream computing, Storm, weight, task scheduling, load balancing, communication cost

中图分类号:

TP311

鲁亮, 于炯, 卞琛, 英昌甜, 师康利, 蒲勇霖. Storm环境下基于权重的任务调度算法[J]. 计算机应用, 2018, 38(3): 699-706.

LU Liang, YU Jiong, BIAN Chen, YING Changtian, SHI Kangli, PU Yonglin. Task scheduling algorithm based on weight in Storm[J]. Journal of Computer Applications, 2018, 38(3): 699-706.

参考文献

[1] 孟小峰,慈祥.大数据管理:概念、技术与挑战[J].计算机研究与发展,2013,50(1):146-169. (MENG X F, CI X. Big data management:concepts, techniques and challenges[J]. Journal of Computer Research and Development, 2013, 50(1):146-169.)
[2] CHEN C L P, ZHANG C Y. Data-intensive applications, challenges, techniques and technologies:a survey on big data[J]. Information Sciences, 2014, 275(11):314-347.
[3] TOSHNIWAL A, TANEJA S, SHUKLA A, et al. Storm@Twitter[C]//Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2014:147-156.
[4] Apache. Apache Storm[EB/OL]. (2017-08-01)[2017-08-10]. http://storm.apache.org.
[5] 孙大为,张广艳,郑纬民.大数据流式计算:关键技术及系统实例[J].软件学报,2014,25(4):839-862. (SUN D W, ZHANG G Y, ZHENG W M. Big data stream computing:technologies and instances[J]. Journal of Software, 2014, 25(4):839-862.)
[6] RANJAN R. Streaming big data processing in datacenter clouds[J]. IEEE Cloud Computing, 2014, 1(1):78-83.
[7] 王铭坤,袁少光,朱永利,等.基于Storm的海量数据实时聚类[J].计算机应用,2014,34(11):3078-3081. (WANG M K, YUAN S G, ZHU Y L, et al. Real-time clustering for massive data using Storm[J]. Journal of Computer Applications,2014,34(11):3078-3081.)
[8] 乔通,赵卓峰,丁维龙.面向套牌甄别的流式计算系统[J].计算机应用,2017,37(1):153-158. (QIAO T, ZHAO Z F, DING W L. Stream computing system for monitoring copy plate vehicles[J]. Journal of Computer Applications, 2017, 37(1):153-158.)
[9] TA V D, LIU C M, NKABINDE G W. Big data stream computing in healthcare real-time analytics[C]//Proceedings of 2016 IEEE International Conference on Cloud Computing and Big Data Analysis. Piscataway, NJ:IEEE, 2016:37-42.
[10] PENG B Y, HOSSEINI M, HONG Z H, et al. R-Storm:resource-aware scheduling in Storm[C]//Proceedings of the 16th Annual Middleware Conference. New York:ACM, 2015:149-161.
[11] 刘月超,于炯,鲁亮.Storm环境下一种改进的任务调度策略[J].新疆大学学报(自然科学版),2017,34(1):90-95. (LIU Y C, YU J, LU L. An improved task schedule strategy in Storm environment[J]. Journal of Xinjiang University (Natural Science Edition), 2017, 34(1):90-95.)
[12] XU J L, CHEN Z H, TANG J, et al. T-Storm:traffic-aware online scheduling in Storm[C]//Proceedings of the 34th IEEE International Conference on Distributed Computing Systems. Piscataway, NJ:IEEE, 2014:535-544.
[13] 郑丽丽,武继刚,陈勇,等.带权图的均衡k划分[J].计算机研究与发展,2015,52(3):769-776. (ZHENG L L, WU J G, CHEN Y, et al. Balanced k-way partitioning for weighted graphs[J]. Journal of Computer Research and Development, 2015, 52(3):769-776.)
[14] SUN D W, ZHANG G Y, YANG S L, et al. Re-Stream:real-time and energy-efficient resource scheduling in big data stream computing environments[J]. Information Sciences, 2015, 319:92-112.
[15] GHADERI J, SHAKKOTTAI S, SRIKANT R. Scheduling storms and streams in the cloud[J]. ACM SIGMETRICS Performance Evaluation Review, 2015, 43(1):439-440.
[16] LIU Y, SHI X, JIN H. Runtime-aware adaptive scheduling in stream processing[J]. Concurrency and Computation:Practice and Experience, 2016, 28(14):3830-3843.
[17] CARDELLINI V, GRASSI V, LO PRESTI F, et al. Distributed QoS-aware scheduling in Storm[C]//Proceedings of the 9th ACM International Conference on Distributed Event-Based Systems. New York:ACM, 2015:344-347.
[18] 熊安萍,王贤稳,邹洋.基于Storm拓扑结构热边的调度算法[J].计算机工程,2017,43(1):37-42.(XIONG A P, WANG X W, ZOU Y. Scheduling algorithm based on Storm topology hot-edge[J]. Computer Engineering, 2017, 43(1):37-42.)
[19] ESKANDARI L, HUANG Z, EYERS D. P-Scheduler:adaptive hierarchical scheduling in Apache Storm[C]//Proceedings of the Australasian Computer Science Week Multiconference. New York:ACM, 2016:Article No. 26.
[20] ANIELLO L, BALDONI R, QUERZONI L. Adaptive online scheduling in Storm[C]//Proceedings of the 7th ACM International Conference on Distributed Event-Based Systems. New York:ACM, 2013:207-218.
[21] MARZ N. Public stormprocessor/storm-benchmark[EB/OL]. (2012-08-20)[2017-08-10]. https://github.com/stormprocessor/storm-Benchmark.
[22] ZHANG M. Intel-hadoop/storm-benchmark forked from manuzhang/storm-benchmark[EB/OL]. (2015-11-02)[2017-08-10]. https://github.com/intel-hadoop/storm-benchmark.

Storm环境下基于权重的任务调度算法

Task scheduling algorithm based on weight in Storm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	倪萍, 陈伟. 基于模糊测试的反射型跨站脚本漏洞检测[J]. 计算机应用, 2021, 41(9): 2594-2601.
[2]	陈俊, 何庆. 基于余弦相似度的改进蝴蝶优化算法[J]. 计算机应用, 2021, 41(9): 2668-2677.
[3]	朱亮, 徐华, 崔鑫. 基于基分类器系数和多样性的改进AdaBoost算法[J]. 计算机应用, 2021, 41(8): 2225-2231.
[4]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[5]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[6]	蔡瑞光, 张德生, 肖燕婷. 参数独立的加权局部均值伪近邻分类算法[J]. 计算机应用, 2021, 41(6): 1694-1700.
[7]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[8]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[9]	严爱军, 魏志远. 案例推理分类器的权重分配及案例库维护方法[J]. 计算机应用, 2021, 41(4): 1071-1077.
[10]	唐延强, 李成海, 宋亚飞. 基于改进粒子群优化和极限学习机的网络安全态势预测[J]. 计算机应用, 2021, 41(3): 768-773.
[11]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[12]	周翔, 翟俊海, 黄雅婕, 申瑞彩, 侯璎真. 基于随机森林和投票机制的大数据样例选择算法[J]. 计算机应用, 2021, 41(1): 74-80.
[13]	王博, 刘连生, 韩绍程, 祝世兴. 基于多策略融合的混合多目标蝗虫优化算法[J]. 计算机应用, 2020, 40(9): 2670-2676.
[14]	杨云龙, 孙建强, 宋国超. 基于门控循环单元和胶囊特征的文本情感分析[J]. 计算机应用, 2020, 40(9): 2531-2535.
[15]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.