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

Fingerprint

Elasticity
Servers
Processing
Engines
Experiments

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Networks and Communications

Cite this

Pundir, M., Kumar, M., Leslie, L. M., Gupta, I., & Campbell, R. H. (2016). Supporting on-demand elasticity in distributed graph processing. In Proceedings - 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 (pp. 12-21). [7484159] (Proceedings - 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). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IC2E.2016.31

Supporting on-demand elasticity in distributed graph processing. / Pundir, Mayank; Kumar, Manoj; Leslie, Luke M.; Gupta, Indranil; Campbell, R H.

Proceedings - 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. Institute of Electrical and Electronics Engineers Inc., 2016. p. 12-21 7484159 (Proceedings - 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).

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

Pundir, M, Kumar, M, Leslie, LM, Gupta, I & Campbell, RH 2016, Supporting on-demand elasticity in distributed graph processing. in Proceedings - 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., 7484159, Proceedings - 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, Institute of Electrical and Electronics Engineers Inc., pp. 12-21, 4th IEEE Annual International Conference on Cloud Engineering, IC2E 2016, Berlin, Germany, 4/4/16. https://doi.org/10.1109/IC2E.2016.31
Pundir M, Kumar M, Leslie LM, Gupta I, Campbell RH. Supporting on-demand elasticity in distributed graph processing. In Proceedings - 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. Institute of Electrical and Electronics Engineers Inc. 2016. p. 12-21. 7484159. (Proceedings - 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). https://doi.org/10.1109/IC2E.2016.31
Pundir, Mayank ; Kumar, Manoj ; Leslie, Luke M. ; Gupta, Indranil ; Campbell, R H. / Supporting on-demand elasticity in distributed graph processing. Proceedings - 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. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 12-21 (Proceedings - 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).
@inproceedings{3792a212135145718d9e8be2329f4912,
title = "Supporting on-demand elasticity in distributed graph processing",
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.",
author = "Mayank Pundir and Manoj Kumar and Leslie, {Luke M.} and Indranil Gupta and Campbell, {R H}",
year = "2016",
month = "6",
day = "1",
doi = "10.1109/IC2E.2016.31",
language = "English (US)",
series = "Proceedings - 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",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "12--21",
booktitle = "Proceedings - 2016 IEEE International Conference on Cloud Engineering, IC2E 2016",
address = "United States",

}

TY - GEN

T1 - Supporting on-demand elasticity in distributed graph processing

AU - Pundir, Mayank

AU - Kumar, Manoj

AU - Leslie, Luke M.

AU - Gupta, Indranil

AU - Campbell, R H

PY - 2016/6/1

Y1 - 2016/6/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84978062212&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84978062212&partnerID=8YFLogxK

U2 - 10.1109/IC2E.2016.31

DO - 10.1109/IC2E.2016.31

M3 - Conference contribution

AN - SCOPUS:84978062212

T3 - Proceedings - 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

SP - 12

EP - 21

BT - Proceedings - 2016 IEEE International Conference on Cloud Engineering, IC2E 2016

PB - Institute of Electrical and Electronics Engineers Inc.

ER -