A state lossless scheduling strategy in distributed stream computing systems. (October 2022)

• Record Type: Journal Article
• Authors: Wu, Minghui; Sun, Dawei; Cui, Yijing; Gao, Shang; Liu, Xunyun; Buyya, Rajkumar
• Is Part Of: Journal of network and computer applications. Volume 206(2022)
• Publication Date: 2022-10
• Subjects: Stream computing -- Online scheduling -- State management -- Bipartite graph -- Hierarchical migration; Microcomputers -- Periodicals; Computer networks -- Periodicals; Application software -- Periodicals; Micro-ordinateurs -- Périodiques; Réseaux d'ordinateurs -- Périodiques; Logiciels d'application -- Périodiques; Application software; Computer networks; Microcomputers; Periodicals; 004.05; 004
• DOI: 10.1016/j.jnca.2022.103462
• Languages: English
• ISSNs: 1084-8045

Abstract

Abstract: Stateful scheduling is of critical importance for the performance of a distributed stream computing system. In such a system, inappropriate task deployment lowers the resource utilization of cluster and introduces more communication between compute nodes. Also an online adjustment to task deployment scheme suffers slow state recovery during task restart. To address these issues, we propose a state lossless scheduling strategy (Sl-Stream) to optimize the task deployment and state recovery process. This paper discusses this strategy from the following aspects: (1) A stream application model and a resource model are constructed, together with the formalization of problems including subgraph partitioning, task deployment and stateful scheduling. (2) A multi-factor topology partitioning method is proposed using a quantum particle swarm algorithm. The assignment between tasks and nodes is optimized using a bipartite graph minimum matching algorithm. (3) A hierarchical local topology migration is performed when an online scheduling is triggered, which ensures the processing sustainability of data streams. (4) A fragment loss-tolerant jerasure tool is used to divide the state data into fragments and periodically save them in upstream vertex instances, which ensures the available fragments be able to reconstruct the whole state in parallel. (5) Metrics including latency, throughput and state recovery time are evaluated in a real distributed stream computing environment. With a comprehensive evaluation of variable-rate input scenarios, the proposed Sl-Stream system provides promising improvements on throughput, latency and state recovery time compared to the existing Storm's scheduling strategies. Highlights: Modeling of stream applications and resources, and formalization of scheduling problems. A multi-factor graph partitioning method to reduce communication delay and balance resource consumption. A one-to-one matching model between subgraphs and nodes using bipartite graph minimum matching algorithm. A fragment loss-tolerant tool for state data division and reconstruction.