Membership dans un système distribué

Cet article aborde la notion de membership et les algorithmes possibles pour aborder cette problématique. Ces notes se basent sur la spécialisation coursera Cloud Computing.

Membership

L'objectif est de maintenir une liste de processus appartenant à un groupe.

La principale difficulté provient du fait que l'erreur est la norme et non un cas d'exception.

Les cibles d'un tel algorithme comprennent :

  • Les clouds et datacenters
  • Serveurs répliqués
  • Bases de données distribuées

Pour la suite de cet article, nous utiliserons un modèle de "Fail-Stop" : un process en échec s'arrête et n'essaye pas de processus de reprise d'erreur. Il doit alors rejoindre à nouveau le groupe.

Le protocole de membership maintient une liste de membres à jour. On se base sur un réseau qui peut ne pas être fiable.

Deux composants sont nécessaires à un tel algorithme :

  • Un détecteur de défaillances
  • Une dissémination de l'information

Détection des défaillances

On cherche ici à détecter les systèmes défaillants.

Les propriétés recherchés sont les suivantes :

  • Complétude : toutes les défaillances doivent être détectées.
  • Exactitude : pas de faux positifs
  • Rapidité : les défaillances doivent être détectées rapidement
  • Passage à l'échelle : pas d'overhead sur les messages, même charge sur tout le système

Implémentations simples

Pour chacune de ces implémentations, chaque nœud incrémente un numéro de séquence.

La première implémentation consiste pour chaque nœud à envoyer un heartbeat à intervalle régulier vers un nœud centralisé. Cette implémentation bien que simple provoque une charge importante sur le nœud de monitoring. Un autre problème survient lorsque le nœud de monitoring devient défaillant.

Une seconde implémentation consiste à structurer le réseau en anneau. Chaque nœud envoie un heartbeat vers ses voisins. Le problème d'un tel système est qu'il n'est pas tolérant aux multi-failures.

Enfin, il peut aussi exister une implémentation en diffusion totale où chaque nœud envoie un heartbeat à tous les nœuds.

Gossip membership

Cet algorithme se base sur un Heartbeat en diffusion totale que l'on adapte avec un algorithme gossip.

  • Chaque nœud maintient une liste des nœuds du groupe dans une table. Chaque ligne contient l'identifiant/l'adresse du nœud, le numéro de sequence (incrémenté par le nœud à chaque heartbeat), et le temps local de la dernière détection.
  • Périodiquement, chaque nœud envoie sa liste de nœuds à n autres nœuds tirés aléatoirement.
  • À réception d'un message de gossip, un nœud fusionne sa liste de membres de la façon suivante :
    • Si l'id de séquence reçu est plus grand, on met à jour la ligne correspondante à la date de réception avec ce numéro de séquence.
    • Si le numéro de séquence est inférieur à celui stocké, notre entrée est plus à jour alors on ignore l'information
    • Deux informations timeouts sont nécessaires : un pour marquer une défaillance, l'autre pour supprimer une entrée marquée comme défaillante. Ce dernier est nécessaire pour éviter de rajouté un nœud marqué comme défaillant mais supprimé prématurément.

Algorithme SWIM

Le protocole SWIM (Scalable Weakly-consistent Infection style process group Membership protocol) offre une approche plus légère que les algorithmes précédents.

Ici, chaque processus de détection effectue un ping vers un processus à vérifier.

  • Si un ACK est reçu, aucun traitement n'est nécessaire
  • Si aucune réponse n'est reçue, le processus de détection envoie un ping à n autres processus pour qu'ils le transmettent au processus cible. Les réponses sont acheminées via le même chemin. Si aucune réponse n'est reçue, le processus est considéré comme défaillant.

Dissémination

La liste des membres du groupe doit être propagé à tous les nœuds du réseau. 3 possibilités existent pour disséminer l'information.

  • Utiliser le Multicast ID. Cette approche n'est pas très fiable.
  • Envoi direct point à point (TCP ou UDP). Très coûteux.
  • En embarquant l'information dans les messages de détection.

Dans le cas de SWIM, la propagation de l'information des groupes prend un temps en O(log(N)).

Mécanisme de suspicion

Afin d'éviter au maximun les faux-positifs, il est possible d'utiliser un état intermédiaire "suspect" avant de marquer un processus comme défaillant. Afin d'éviter les bagotages entre les états actifs et suspects, le processus suspect incrémente un compteur qui est utilisé pour marquer un processus comme suspect que lorsque le compteur reçu par le monitoring est supérieur au compteur que l'on garde en mémoire.

Post a Comment

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*