Stateful load balancing for parallel stream processing

Qingsong Guo*, Yongluan Zhou

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

1 Citation (Scopus)

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 languageEnglish
Title of host publicationEuro-Par 2017 : Parallel Processing Workshops
EditorsDora 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 pages14
PublisherSpringer
Publication date1 Jan 2018
Pages80-93
ISBN (Print)9783319751771
DOIs
Publication statusPublished - 1 Jan 2018
EventInternational Workshops on Parallel Processing, Euro-Par 2017 - Santiago de Compostela, Spain
Duration: 28 Aug 201729 Aug 2017

Conference

ConferenceInternational Workshops on Parallel Processing, Euro-Par 2017
Country/TerritorySpain
CitySantiago de Compostela
Period28/08/201729/08/2017
SeriesLecture notes in computer science
Volume10659
ISSN0302-9743

Keywords

  • Load balancing
  • State movement
  • Stream processing

Cite this