Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Load Balancing for Skewed Streams on Heterogeneous Clusters
KTH, School of Electrical Engineering and Computer Science (EECS). (SCS)ORCID iD: 0000-0001-5872-7809
Show others and affiliations
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Streaming applications frequently encounter skewed workloads and execute on heterogeneous clusters. Optimal re- source utilization in such adverse conditions becomes a challenge, as it requires inferring the resource capacities and input distribution at run time. In this paper, we tackle the aforementioned challenges by modeling them as a load balancing problem. We propose a novel partitioning strategy called Consistent Grouping (CG), which enables each processing element instance (PEI) to process the workload according to its capacity. The main idea behind CG is the notion of small, equal-sized “virtual workers” at the sources, which are assigned to physical workers based on their capacities. We provide a theoretical analysis of the proposed algorithm and show via extensive empirical evaluation that our proposed scheme outperforms the state-of-the-art approaches, like key grouping. In particular, CG achieves 3.44x better performance in terms of latency compared to key grouping.

Keywords [en]
Load Balancing, Stream Processing, Distributed Systems, Heterogenous clusters
National Category
Computer Systems
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-223352OAI: oai:DiVA.org:kth-223352DiVA, id: diva2:1183524
Note

QC 20180411

Available from: 2018-02-17 Created: 2018-02-17 Last updated: 2018-04-11Bibliographically approved
In thesis
1. Mining Big and Fast Data: Algorithms and Optimizations for Real-Time Data Processing
Open this publication in new window or tab >>Mining Big and Fast Data: Algorithms and Optimizations for Real-Time Data Processing
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2018. p. 42
Series
TRITA-EECS-AVL ; 2018:27
Keywords
Stream Processing, Load Balancing, Fully Dynamic Graphs, Real-Time Data Processing, Top-k Densest Subgraph, Frequent Subgraph Mining
National Category
Computer Systems
Research subject
Information and Communication Technology; Computer Science
Identifiers
urn:nbn:se:kth:diva-225487 (URN)978-91-7729-729-1 (ISBN)
Public defence
2018-05-07, Sal B, Electrum building, Kistagången 16, Stockholm, 09:00 (English)
Opponent
Supervisors
Note

QC 20180409

Available from: 2018-04-09 Created: 2018-04-05 Last updated: 2018-04-10Bibliographically approved

Open Access in DiVA

ICDCS2018(570 kB)3 downloads
File information
File name FULLTEXT01.pdfFile size 570 kBChecksum SHA-512
998a47cae755d2d5ba446232631c7402a2c63ab9fd09e18f3caa6105541c584b2e32c985b2416159d64196fda1300318aae829e415e4501642d6fc88e8bf3bfb
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Nasir, Muhammad Anis UddinGirdzijauskas, Sarunas
By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 3 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 12 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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