FlowFlex: Malleable Scheduling for Flows of MapReduce Jobs

Abstract : We introduce FlowFlex, a highly generic and effective scheduler for flows of MapReduce jobs connected by precedence constraints. Such a flow can result, for example, from a single user-level Pig, Hive or Jaql query. Each flow is associated with an arbitrary function describing the cost incurred in completing the flow at a particular time. The overall objective is to minimize either the total cost (minisum) or the maximum cost (minimax) of the flows. Our contributions are both theoretical and practical. Theoretically, we advance the state of the art in malleable parallel scheduling with precedence constraints. We employ resource augmentation analysis to provide bicriteria approximation algorithms for both minisum and minimax objective functions. As corollaries, we obtain approximation algorithms for total weighted completion time (and thus average completion time and average stretch), and for maximum weighted completion time (and thus makespan and maximum stretch). Practically, the average case performance of the FlowFlex scheduler is excellent, significantly better than other approaches. Specifically, we demonstrate via extensive experiments the overall performance of FlowFlex relative to optimal and also relative to other, standard MapReduce scheduling schemes. All told, FlowFlex dramatically extends the capabilities of the earlier Flex scheduler for singleton MapReduce jobs while simultaneously providing a solid theoretical foundation for both.
Type de document :
Communication dans un congrès
David Hutchison; Takeo Kanade; Madhu Sudan; Demetri Terzopoulos; Doug Tygar; Moshe Y. Vardi; Gerhard Weikum; David Eyers; Karsten Schwan; Josef Kittler; Jon M. Kleinberg; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan; Bernhard Steffen. 14th International Middleware Conference (Middleware), Dec 2013, Beijing, China. Springer, Lecture Notes in Computer Science, LNCS-8275, pp.103-122, 2013, Middleware 2013. 〈10.1007/978-3-642-45065-5_6〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01480794
Contributeur : Hal Ifip <>
Soumis le : mercredi 1 mars 2017 - 17:33:30
Dernière modification le : jeudi 2 mars 2017 - 10:18:42
Document(s) archivé(s) le : mardi 30 mai 2017 - 18:18:35

Fichier

978-3-642-45065-5_6_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Viswanath Nagarajan, Joel Wolf, Andrey Balmin, Kirsten Hildrum. FlowFlex: Malleable Scheduling for Flows of MapReduce Jobs. David Hutchison; Takeo Kanade; Madhu Sudan; Demetri Terzopoulos; Doug Tygar; Moshe Y. Vardi; Gerhard Weikum; David Eyers; Karsten Schwan; Josef Kittler; Jon M. Kleinberg; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan; Bernhard Steffen. 14th International Middleware Conference (Middleware), Dec 2013, Beijing, China. Springer, Lecture Notes in Computer Science, LNCS-8275, pp.103-122, 2013, Middleware 2013. 〈10.1007/978-3-642-45065-5_6〉. 〈hal-01480794〉

Partager

Métriques

Consultations de la notice

31

Téléchargements de fichiers

33