Déploiement auto-adaptatif d’intergiciel sur plate-forme élastique

 Un système distribué est défini par Tanenbaum et al. [37] comme une collection d’ordinateurs indépendants qui apparaˆıt à ses utilisateurs comme un système unique et cohérent. Cependant, un système distribué n’est pas toujours qu’une collection d’ordinateurs mais peut aussi être une collection de processus, de processeurs, et plus généralement d’entités autonomes. Ces entités autonomes et interconnectées coopèrent pour la réalisation d’un objectif. Si les entités autonomes sont, par exemple, des processus, l’objectif est l’exécution d’un algorithme distribué dont chaque processus exécute le code. Les entités qui composent ces systèmes partagent un certain nombre de caractéristiques de base [38] : ❼ elles sont autonomes et sont ainsi en mesure d’exécuter des tˆaches de manière indépendante ❼ elles sont interconnectées : directement o`u indirectement, ces entités doivent pouvoir communiquer, selon un modèle de communication; ❼ elles disposent d’un mécanisme de coordination leur permettant de coopérer pour atteindre un objectif. Ces entités peuvent être homogènes (dans ce cas, elles sont identiques) ou hétérogènes. Elles sont réparties géographiquement, sont concurrentes et asynchrones (il n’existe pas un temps global pour tout le système et chaque entité à son horloge locale). Un des avantages majeurs des systèmes distribués est le partage de ressources (matérielles et/ou logicielles). Ceci permet aux utilisateurs d’accéder à des ressources distantes, d’avoir accès à des services qu’une seule entité ne pourrait offrir (augmentation de performance par une parallélisation par exemple). Contrairement à un système centralisé, caractérisé par un élément central qui rend le système indisponible en cas de panne, et qui constitue un goulet d’étranglement, un système distribué n’a pas un élément central et peut être tolérant aux pannes (continuer à fonctionner après la défaillance d’une partie des entités), en répliquant par exemple les ressources et les calculs sur différents sites, augmentant ainsi la fiabilité du système. Cependant, ces systèmes présentent plusieurs points de défaillance possibles (puisque chaque entité est autonome et peut tomber en panne indépendamment des autres) et sont difficiles à gérer. De même, leur sécurité est plus complexe à assurer puisque les entités peuvent être réparties géographiquement. Les systèmes informatiques sont passés d’une époque o`u ils étaient chers, centralisés, larges, isolés (1945-1985) à une autre époque (1985+) marquée par deux avancées majeures que sont le développement de puissants microprocesseurs et l’avènement de réseaux informatiques de plus en plus performants. L’arrivée de ces microprocesseurs qui avaient la puissance des gros systèmes a réduit la taille et les coˆuts de ces matériels. Quant aux réseaux, ils ont permis d’interconnecter des machines proches (LAN) ou lointaines (WAN) afin qu’elles puissent s’échanger des informations. Contrairement aux précédents, ces systèmes n’étaient plus centralisés mais distribués.

Exemples de systèmes distribués contemporains

Différents types de plates-formes distribuées sont apparues au début des années 2000 grˆace à l’exploitation des travaux antérieurs et aux avancées technologiques. Parmi ces platesformes, on peut citer les grilles (grid), les clouds, les réseaux Ad hoc. Les réseaux Ad hoc sont des réseaux sans infrastructure [39], dans lesquels il n’existe pas une entité centrale qui coordonne les communications comme c’est le cas dans les réseaux avec infrastructure. Ils sont constitués d’un ensemble de nœuds, dotés de capacités de communication sans fil, qui participent eux mêmes au routage des messages en transmettant ceux qui ne leur sont pas destinés pour qu’ils atteignent leur destination. Les entités qui les constituent peuvent être mobiles (se déplacer de manière indépendante le cas échéant) avec pour conséquence une topologie du réseau qui change continuellement. Chaque entité peut communiquer avec celles qui sont dans sa portée radio. Si tous les nœuds sont mobiles on les appelle MANET (Mobile Ad hoc NETwork). Les nœuds peuvent être des téléphones, des ordinateurs portables, tablettes, des véhicules, etc. Les réseaux de capteurs sans fil [40] sont un cas particulier des réseaux ad hoc. Les nœuds sont des capteurs, disposant d’interfaces de communication sans fil. Les données obtenues par les capteurs sont transmises à un élément central en les faisant transiter éventuellement par d’autres nœuds. 10 1.1. Généralités Les grilles informatiques Une grille informatique (grid computing) est un type de plate-forme distribuée introduit à la fin des années 90 par Ian Foster et Carl Kesselman [41, 42] qui le définissaient comme une “infrastructure matérielle et logicielle qui fournit un accès sˆur (fiable), accessible et bon marché à de grandes capacités de calcul”. La grille signifiait alors une infrastructure de calcul distribué pour la science de pointe avec des applications très gourmandes en puissance de calcul (simulations de physique nucléaire, prédictions météorologiques,…). Le terme de grille a été choisi par analogie avec le réseau électrique (appelé power grid). Cela signifie que la fourniture des services informatiques devrait avoir des caractéristiques semblables à la distribution de l’électricité : disponible partout, simple et facile d’accès à travers une interface standard (prise électrique normalisée), utilisation à la demande et en fonction des moyens de l’utilisateur (pas forcément informaticien) sans avoir à se préoccuper des aspects techniques de production (types de machines, moyens de transport, provenance, etc.). Le concept a été popularisé au début des années 2000 même si plusieurs travaux antérieurs permettant sa mise en production existaient bien avant sans porter le nom de grille [43]. Les grilles sont organisées dans une architecture en couche : entre la couche physique (ou fabrique) et la couche application se trouve une couche intermédiaire appelé intergiciel (middleware) qui offre divers services aux applications et aux utilisateurs (découverte et allocation de ressources par exemple). Parmi ces intergiciels on peut citer Globus [2, 44], Unicore [45], DIET [16]. Les grilles ont évolué en trois phases : les premières grilles étaient axées d’abord sur le partage de la puissance de calcul entre centres informatiques, le partage des données a suivi. Elles utilisaient des solutions sur mesure, pour des besoins spécifiques (première version de Globus). La deuxième génération se caractérise par l’utilisation des intergiciels permettant d’intégrer des technologies de grille différentes. La troisième génération correspond à l’intégration des technologies web dans les intergiciels, qui avec les techniques de virtualisation rendent la complexité de l’infrastructure presque invisible. Ils ont été ensuite enrichis par ajout d’une couche de sémantique, les rendant plus “intelligents” et autonomes. Cependant, ces grilles ne prenaient pas en compte les nouveaux paramètres comme la généralisation des appareils mobiles, les réseaux sans fil, etc. De nouveaux projets de grille ont émergés en mettant l’accent dès leur conception sur des problèmes liés à des notions comme l’ubiquité (“pervasiveness”) et l’auto-gestion (“self-management”). Les grilles jusqu’à la troisième génération sont qualifiées de grilles traditionnelles et les autres de grilles émergentes [46]. Des infrastructures de grilles sont aujourd’hui en production à travers le monde comme grid’5000 [47], EGI [48], OSG1 , etc. L’OGF (Open Grid Forum)2 coordonne les efforts de standardisation dans le domaine. Les Clouds Le Cloud [3, 49] est une évolution du concept de grille. Il désigne un ensemble de technologies et systèmes permettant de fournir divers types de ressources (calcul, stockage, logiciels, etc.) à la demande, à travers internet et généralement payant en fonction de l’utilisation. Les ressources sont fournies de manière dynamique et peuvent ainsi s’adapter à la charge de l’utilisateur. Cela permet au fournisseur d’exploiter son infrastructure de   manière optimale. Le cloud est en général la propriété d’une seule organisation, peut être privé, public, hybride, communautaire. Une caractéristique du cloud est l’élasticité, permettant au fournisseur d’être en mesure d’augmenter ou de réduire les ressources offertes en fonction de la variation des besoins des utilisateurs. Plusieurs types de solutions de cloud sont disponibles [50, 51] comme : OpenStack3 , OpenNebula4 , Eucalyptus5 . L’intergiciel de grille et cloud DIET L’intergiciel DIET [16] nous sert de cas d’utilisation, et les travaux décrits dans ce manuscrit lui sont appliqués. Figure 1.1: Hierarchie multi-MA de DIET. DIET est un intergiciel GridRPC [52]. Un des objectifs de l’API GridRPC [53] est de définir clairement une syntaxe et une sémantique pour les GridRPC qui sont une extension des Remote Procedure Call (RPC) [54] appliquée au domaine des grilles de calcul. Le modèle de programmation RPC est l’un des premiers modèles permettant d’exécuter des applications sur un environnement distribué. Les applications client et serveur des utilisateurs finaux doivent être décrites dans le modèle de programmation fourni. L’architecture par composant de DIET est structurée de manière hiérarchique pour améliorer le passage à l’échelle comme illustrée à la Fig. 1.1 . La boite à outils DIET est implémentée en Corba [55]. Il bénéficie par conséquent des mises à jour des services standardisés et stables d’implémentation à haute performance et librement disponibles de Corba. DIET est constitué de plusieurs types de composants. Un Client est une application qui utilise l’infrastructure DIET pour résoudre un problème en utilisant une approche GridRPC. Un SeD (Server Daemon) joue le rˆole de fournisseur de services. Il exporte ses fonctionnalités via une interface de service de calcul standardisée. Un seul SeD peut offrir plusieurs services de calcul. Le troisième composant de DIET, les agents, facilitent la localisation et l’invocation des services et donc l’interaction entre les clients et les SeDs. La hiérarchie des agents fournit des services de haut niveaux comme l’ordonnancement et la gestion des données. Ces services permettent un passage à l’échelle grˆace à leur distribution dans la hiérarchie des agents composés d’un agent maˆıtre (Master Agent ou MA) et de plusieurs agents locaux (Local Agents ou LA). Plusieurs hiérarchies peuvent être inter-connectées pour former une plateforme multi-MA. Une inter-action typique de DIET se déroule selon le scénario suivant : (1) D’abord un Client se connecte à la hiérarchie et envoie un message de découverte en fonction du type de service qu’il souhaite utilisé. Le message est envoyé au MA auquel le client est connecté; (2) ensuite, le message est propagé dans la hiérarchie du MA vers les SeDs à travers les LA; (3) Les SeDs qui ont re¸cu le message répondent avec un vecteur d’estimation : un ensemble de valeurs qui décrit la disposition du SeD à traiter la requête. En fonction de l’implémentation du service, le vecteur d’estimation peut contenir des informations comme le puissance de calcul, la quantité de RAM, le temps estimé pour exécuter la requête, le nombre de requête en file d’attente, etc.; (4) A chaque niveau de la hiérarchie des agents, les ` vecteurs d’estimation sont agrégés de sorte que le MA ne va recevoir qu’un nombre réduit de vecteurs; (5) Enfin, un ou plusieurs vecteurs sont retournés au Client qui avait lancé la requête. Ce dernier choisit le SeD qui lui convient; (6) La requête et les données nécessaires pour résoudre le problème sont envoyées par le Client au SeD choisi. 1.1.2 Tˆaches classiques Bien que les systèmes distribués se présentent sous différentes facettes, un certain nombre de problèmes fondamentaux leur sont communs et servent de base au domaine. Un concepteur d’une application distribuée peut être amené à trouver une solution ou à utiliser les algorithmes existants concernant un ou plusieurs de ces problèmes. En plus de la tolérance aux pannes, un certain nombre de ces problèmes sont décrits ci-dessous. Election de leader ´ Plusieurs applications distribuées reposent sur l’existence d’un processus leader. L’élection d’un leader [56] consiste à distinguer un seul processus qui sera appelé leader avec un statut particulier à partir de tous les processus (ou d’un groupe de processus) candidats. Les autres processus sont dans un autre état différent de celui du leader. Lorsque le leader meurt ou devient injoignable, un autre processus est élu parmi les processus qui sont dans un état correct. Lorsque le graphe des processus n’est pas connexe, un leader est élu pour chaque composante connexe, et lorsque le graphe redevient connexe, un seul leader reste.  Exclusion mutuelle Dans un système distribué, les processus s’exécutent ensemble de manière simultanée et coopèrent pour atteindre un objectif. Ils peuvent donc chercher à avoir accès à une même ressource partagée. L’objectif des algorithmes d’exclusion mutuelle [57] est de garantir qu’au plus, un seul processus peut entrer en section critique d’une ressource partagée à un moment donné. Lorsqu’un processus entre en section critique, les autres requêtes devront attendre sa sortie pour qu’un autre processus puisse avoir l’accès à la ressource. Certaines ressources ne peuvent être utilisées que par un seul processus à la fois (exemple de l’imprimante) à un moment donné. L’exclusion mutuelle de groupe [58, 59] est une généralisation de l’exclusion mutuelle dans laquelle plusieurs ressources sont partagées entre les processus et plusieurs processus appartenant au même groupe peuvent accéder simultanément à la même ressource partagée. Cependant, des processus de groupes différents doivent accéder aux ressources partagées de manière exclusive. Détection de propriété globale L’état global d’un système distribué (ou une configuration du système) est constitué de l’ensemble des états des processus du système à un moment donné. Il est parfois nécessaire de déterminer si cet état global satisfait à un ou plusieurs critères (“stabilité”, terminaison, …). La détection de la terminaison [60] d’un calcul distribué est un problème dans lequel on cherche à déterminer si tous les processus du système ont terminé un calcul. Cette détection de la terminaison peut être effectuée par une entité centrale qui a une vue globale du système. Si par contre, chaque processus doit détecter lui même la terminaison du calcul global, on dit que c’est une détection distribuée de la terminaison, qui est un problème fondamental dans les systèmes distribués. Depuis son introduction au début des années 80 [61, 62], la détection distribuée de la terminaison d’un algorithme a été bien étudiée [63–68]. Algorithmes à vagues Les algorithmes à vagues [69–73] sont un type d’algorithme distribué classique. Ils sont utilisés, entre autres cas, pour diffuser une information dans un réseau, collecter des valeurs, synchroniser, etc. Un algorithme à vagues peut être constitué d’une ou de plusieurs vagues successives. Dans un algorithme à vagues, un nœud initie une vague en diffusant une information (jeton, requête,…) qui est propagée dans le réseau, ensuite les réponses sont remontées vers l’initiateur qui prend une “décision” et peut lancer une autre vague si nécessaire. Les algorithmes d’écho [69], de collecte et d’agrégation de données dans un réseau [74] sont des types d’algorithmes à vagues. Les algorithmes d’écho [69], utilisent une technique de diffusion permettant à un nœud de transmettre une information à un autre nœud. L’information est transmise par chaque nœud à ses voisins jusqu’à ce qu’elle atteigne le destinataire. L’inconvénient de cette méthode est le coˆut élevé en nombre de messages qu’elle induit. Ses avantages sont sa simplicité et sa facilité de mise en œuvre. Les algorithmes distribués d’agrégation de données [74] sont des algorithmes à vagues, qui permettent de diffuser une requête dans un réseau et de collecter et d’agréger les  réponses vers le nœud source qui avait émis la requête. Ce type d’algorithme agit en deux phases : une phase durant laquelle un nœud source diffuse une requête qui est propagée par chaque nœud à ses voisins jusqu’à ce que la requête atteigne les feuilles; et une deuxième phase durant laquelle chaque nœud, en commen¸cant par les feuilles, renvoie sa réponse à son parent et ces réponses sont agrégées au fur et à mesure que l’information remonte vers le nœud source qui avait émis la requête. Les algorithmes à vagues se divisent en deux familles : celle des algorithmes qui utilisent une circulation d’un jeton et celle des algorithmes qui utilisent une propagation d’information avec retour ou PIF (Propagation of Information with Feedback). Un déploiement de DIET fonctionne sous la forme d’un PIF. Lorsqu’un client se connecte sur un master, ce dernier diffuse une requête dans le réseau pour trouver le meilleur SeD (les SeDs sont au niveau des feuilles) pour satisfaire le client. Les réponses des SeDs sont agrégées au fur et à mesure qu’elles remontent vers le master qui avait émis la requête. 

Tolérance aux fautes

La tolérance aux pannes vise à masquer les effets d’une défaillance ou à restaurer un comportement conforme à sa spécification pour un système qui a dévié de sa spécification à cause d’une faute [73]. Plus généralement, l’objectif est de gérer les pannes qui peuvent survenir pendant une exécution comme l’arrêt brutal (crash) d’un processus, une rupture d’un lien de communication entre deux nœuds. Un système distribué peut être complexe, impliquant divers types de ressources autonomes (pouvant défaillir localement et de manière indépendante), géographiquement réparties, raison pour laquelle les fautes et les défaillances sont plus courantes que dans les systèmes centralisés. Une panne peut être locale et affecter le comportement d’une partie des autres nœuds du système sans affecter une autre partie. En plus de la possibilité de pouvoir partager des ressources, avoir des systèmes en mesure de continuer à fonctionner (même si ce n ’est pas de manière optimale) même lorsque des défaillances touchent une partie des éléments qui le composent est un objectif majeur dans la conception des systèmes distribués que l’on cherche à rendre fiable, disponible, sˆur et maintenable [37]. Un système distribué est en panne lorsqu’il ne se comporte plus conformément à sa fonction (ce pour quoi il a été prévu) [75]. Une erreur est une partie de l’état du système qui peut causé une panne. Une faute est ce qui cause une erreur. Etre capable de détecter ˆ les fautes est donc d’une grande importance. Ainsi, un système est tolérant aux pannes s’il peut continuer à fournir le service pour lequel il est prévu, et ceci même en présence de fautes. Types de pannes Différents modèles de fautes sont considérés dans les systèmes distribués. Lorsqu’on a une vue du système distribué de niveau processus, on peut distinguer les différents types de fautes au niveau processus [37, 73, 75]. ❼ les arrêts : un processus à l’arrêt cesse d’exécuter ses actions (interne, de communication, de lecture et d’écriture). L’arrêt peut être définitif (“crash stop”) ou temporaire (“crash recovery”); 

Généralités

les omissions : elles modélisent les fautes qui peuvent conduire à la perte de messages. Ce type de faute peut affecter les canaux de communication et se manifester sous la forme d’une rupture du lien (du à une problème au niveau du réseau physique sous-jacent par exemple) rendant certaines communications impossibles. Les fautes au niveau des canaux peuvent aussi provoquer la perte, la duplication, la transmission hors délais des messages. Un canal qui peut perdre des messages peut être modélisé en considérant qu’un des processus au bout du canal échoue à transmettre ou à recevoir certains messages qu’il devait envoyer ou recevoir. Un autre moyen de modéliser les pertes de messages dans un système synchrone avec passage de messages est de permettre la perte d’au plus un certain nombre de messages à chaque round, mais les canaux sur lesquels ces pertes apparaissent peuvent changer d’un round en un autre; ❼ les pannes temporelles : elles sont dues à un délai non respecté, par exemple dans un système temps réel o`u on exige que les actions soient terminées dans un intervalle de temps donné. Les différents types de pannes peuvent être classés dans des catégories de plus haut niveau : 

les pannes transitoires

une panne transitoire peut perturber l’état d’un processus d’une manière arbitraire. Elles capturent les effets de l’environnement, dont la durée est limitée. L’élément responsable de la panne peut n’être actif que pendant un temps limité, mais l’effet produit sur l’état global du système reste. Les omissions sont un cas de panne transitoire, lorsque l’état d’un canal est perturbé; 

les pannes byzantines 

elles modélisent un comportement arbitraire des processus. Ce dernier modèle est utile pour simuler des attaques et situations dans lesquelles les fautes sont difficiles à caractériser. Un algorithme dans le modèle avec fautes byzantines doit donc fonctionner correctement (atteindre son but) quel que soit le comportement des processus. Techniques de tolérance aux pannes Pour assurer une gestion des pannes qui peuvent éventuellement survenir dans un système distribué, il faut d’abord être en mesure de détecter ces événements, c’est-à-dire, être en mesure de détecter que le système ne se comporte plus de manière conforme à sa fonction. La détection d’une panne n’est pas toujours possible (par exemple dans un système asynchrone o`u le temps d’exécution des actions n’est pas borné). Mais lorsque la détection est possible, elle peut se faire lorsqu’on détecte un signal ou message d’erreur. Une erreur latente est une erreur présente mais non détectée. Une fois la faute détectée, il faut la gérer. Les techniques utilisées pour assurer la tolérance aux pannes peuvent être regroupées en deux catégories selon que les pannes sont masquées ou non masquées. Pannes masquées Lorsqu’une panne est masquée, son occurrence n’a pas d’impact sur le système. Cette catégorie de techniques adoptent une vision pessimiste de la tolérance aux pannes. Ces algorithmes tolèrent des dysfonctionnements continus touchant le système. Ces techniques sont nécessaires dans les systèmes critiques (mettant en général la vie des personnes en  danger en cas de défaillance total : un avion doit pouvoir continuer à voler même si un de ses appareils ne fonctionne pas parfaitement). Elles sont cependant difficiles à mettre en œuvre et ne tolèrent qu’un nombre restreint de dysfonctionnements. Les techniques de réplication utilisées pour assurer la tolérance aux pannes font partie de cette catégorie. Dans les techniques de réplication, les données et/ou les programmes sont répliqués ce qui permet au système de pouvoir continuer à fonctionner même en présence de pannes . Pannes non masquées Dans cette catégorie, les pannes peuvent affecter temporairement le comportement du système, moment pendant lequel il ne se comporte plus exactement comme spécifié. Cependant, une restauration du comportement conforme à la spécification aura lieu. Parmi les techniques utilisées pour assurer la restauration d’un comportement correct on retrouve la reprise sur panne [77–79], et les algorithmes auto-stabilisants [36]. La reprise sur panne repose sur un historique, un enregistrement périodique des états des processus au cours de leur exécution, sauvegardé dans une mémoire stable. Lorsqu’une panne est détectée, le système est restauré à partir des derniers états sauvegardés. L’état retrouvé n’est pas forcément l’état avant la panne, mais un état correct. Algorithmes de consensus Il existe des situations dans lesquelles des processus distribués doivent trouver un accord, prendre la même décision,… C’est le cas, par exemple, dans un système de transaction o`u tous les processus qui participent doivent tomber d’accord sur l’opération à exécuter et l’appliquer : soit sauvegarder les résultats de la transaction, soit les annuler. Dans tous les cas, la décision prise doit être la même pour tous les processus qui participent. Ils vont donc appliquer la même opération. Ce problème, connu sous le nom de consensus  , implique un ensemble de processus distribués, dont certains peuvent ne pas être fiables. Chaque processus choisit une valeur initiale, à partir d’un ensemble commun à tous les processus. Le problème consiste, pour les processus fiables, à trouver un consensus, c’est à dire choisir, de manière irrévocable, la même valeur finale, parmi celles proposées; en respectant les conditions suivantes : ❼ tout processus fiable finira par décider, c’est à dire choisir une valeur finale (terminaison); ❼ la valeur finale choisie doit être identique pour tous les processus fiables (accord); ❼ la valeur finale choisie doit avoir été proposée (validité). Ainsi, si tous les processus fiables avaient choisi la valeur initiale v, alors la valeur finale doit être v. Il existe des variantes du problème dans lesquelles, on exige plus que tous les processus choisissent la même valeur, mais que le cardinal de l’ensemble des valeurs choisies soit au plus égal à un entier k (“k-set consensus”). Dans ce cas, le consensus devient un cas particulier lorsque k = 1 [82]. Dans un système o`u le réseau et les processus sont complètement fiables, le problème peut trouver une solution triviale. Par exemple, les processus peuvent s’échanger les valeurs et choisir une valeur finale de manière déterministe en appliquant la même fonction (le maximum/minimum par exemple) à l’ensemble (des valeurs initiales) re¸cu. Le même ensemble sera re¸cu par tous puisqu’il n’y a pas de pannes.