Les mécanismes de gestion de pannes dans un réseau à large échelle

Mécanismes de détection de pannes

Dans l’optique de soulager le plus possible les nœuds de notre système, plus particulièrement les DBMS Nodes, nous assignons aux TM Nodes la responsabilité de détecter les pannes. La détection des pannes doit prendre en compte les deux principaux typesde pannes déjà définis à savoir les pannes de nœud et celles de communication8.
Nous considérons que chaque TM Node a une connaissance de l’existence des autres TM Nodes. L’ensemble des informations relatives à ces TM Nodes est stocké dans une table que nous appelons vue. Pour limiter la taille de cette vue, nous supposons qu’un TM Node ne connaît pas tous les autres TM Nodes, mais seulement quelques uns.
Ainsi, lors du processus de routage d’une nouvelle requête, si un TM Node Ti , n’arrive pas à joindreun DBMS Node DBi, il contacte les pairs de sa vue qui, à leur tour, vont essayer decontacter le DBMS Node suspecté. Si aucun pair Tk de sa vue n’arrive à joindre le DBMSNode DBi, celui-ci est suspecté d’être en panne. Par contre, si au moins l’un d’entre eux réussità le contacter, nous concluons que le nœud n’est pas en panne mais plutôt qu’il y a unproblème de communication entre lui et le TM Node Ti . On peut ainsi distinguer les pannes de nœud de celles de communication.
La fiabilité de la détection est tributaire de l’état des TM Nodes de la vue. Par conséquent,chaque TM Node doit effectuer une gestion interne efficace de sa vue. Ainsi, il doit connaître approximativement l’état de chacun de ses pairs de sa vue avant de le contacter. Ceci lui permet de choisir judicieusement les nœuds susceptibles de répondre à sa demande. En d’autres termes, il ne sélectionne pas les TM Nodes en panne. L’une des techniques de détection de panne vues au premier chapitre pourrait être utilisée (par exemple, les messages ping/pong).
Les pannes de SGBD, de transactions et celles du module de traitement des transactions sont détectées à la suite de la réception d’un accusé de traitement. Cet accusé est délivré par le DBMS Node qui a été choisi pour exécuter la transaction et il signale si l’exécution s’est bien déroulée. Évidement dans le cas d’une des trois pannes précédentes, il révèle une mauvaise terminaison de la transaction (Rollback, unknown data, …).

La détection des pannes dans un réseau à large échelle

La technique de détection des pannes de communication reposant sur un tiers (les TM Nodes d’une vue) ne répond pas parfaitement au critère de justesse. Nous rappelons qu’uneLes pannes de SGBD et celles du module de traitement de transactions sont assimilées à despannes de nœud. détection n’est juste que si un nœud considéré en panne l’est effectivement. En effet, on ne peut vraiment dire qu’un nœud est réellement en panne que s’il est inaccessible par tout autre nœud. Dans les systèmes à grande échelle où un nœud a une vue limitée du système, il n’est pas évident de garantir la détection de la panne d’un nœud par le passage sur tous les autres nœuds. Car les nœuds choisis pour contacter le nœud suspecté peuvent tomber en panne avantla fin de la procédure de détection. De ce fait, on ne peut réellement s’assurer si le nœud est en panne ou si on a plusieurs liens de communication défectueux (panne de communication).
La seule chose que l’on peu faire est alors de suspecter le nœud. De ce fait, notre méthode de détection ne peut régler ce problème de justesse avec précision dans de tels environnements. Néanmoins, nous avons tenté d’assurer la complétude, autrement dit : tout nœud en panne est au moins suspecté de l’être.
Notre traitement visant à tolérer les pannes s’appuie sur un modèle de système partiellement synchrone en utilisant des délais d’attente bornant les différentes phases du traitement. Celuici tout en se donnant comme objectif de garantir une bonne détection des pannes (fautes dusystème) pour les tolérer, se doit d’être le moins encombrant pour le système (i.e. il doit être le moins coûteux possible en termes de ressources empruntées au système).
Le diagramme ci-dessous montre les différentes étapes de la procédure d’exécution d’unetransaction d’un client par un DBMS Node à la suite du choix effectué par un TM Node. Ilreprésente aussi les différentes possibilités de panne au cours de la procédure d’exécution.

Algorithme de détection des pannes de nœud et de communication

Nous avons déjà parlé de notre procédure de distinction entre les pannes de nœud et celles de communication, l’algorithme de détection ci-dessous est appelé en cas de suspicion d’un nœud pour valider s’il est effectivement en panne ou s’il s’agit d’une panne de communication. Il renvoie true dans le premier cas et false dans le second.
Il demande à un ensemble de k nœuds qui sont des TM Nodes et constituent la vue d’un autre TM Node de faire un « ping » à un DBMS Node qui leur est donné et d’alerter lecommanditaire de la réception ou non d’un « pong ». Selon les réponses reçues, on conclutcomme dit précédemment.

Mécanismes de tolérance aux pannes

Une fois qu’une panne est détectée, il reste à trouver les moyens pour la gérer de sorte que les performances de notre système ne se dégradent pas. Nous présentons dans cette section les différents algorithmes utilisés pour atteindre cet objectif. En fonction des types de panne et du type de nœud qui l’a observé, un algorithme spécifique est exécuté par ce dernier. Ainsi nous avons trois algorithmes que nous allons présenter. Nous commençons d’abord par les Client Nodes qui voient labase de données répartie comme une boîte noire et donc jouent un rôle passif, puis nous exposons l’algorithme utilisé par les DBMS Nodes et enfin celui des TM Nodes.

Algorithme des DBMS Nodes

Les pannes vues à partir d’un DBMS Node

On remarque les pannes des Client Nodes qui n’ont d’effet sur le système que lorsque le client rejoint le système et relance sa transaction (modification) alors que celle-ci a déjà été exécutée. Pour éviter de ré-exécuter une transaction, on journalise toutes les transactions exécutées et on fait de sorte que si un nœud client relance une exécution, qu’il la relance avecles mêmes références (numéro). L’autre type de panne que l’on peut observer est celle d’un TM Node à qui on doit envoyer un accusé de traitement.

Description de l’algorithme

Les DBMS Nodes sont chargés de l’exécution des transactions. Après avoir transmise une transaction à un DBMS Node, le TM Node attend de la part de celui-ci une notification de la bonne terminaison ou non de l’exécution de la transaction, ceci, pour garantir la cohérencedu catalogue. De la même manière le client initiateur de la transaction attend aussi de la part du DBMS Node des résultats. Durant cette phase d’attente de réponse et de notification, on peut avoir des pannes de communication ou de nœud. Alors, pour prendre en compte ces pannes, lorsqu’un DBMS Node envoie un message denotification à un TM Node, il déclenche un timeout. A l’expiration de ce timeout, s’il ne reçoit pas d’accusé de réception de la part du TM Node, il bufférise le message de notification afin de pouvoir le réémettre plus tard. Ces messages de notification bufférisés pour absence d’accusé de réception, seront envoyés sous forme d’annexes (piggybacking) au prochain TM Node qui sollicitera les services du DBMS Node et effacés après la réception de l’acquittement de ce TM Node.
Enfin, si un TM Node reçoit des messages sous forme de piggybacking, il est tenu de les interpréter et de faire le traitement nécessaire. La section 3.3 détaille ce dernier point.
La section suivante présente l’algorithme que nous avons utilisé pour atteindre cette fin.

Description de l’algorithme

Les TM Nodes sont le cœur du système. En effet, en plus de leur tâche d’équilibrage de charge et du choix du DBMS Node le plus adéquat, leur rôle de « décideur » leur incombe la détection des principales pannes afin de les tolérer. Ils doivent donc traiter ces pannes lorsqu’elles surviennent pour ne pas bloquer le système, éviter l’effet de cascade des pannes et assurer un service dans le pire des cas dégradé.

Tolérance des pannes vues par les TM Nodes

Outre leur devoir de router les requêtes, les TM Nodes doivent assurer la détection des principales pannes (pannes en rapport aux DBMS Node) et essayer de minimiser leur occurrence, si cela est toutefois possible. Cependant si des pannes surviennent, elles doiventêtre traitées pour ne pas affecter les performances du système, éviter l’effet de cascade des pannes et assurer un service dans le pire des cas dégradé.
Ce faisant, après avoir choisi et routé une transaction Tk vers un DBMS Node DBi , le TM Node écrit dans le catalogue une information montrant que Tk est en cours de traitement sur DBi et initialise un timeout. A l’expiration du timeout, le TM Node déclenche une procédure de détection, et choisit en parallèle un autre DBMS Node DBj pour l’exécution de Tk. Si la détection révèle qu’on a une panne de nœud, on marque (avec un flag) que le DBMS Node DBi est en panne. S’il s’agit d’une panne de communication, le TM Node peut temporairement écarter le DBMS Node DBi des candidats à l’exécution des futures et proches transactions. La durée de la mise à l’écart d’un nœud (en cas de panne de communication) dépend de la nature des réseaux (ou la localisation géographique) et ne fait pas partie de notre présent travail. Nous supposons par la suite que cette durée de mise à l’écart est connue et est identique pour tous les nœuds, quelque soit leur localisation géographique.
A la réception d’un accusé de traitement de la part du DBMS Node avant la fin du timeout, le TM Node regarde si la transaction a été bien exécutée. A l’affirmatif, il met à jour le catalogue. Dans le cas contraire, on relance l’exécution de la transaction Tk sur un autre DBMS Node et marque le premier comme étant en panne (du moins suspecté d’être en panne).
Chaque TM Node dispose d’une liste locale SL de nœuds suspects. Tout DBMS Node en panne de communication avec lui est mis dans cette liste, ce qui lui permet de ne pas les prendre en compte dans ces traitements futurs. Une tâche de fond peut s’assurer périodiquement de vérifier les communications rétablies pour actualiser la liste. Il en est de même pour les DBMS Nodes en panne et signalés au niveau du catalogue.

Validation différée des transactions

A la section 3.2, il a été souligné qu’il pouvait arriver qu’un DBMS Node garde en mémoire, des messages de notification de fin de traitement, à défaut de ne pas s’assurer de la bonne réception de ceux-ci par les TM Nodes initiateurs. Alors, ces messages de notificationdoivent être envoyés selon le mécanisme de piggybacking. En d’autres termes, les messages sont annexés à un des messages envoyés à un TM Node.
Par la suite, lorsqu’un TM Node TMi reçoit plus d’un message de notification, il rétablit la cohérence du catalogue en validant toutes les transactions concernées par ces messages différés. En effet, pour chacune des notifications annexées, comme la transaction correspondante a été lancée par un TM Node TMj il y a au moins une durée égale à la durée d’un timeout, on peut distinguer les cas suivants :

Le TM Node TMj

avait reçue la notification de validation et avait faits tous les traitements nécessaires au niveau du catalogue mais n’avait pas pu envoyer d’acquittement au DBMS Node. Dans ce cas la notification est ignorée, et un acquittement sera envoyé au DBMS Node pour qu’il ne bufférise pas de nouveau la notification.
Le TM Node TMj n’a pas reçu de message de notification et à l’expiration du timeout il a déjà relancée la transaction sur un autre DBMS Node. Dans ce cas, le TM Node TMi s’appuie sur le catalogue pour prendre une décision. S’il est écrit que la transaction est toujours en cours d’exécution sur le DBMS Node, il valide la transaction si et seulement si la notification révèle une réussite totale de l’exécution.
Sinon, il efface complètement l’écriture de traitement en cours. Par contre, si on a marqué que la transaction a été validée sur le DBMS Node alors on sait que le TM Node TMjavait reçu l’accusé de traitement et on ne fait rien.Pour limiter le nombre d’accès au catalogue, on peut imposer aux TM Nodes de n’effectuer aucun traitement pour les accusés de traitement arrivant après leurs timeout. Par ailleurs, pour accélérer la procédure de détection, un TM Node peut envoyer un message « ping » à un DBMS Node pour savoir s’il est actif avant de lui envoyer la transaction à exécuter. Ainsi s’il ne reçoit pas de message « pong », il lance une procédure de détection de panne de nœud ou de communication et en même temps choisit un autre DBMS Node pour l’exécution. Cependant, dans un environnement fortement volatile où les pannes sont fréquentes, il peut se produire assez souvent une panne entre l’envoi d’une commande « ping » et celui de la transaction à exécuter. En plus le nombre de commandes « ping » augmente la charge du système, ce qui surcharge rapidement un système à large échelle.

Algorithme

A la réception d’une transaction, tout TM Node appelle l’algorithme

Select_DB(Exc_List : liste de DBMS Nodes), elle choisit un DBMS Node selon sa charge, sa fraîcheur… Elle ne prend pas en compte les DBMS Nodes contenus dans la liste Exc_List.
Envoi_requete(DB : DBMS Node, T : Transaction, Cl : Client Node), elle envoie la transaction T au DBMS Node DB pour qu’il l’exécute et inscrit dans le catalogue que le traitement de T est en cours sur DB.
Initialise(tt : timeout), elle initialise un timeout.
Receive_reponse(DB : DBMS Node, T : transaction, tt : timeout, etat : boolean, list_ACK_T : liste d’accusés de traitement), c’est une fonction bloquante mais avecun temps d’attente donné et à la fin duquel elle renvoie false, sinon, ce qui suppose qu’on a reçue une réponse entre temps, elle renvoie true, et etat prend la valeur de l’accusé envoyé par le DBMS Node.
Run_Node_failure_detection(DB : DBMS Node), comme expliqué quelques lignes en haut, cette fonction lance la détection de pannes de nœud. En cas de panne avérée, le nœud en question ne sera plus pris en compte dans les traitements futurs jusqu’à ce qu’il soit rétablit.
Delete_of _Nodes_liste(DB : DBMS Node), elle supprime le DBMS Node DB de la liste des métadonnées portant sur les nœuds actifs.
Envoi_ACK(DB : DBMS Node), elle envoie un acquittement au DBMS Node DB.
Taille(list : Liste d’accusés de traitement), elle renvoie le nombre d’éléments de la liste.
Traiter(list : Liste d’accusés de traitement), chaque accusé de la liste est recherché, au niveau du catalogue, dans la liste notifiant les traitements en cours d’exécution. S’il y apparaît, le traitement est signalé validé ou annulé selon le contenu de l’accusé.
Déjà_archiver(DB : DBMS Node, T : Transaction), renvoie true si la transaction T exécutée par le nœud DB est déjà archivée sinon on a false.
Archiver(DB : DBMS Node, T : Transaction), elle archive la transaction T exécutée par le nœud DB.
Suspect_List, c’est une liste de DBMS Nodes suspectés en panne.

Diagramme de processus UML de notre traitement

Cette section est une récapitulation de notre procédure de traitement. Nous représentons ici le diagramme de processus UML de notre protocole de traitement de transactions tolérantaux pannes dans une base de données à large échelle. Nous faisons une abstraction des nœuds du catalogue que nous considérons peu dans cette étude.

Conclusion

La tolérance aux pannes s’appuie sur la détection dans ses solutions optimistes. La détection, compromis entre les propriétés de justesse et de complétude, est difficile à mettre en œuvre avec la non fiabilité des réseaux de communication, il en découle qu’aucune solution de tolérance aux pannes n’est parfaite. Notre solution de détection se base principalement sur les échanges de messages du type « ping/pong » mais n’utilise pas les envois périodiques de messages de détection de pannes. Au contraire, c’est à l’échec de la demande d’un service à un DBMS Node que le processus de détection est lancé, ceci diminue considérablement le nombre de messages dans un environnement à large échelle mais évidemment retarde la détection. A la détection d’une panne, le nœud concerné n‘est plus pris en compte par la suite dans les traitements effectués par les TM Nodes à moins qu’il s’agisse d’une panne de communication où seul le TM Node ayant déclenché le processus de détection ne considère plus le DBMS Node concerné dans ses traitements futurs.