Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
When Two Choices Are not Enough: Balancing at Scale in Distributed Stream Processing
KTH, School of Information and Communication Technology (ICT), Software and Computer systems, SCS.ORCID iD: 0000-0001-5872-7809
2016 (English)In: 2016 32ND IEEE INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE), 2016, 589-600 p.Conference paper, Published paper (Refereed)
Abstract [en]

Carefully balancing load in distributed stream processing systems has a fundamental impact on execution latency and throughput. Load balancing is challenging because real-world workloads are skewed: some tuples in the stream are associated to keys which are significantly more frequent than others. Skew is remarkably more problematic in large deployments: having more workers implies fewer keys per worker, so it becomes harder to "average out" the cost of hot keys with cold keys. We propose a novel load balancing technique that uses a heavy hitter algorithm to efficiently identify the hottest keys in the stream. These hot keys are assigned to d >= 2 choices to ensure a balanced load, where d is tuned automatically to minimize the memory and computation cost of operator replication. The technique works online and does not require the use of routing tables. Our extensive evaluation shows that our technique can balance real-world workloads on large deployments, and improve throughput and latency by 150% and 60% respectively over the previous state-of-the-art when deployed on Apache Storm.

Place, publisher, year, edition, pages
2016. 589-600 p.
Series
IEEE International Conference on Data Engineering, ISSN 1084-4627
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-193258ISI: 000382554200050Scopus ID: 2-s2.0-84980322422ISBN: 978-1-5090-2020-1 (print)OAI: oai:DiVA.org:kth-193258DiVA: diva2:1033630
Conference
32nd IEEE International Conference on Data Engineering (ICDE), MAY 16-20, 2016, Helsinki, FINLAND
Note

QC 20161007

Available from: 2016-10-07 Created: 2016-09-30 Last updated: 2016-10-07Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Nasir, Muhammad Anis Uddin
By organisation
Software and Computer systems, SCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 7 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf