A Task Allocation Method for Stream Processing with Recovery Latency Constraint
作者机构：College of Computer Science and Technology Jilin University Changchun 130012 China Key Laboratory of Symbolic Computation and Knowledge Engineering of the Ministry of Education Changchun 130012 China Department of Computer and Information Sciences Temple University Philadelphia PA 19122 U.S.A. Department of Computer Science West Chester University of Pennsylvania West Chester PA 19383 U.S.A.
出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)
年 卷 期：2018年第33卷第6期
页 面：1125-1139页
核心收录：
学科分类：0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）]
基 金：This work is supported by the National Key Research and Development Program of China under Grant No. 2017YFC1502306 the National Natural Science Foundation of China under Grant No. 61602205 the China Scholarship Council and the National Science Foundation of the U.S. under Grant Nos. CNS 1629746 CNS 1564128 CNS 149860 CNS 1461932 CNS 1460971 CNS 1439672 CNS 1301774 and ECCS 1231461.
主 题：stream processing task allocation fault-tolerance upstream backup, recovery latency
摘 要：Stream processing applications continuously process large amounts of online streaming data in real time or nearreal time. They have strict latency constraints. However, the continuous processing makes them vulnerable to any failures,and the recoveries may slow down the entire processing pipeline and break latency constraints. The upstream backupscheme is one of the most widely applied fault-tolerant schemes for stream processing systems. It introduces complexbackup dependencies to tasks, which increases the difficulty of controlling recovery latencies. Moreover, when dependenttasks are located on the same processor, they fail at the same time in processor-level failures, bringing extra recovery latencies that increase the impacts of failures. This paper studies the relationship between the task allocation and therecovery latency of a stream processing application. We present a correlated failure effect model to describe the recoverylatency of a stream topology in processor-level failures under a task allocation plan. We introduce a recovery-latency awaretask allocation problem （RTAP） that seeks task allocation plans for stream topologies that will achieve guaranteed recoverylatencies. We discuss the difference between RTAP and classic task allocation problems and present a heuristic algorithmwith a computational complexity of O（n log2 n） to solve the problem. Extensive experiments were conducted to verify thecorrectness and effectiveness of our approach. It improves the resource usage by 15%-20% on average.
维普期刊数据库