Dynamic data stream load balancing strategy based on load awareness
LI Ziyang1, YU Jiong1,2, BIAN Chen2, WANG Yuefei2, LU Liang2
1. School of Software, Xinjiang University, Urumqi Xinjiang 830008, China; 2. School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China
Abstract：Concerning the problem of unbalanced load and incomplete comprehensive evaluation of nodes in big data stream processing platform, a dynamic load balancing strategy based on load awareness algorithm was proposed and applied to a data stream processing platform named Apache Flink. Firstly, the computational delay time of the nodes was obtained by using the depth-first search algorithm for the Directed Acyclic Graph (DAG) and regarded as the basis for evaluating the performance of the nodes, and the load balancing strategy was created. Secondly, the load migration technology for data stream was implemented based on the data block management strategy, and both the global and local load optimization was implemented through feedback. Finally, the feasibility of the algorithm was proved by evaluating its time-space complexity, meanwhile the influence of important parameters on the algorithm execution was discussed. The experimental results show that the proposed algorithm increases the efficiency of the task execution by optimizing the load sharing between nodes, and the task execution time is shortened by 6.51% averagely compared with the traditional load balancing strategy of Apache Flink.
[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] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113. [3] 陈付梅, 韩德志, 毕坤, 等.大数据环境下的分布式数据流处理关键技术探析[J]. 计算机应用, 2017, 37(3): 620-627. (CHEN F M, HAN D Z, BI K, et al. Key technologies of distributed data stream processing based on big data[J]. Journal of Computer Applications, 2017, 37(3): 620-627.) [4] 孙大为, 张广艳, 郑纬民.大数据流式计算: 关键技术及系统实例[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.) [5] QIAN Z, HE Y, SU C, et al. TimeStream: reliable stream computation in the cloud[C]//Proceedings of the 8th ACM European Conference on Computer Systems. New York: ACM, 2013: 1-14. [6] ALEXANDROV A, BERGMANN R, EWEN S, et al. The stratosphere platform for big data analytics[J]. The VLDB Journal, 2014, 23(6): 939-964. [7] CARBONE P, KATSIFODIMOS A, EWEN S, et al. Apache Flink: stream and batch processing in a single engine[J]. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2015, 36(4):28-38. [8] KOSTAS T, ELLEN F. Introduction to Apache Flink[M]. Sebastopol: O'Reilly Media, 2016: 54. [9] TANMAY D. Learning Apache Flink[M]. Birmingham: Packt Publishing, 2017: 63. [10] CARBONE P, FÓRA G, EWEN S, et al. Lightweight asynchronous snapshots for distributed data flows[EB/OL]. [2017-01-10]. https://arxiv.org/pdf/1506.08603. [11] CARBONE P, TRAUB J, KATSIFODIMOS A, et al. Cutty: aggregate sharing for user-defined windows[C]//Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. New York: ACM, 2016: 1201-1210. [12] CHINTAPALLI S, DAGIT D, EVANS B, et al. Benchmarking streaming computation engines: Storm, Flink and Spark streaming[C]//Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium Workshops. Piscataway, NJ: IEEE, 2016: 1789-1792. [13] COLLINS R L, CARLONI L P. Flexible filters: load balancing through backpressure for stream programs[C]//Proceedings of the Seventh ACM International Conference on Embedded Software. New York: ACM, 2009: 205-214. [14] SUN D, ZHANG G, YANG S, 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] ANIELLO L, BALDONI R, QUERZONI L. Adaptive online scheduling in Storm [C]//DEBS 2013: Proceedings of the 7th ACM International Conference on Distributed Event-Based Systems. New York: ACM, 2013: 207-218. [16] KWON Y C, BALAZINSKA M, HOWE B, et al. Skew-resistant parallel processing of feature-extracting scientific user-defined functions[C]//Proceedings of the 1st ACM Symposium on Cloud Computing. New York: ACM, 2010: 75-86. [17] LOHRMANN B, JANACIK P, KAO O. Elastic stream processing with latency guarantees[C]//Proceedings of the 2015 IEEE 35th International Conference on Distributed Computing Systems. Piscataway, NJ: IEEE, 2015: 399-410. [18] Fabian Hueske. Incubator-Flink[EB/OL]. [2017-03-26]. https://github.com/physikerwelt/incubator-flink.
2017, Vol. 37 
