Ls-Stream: Lightening Stragglers in Join Operators for Skewed Data Stream Processing
IEEE Transactions on Computers · 2025-08 · 74 (8) · 2841-2855
DOI: 10.1109/tc.2025.3575917 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Computers, 2025-08. Verfasst von Minghui Wu und 4 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 33 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Fundamental Research Funds for the Central Universities.
Abstract (Originalsprache)
Load imbalance can lead to the emergence of stragglers, i.e., join instances that significantly lag behind others in processing data streams. Currently, state-of-the-art solutions are capable of balancing the load between join instances to mitigate stragglers by managing hot keys and random partitioning. However, these solutions rely on either complicated routing strategies or resource-inefficient processing structures, making them susceptible to frequent changes in load between instances. Therefore, we present Ls-Stream, a data stream scheduler that aims to support dynamic workload assignment for join instances to lighten stragglers. This paper outlines our solution from the following aspects: (1) The models for partitioning, communication, matrix, and resource are developed, formalizing problems like imbalanced load between join instances and state migration costs. (2) Ls-Stream employs a two-level routing strategy for workload allocation by combining hash-based and key-based data partitioning, specifying the destination join instances for data tuples. (3) Ls-Stream also constructs a fine-grained model for minimizing the state migration cost. This allows us to make trade-offs between data transfer overhead and migration benefits. (4) Experimental results demonstrate significant improvements made by Ls-Stream: reducing maximum system latency by 49.3% and increasing maximum throughput by more than 2x compared to existing state-of-the-art works.
Förderung
- National Natural Science Foundation of China
- Fundamental Research Funds for the Central Universities
Zitieren
APA
Wu, M., Sun, D., Gao, S., Li, K., & Buyya, R. (2025). Ls-Stream: Lightening Stragglers in Join Operators for Skewed Data Stream Processing. IEEE Transactions on Computers, 74(8), 2841-2855. https://doi.org/10.1109/tc.2025.3575917
Vancouver
Wu M, Sun D, Gao S, Li K, Buyya R. Ls-Stream: Lightening Stragglers in Join Operators for Skewed Data Stream Processing. IEEE Transactions on Computers. 2025;74(8):2841-2855. doi:10.1109/tc.2025.3575917
BibTeX
@article{Wu2025,
author = {Wu, Minghui and Sun, Dawei and Gao, Shang and Li, Keqin and Buyya, Rajkumar},
title = {Ls-Stream: Lightening Stragglers in Join Operators for Skewed Data Stream Processing},
journal = {IEEE Transactions on Computers},
year = {2025},
volume = {74},
number = {8},
pages = {2841--2855},
doi = {10.1109/tc.2025.3575917}
}
EUVIMED