Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
The power of both choices: Practical load balancing for distributed stream processing engines
KTH, Skolan för elektro- och systemteknik (EES), Kommunikationsnät.ORCID-id: 0000-0001-5872-7809
Vise andre og tillknytning
2015 (engelsk)Inngår i: Proceedings - International Conference on Data Engineering, IEEE conference proceedings, 2015, s. 137-148Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

We study the problem of load balancing in distributed stream processing engines, which is exacerbated in the presence of skew. We introduce Partial Key Grouping (PKG), a new stream partitioning scheme that adapts the classical 'power of two choices' to a distributed streaming setting by leveraging two novel techniques: key splitting and local load estimation. In so doing, it achieves better load balancing than key grouping while being more scalable than shuffle grouping. We test PKG on several large datasets, both real-world and synthetic. Compared to standard hashing, PKG reduces the load imbalance by up to several orders of magnitude, and often achieves nearly-perfect load balance. This result translates into an improvement of up to 60% in throughput and up to 45% in latency when deployed on a real Storm cluster.

sted, utgiver, år, opplag, sider
IEEE conference proceedings, 2015. s. 137-148
Emneord [en]
Balancing, Distributed parameter control systems, Engines, Distributed stream processing, Distributed streaming, Large datasets, Load balance, Load imbalance, Novel techniques, Orders of magnitude, Power-of-two, Network management
HSV kategori
Identifikatorer
URN: urn:nbn:se:kth:diva-176121DOI: 10.1109/ICDE.2015.7113279Scopus ID: 2-s2.0-84940858966ISBN: 9781479979639 (tryckt)OAI: oai:DiVA.org:kth-176121DiVA, id: diva2:874693
Konferanse
2015 31st IEEE International Conference on Data Engineering, ICDE 2015, 13 April - 17 April 2015
Merknad

QC 20151127

Tilgjengelig fra: 2015-11-27 Laget: 2015-11-02 Sist oppdatert: 2018-04-05bibliografisk kontrollert
Inngår i avhandling
1. Mining Big and Fast Data: Algorithms and Optimizations for Real-Time Data Processing
Åpne denne publikasjonen i ny fane eller vindu >>Mining Big and Fast Data: Algorithms and Optimizations for Real-Time Data Processing
2018 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
Abstract [en]

In the last decade, real-time data processing has attracted much attention from both academic community and industry, as the meaning of big data has evolved to incorporate as well the speed of data. The massive and rapid production of data comes via numerous services, i.e., Web, social networks, Internet of Things (IoT) and mobile devices. For instance, global positioning systems are producing continuous data points using various location-based services. IoT devices are continuously monitoring variety of parameters, like temperature, heart beats, and others, and sending the data over the network. Moreover, part of the data produced by these real-time services is linked-data that requires tools for streaming graph analytics. Real-time graphs are ubiquitous in many fields, from the web advertising to bio-analytics. Developing analytical tools to process this amount of information at a real-time is challenging, yet extremely essential, for developing new services in areas such as web analytics, e-health and marketing.

Distributed stream processing engines (dspes) are often employed for real-time data processing, as they distribute work to many machines to achieve the required performance guarantees, i.e., low latency and high throughput. However, the scalability of dspes is often questioned when the input streams are skewed or the underlying resources are heterogeneous. In this thesis, we perform a scalability study for dspes. In particular, we study the load- balancing problem for dspes, which is caused by the skewness in the workload and heterogeneity in the cluster. In doing so, we develop several efficient and accurate algorithms to reduce the load imbalance in a distributed system. Moreover, our algorithms are integrated into Apache Storm, which is an open source stream processing framework.

Another dimension of real-time data processing involves developing novel algorithms for graph-related problems. The later part of the thesis presents several algorithms for evolving graphs. One of the most interesting features of real-world networks is the presence of community structure, which divides a network into groups of nodes with dense connections internally and sparse connections between groups. We study the community detection problem in the fully dynamic settings by formulating it as a top-k densest subgraph problem. In doing so, we achieve an extremely efficient approximation algorithm that scales to graphs with billions of edges. Further, we study the top-k graph pattern-mining problem in fully dynamic settings and develop a probabilistic algorithm using reservoir sampling. We provide the theoretical analysis for the proposed algorithms and show via empirical evaluation that our algorithms achieve up to several orders of magnitude improvement compared to the state-of-the-art algorithm.

sted, utgiver, år, opplag, sider
Stockholm: KTH Royal Institute of Technology, 2018. s. 42
Serie
TRITA-EECS-AVL ; 2018:27
Emneord
Stream Processing, Load Balancing, Fully Dynamic Graphs, Real-Time Data Processing, Top-k Densest Subgraph, Frequent Subgraph Mining
HSV kategori
Forskningsprogram
Informations- och kommunikationsteknik; Datalogi
Identifikatorer
urn:nbn:se:kth:diva-225487 (URN)978-91-7729-729-1 (ISBN)
Disputas
2018-05-07, Sal B, Electrum building, Kistagången 16, Stockholm, 09:00 (engelsk)
Opponent
Veileder
Merknad

QC 20180409

Tilgjengelig fra: 2018-04-09 Laget: 2018-04-05 Sist oppdatert: 2018-04-10bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Personposter BETA

Nasir, M. Anis U.

Søk i DiVA

Av forfatter/redaktør
Nasir, M. Anis U.
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 45 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf