Stateful load balancing for parallel stream processing

Qingsong Guo; Yongluan Zhou

doi:10.1007/978-3-319-75178-8_7

Stateful load balancing for parallel stream processing

Qingsong Guo^*, Yongluan Zhou

^*Corresponding author for this work

Department of Computer Science

Abstract

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.

Original language	English
Title of host publication	Euro-Par 2017 : Parallel Processing Workshops
Editors	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
Number of pages	14
Publisher	Springer
Publication date	1 Jan 2018
Pages	80-93
ISBN (Print)	9783319751771
DOIs	https://doi.org/10.1007/978-3-319-75178-8_7
Publication status	Published - 1 Jan 2018
Event	International Workshops on Parallel Processing, Euro-Par 2017 - Santiago de Compostela, Spain Duration: 28 Aug 2017 → 29 Aug 2017

Conference

Conference	International Workshops on Parallel Processing, Euro-Par 2017
Country/Territory	Spain
City	Santiago de Compostela
Period	28/08/2017 → 29/08/2017

Series	Lecture notes in computer science
Volume	10659
ISSN	0302-9743

Keywords

Load balancing
State movement
Stream processing

Access to Document

10.1007/978-3-319-75178-8_7

Cite this

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

Guo, Q & Zhou, Y 2018, Stateful load balancing for parallel stream processing. in DB Heras, L Bougé, G Mencagli, E Jeannot, R Sakellariou, RM Badia, JG Barbosa, L Ricci, SL Scott, S Lankes & J Weidendorfer (eds), Euro-Par 2017: Parallel Processing Workshops. Springer, Lecture notes in computer science, vol. 10659, pp. 80-93, International Workshops on Parallel Processing, Euro-Par 2017, Santiago de Compostela, Spain, 28/08/2017. https://doi.org/10.1007/978-3-319-75178-8_7

Guo, Qingsong ; Zhou, Yongluan. / Stateful load balancing for parallel stream processing. Euro-Par 2017: Parallel Processing Workshops. editor / 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. pp. 80-93 (Lecture notes in computer science, Vol. 10659).

@inproceedings{488bd4b1e3ad4ef28d116cfd66b2d782,

title = "Stateful load balancing for parallel stream processing",

abstract = "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.",

keywords = "Load balancing, State movement, Stream processing",

author = "Qingsong Guo and Yongluan Zhou",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-75178-8_7",

language = "English",

isbn = "9783319751771",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "80--93",

editor = "Heras, {Dora B.} and Luc Boug{\'e} and Gabriele Mencagli and Emmanuel Jeannot and Rizos Sakellariou and Badia, {Rosa M.} and Barbosa, {Jorge G.} and Ricci, {Laura } and Scott, {Stephen L.} and Stefan Lankes and Josef Weidendorfer",

booktitle = "Euro-Par 2017",

note = "International Workshops on Parallel Processing, Euro-Par 2017 ; Conference date: 28-08-2017 Through 29-08-2017",

}

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 -

Stateful load balancing for parallel stream processing

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this