A Task Allocation Method for Stream Processing with Recovery Latency Constraint  

作　　者：Hong-Liang Li Jie Wu Zhen Jiang Xiang Li Xiao-Hui Wei 

机构地区：[1]College of Computer Science and Technology, Jilin University, Changchun 130012, China [2]Key Laboratory of Symbolic Computation and Knowledge Engineering of the Ministry of Education Changchun 130012, China [3]Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122, U.S.A. [4]Department of Computer Science, West Chester University of Pennsylvania, West Chester, PA 19383, U.S.A.

出　　处：《Journal of Computer Science & Technology》2018年第6期1125-1139,共15页计算机科学技术学报（英文版）

基　　金：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 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.

关 键 词：STREAM processing task allocation FAULT-TOLERANCE UPSTREAM backup  RECOVERY LATENCY 

分 类 号：TP[自动化与计算机技术]