摘要
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.
基金
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.
