Storm环境下基于拓扑结构的任务调度策略

doi:10.11772/j.issn.1001-9081.2018040741

计算机应用 ›› 2018, Vol. 38 ›› Issue (12): 3481-3489.DOI: 10.11772/j.issn.1001-9081.2018040741

Storm环境下基于拓扑结构的任务调度策略

刘粟, 于炯, 鲁亮, 李梓杨

新疆大学信息科学与工程学院, 乌鲁木齐 830046

收稿日期:2018-04-11 修回日期:2018-06-18 出版日期:2018-12-10 发布日期:2018-12-15
通讯作者: 于炯
作者简介:刘粟(1994-),女,吉林吉林人,硕士研究生,CCF会员,主要研究方向:分布式计算、内存计算;于炯(1964-),男,北京人,教授,博士生导师,博士,CCF会员,主要研究方向:网格计算、分布式计算;鲁亮(1990-),男,湖南湘潭人,博士,CCF会员,主要研究方向:云计算、分布式计算、内存计算;李梓杨(1993-),男,新疆乌鲁木齐人,博士研究生,CCF会员,主要研究方向:云计算、分布式计算。
基金资助:
国家自然科学基金资助项目（61462079，61562078，61562086）；国家科技支撑项目（2015BAH02F01）。

Task scheduling strategy based on topology structure in Storm

LIU Su, YU Jiong, LU Liang, LI Ziyang

College of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China

Received:2018-04-11 Revised:2018-06-18 Online:2018-12-10 Published:2018-12-15
Contact: 于炯
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61462079, 61562078, 61562086), the National Science and Technology Support Program (2015BAH02F01).

摘要/Abstract

摘要： 针对Storm流式计算平台中默认轮询调度策略存在通信开销大、负载不均衡的问题，提出基于拓扑结构的任务调度策略（TS²）。首先，选取CPU资源充足且可用的工作节点并各分配一个进程，消除节点内进程间通信开销，优化进程部署；然后，分析拓扑结构，找出拓扑中度最大的组件，优先分配该组件的线程；最后，在满足节点可承载最大线程数的条件下，尽可能将关联任务部署到同一个节点来减少节点间通信开销，改善集群负载均衡，优化线程部署。实验结果表明：在系统延迟方面，与Storm默认调度策略和离线调度策略相比，TS²的平均优化率分别为16.91%和5.69%，有效提高了系统的实时性；在节点间通信开销方面，TS²相比于Storm默认调度策略平均降低了15.75%；在平均吞吐量方面，TS²相比于Storm默认调度策略平均提升了14.21%。

关键词: Storm, 流式计算, 任务调度, 拓扑结构, 通信开销

Abstract: In order to solve the problems of large communication cost and unbalanced load in the default round-robin scheduling strategy of Storm stream computing platform, a Task Scheduling Strategy based on Topology Structure (TS²) in Storm was proposed. Firstly, the work nodes with sufficient and available Central Processing Unit (CPU) resources were selected and only a process was allocated to each work node to eliminate the communication cost between processes within the nodes and optimize the process deployment. Then, the topology structure was analyzed, the component with the biggest degree in the topology was found and the thread of the component was assigned with the highest priority. Finally, under the condition of the maximum number of threads that a node could carry, the associated tasks were deployed to the same node as far as possible to reduce the communication cost between nodes, improve the load balance of cluster and optimize the thread deployment. The experimental results show that, in terms of system latency, the average optimization rate of TS² is 16.91% and 5.69% respectively compared with Storm default scheduling strategy and offline scheduling strategy, which effectively improves the real-time performance of system. Additionally, compared with the Storm default scheduling strategy, the communication cost between nodes of TS² is reduced by 15.75% and its average throughput is improved by 14.21%.

Key words: Storm, stream computing, task scheduling, topology structure, communication cost

中图分类号:

刘粟, 于炯, 鲁亮, 李梓杨. Storm环境下基于拓扑结构的任务调度策略[J]. 计算机应用, 2018, 38(12): 3481-3489.

LIU Su, YU Jiong, LU Liang, LI Ziyang. Task scheduling strategy based on topology structure in Storm[J]. Journal of Computer Applications, 2018, 38(12): 3481-3489.

参考文献

[1] Seagate. Data Age 2025[EB/OL].[2017-11-29]. https://www.seagate.com/files/www-content/our-story/trends/files/data-age-2025-white-paper-simplified-chinese.pdf.
[2] 孙大为,张广艳,郑纬民.大数据流式计算:关键技术及系统实例[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.)
[3] 乔通,赵卓峰,丁维龙.面向套牌甄别的流式计算系统[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.)
[4] 蔡宇,赵国锋,郭航.实时流处理系统Storm的调度优化综述[J].计算机应用研究,2018,35(9):2567-2573.(CAI Y, ZHAO G F, GUO H. Survey of real-time processing system Storm scheduling optimization[J]. Application Research of Computers, 2018, 35(9):2567-2573.)
[5] 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.
[6] XU J L, CHEN Z H, TANG J, et al. T-Storm:traffic-aware online scheduling in Storm[C]//Proceedings of the 2014 IEEE 34th International Conference on Distributed Computing Systems. Piscataway, NJ:IEEE, 2014:535-544.
[7] FISCHER L, BERNSTEIN A. Workload scheduling in distributed stream processors using graph partitioning[C]//Proceedings of the 2015 IEEE International Conference on Big Data. Piscataway, NJ:IEEE, 2015:124-133.
[8] 鲁亮,于炯,卞琛,等.Storm环境下基于权重的任务调度算法[J].计算机应用,2018,38(3):699-706.(LU L, YU J, BIAN C, et al. Task scheduling algorithm based on weight in Storm[J]. Journal of Computer Applications, 2018, 38(3):699-706.)
[9] ZHANG J, LI C L, ZHU L Y, et al. The real-time scheduling strategy based on traffic and load balancing in Storm[C]//Proceedings of the 2016 IEEE 18th International Conference on High Performance Computing and Communications, IEEE 14th International Conference on Smart City, and IEEE 2nd International Conference on Data Science and Systems. Piscataway, NJ:IEEE, 2016:372-379.
[10] 熊安萍,王贤稳,邹洋.基于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.)
[11] 鲁亮,于炯,卞琛,等.大数据流式计算框架Storm的任务迁移策略[J].计算机研究与发展,2018,55(1):71-92.(LU L, YU J, BIAN C, et al. A task migration strategy in big data stream computing with Storm[J]. Journal of Computer Research and Development, 2018, 55(1):71-92.)
[12] 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.
[13] CHEN Z, XU J, TANG J, et al. GPU-accelerated high-throughput online stream data processing[J]. IEEE Transactions on Big Data, 2018, 4(2):191-202.
[14] CHEN Y R, LEE C R. G-Storm:a GPU-aware Storm scheduler[C]//Proceedings of the 2016 IEEE 14th International Conference on Dependable, Autonomic and Secure Computing, 14th International Conference on Pervasive Intelligence and Computing, 2nd International Conference on Big Data Intelligence and Computing and Cyber Science and Technology Congress. Piscataway, NJ:IEEE, 2016:738-745.
[15] 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.
[16] CARDELLINI V, GRASSI V, PRESTI F L, 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.
[17] FARAHABADY M R H, SAMANI H R D, WANG Y, et al. A QoS-aware controller for Apache Storm[C]//Proceedings of the 201615th IEEE International Symposium on Network Computing and Applications. Piscataway, NJ:IEEE, 2016:334-342.
[18] 李梓杨,于炯,卞琛,等.基于负载感知的数据流动态负载均衡策[J].计算机应用,2017,37(10):2760-2766.(LI Z Y, YU J, BIAN C, et al. Dynamic data stream load balancing strategy based on load awareness[J]. Journal of Computer Applications, 2017, 37(10):2760-2766.)
[19] QIAN W, SHEN Q N, QIN J, et al. S-Storm:a slot-aware scheduling strategy for even scheduler in Storm[C]//Proceedings of the 2016 IEEE 18th International Conference on High Performance Computing and Communications, IEEE 14th International Conference on Smart City, IEEE 2nd International Conference on Data Science and Systems. Piscataway, NJ:IEEE, 2017:623-630.
[20] LI C, ZHANG J, LUO Y. Real-time scheduling based on optimized topology and communication traffic in distributed real-time computation platform of Storm[J]. Journal of Network and Computer Applications, 2017, 87(1):110-115.
[21] ZHANG J, LI C L, ZHU L Y, et al. The real-time scheduling strategy based on traffic and load balancing in Storm[C]//Proceedings of the 2016 IEEE 18th International Conference on High Performance Computing and Communications, IEEE 14th International Conference on Smart City, IEEE 2nd International Conference on Data Science and Systems. Piscataway, NJ:IEEE, 2016:372-379.

Storm环境下基于拓扑结构的任务调度策略

Task scheduling strategy based on topology structure in Storm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[2]	刘智翔, 刘慧超, 黄冬梅, 周丽萍, 苏诚. 多种任务调度混合的IB-LBM并行优化方法[J]. 计算机应用, 2020, 40(2): 386-391.
[3]	李孜颖, 石振国. 面向大数据任务的调度方法[J]. 计算机应用, 2020, 40(10): 2923-2928.
[4]	孙小涓, 石涛, 胡玉新, 佟继周, 李冰, 宋峣. 基于流式计算的空间科学卫星数据实时处理[J]. 计算机应用, 2019, 39(6): 1563-1568.
[5]	张译天, 于炯, 鲁亮, 李梓杨. 大数据流式计算框架Heron环境下的流分类任务调度策略[J]. 计算机应用, 2019, 39(4): 1106-1116.
[6]	沙宗轩, 薛菲, 朱杰. 基于并行强化学习的云机器人任务调度策略[J]. 计算机应用, 2019, 39(2): 501-508.
[7]	孙敏, 叶侨楠, 陈中雄. 云环境下方差定向变异遗传算法的任务调度[J]. 计算机应用, 2019, 39(11): 3328-3332.
[8]	刘鹏飞, 毛莺池, 王龙宝. 基于云雾协作模型的任务分配方法[J]. 计算机应用, 2019, 39(1): 8-14.
[9]	陆秋琴, 靳超. 煤炭运输公路网络可靠性仿真分析[J]. 计算机应用, 2019, 39(1): 292-297.
[10]	李梓杨, 于炯, 卞琛, 鲁亮, 蒲勇霖. 基于流网络的流式计算动态任务调度策略[J]. 计算机应用, 2018, 38(9): 2560-2567.
[11]	鲁亮, 于炯, 卞琛, 英昌甜, 师康利, 蒲勇霖. Storm环境下基于权重的任务调度算法[J]. 计算机应用, 2018, 38(3): 699-706.
[12]	李昆仑, 关立伟, 郭昌隆. 基于聚类和改进共生演算法的云任务调度策略[J]. 计算机应用, 2018, 38(3): 707-714.
[13]	毛莺池, 穆超, 包威, 李晓芳. 空间众包中多类型任务的分配与调度方法[J]. 计算机应用, 2018, 38(1): 6-12.
[14]	丁大钊, 陈云杰, 靳彦青, 刘树新. 基于拓扑连接紧密度的相似性链路预测算法[J]. 计算机应用, 2017, 37(8): 2129-2132.
[15]	韩虎, 王鹏, 程琨, 李波. 基于多尺度量子谐振子算法的云计算任务调度[J]. 计算机应用, 2017, 37(7): 1888-1892.