Un service de recouvrement arri`ere pour la grille 

Télécharger le fichier pdf d’un mémoire de fin d’études

Un environnement d’ex´ecution hautement dynamique

Une grille de calcul est un environnement d’ex´ecution hautement dynamique en raison de la volatilit´e des nœuds qui la composent. Nous caract´erisons maintenant cette volatilit´e et mettons en ´evidence les besoins en tol´erance aux fautes.
Plusieurs situations peuvent entraˆıner des connections et d´econnections volontaires. Tout d’abord, le propri´etaire de ressources peut `a tout moment d´ecider de les retirer de la grille pour en faire un usage exclusif. Ce cas est tr`es fr´equent pour des nœuds dont les ressources sont exploit´ees par la grille en p´eriode d’inactivit´e, comme dans les grilles de calcul pair `a pair ou dans les r´eseaux de stations de travail. De la mˆeme mani`ere, une institution peut temporairement retirer ses ressources de la grille pour ex´ecuter des tˆaches prioritaires. Dans le cadre d’op´erations de maintenance, comme des mises `a jour mat´erielles ou logicielles, les nœuds peuvent aussi temporairement ˆetre d´econnect´es de la grille.
La seconde source de volatilit´e est l’occurrence de d´efaillances mat´erielles. Le temps moyen entre deux d´efaillances ou MTBF 2 caract´erise la fr´equence des d´efaillances dans un syst`eme. Etant donn´e le nombre de ressource composant une grille de calcul, la fr´equence des d´efaillances y est elev´ee. En g´en´eral, lors de l’achat de mat´eriel informatique, celui-ci est garanti trois ans. On peut donc supposer qu’au-del`a de trois ans, le risque de subir une d´efaillance devient grand. Dans le cas d’une grille compos´ee de 25000 nœuds, cela signifie que le MTBF serait environ de un jour.
Ce calcul simple n’a pas pour but d’ˆetre pr´ecis. En effet, il est suppos´e ici que la probabilit´e de d´efaillance est lin´eaire au cours du temps, ce qui est assez loin de la r´ealit´.
Cependant il met clairement en ´evidence l’importance du probl`eme des d´efaillances dans les syst`emes distribu´es de grande taille comme les grilles de calcul. Ces d´efaillances mat´erielles peuvent affecter un nœud de la grille ou le mat´eriel servant a` l’interconnexion des nœuds. Dans le second cas, ce sont tous les nœuds d´ependant de ce mat´eriel qui sont d´econnect´es de la grille.
Le probl`eme li´e aux d´econnections de nœuds est que des applications ou des services de la grille peuvent ˆetre en cours d’ex´ecution sur les nœuds se d´econnectant. Comme nous le d´ecrivons en d´etail dans la partie 1.2, la d´econnexion d’un nœud de la grille peut entraˆıner une perte d’information pour les applications ou services s’ex´ecutant sur ce nœud, et compromettre leurs bon fonctionnement.
Dans le cas de d´econnections volontaires, il peut ˆetre exig´e de demander une autori-sation de d´econnexion pr´ealablement. Dans ce cas, le syst`eme de grille est pr´evenu que la d´econnexion va avoir lieu et peut ex´ecuter les actions n´ecessaires pour ´eviter toute perte d’information, avant d’autoriser la d´econnexion. Cependant, si la d´econnexion est li´ee a` une d´efaillance, cette solution n’est pas applicable.
Si aucune mesure particuli`ere n’est prise pour traiter cet ´ev`enement, les ressources d’une grille de calcul deviennent inexploitables. En effet, en cas de d´efaillance d’un nœud o`u s’ex´ecute un ou plusieurs processus d’une application distribu´ee, la cons´equence peut ˆetre la d´efaillance de toute l’application distribu´ee. L’utilisateur n’obtient alors pas le r´esultat qu’il attendait. De plus, toutes les ressources consomm´ees par les autres processus de cette application distribu´ee, le sont inutilement. Si c’est un processus appartenant `a un service de grille qui s’ex´ecutait sur le nœud d´efaillant, ce service devient lui aussi d´efaillant. Si ce service est indispensable au bon fonctionnement du syst`eme de grille, ce sont toutes les ressources de la grille qui deviennent potentiellement inexploitables. C’est pourquoi nous avons besoins de m´ecanismes de tol´erance aux fautes pour ˆetre capables de traiter les cons´equences d’une d´econnexion subie.

La tol´erance aux fautes dans les syst`emes distribu´es

Dans cette section, nous pr´esentons la probl´ematique de la tol´erance aux fautes dans les syst`emes distribu´es et plus particuli`erement dans les grilles de calcul. Dans un premier temps, nous d´efinissons le vocabulaire utilis´e dans ce domaine. Puis nous pr´esentons le mod`ele de faute adapt´e au contexte des grilles de calcul. Enfin nous dressons un panorama des techniques de tol´erance aux fautes.

Faute, erreur et d´efaillance

Avant d’aller plus loin dans la r´eflexion sur la tol´erance aux fautes dans les grilles de calcul, il est important de d´efinir les termes et notions se rapportant `a ce domaine. Pour ce faire, nous nous appuyons sur les travaux pr´esent´es par Laprie [114].
La d´efaillance d’un syst`eme informatique se d´efinit par rapport au service qu’il fournit. La sp´ecification du service fourni par un syst`eme informatique est un accord entre les fournisseurs et les utilisateurs du syst`eme sur la description du comportement attendu pour ce syst`eme. Un comportement non conforme `a cette description est une d´efaillance du syst`eme.
D´efinition 1.17 (D´efaillance) Un syst`eme est d´efaillant quand son comportement ne suit pas sa sp´ecification.
D´efinition 1.18 (Erreur) Une erreur est un ´etat interne du syst`eme susceptible de provoquer une d´efaillance.
D´efinition 1.19 (Faute) Une faute est une action ou un ´ev`enement pouvant entraˆıner une erreur.
Il existe deux principales cat´egories de fautes : les fautes d’origine mat´erielle, par exemple un court-circuit ou une surchauffe, et les fautes d’origine humaine qui peuvent ˆetre li´ees `a une mauvaise conception du syst`eme ou `a une mauvaise action, effectu´ee par inadvertance ou volontaire, sur ce syst`eme.
Une erreur est la manifestation d’un point vue interne au syst`eme d’une faute et une d´efaillance la manifestation d’un point de vue externe au syst`eme d’une erreur. Il existe donc une relation de causalit´e entre faute, erreur et d´efaillance.
Un syst`eme complexe peut ˆetre vu comme un ensemble de sous-syst`emes le composant.
La d´efaillance d’un sous-syst`eme est alors une faute pour le syst`eme auquel il appartient.
Les notions de faute et de d´efaillance d´ependent donc du point de vue.
Prenons l’exemple, illustr´e par la figure 1.6, d’une application parall`ele ex´ecut´ee sur une grille de calcul. Cette application est compos´ee d’un ensemble de processus distribu´es sur des nœuds de la grille, qui doivent par moment communiquer entre eux pour ´echanger leurs donn´ees. Une faute mat´erielle se produit sur un nœud ex´ecutant un processus de l’application : un disque dur sur ce nœud est d´efaillant. Les donn´ees pr´esentes sur ce disque ne sont alors plus accessibles. Une tentative d’acc`es `a ces donn´ees par le processus va activer l’erreur et entraˆıner la d´efaillance du processus. Du point de vue de l’application parall`ele, la d´efaillance d’un processus est une faute cr´eant une erreur latente : on ne peut plus communiquer avec le processus fautif. Les autres processus de l’application peuvent continuer leur ex´ecution. Cependant lors de la prochaine phase de communication, l’erreur va ˆetre activ´ee car les processus non fautifs vont tenter de communiquer avec le processus fautif mais ne vont par r´eussir `a r´ecup´erer les donn´ees de ce processus n´ecessaires `a la poursuite de l’ex´ecution. L’application parall`ele ne peut pas terminer son ex´ecution et rendre le r´esultat attendu `a l’utilisateur : elle est d´efaillante.

Les fautes dans les grilles de calcul

Les mod`eles de fautes Plusieurs mod`eles de fautes sont d´ecrits dans la litt´erature. On peut en distinguer trois principaux : les fautes par arrˆet total, les fautes par omission et les fautes byzantines. Pour sp´ecifier ces mod`eles, nous consid´erons un syst`eme compos´e d’un ensemble de composants communiquant par messages.
D´efinition 1.20 (Faute par arrˆet total) Le composant fonctionne conform´ement a` sa sp´ecification jusqu’`a la faute par arrˆet total [85] o`u il s’arrˆete de fonctionner.
D´efinition 1.21 (Faute par omission) Lors d’une faute par omission [146], le com-posant peut oublier certains messages en ´emission ou en r´eception.
D´efinition 1.22 (Faute byzantine) Un composant au comportement byzantin [112] peut envoyer des messages qui ne suivent pas sa sp´ecification. Ceci inclut des comporte-ments malveillants.
Ces trois types de fautes couvrent l’ensemble du spectre des fautes pouvant intervenir dans un syst`eme informatique, une faute par arrˆet total ´etant le cas le plus simple et une faute byzantine ´etant le cas le plus complexe a` traiter. Il est important de choisir le mod`ele adapt´e au contexte d’´etude car plus le mod`ele de faute est complexe, plus les m´ecanismes a` employer pour traiter ces fautes sont coˆuteux.
Un mod`ele de faute pour la grille Comme nous l’avons vu pr´ec´edemment, ´etant donn´e l’´echelle des grilles de calcul, les risques de subir une d´efaillance mat´erielle sont elev´es. La d´efaillance d’une ressource physique a pour cons´equence la d´efaillance des pro-cessus li´es a` cette ressource, comme illustr´e par la figure 1.6. Du point du vue de l’appli-cation ou du service auquel appartient ce processus, une telle d´efaillance est une faute par arrˆet total.
Dans le cas d’une grappe de calcul, toutes les machines de la grappe sont regroup´ees dans le mˆeme lieu et d´ependent g´en´eralement du mˆeme syst`eme de refroidissement. La d´efaillance du syst`eme de refroidissement a alors pour cons´equence une surchauffe pour l’ensemble des machines de la grappe, qui doivent donc s’arrˆeter. On parle alors de d´efaillances corr´el´ees. Ce cas doit ˆetre pris en compte dans le contexte des grilles de calcul.
Les grilles de calcul sont compos´ees de nœuds et de liens d’interconnexion. Une faute par omission dans ce contexte serait li´ee `a la surcharge temporaire de certains liens d’in-terconnexion. Par exemple, en cas de congestion sur un switch celui-ci peut ˆetre amen´ `a ignorer certains paquets. Cependant nous consid´erons que les canaux de communications entre processus de la grille sont ´equitables.
D´efinition 1.23 (Canal de communication ´equitable) Si un canal de communica-tion entre deux processus non fautifs est ´equitable et si un message est ´emis une infinit´e de fois par un processus sur ce canal, un sous ensemble de ces messages est re¸cu par l’autre processus. De plus, un message doit avoir et´ ´emis par un processus pour pouvoir ˆetre re¸cu.
Cette deuxi`eme propri´et´ signifie que le canal de communication ne peut pas cr´eer de messages.
En mettant en place des m´ecanismes de r´e´emission de messages, des canaux de com-munication ´equitables peuvent ˆetre transform´es en canaux de communication fiables. Ces m´ecanismes sont g´en´eralement mis en œuvre au niveau des couches basses de la pile logi-cielle des protocoles de communication.
D´efinition 1.24 (Canal de communication fiable) Si un canal de communication entre deux processus non fautifs est fiable, un message ´emis par un processus sur ce canal est re¸cu par l’autre processus.
L’utilisation de num´eros de s´equence permet de mettre en œuvre des canaux de com-munication FIFO3 a` partir de canaux de communication fiables. Le protocole TCP [1], par exemple, offre ces propri´et´es.
Le mat´eriel servant `a l’interconnexion des ressources de la grille peut lui aussi subir des d´efaillances mat´erielles. Dans ce cas, il devient impossible de communiquer avec les nœuds d´ependant du mat´eriel d´efaillant. A nouveau, nous consid´erons qu’il s’agit d’une d´efaillance corr´el´ee par arrˆet total de ces nœuds.
Concevoir un syst`eme capable de supporter des fautes byzantines est important prin-cipalement si ce syst`eme peut faire l’objet d’attaques. Comme nous l’avons vu dans la section 1.1.1, le partage de ressources dans une grille de calcul se fait dans le cadre d’une organisation virtuelle. Celle-ci se mat´erialise par un contrat entre les membres composant l’organisation virtuelle, d´efinissant les comportements autoris´es au sein de cette organisa-tion virtuelle. De plus, l’utilisation d’un service dans la grille est r´egie par des accords sur la qualit´e de service (Service Level Agreement [116]) pass´es entre le service et ses utilisateurs, garantissant le comportement fourni par ce service. Enfin, des m´ecanismes d’authentifi-cation et d’autorisation [76] limitent les actions possibles pour les utilisateurs de la grille `a un cadre pr´ed´efini. Etant donn´e cet ensemble de garanties, nous ne consid´erons pas les fautes byzantines au cours de notre ´etude.

Fondements de la tol´erance aux fautes dans les syst`emes distribu´es

Les deux mani`eres de traiter les fautes dans un syst`eme sont d’utiliser des techniques permettant de pr´evenir les fautes ou des techniques permettant de traiter les cons´equences des fautes. La pr´evention des fautes (fault avoidance) inclut l’ensemble des techniques permettant de fournir du code fiable, i.e. qui ne contient pas d’erreurs. Cependant, il est impossible de pr´evenir toutes les fautes, et en particuliers les fautes mat´erielles, dans le cas d’un syst`eme de tr`es grande taille comme une grille de calcul. C’est pourquoi des m´ecanismes de tol´erance aux fautes, capables de traiter les cons´equences d’une faute sont n´ecessaires.
Pour pouvoir traiter les cons´equences d’une faute, il faut tout d’abord ˆetre capable de d´etecter cette faute, c’est-`a-dire ˆetre capable de d´etecter la d´efaillance `a l’origine de la faute. Avant de pr´esenter les principales techniques de tol´erance aux fautes existantes, nous faisons une courte introduction `a la probl´ematique des d´etecteurs de d´efaillance.
Les d´etecteurs de d´efaillance D´etecter les d´efaillances dans un syst`eme distribu´e asynchrone, i.e. un syst`eme o`u aucune hypoth`ese n’est faite sur le temps de transmis-sion des messages ou le temps de calcul des processeurs, est un probl`eme complexe. En effet, il est dans ce cas `a priori impossible de distinguer un processus tr`es lent d’un pro-cessus d´efaillant. Ce probl`eme est la raison de l’impossibilit´e d’une solution d´eterministe pour le consensus dans un syst`eme distribu´e asynchrone o`u un processus peut subir une d´efaillance [70]. Pour r´esoudre ce probl`eme, Chandra et Toueg [41] ont propos´e la notion de d´etecteur de d´efaillance non fiable.
Dans la r´ealit´e, il n’existe pas de syst`emes distribu´es compl`etement asynchrones. La plupart des syst`emes distribu´es se comporte de mani`ere quasi-synchrone, i.e. les d´elais dans le syst`eme sont born´es la plupart du temps, mˆeme s’ils peuvent avoir un comporte-ment asynchrone de temps en temps. Les d´etecteurs de d´efaillance non fiables cherchent `a exploiter cette propri´et´. En effet, un d´etecteur de d´efaillance non fiable est un oracle distribu´e qui fournit aux processus une vue approximative des d´efaillances dans le syst`eme au cours de l’ex´ecution : le d´etecteur de d´efaillance fournit une liste des processus sus-pect´es d’avoir subi une d´efaillance. Comme il est impossible de distinguer un processus lent d’un processus d´efaillant dans un syst`eme asynchrone, le d´etecteur de d´efaillance va faire des erreurs : il va suspecter des processus non fautifs et ne pas suspecter des processus fautifs. Les deux propri´et´es caract´erisant les d´etecteurs de d´efaillance sont la compl´etude et la pr´ecision. Parmi les huit classes de d´etecteurs de d´efaillance d´efinies par Chandra et Toueg, ⋄S est celui ayant les propri´et´es minimales pour r´esoudre le probl`eme du consensus : compl´etude forte et pr´ecision ultimement4 faible.
Propri´et´ 1.1 (Compl´etude forte) Tous les processus d´efaillants sont ultimement sus-pect´es par tous les processus non d´efaillants.
Propri´et´ 1.2 (Pr´ecision ultimement faible) Certains processus non d´efaillants ne sont ultimement jamais suspect´es par les processus non d´efaillants.
Si le syst`eme se comporte de mani`ere quasi-synchrone pendant suffisamment longtemps, le d´etecteur de d´efaillance peut fournir ces propri´et´es. Des travaux se sont int´eress´es a` la mise en œuvre de d´etecteurs de d´efaillance dans les grilles de calcul [19, 51]. La mise en œuvre de d´etecteurs de d´efaillance est hors du champ d’´etude de ce document.
Tol´erance aux fautes par duplication La d´efaillance d’un processus ou d’une ma-chine physique entraˆıne une perte d’informations, par exemple des donn´ees ou l’´etat du processus. Le seul moyen d’´eviter cette perte d’information est de dupliquer les donn´ees dans un endroit o`u elles ne seront pas alt´er´ees par la d´efaillance. Les techniques de tol´erance aux fautes dans les syst`emes distribu´es se fondent donc sur des techniques de duplication des informations.

Les techniques de tol´erance aux fautes

Nous pr´esentons maintenant les deux familles de techniques de tol´erance aux fautes existantes, i.e. les techniques de recouvrement arri`ere et les techniques de duplication. Nous d´ecrivons les propri´et´es de chacune d’entre elles, ainsi que les probl`emes techniques qu’elles soul`event. Puis nous ´etudions les cas d’utilisation de ces techniques.

Techniques de recouvrement arri`ere

Les techniques de recouvrement arri`ere se fondent sur la sauvegarde de points de reprise. D´efinition 1.25 (Point de reprise) Un point de reprise d’une application est un en-semble de donn´ees d´ecrivant l’´etat de l’application.
Des points de reprise de l’application sont enregistr´es sur un support de stockage stable durant l’ex´ecution de l’application pour pouvoir, en cas de d´efaillance, red´emarrer l’appli-cation a` partir d’un de ces points de reprise. Ainsi l’application ne red´emarre pas depuis z´ero apr`es une d´efaillance. Elle effectue un retour arri`ere dans l’´etat sauvegard´ dans un point de reprise. Definition 1.26 (Retour arri`ere) Un retour arri`ere correspond au red´emarrage de l’ap-plication depuis un ´etat ant´erieur a` l’´etat au moment de la d´efaillance.
D´efinition 1.27 (Stockage stable) Un support de stockage stable est une abstraction repr´esentant une solution de stockage de donn´ees assurant l’int´egrit´ et la disponibilit´e des donn´ees en d´epit des d´efaillances et fournissant des op´erations de lecture et d’´ecriture atomiques. La mani`ere de mettre en œuvre ce type de support d´epend du mod`ele de faute consid´er´ [105, 113].
Le cas le plus simple est celui d’une application mono-processus. Dans ce cas sauve-garder un point de reprise de l’application se r´esume `a sauvegarder les informations n´ecessaires au red´emarrage du processus. Ceci peut ˆetre fait en collaboration avec l’ap-plication si celle-ci a et´ con¸cue pour pouvoir le faire. Dans ce cas, c’est l’application qui d´etermine l’ensemble des informations n´ecessaires `a son red´emarrage.
La solution alternative consiste `a utiliser un outil ext´rieur `a l’application pour sauveg-arder les points de reprise [99, 108]. Ce type de solutions transparentes pour l’application, a l’avantage de simplifier le travail du concepteur de l’application et de fournir une solution de sauvegarde de points de reprise `a des applications qui n’ont pas initialement et´ con¸cues dans ce but. Le principe est alors de sauvegarder l’image du processus du point de vue du syst`eme d’exploitation (m´emoire, registres, etc.) pour ˆetre capable de le red´emarrer plus tard. Il n’est dans ce cas pas n´ecessaire d’avoir connaissance du fonctionnement interne de l’application.
Applications distribu´ees Pour les applications distribu´ees, la sauvegarde de points de reprise est une tˆache plus complexe car les communications entre les processus de l’application cr´eent des d´ependances entre eux. Il faut, apr`es une d´efaillance, ˆetre capable de r´etablir l’application dans un ´etat global coh´erent.
D´efinition 1.28 (Etat global coh´erent) Un ´etat global coh´erent d’une application apr`es une d´efaillance est un ´etat qui aurait pu ˆetre observ´e durant l’ex´ecution normale de l’application [42].
Le probl`eme des d´ependances entre processus est illustr´e par la figure 1.7. Dans cet exemple, nous ´etudions l’´etat global form´e par les points de reprise de trois processus d’une application distribu´ee. Imaginons que ces trois processus subissent une d´efaillance et red´emarrent depuis leur dernier point de reprise. Dans le cas de la figure 1.7(b), l’´etat courant du processus p1 refl`ete la r´eception du message m0 alors que l’´etat du processus p0 ne refl`ete pas son ´emission. p1 est un processus orphelin.
D´efinition 1.29 (Processus orphelin) Un processus orphelin est un processus dont l’´etat d´epend d’un message qui n’a pas et´ envoy´. Par extension, nous appelons message orphelin, le message a` l’origine de la cr´eation du processus orphelin.
En fait, le processus ´emetteur du message a fait un retour arri`ere dans un ´etat pr´ec´edent l’´emission de ce message. Le probl`eme est qu’il est a` priori impossible de d´eterminer si le processus va ´emettre le mˆeme message lors de sa r´eex´ecution, des ´ev`enements ext´erieurs comme la r´eception de nouveaux messages pouvant modifier son comportement. Apr`es une d´efaillance, il faut donc r´etablir l’application dans un ´etat sans processus orphelin.

Cout

Comme nous l’avons vu dans le chapitre 1, la tol´erance aux fautes se fonde sur de la duplication, et est donc consommatrice de ressources. Cependant les ressources agr´eg´ees dans une grille de calcul doivent en priorit´e servir `a l’ex´ecution des applications des util-isateurs. Il faut donc tenter de r´eduire au maximum les ressources consomm´ees par les m´ecanismes de tol´erance aux fautes.
Plus le niveau de disponibilit´e offert par une solution de tol´erance aux fautes est grand, plus elle est coˆuteuse en terme de ressources consomm´ees. Le probl`eme `a r´esoudre est donc de trouver le bon compromis permettant d’offrir de bonnes performances aux utilisateurs tout en r´epondant aux besoins de fiabilit´e et de simplicit´e d’utilisation.

Analyse des contraintes li´ees aux grilles de calcul

Nous pr´esentons maintenant les contraintes li´ees aux caract´eristiques des grilles de calcul que nous devons prendre en compte.

Volatilite

La volatilit´e des nœuds de la grille est caus´ee par les connexions et d´econnexions volontaires, et par les d´efaillances affectant l’infrastructure de grille. Les connexions de nouveaux nœuds ne mettent pas en danger la terminaison des applications s’ex´ecutant sur la grille. Cependant, si aucun m´ecanisme n’est pr´evu pour traiter le cas de la d´econnexion volontaire d’un nœud, celle-ci doit alors ˆetre consid´er´e comme la d´efaillance du nœud. En effet, le r´esultat est le mˆeme puisque dans les deux cas, les processus s’ex´ecutant sur ce nœud sont perdus.
Pour optimiser les performances des applications sur la grille, l’allocation de ressources prend g´en´eralement en compte l’h´et´erog´en´eit´ de la grille notamment pour ce qui concerne les liens d’interconnexion. Pour optimiser les performances d’une application parall`ele par exemple, il est pr´ef´erable d’avoir une latence faible et une bande passante elev´ee entre les nœuds sur lesquels elle s’ex´ecute. Ceci peut par exemple amener `a s´electionner plusieurs nœuds d’une mˆeme grappe de calcul pour ex´ecuter une application donn´ee. Dans ce cas, l’application peut subir la d´efaillance corr´el´ee de plusieurs nœuds. Il faut donc que les m´ecanismes de tol´erance aux fautes soient capables de traiter ce cas.

Passage `a l’´echelle

La taille d’une grille de calcul peut aller jusqu’`a plusieurs dizaines de milliers de ressources. Elle permet d’ex´ecuter des applications distribu´ees compos´ees de milliers de processus. Les solutions de tol´erance aux fautes que nous proposons doivent donc passer `a l’´echelle. Cela signifie qu’elles doivent offrir de bonnes performances mˆeme pour des applications de grande taille.
En outre, plus le nombre de nœuds sur lesquels s’ex´ecute les processus d’une application est elev´e, plus la probabilit´e de d´efaillances est grande. Les solutions de tol´erance aux fautes que nous proposons doivent donc ˆetre adapt´ees `a des fr´equences de d´efaillances elev´ees.

H´et´erog´en´eit´

Dans le chapitre 1, nous avons vu qu’une grille de calcul peut ˆetre compos´ee de ressources h´et´erog`enes comme des ordinateurs personnels et des grappes de calcul. Cette h´et´erog´en´eit´ peut aussi se retrouver dans le logiciel. Il est par exemple fort probable que des ressources appartenant `a des domaines d’administration diff´erents ne soient pas equip´ees des mˆemes logiciels. Cependant, des applications peuvent ˆetre distribu´ees sur ces ressources h´et´erog`enes. Il faut alors ˆetre capable d’assurer l’ex´ecution fiable de ces applications en prenant en compte cette h´et´erog´en´eit´.
Cette h´et´erog´en´eit´ se retrouve aussi dans la vari´et´e des applications qui peuvent ˆetre ex´ecut´ees sur une grille de calcul. Ces applications peuvent avoir des caract´eristiques et des besoins en tol´erance aux fautes diff´erents. C’est pourquoi il est souhaitable de proposer des solutions de tol´erance aux fautes g´en´eriques, capables de s’adapter `a la vari´et´ des besoins.

Approche proposee

L’objectif principal auquel tente de r´epondre cette th`ese est d’assurer l’ex´ecution fiable sur grille de calcul d’applications de calcul haute performance. Pour atteindre cet objectif, nous proposons un ensemble de solutions qui peuvent ˆetre regroup´ees autour de trois axes principaux :
– Un service de recouvrement arri`ere pour assurer le red´emarrage automatique des applications d´efaillantes.
– Un cadre pour mettre en œuvre des services de grille hautement disponibles et auto-r´eparants.
– Un protocole de recouvrement arri`ere passant a` l’´echelle pour les applications a` ´echange de messages.
Nous d´ecrivons dans la suite de ce paragraphe, les contributions associ´ees `a chacun de ces axes.

Un service de recouvrement arri`ere pour applications distribu´ees

Pour assurer que les applications ex´ecut´ees sur une grille se terminent correcte-ment, il faut ˆetre capable de red´emarrer celles dont l’ex´ecution est interrompue par une d´efaillance dans l’infrastructure sous-jacente. Telle est la mission de notre service de re-couvrement arri`ere, nomm´e XtreemGCP [127] et con¸cu dans le cadre du projet europ´een XtreemOS [204].
Pour simplifier l’utilisation de la grille, l’utilisateur doit pouvoir ˆetre d´echarg´ compl`etement de la gestion des d´efaillances. Il est admis que les techniques de recouvrement arri`ere sont les plus adapt´ees pour la tol´erance aux fautes d’applications de calcul haute performance. Un service de recouvrement arri`ere pour grille de calcul doit pouvoir red´emarrer automatiquement les applications d´efaillantes. Il doit de plus ˆetre ca-pable de s’adapter a` la vari´et´ des caract´eristiques des applications et a` l’h´et´erog´en´eit´ des ressources sur lesquelles elles s’ex´ecutent. Enfin, dans la perspective de simplifier l’u-tilisation de la grille, il est souhaitable qu’il puisse fournir des m´ecanismes de tol´erance aux fautes transparents pour les applications qui n’ont pas et´ con¸cues pour tol´erer les d´efaillances.
Pour assurer le red´emarrage automatique des applications, XtreemGCP prend en charge les interactions n´ecessaires avec les services du syst`eme de grille. Dans le cadre du syst`eme XtreemOS, ceci inclut des interactions avec le service de gestion des travaux [47] pour obtenir les ressources n´ecessaires pour remplacer les ressources d´efaillantes, ou en-core les interactions avec le syst`eme de fichier distribu´e XtreemFS [91] pour le stockage des donn´ees g´en´er´ees par la sauvegarde des points de reprise.
Fond´e sur une architecture compl`etement distribu´ee lui permettant de passer `a l’´echelle, XtreemGCP est con¸cu de mani`ere g´en´erique pour pouvoir y int´egrer dans le futur diff´erents travaux de la communaut´e en tol´erance aux fautes. Cette g´en´ericit´ permet de prendre en charge l’h´et´erog´en´eit´ de la grille et des applications qui s’y ex´ecutent. Ainsi XtreemGCP peut exploiter des m´ecanismes de tol´erance aux fautes qui seraient directement inclus dans l’application ou dans des biblioth`eques tol´erantes aux fautes utilis´ees par l’applica-tion, comme certaines biblioth`eques de communication MPI [30, 166, 93]. De plus, nous proposons une interface g´en´erique aux m´ecanismes de sauvegarde de points de reprise de processus, tels que BLCR [99] ou OpenVZ [143]. Cette interface permet `a XtreemGCP d’int´egrer simplement plusieurs de ces m´ecanismes. Ainsi il est capable de g´erer des applica-tions distribu´ees sur des ressources h´et´erog`enes fournissant des m´ecanismes de sauvegarde de points de reprise de processus diff´erents.
Enfin, pour permettre a` l’utilisateur de la grille, qui n’est pas n´ecessairement informati-cien, de rendre sont application tol´erante aux fautes sans modifier celle-ci, nous proposons de fournir des solutions de recouvrement arri`ere appliqu´ees de mani`ere transparente pour l’application. Ainsi XtreemGCP permet de mettre en œuvre diff´erents protocoles de re-couvrement arri`ere pour applications a` ´echange de messages. Pour cela, il se fonde sur des solutions de sauvegarde de points de reprise de processus mises en œuvre par le syst`eme d’exploitation des nœuds de la grille [99, 143].
Le chapitre 3 pr´esente la conception du service XtreemGCP. Ces travaux sont le fruit de collaborations avec les membres du projet XtreemOS, et plus particuli`erement avec John Mehnert-Sphan et Mickael Sch¨ottner de Heinrich-Heine University of D¨usseldorf. La mise en œuvre de ce service [127], l’int´egration de diff´erents outils de sauvegarde de processus, et la mise en œuvre de protocoles de recouvrement arri`ere au sein du service [68], ont et´ r´ealis´ees par les partenaires du projet.

Un cadre pour la mise en œuvre de services hautement disponibles

La haute disponibilit´e des services du syst`eme de grille est un enjeu majeur. Si un utilisateur doit soumettre une application pour en obtenir les r´esultats au plus vite, il faut que le service de soumission d’application lui permette de le faire. De mˆeme pour qu’un service tel que XtreemGCP soit capable de red´emarrer une application d´efaillante, il faut qu’il soit disponible au moment o`u l’application subit la d´efaillance. Cependant ces services s’ex´ecutant eux aussi sur des nœuds de la grille, ils peuvent subir des d´efaillances. La volatilit´e des nœuds de la grille peut compromettre la disponibilit´e de ces services.
Les r´eseaux pair-a`-pair structur´es [163, 182] sont une solution attrayante pour la con-ception de syst`emes de grilles adapt´ees aux grilles de grande taille et dynamiques [103, 155] car ils fournissent des primitives de routage tol´erantes aux fautes et passant a` l’´echelle.
Notre objectif est d’assurer la haute disponibilit´e des services de grille dans ce contexte. Nous voulons ˆetre capable d’assurer la haute disponibilit´e des services sans intervention humaine pour g´erer les cons´equences des d´efaillances. De plus, nous voulons que les services existants puissent ˆetre rendus hautement disponibles avec un effort minimal de la part du programmeur. Enfin, dans un souci de simplicit´e d’utilisation, nous voulons que les d´efaillances que subissent ces services soient rendues compl`etement transparentes pour leurs utilisateurs.
Pour rendre les services de grille hautement disponibles, nous optons pour une tech-nique de duplication active car un service en interaction avec le monde ext´erieur ne peut supporter de retour arri`ere. De plus, ce choix permet de dupliquer des services `a ´etat au comportement d´eterministe sans modification de ceux-ci. L’´etude des services composant le syst`eme de grille Vigne [159] nous a montr´e qu’ils ´etaient d´eterministes. Nos travaux portent donc sur la duplication active de service dans un r´eseau pair-`a-pair structur´e.
En distribuant les services dupliqu´es dans une table de hachage distribu´ee mise en œuvre au dessus du r´eseau pair-a`-pair structur´e, il est possible de g´erer un grand nombre de service et de r´epartir la charge des services dupliqu´es sur l’ensemble des nœuds de la grille. En exploitant les solutions de routage fond´ees sur des cl´es, ´evitant d’associer les services de la grille a` des adresses physiques, la duplication active des services et les reconfigurations n´ecessaires pour traiter les cons´equences des d´efaillances, peuvent ˆetre rendues compl`etement transparentes pour les utilisateurs.
Semias est le cadre que nous avons con¸cu et mis en œuvre pour rendre des services de grille hautement disponibles et auto-r´eparants. L’auto-r´eparation est la capacit´e d’un syst`eme `a maintenir son niveau de disponibilit´e. Elle implique des reconfigurations au-tomatiques pour remplacer les duplicatas d´efaillants par de nouveaux duplicatas et ainsi garantir la haute disponibilit´e des services sans intervention humaine.
Dans le chapitre 4, nous pr´esentons l’architecture de Semias. Cette architecture est con¸cue pour g´erer efficacement la volatilit´e des nœuds de la grille. Nous d´ecrivons notre solution d’auto-r´eparation pour assurer la haute disponibilit´e des services dans un environ-nement tr`es dynamique tout en limitant le coˆut des reconfigurations. Nous pr´esentons enfin une ´evaluation de notre prototype sur Grid’5000. Dans le cadre de ces ´evaluations, nous avons utilis´e Semias pour rendre le service de gestion d’application de Vigne hautement disponible et auto-r´eparant.
Trois stagiaires que j’ai encadr´e, ont particip´e aux travaux sur Semias : Rajib Nath, ´ ´etudiant en Master `a University of Tennessee (Etats-Unis), S´ebastien Gillot, ´etudiant en Master `a l’Universit´ de Rennes 1, et Stefania Costache, ´etudiante en Master `a Politehnica University of Bucarest (Roumanie).

Un protocole de recouvrement arri`ere pour applications `a ´echange de messages de grande taille

Les grilles de calcul peuvent fournir de grandes capacit´es de ressources de calcul et donc permettre aux utilisateurs d’ex´ecuter des applications de tr`es grande taille. Nombre de ces applications sont fond´ees sur l’´echange de messages. De nombreux protocoles de recouvrement arri`ere pour applications a` ´echange de messages existent, mais tr`es peu abordent le probl`eme du passage a` l’´echelle. La sauvegarde de points de reprise coordonn´es, technique la plus couramment employ´ee, n´ecessite le retour arri`ere de tous les processus de l’application apr`es la d´efaillance d’un d’entre eux. Elle n’est pas adapt´ee pour des applications de grande taille [117] ex´ecut´ees dans un environnement dynamique.
Nous proposons un protocole `a enregistrement de messages optimiste adapt´e aux appli-cations `a ´echange de messages de grande taille. Les protocoles `a enregistrement de messages peuvent par nature passer `a l’´echelle car ils ne n´ecessitent aucune coordination entre les processus de l’application en fonctionnement normal. De plus, ils sont adapt´es aux environ-nements dynamiques car ils ne n´ecessitent pas le red´emarrage de tous les processus suite `a une d´efaillance. Enfin Les protocoles `a enregistrement de messages optimiste peuvent offrir de bonnes performances car ils permettent d’effectuer les sauvegardes d’information sur support stable en parall`ele avec l’ex´ecution des processus de l’application.
Le seul surcoˆut en terme de performance engendr´ par les protocoles a` enregistrement de messages optimistes est li´e a` la gestion des informations de d´ependance entre les proces-sus de l’application qui sont n´ecessaires lors du recouvrement pour d´etecter les processus orphelins. Les protocoles optimistes attachent des informations de d´ependance sur les mes-sages de l’application. Pour les protocoles existants capables tol´erants plusieurs fautes, la taille de ces informations est proportionnelle a` la taille de l’application.
Pour un meilleur passage `a l’´echelle, nous proposons un nouveau protocole fond´e sur l’enregistrement de messages optimiste actif qui permet de limiter la taille des informations attach´ees sur chaque message de l’application tout en conservant la capacit´e de tol´erer plusieurs fautes simultan´ees.
La gestion centralis´ee de la sauvegarde des informations de d´ependances consid´er´ee dans les travaux sur les protocoles a` enregistrement de messages est une autre limite au passage a` l’´echelle. C’est pourquoi nous proposons une solution distribu´ee pour la sauvegarde des informations de d´ependance fond´ee sur l’utilisation de la m´emoire volatile des nœuds sur lesquels est ex´ecut´ee l’application.
Dans le chapitre 5, nous d´ecrivons le protocole O2P [162] et prouvons qu’il est capable de tol´erer plusieurs fautes simultan´ees de processus de l’application. Nous d´ecrivons ensuite une mise en œuvre de ce protocole et de la solution distribu´ee que nous proposons pour la sauvegarde des informations de d´ependance dans la biblioth`eque Open MPI. Enfin nous pr´esentons une ´evaluation de ces solutions sur la plate-forme Grid’5000.

Table des matières

Introduction
1 Les d´efaillances dans les grilles de calcul 
1.1 Les grilles de calcul
1.1.1 Un peu d’histoire
1.1.2 Les applications de calcul scientifique
1.1.3 L’architecture des grilles de calcul
1.1.4 Les d´efis li´es `a l’utilisation des grilles de calcul
1.1.5 Les syst`emes de grille
1.1.6 Un environnement d’ex´ecution hautement dynamique
1.2 La tol´erance aux fautes dans les syst`emes distribu´es
1.2.1 Faute, erreur et d´efaillance
1.2.2 Les fautes dans les grilles de calcul
1.2.3 Fondements de la tol´erance aux fautes dans les syst`emes distribu´es
1.2.4 Les techniques de tol´erance aux fautes
1.3 Synth`ese
2 Ex´ecution fiable d’applications sur grille de calcul 
2.1 D´efinition des besoins
2.1.1 Fiabilit´e
2.1.2 Simplicit´e d’utilisation
2.1.3 Coˆut
2.2 Analyse des contraintes li´ees aux grilles de calcul
2.2.1 Volatilit´e
2.2.2 Passage `a l’´echelle
2.2.3 H´et´erog´en´eit´e
2.3 Approche propos´ee
2.3.1 Un service de recouvrement arri`ere pour applications distribu´ees
2.3.2 Un cadre pour la mise en œuvre de services hautement disponibles
2.3.3 Un protocole de recouvrement arri`ere pour applications `a ´echange de messages de grande taille
2.4 Synth`ese
3 Un service de recouvrement arri`ere pour la grille 
3.1 Probl´ematique
3.1.1 Mod`ele d’application
3.1.2 Le syst`eme de grille XtreemOS
3.1.3 Cas d’utilisation des techniques de recouvrement arri`ere dans une grille
3.1.4 Objectifs
3.1.5 Travaux apparent´es
3.1.6 Conclusion
3.2 XtreemGCP : un service de traitement automatique des d´efaillances fond´e sur le recouvrement arri`ere pour des applications distribu´ees
3.2.1 D´efinitions
3.2.2 Architecture du syst`eme
3.2.3 Interface g´en´erique pour les outils de sauvegarde de points de reprise de processus
3.2.4 Prise en charge des applications distribu´ees
3.2.5 Gestion des donn´ees
3.2.6 Interface pour les utilisateurs de XtreemGCP
3.3 Synth`ese
4 Semias, cadre pour la r´ealisation de services de grille hautement disponibles et auto-r´eparants
4.1 Probl´ematique
4.1.1 Contexte : l’intergiciel de grille Vigne
4.1.2 Objectifs
4.1.3 Mod`ele consid´er´e
4.1.4 Vers des services de grille hautement disponibles et auto-r´eparants
4.1.5 Travaux apparent´es
4.1.6 Conclusion
4.2 Semias, un cadre pour la mise en œuvre de services hautement disponibles et auto-r´eparants dans la grille
4.2.1 Principes de fonctionnement
4.2.2 Description de l’architecture
4.2.3 Gestion des reconfigurations
4.3 Evaluation
4.3.1 Duplication active des gestionnaires d’application de Vigne
4.3.2 Evaluation dans un environnement statique
4.3.3 Evaluation dans un environnement dynamique
4.3.4 Passage `a l’´echelle
4.4 Synth`ese
5 Tol´erance aux fautes pour applications distribu´ees `a ´echange de messages de grande taille 
5.1 Probl´ematique
5.1.1 Mod`ele d’´etude
5.1.2 Enjeux li´es `a l’utilisation de techniques de recouvrement arri`ere
5.1.3 Etat de l’art des techniques de recouvrement arri`ere
5.1.4 Conclusion
5.2 O2P, un protocole `a enregistrement de messages optimiste actif
5.2.1 Influence de la quantit´e de donn´ee attach´ee sur les messages d’une application
5.2.2 Principes de l’enregistrement de messages optimiste actif
5.2.3 Description du protocole O2P en fonctionnement normal
5.2.4 Prise en charge des d´efaillances
5.3 Gestion distribu´ee de la sauvegarde des messages
5.3.1 M´ethode d’´evaluation
5.3.2 Mise en œuvre de O2P dans Open MPI
5.3.3 Evaluation de O2P avec un enregistreur d’evenements cent ´ ralise
5.3.4 Evaluation de O2P avec un enregistreur d’´ev´enements dist ´ ribu´e
5.4 Synth`ese
Conclusion 
Bibliographie 

Télécharger le rapport complet