Supporting on-demand elasticity in distributed graph processing

Mayank Pundir, Manoj Kumar, Luke M. Leslie, Indranil Gupta, R H Campbell

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

While distributed graph processing engines have become popular for processing large graphs, these engines are typically configured with a static set of servers in the cluster. In other words, they lack the flexibility to scale-out or scale-in the number of servers, when requested to do so by the user. In this paper, we propose the first techniques to make distributed graph processing truly elastic. While supporting on-demand scale-out/in operations, we meet three goals: i) perform scale-out/in without interrupting the graph computation, ii) minimize the background network overhead involved in the scale-out/in, and iii) mitigate stragglers by maintaining load balance across servers. We present and analyze two techniques called Contiguous Vertex Repartitioning (CVR) and Ring-based Vertex Repartitioning (RVR) to address these goals. We implement our techniques in the LFGraph distributed graph processing system, and incorporate several systems optimizations. Experiments performed with multiple graph benchmark applications on a real graph indicate that our techniques perform within 9% and 21% of the optimum for scale-out and scale-in operations, respectively.

Original languageEnglish (US)
Title of host publicationProceedings - 2016 IEEE International Conference on Cloud Engineering, IC2E 2016
Subtitle of host publicationCo-located with the 1st IEEE International Conference on Internet-of-Things Design and Implementation, IoTDI 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages12-21
Number of pages10
ISBN (Electronic)9781509019618
DOIs
StatePublished - Jun 1 2016
Event4th IEEE Annual International Conference on Cloud Engineering, IC2E 2016 - Berlin, Germany
Duration: Apr 4 2016Apr 8 2016

Publication series

NameProceedings - 2016 IEEE International Conference on Cloud Engineering, IC2E 2016: Co-located with the 1st IEEE International Conference on Internet-of-Things Design and Implementation, IoTDI 2016

Other

Other4th IEEE Annual International Conference on Cloud Engineering, IC2E 2016
CountryGermany
CityBerlin
Period4/4/164/8/16

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Supporting on-demand elasticity in distributed graph processing'. Together they form a unique fingerprint.

Cite this