Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

HAL Id: hal-01329731 https://hal.archives-ouvertes.fr/hal-01329731 Submitted on

HAL Id: hal-01329731 https://hal.archives-ouvertes.fr/hal-01329731 Submitted on 9 Jun 2016 HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci- entific research documents, whether they are pub- lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. Problème d’ordonnancement dans Hadoop, ordonnancement sur des machines parallèles équivalentes et distribuées Aymen Jlassi, Patrick Martineau To cite this version: Aymen Jlassi, Patrick Martineau. Problème d’ordonnancement dans Hadoop, ordonnancement sur des machines parallèles équivalentes et distribuées. Conférence d’informatique en Parallélisme, Archi- tecture et Système (Compas’2016), Jul 2016, Lorient, France. hal-01329731 Compas’2016 : Parallélisme / Architecture / Système Lorient, France, du 5 au 8 juillet 2016 Problème d’ordonnancement dans Hadoop, ordonnancement sur des machines parallèles équivalentes et distribuées Aymen Jlassi ♦, Patrick Martineau♦ Université François-Rabelais de Tours,♦ CNRS, LI EA 6300, OC ERL CNRS 6305, Tours, France 64 Avenue Jean de Portalis, 37200 Tours - France {aymen.jlassi, patrick.martineau}@univ-tours.fr Résumé Les outils de gestion de gros volumes de données sont connus pour leur capacité à exécuter un grand nombre de travaux sur des volumes de données énormes (de l’ordre de plusieurs Pétaoc- tets). De ce fait, ces outils utilisent de grandes infrastructures capables de fournir la puissance de calcul demandée de manière à effectuer les traitements dans un temps raisonnable. Dans ce papier, on s’intéresse à l’amélioration des performances du logiciel "Hadoop", le logi- ciel libre de référence dans l’univers des logiciels de traitement de gros volumes de données. Dans une première partie, on modélise le problème d’ordonnancement à l’aide de la program- mation linéaire, on évalue le modèle et on calcule ainsi une borne inférieure pour la version hors ligne du problème. On propose une heuristique et on évalue la solution qu’on propose sur des instances de taille moyenne. Mots-clés : Architecture parallèle et distribuée, Ordonnancement, Grid & Clouds 1. Introduction Suite à la publication des travaux de recherche chez Google en 2004 : la présentation du mo- dèle MapReduce [2] et les fondements d’un système de ﬁchier distribué GFS, Yahoo ! a créé Hadoop, un logiciel libre capable de traiter des énormes quantités de données et de répondre aux besoins de plusieurs entreprises. Hadoop est basé sur une architecture client-serveur, l’uti- lisateur soumet les travaux au serveur et ce dernier s’occupe de leur ordonnancement sur la grappe. De nos jours, Facebook, General motors, Orange et beaucoup d’autres entreprises uti- lisent Hadoop dans leurs centres de données. Notre objectif est l’optimisation des performances de Hadoop en améliorant la politique d’or- donnancement des travaux sur la grappe. Il existe plusieurs références bibliographiques abor- dant le problème d’ordonnancement des travaux Map/Reduce dans le contexte du logiciel Hadoop. Le premier ordonnanceur dans Hadoop est FIFO (premier arrivé premier servi), cet ordonnanceur exécute les travaux dans l’ordre de leur soumission. "Fair" [7], "capacity" [3] et "Dynamic Priority scheduler" [6] sont des ordonnanceurs hiérarchiques constitués de plusieurs niveaux de ﬁles d’attente avec des priorités entre elles. "Fair" résout le problème de famine ren- contré en utilisant FIFO et "Capacity" gère davantage l’hiérarchie de ﬁles d’attente que "Fair". Compas’2016 : Parallélisme / Architecture / Système Lorient, France, du 5 au 8 juillet 2016 Pour plus de détails concernant les travaux de recherche abordant l’ordonnancement dans Ha- doop, les papiers [5], [1] et [4] synthétisent la plupart de ces travaux. On déﬁnit le problème d’ordonnancement dans Hadoop comme suit : on considère une grappe constituée de M machines. Chaque machine Mj est caractérisée par (1) un ensemble de slots ms j dont mSm j slots qui exécutent des tâches Map et mSr j slots qui exécutent des tâches Reduce, (2) une capacité mr j de mémoire (RAM) et une quantité mh j de disque dur (3) une fréquence de calcul vj de chaque slot. On considère un ensemble de travaux W de types Map / Reduce et un ensemble de blocs de données noté Ab. Un travail est un ensemble de tâches Map et de tâches Reduce. Ces travaux sont décomposés en un ensemble de N(= Nm + Nr) tâches (composés de deux sous ensembles : Lm tâches Map et Lr tâches Reduce) dont Nm(= card(Lm)) tâches Map et Nr(= card(Lr)) tâches Reduce. Chaque tâche T w′ i est associée à un travail w′ ∈W et sa durée d’exécution est notée pi. On note bi,i′ la bande passante réservée pour assurer l’échange des données entre deux tâches T w′ i et T w′ i′ qui s’exécutent sur deux machines différentes. Pour chaque tâche T w′ i , on considère Ei l’ensemble des np i tâches qui doivent s’exécuter avant la tâche T w′ i . Lorsque la tâche T w′ i s’exécute, elle nécessite une quantité nr i de RAM, une quantité nh i de disque dur, un slot et traite un ensemble Bi de données divisées en nb i ⩾1 blocs lus sur le système de ﬁchiers. Dans la version actuelle du logiciel, une tâche Map dans Hadoop effectue des traitements sur un seul bloc de données [8]. Tous les blocs de données ont la même taille S. On note rb le nombre de réplications d’un bloc b. Db est alors l’ensemble des machines qui contiennent le bloc b et bwd la bande passante allouée pour migrer un bloc d’une machine à une autre, si nécessaire. L’architecture de la grappe est modélisée par un graphe G = (V, E) où l’ensemble des nœuds V présente les machines et l’ensemble des arcs E présente les liaisons ﬁ- laires entre elles. On considère P l’ensemble des chemins entre les machines, Pu est l’ensemble des couples de machines qui utilisent l’arc u. Chaque chemin est composé de plusieurs arcs eu ∈E dont la capacité maximale de bande passante bwd est identique pour tous les arcs. On note T l’horizon de temps nécessaire pour l’ordonnancement des tâches sur les machines en tenant compte de la gestion des ressources. On cherche à minimiser la somme des dates de ﬁns des exécutions des travaux. Dans une première partie, on traite le problème dans sa version hors ligne, on le modélise ma- thématiquement, on évalue le modèle et on calcule une borne inférieure. Dans une deuxième étape, on propose une heuristique de résolution et on l’évalue par rapport à la borne inférieure trouvée précédemment. 2. Modélisation mathématique du problème Dans cette partie, on présente une formulation mathématique basée sur la programmation li- néaire, indexée par le temps du problème d’ordonnancement. Les variables du modèle sont présentées dans (1), (2), (3), (4) et (5). xj,s i,t = 1 si la tâche i est exécutée sur le slot s de la machine j à l’instant (t, t+1 ] (1) 0 Sinon yj,j ′ b,t =    1 si le bloc b est sur la machine j à l’instant (t, t + 1] après une migration (2) de la machine j’ avant l’instant t 0 Sinon uj,j ′ b,t =    1 si le bloc b est en cours de migration de la machine j vers la machine j’ (3) à l’instant (t, t+1 ] 0 Sinon Compas’2016 : Parallélisme / Architecture / Système Lorient, France, du 5 au 8 juillet 2016 zj,j ′ l,l ′,t =    1 si la tâche Map l’ a terminé son exécution à l’instant t sur la machine j’ (4) et la tâche l est exécutée sur la machine j après l’instant t 0 Sinon Cw ′ = t, ∀w′ = 1...W, t ∈[1..T] : Date de ﬁn d’exécution de la dernière tâche du travail w’. (5) On cherche à minimiser la somme des dates de ﬁn des différents travaux soumis. La fonction objective est : MinimizeObj = W X w ′=1 Cw ′ On a quatre types de contraintes : Les contraintes de ressources : La contrainte (6) suppose qu’à chaque instant, la quantité de mémoire consommée par les tâches qui s’exécutent sur une machine j ne dépasse pas la quan- tité de mémoire sur la machine. Les contraintes (7) et (8) imposent qu’un slot (coeur virtuel) ne puisse exécuter qu’une seule tâche à la fois. La contrainte (9) contrôle l’utilisation du disque dur. À chaque instant, la somme de la quantité du disque dur (HDD) utilisée par les tâches et la quantité de HDD utilisée pour l’enregistrement et la migration des données ne doivent pas dépasser la quantité disponible sur la machine. Les contraintes reliées à l’exécution des tâches : La contrainte (10) sert à déﬁnir la date de ﬁn de la dernière tâche de chaque travail. La contrainte (11) déﬁnit la relation de précédence entre les tâches. Les contraintes (??) et (15) déﬁnissent les durées des tâches "Map" et "Reduce". Les contraintes (12) et (16) imposent qu’à chaque instant, une tâche "Map" ou "Reduce" ne puisse s’exécuter que sur un seul slot. Les uploads/Management/ aymen-jlassi-compas2016.pdf