Stateful load balancing for parallel stream processing
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Stateful load balancing for parallel stream processing. / Guo, Qingsong; Zhou, Yongluan.
Euro-Par 2017: Parallel Processing Workshops. ed. / Dora B. Heras; Luc Bougé; Gabriele Mencagli; Emmanuel Jeannot; Rizos Sakellariou; Rosa M. Badia; Jorge G. Barbosa; Laura Ricci; Stephen L. Scott; Stefan Lankes; Josef Weidendorfer. Springer, 2018. p. 80-93 (Lecture notes in computer science, Vol. 10659).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Stateful load balancing for parallel stream processing
AU - Guo, Qingsong
AU - Zhou, Yongluan
PY - 2018/1/1
Y1 - 2018/1/1
N2 - Timely processing of streams in parallel requires dynamic load balancing to diminish skewness of data. In this paper we study this problem for stateful operators with key grouping for which the process of load balancing involves a lot of state movements. Consequently, load balancing is a bi-objective optimization problem, namely Minimum-Cost-Load-Balance (MCLB). We address MCLB with two approximate algorithms by a certain relaxation of the objectives: (1) a greedy algorithm ELB performs load balancing eagerly but relaxes the objective of load imbalance to a range; and (2) a periodic algorithm CLB aims at reducing load imbalance via a greedy procedure of minimizing the covariance of substreams but ignores the objective of state movement by amortizing the overhead of it over a relative long period. We evaluate our approaches with both synthetic and real data. The results show that they can adapt effectively to load variations and improve latency efficiently comparing to the existing solutions whom ignored the overhead of state movement in stateful load balancing.
AB - Timely processing of streams in parallel requires dynamic load balancing to diminish skewness of data. In this paper we study this problem for stateful operators with key grouping for which the process of load balancing involves a lot of state movements. Consequently, load balancing is a bi-objective optimization problem, namely Minimum-Cost-Load-Balance (MCLB). We address MCLB with two approximate algorithms by a certain relaxation of the objectives: (1) a greedy algorithm ELB performs load balancing eagerly but relaxes the objective of load imbalance to a range; and (2) a periodic algorithm CLB aims at reducing load imbalance via a greedy procedure of minimizing the covariance of substreams but ignores the objective of state movement by amortizing the overhead of it over a relative long period. We evaluate our approaches with both synthetic and real data. The results show that they can adapt effectively to load variations and improve latency efficiently comparing to the existing solutions whom ignored the overhead of state movement in stateful load balancing.
KW - Load balancing
KW - State movement
KW - Stream processing
UR - http://www.scopus.com/inward/record.url?scp=85042502319&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-75178-8_7
DO - 10.1007/978-3-319-75178-8_7
M3 - Article in proceedings
AN - SCOPUS:85042502319
SN - 9783319751771
T3 - Lecture notes in computer science
SP - 80
EP - 93
BT - Euro-Par 2017
A2 - Heras, Dora B.
A2 - Bougé, Luc
A2 - Mencagli, Gabriele
A2 - Jeannot, Emmanuel
A2 - Sakellariou, Rizos
A2 - Badia, Rosa M.
A2 - Barbosa, Jorge G.
A2 - Ricci, Laura
A2 - Scott, Stephen L.
A2 - Lankes, Stefan
A2 - Weidendorfer, Josef
PB - Springer
T2 - International Workshops on Parallel Processing, Euro-Par 2017
Y2 - 28 August 2017 through 29 August 2017
ER -
ID: 194909417