Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Context-Aware Usage Prediction Approach for Smartphone Applications Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Towards Truly Elastic Distributed Graph Computing in the Cloud

Authors : Lu Lu, Xuanhua Shi, Hai Jin

Published in: Advances in Services Computing

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Elasticity is very important to the scale-out distributed systems running on today’s large-scale multi-tenant clouds, regardless public or private. An elastic distributed data processing system must have the capability of: (1) dynamically balancing the computing load among workers due to their performance heterogeneity and dynamicity; (2) fast recovering the lost memory state of failure workers with acceptable overheads during the regular execution.
Unfortunately, we found that the design of the state-of-the-art distributed graph computing system only works well in small sized dedicated clusters. We implement a distributed graph computing prototype, X-Graph, and demonstrate the capabilities of being elastic in three ways. First, we present menger, a novel two-level graph partition framework, which further splits one worker-level partition into several sub-partitions as the basic migration units, and each has the “migration affinity” with one of the other workers. Second, we implement a dynamical load balancer based on menger, which prefers the worker that has the affinity of the sub-partition to be migrated as the destination, and completely avoids the costly sophistical graph re-partitioning algorithms. Third, we implement a differentiated replication frame-work, which supports parallel recovery for lost partitions just like general-purpose dataflow systems.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Social Aware Mobile Payment Service Popularity Analysis: The Case of WeChat Payment in China
Literature
1.
2.
3.
4.
Ahmad, F., Chakradhar, S., Raghunathan, A., Vijaykumar, T.N.: Tarazu: optimizing mapreduce on heterogeneous clusters. In: ASPLOS 2012, pp. 61–74 (2012)
5.
Chen, R., Weng, X., He, B., Yang, M., Choi, B., Li, X.: Improving large graph processing on partitioned graphs in the cloud. In: SoCC 2012, p. 3 (2012)
6.
Cipar, J., Ho, Q., Kim, J.K., Lee, S., Ganger, G.R., Gibson, G.: Solving the straggler problem with bounded staleness. In: HotOS 2013 (2013)
7.
Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51, 107–113 (2008)CrossRef
8.
Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., Guestrin, C.: PowerGraph: distributed graph-parallel computation on natural graphs. In: OSDI 2012, p. 2 (2012)
9.
Hendrickson, B., Devine, K.: Dynamic load balancing in computational mechanics. Comput. Methods Appl. Mech. Eng. 184, 485–500 (2000)CrossRefMATH
10.
Hindman, B., Konwinski, A., Zaharia, M., Ghodsi, A., Joseph, A.D., Katz, R., Shenker, S., Stoica, I.: Mesos: a platform for fine-grained resource sharing in the data center. In: NSDI 2011, p. 22 (2011)
11.
Khayyat, Z., Awara, K., Alonazi, A.: Mizan: a system for dynamic load balancing in large-scale graph processing. In: EuroSys 2013, pp. 169–182 (2013)
12.
Kumar, V., Vavilapallih, Murihyh, A.C., Douglasm, C., Agarwali, S., Konarh, M., Evansy, R., Gravesy, T., Lowey, J., Shahh, H., Sethh, S., Sahah, B., Curinom, C., Omaleyh, O., Radiah, S.: Apache hadoop YARN: yet another resource negotiator. In: SoCC 2013, p. 5 (2013)
13.
Kyrola, A., Blelloch, G., Guestrin, C.: GraphChi: large-scale graph computation on just a pc. In: OSDI 2012, pp. 31–46 (2012)
14.
Low, Y., Gonzalez, J., Kyrola, A., Bickon, D., Guestrin, C., Hellersten, J.M.: GraphLab: a new framework for parallel machine learning. In: UAI 2010 (2010)
15.
Low, Y., Gonzalez, J., Kyrola, A., Bickon, D., Guestrin, C., Hellersten, J.M.: Distributed GraphLab: a framework for machine learning in the cloud. In: PVLDB 2012, pp. 716–727 (2012)
16.
Malewicz, G., Austern, M.H., L., Hundt, R.: Whare-Map: heterogeneity in homogeneous warehouse-scale computers. In: ISCA 2013, pp. 619–630 (2013)
17.
Nguyen, D., Lenharth, A., Pingali, K.: A lightweight infrastructure for graph analytics. In: SOSP 2013, pp. 456–471 (2013)
18.
Power, R., Li, J.: Piccolo: building fast, distributed programs with partitioned tables. In: OSDI 2010, pp. 1–14 (2010)
19.
Roy, A., Mihailovic, I., Zwaenpoel, W.: X-Stream: edge-centric graph processing using streaming partitions. In: SOSP 2013, pp. 472–488 (2013)
20.
Salihoglu, S., Widom, J.: GPS: a graph processing system. In: SSDBM 2013, p. 8 (2013)
21.
Schwarzkopf, M., Konwinski, A., Abdelmalek, M., Wilkes, J.: Omega: flexible, scalable schedulers for large compute clusters. In: EuroSys 2013, pp. 351–364 (2013)
22.
Stanton, I., Kliot, G.: Streaming graph partitioning for large distributed graphs. In: KDD 2012, pp. 1222–1230 (2012)
23.
Yu, Y., Isard, M., Fetterly, D., Budiu, M., Lfarer-Lingsson, Kumar, P., Currey, G.J.: DryadLINQ: a system for general-purpose distributed data-parallel computing using a high-level language. In: OSDI 2008, pp. 1–14 (2008)
24.
Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J., Mccauley, M., Frankin, M.J., Shenker, S., Stoca, I.: Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing. In: NSDI 2012 (2012)
25.
Zhang, X., Tune, E., Hagmann, R., Jnagal, R., Gokhale, V., Wilkes, J.: CPI2: CPU performance isolation for shared compute cluster. In: EuroSys 2013, pp. 379–391 (2013)
Metadata
Title
Towards Truly Elastic Distributed Graph Computing in the Cloud
Authors
Lu Lu
Xuanhua Shi
Hai Jin
Copyright Year
2015
Book
Advances in Services Computing

Print ISBN: 978-3-319-26978-8

Electronic ISBN: 978-3-319-26979-5

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-26979-5_23

Premium Partner

    Image Credits