Home

Tolérance aux défaillances

Introduction

J'ai effectué une thèse dans le projet ADP (Algorithmes Distribué et Protocoles) dirigé par Michel Raynal à l'IRISA (Rennes). Cette thèse porte sur la tolérance aux défaillances dans des environnements asynchrones distribués reposant sur l'utilisation de techniques de communications de groupes. Plus particulièrement, à la mise en oeuvre de technique de réplication dite actives. Une tâche critique est répliquée par de nombreuses entité qui exécutent toutes le même code et pour lesquelles, on fait en sorte que les requêtes soumises par l'environnement soient toutes traitées dans le même ordre par chacun des replicas. Ceci implique que si d'une part le code exécuté par les entités est déterministe, et que si d'autre part l'état initial de chacun des replicas est identique, alors les états locaux de chacun des replicas évoluent de manière cohérente. Par opposition à la réplication passive où il existe deux sortes de replicas, le maitre et les esclaves, la réplication active présente l'avantage de masquer de manière plus efficace (en temps de réponse observable par l'environnement) les fautes des replicas. En effet, dans la réplication passive, toutes les requêtes sont traitées par le maitre. Les replicas passifs ne servent qu'en cas de panne du maitre. Ceux-ci, dès lors qu'ils ont détecté une panne du maitre, doivent s'entendre pour élire un nouveau maitre de manière à poursuivre le traitement des tâches. Cela est coûteux en terme de performances vis à vis de l'environnement. Au contraire, dans la réplication active, puisque tous les replicas participent au traitement des requêtes, la panne de l'un des deux est complètement masquée.

Afin de pouvoir garantir que les requêtes seront bien toutes traitées dans le même ordre par chacun des replicas, il est nécessaire d'implementer une primitive de communications appelées total order au sein du groupe de processus. Une telle primitive nécessite que les processus aient la possibilité de se mettre d'accord. On entend par là, qu'il doit être possible à partir d'un ensemble de valeurs (typiquement ici, les identificateurs des transactions à traiter), initialement réparties sur chacun des processus et potentiellement différentes, de pouvoir converger à coup sûr, vers une valeur unique connue de tous les processus (typiquement ici, l'ordre dans lequel les processus vont traiter les transactions.). Et ceci, malgré l'occurence possible de pannes lors du calcul distribué nécessaire à cet accord.

Par ailleurs, on désire pouvoir insérer, ou enlever des processus au sein du groupe de manière dynamique, afin de pouvoir en ajuster la taille. Ceci permet d'atteindre le niveau de confiance souhaité lorsque l'on connait la probabilité d'occurence de pannes de chacun des replicas pris séparément (on suppose bien entendu que les pannes sont des évènements aléatoires indépendants). Pour cela, on a besoin d'un service de calcul de la composition du groupe. Celui-ci doit synthétiser une composition pour le groupe la plus fidèle possible à la réalité. On part pour cela des compositions approchées proposées par chacun des membres du groupe et là encore on calcule une composition unique connue de tous.

De plus, il est nécessaire que ces changements de composition dans le groupe soient synchronisés d'une manière ou d'une autre avec l'ordonnancement des transactions (qui est une tache traitée de manière indépendante). En effet, sans cela, il se pourrait que certains processus ne traitent pas les mêmes requêtes, conduisant ainsi à une divergence de l'état global que l'on cherche à construire. Pour cela, il faut résoudre le problème appelé view synchrony . Une implémentation possible de ce problème consiste à traiter les changements de composition du groupe de manière virtuellement synchrone sur l'ensemble des processus, c'est-à-dire au même instant logique (pas forcément physique), à savoir, après le traitement d'une tâche prédéterminée (prise dans le flux des tâches à traiter). Là encore, il faut que l'ensemble des processus se mettent d'accord sur l'instant logique précis, auquel doit avoir lieu le changement de composition du groupe.

Le problème de l'accord distribué réapparaît de manière récurrente dans tout ce qui précède. C'est un des problèmes fondamentaux de l'algorithmique distribuée, que l'on appelle aussi consensus. Une abondante littérature lui est consacré. En effet, il a été montré que ce problème ne connaissait pas de solution déterministe dans un environnement distribué purement asynchrone. Rappelons qu'un système est dit asynchrone, s'il n'existe pas de borne sur les vitesses de calcul des entités composant le système, ni sur les vitesses de transmission des messages. Cela signifie que l'on ne peut pas recourir au temps physique dans l'écriture des algorithmes. Tout se passe comme si chaque composant du système vivait dans son propre referentiel logique (pas forcément physique), à savoir, après le traitement d'une tâche physique, sans qu'il soit jamais possible de les synchroniser tous sur une même référence.


Logiciel

Durant mon travail de thèse, j'ai participé au développement d'un prototype de plateforme de tolérance aux défaillances. Pour une brève introduction aux principes de fonctionnement de Eden, vous pouvez consulter la présentation suivante que j'ai donné lors du workshop Argo organisé par le Lasid à l'Université Fédérale de Bahia (Brésil) (en Anglais uniquement):
Frédéric Tronel
Last modified: Thu Oct 18 11:20:23 MEST 2001