Présentation

Sujet : Consesus Protocol

Enseignants : D. Donsez, GP. Bonneau

Auteur : Rama CODAZZI

Introduction

Le problème du consensus est peut-être le problème majeur en application répartie et possède un intérêt certain, autant sur le plan pratique que théorique.

Le problème du consensus peut être rapidement définit, de manière informelle, de la façon suivante : «Soit un ensemble de processus, chacun proposant une valeur, trouver un protocole réparti afin de mettre tous les processus d’accord sur une des valeurs proposées initialement».

L’intérêt d’un tel protocole vient du fait que, si nous étions capable de résoudre le problème du consensus, nous serions alors capable d’implémenter des services tolérants aux fautes. En pratique pour mettre en place un système tolérant aux fautes, il suffit de répartir le calcul sur plusieurs ordinateurs.

Ainsi, si l’un d’entre eux vient à tomber en panne, le système continuera à marcher de manière transparente, les autres ordinateurs continuant à fournir le service. La principale difficulté d’un tel schéma, est qu’il est nécessaire de s’assurer de la cohérence du service, et pour cela tous les ordinateurs doivent effectuer les différents calculs dans le même ordre.

Propriétés du Consensus

Propriétés des Consensus

Accord : la valeur décidée est la même pour tous les processus corrects

Intégrité : tout processus décide au plus une fois (sa décision est définitive)

Validité : la valeur décidée est l’une des valeurs proposées

Terminaison : tout processus correct décide au bout d’un temps fini

Type de défaillance d'un processus

Arrêt (crash failure ou panne franche) : le processus fonctionne correctement jusqu’à un point où il cesse définitivement d’agir.

Omission
- omission en émission : le processus omet certaines émissions qu’il aurait dû faire, ou cesse définitivement.
- omission en réception : le processus ignore certains messages en réception, ou cesse définitivement.

Arbitraire (byzantine failure) : le processus ment (par omission ou par contenu arbitraire des messages envoyés)

Mise en place de l'Algorithme paxos

Les hypothèses

Communication
- Asynchrone
- Pas d’altération de messages
- Possibilité de pertes
Processus
- Nombre fixe
- Fautes franches avec possibilité de reprise (crash-recovery). Chaque processus possède un état persistant

Principe de algorithme Paxos

Repose sur un leader (utilisation d’un détecteur Ω)

Le leader démarre un nouveau “ballot” (i.e.,ronde, vue, scrutin)
Cherche à joindre une majorité d’agents
- Les agents rejoigne toujours les “ballots” les plus récents (ignore les “ballots” anciens)
- Deux phases :
  - Collecter les résultats des scrutins (ballot) précédents de la part d’une majorité d’agent
  - Puis proposer une nouvelle valeur, et obtenir une majorité pour l'approuver
L’algorithme s’arrête si il existe un leader unique pendant les 2 tours d’échanges avec une majorité de d’agents

un balot est de la forme : Paire <num, process_id>

Le leader courant p choisit localement un numéro unique croissant : –Si le dernier ballot connu est <n, q> alors p choisit <n+1, p>

Exemple d’exécution

Il y a 3 phases lors de l’exécution de l’algorithme :

Phase 1 : Préparation (Prepare)
- Objectif : demander à joindre le tour (ballot) courant et collecter les informations des décisions passées

Phase 2 : Acceptation
- Le leader reçoit une majorité de ACK avec et renvoie un accept à tous
- les autres process reçoivent le accept et le renvoie à tous

Phase 3 : Décision

Remarques :

Il peut y avoir plusieurs leader concurrents
Les numéros de ballot permettent de distinguer les valeurs proposées par les différents leader

Fig. 1 : Exemple d’exécution avec 1 leader

Fig. 1 : Exemple d’exécution avec un client

Lien avec Zookeeper

Zookeper utilise un protocole différent que Paxos mais il partage avec lui quelques aspect clés :

Un leader propose une valeur à tout les autres process
le leader attend les ack d'un maximum d'autres process avant d'envoyer un demande de changement de valeur
l'utilisation des Ballots

Un exemple d’implémentation

Principe

"

Zookeeper fonctionne en fournissant un espace mémoire partagé par toutes les instances d’un même ensemble de serveurs Zookeeper. Cet espace mémoire est hiérarchique, à la manière d’un système de fichier composé de répertoires et de fichiers à la différence que, dans le cas de Zookeeper, on ne parle pas de répertoires et de fichiers mais de nœuds. Chaque nœud s’appelle un ZNode.

Cette hiérarchie de nœuds va se répliquer et se synchroniser sur tous les serveurs créé par Zookeeper.

Le fonctionnement d’un ensemble Zookeeper nécessite l’élection d’un leader parmi les instances qui le composent. Lorsqu’un client écrit/modifie des données dans les ZNodes, c’est le leader qui effectue l’opération puis la transmet aux autres membres. Une fois qu’un certain nombre d’instances ont appliqué l’opération, cette dernière est considérée comme valide au sein de l’ensemble Zookeeper.

Ledit nombre est appelé le quorum. Comme lors d’une élection au sein d’un groupe de personnes, le quorum représente le nombre minimum d’instances Zookeeper pour qu’une décision (typiquement, décider si la valeur affectée dans un ZNode est validée sur l’ensemble Zookeeper) soit prise par l’ensemble Zookeeper.

Le calcul du quorum s’effectue selon la formule suivante : quorum = n/2

avec n le nombre de serveurs présents dans l’ensemble Zookeeper sachant que l’on arrondira toujours le résultat à la valeur supérieure (par exemple 3/2 = 1.5 => quorum = 2) on ajoute +1 si la valeur ne représente pas une majorité stricte (par exemple 2/2 = 1 => quorum = 2)

Installation en local d’un ensemble de 1 Zookeeper

Tout d'abord, nous allons creer une instance standalone

Après avoir créé un fichier config et choisi le port client tel que si dessous :

tickTime=2000

//dataDir : attention changer avec votre path vers votre tmp qu’il faudra créer si vous le placez comme moi dans le répertoire d’installation de zookeeper //

dataDir=[chemin d'acces]/zookeeper-3.4.6/tmp clientPort=2181

Il suffit de démarer le serveur à l'aide de la commande

./zkServer.sh start

Puis de nous y connecter

bin/zkCli.sh -server 127.0.0.1:2181

Il faut maintenant creer un noeud et lui associer une valeur :

create /xebia hello

On obtient alors un Znode /xebia associé à la valeur hello

Installation en local d’un ensemble de 3 Zookeepers

Déplaçons notre instance dans un repertoire nommé zookeeper-1 pour plus de lisibilité

Il faut modifier le fichier de configuration afin de dire comment les serveurs doivent communiquer entre eux.

tickTime=2000

ATTENTION : changer dataDir et n’oubliez pas de créer le répertoire tmp

dataDir=[chemin]/zookeeper-1/tmp clientPort=2181 server.1=localhost:2888:3888 server.2=localhost:2889:3889 server.3=localhost:2890:3890 initLimit=5 syncLimit=2

Dans un autre terminal se connecter sur une autre instance de notre ensemble, par exemple sur le serveur 2 :

./zookeeper-2/bin/zkCli.sh -server 127.0.0.1:2182

puis modifier la valeur affectée au ZNode xebia:

set /xebia world

on constate que le watcher s’est déclenché :

WATCHER::

WatchedEvent state:SyncConnected type:NodeDataChanged path:/xebia

Cela montre la synchronisation et la réplication des données dans notre ensemble Zookeeper. Maintenant nous allons tester la réelection d’un leader dans notre ensemble.

La première chose à faire est de connaître le leader en cours dans notre ensemble. Pour cela, nous utilisons la commande suivante pour chaque serveur :

Cela nous donnera, dans l’ordre, l’affectation de chacun de nos serveur comme follower ou leader. Dans mon cas, par exemple, j’ai obtenu la réponse suivante :

Mode: follower Mode: follower Mode: leader

Nous allons stopper le serveur leader en utilisant le résultat de la commande précédente. Ici, le serveur 3 était le leader :

./zookeeper-3/bin/zkServer.sh stop

Puis, on relance sur notre ensemble, maintenant composé de 2 instances, la commande suivante :

echo stat | nc localhost 2181 | grep Mode && echo stat | nc localhost 2182 | grep Mode

Résultat :

Mode: follower Mode: leader

Ici, je constate que le serveur 2 est devenu le leader.

Si finalement nous stoppons un serveur supplémentaire nous allons tomber à un seul élément dans notre ensemble Zookeeper initialement composé de 3 et dont le quorum dans ce cas est de 2. Par conséquent, cela devrait avoir des conséquences négatives sur notre ensemble. Vérifions cela:

./zookeeper-2/bin/zkServer.sh stop

La réponse est :

This ZooKeeper instance is not currently serving requests

Notre ensemble zookeeper est hors service !

Redémarrons le serveur 2 :

./zookeeper-2/bin/zkServer.sh start

Interrogeons de nouveau l’état du serveur 2 :

echo stat | nc localhost 2181

Mode: follower Mode: leader

et nous pouvons voir que notre ensemble Zookeeper est de nouveau up !

Conclusion

Le problème du consensus est très complexe mais certains algorithmes permettent d'en la plupart des cas, le résoudre.

Une autre solution consiste à utiliser un détecteur de faute, mais c'est un autre sujet :D

Consesus Protocol

Contents