Difference between revisions of "Consesus Protocol"

From air
Jump to navigation Jump to search
 
(21 intermediate revisions by one other user not shown)
Line 1: Line 1:
−
==Présentation==
 +
=Présentation=
   
 
Sujet : Consesus Protocol
  
Sujet : Consesus Protocol
Line 7: Line 7:
 
Auteur : Rama CODAZZI
  
Auteur : Rama CODAZZI
   
−
==Introduction==
 +
=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 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.
Line 17: Line 17:
 
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.
  
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=
−
== Exemple d'une erreur ==
  
   
  +
== Propriétés des Consensus ==
−
== Mise en place de l'Algorithme paxos ==
  
   
  +
*Accord : la valeur décidée est la même pour tous les processus corrects
−
== Exemple avec le cas de l'erreur ci dessus ==
  
   
  +
*Intégrité : tout processus décide au plus une fois (sa décision est définitive)
−
== Lien avec Zookeeper ==
  
  +
−
Is Zab just a special implementation of Paxos?
  
  +
*Validité : la valeur décidée est l’une des valeurs proposées
−
No, Zab is a different protocol than Paxos, although it shares with it some key aspects, as for example:
  
  +
−
A leader proposes values to the followers
  
  +
*Terminaison : tout processus correct décide au bout d’un temps fini
−
Leaders wait for acknowledgements from a quorum of followers before considering a proposal committed (learned)
  
  +
−
Proposals include epoch numbers, which are similar to ballot numbers in Paxos
  
  +
== Type de défaillance d'un processus ==
−
The main conceptual difference between Zab and Paxos is that it is primarily designed for primary-backup systems, like Zookeeper, rather than for state machine replication.
  
  +
  +
*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
  +
  +
  +
[[File:Paxos1.PNG||600px|thumb|center|Fig. 1 : Exemple d’exécution avec 1 leader]]
  +
  +
[[File:Paxos2.PNG||600px|thumb|center|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 ==
  
== Un exemple d’implémentation ==
   
  +
=== Principe ===
−
tuto zookeeper
  
  +
"
  +
  +
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
  +
  +
[[File:Zookeeper.PNG]]
  +
  +
=== 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 :
  +
  +
'''echo stat | nc localhost 2181 | grep Mode && echo stat | nc localhost 2182 | grep Mode && echo stat | nc localhost 2183 | grep Mode'''
  +
  +
  +
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
−
==Abstract==
  
  +
Mode: leader'''
   
  +
et nous pouvons voir que notre ensemble Zookeeper est de nouveau up !
−
==Synthèse==
  
   
  +
=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
−
==Conclusion==
  
   
−
==Références==
 +
=Références=
−
- https://fr.wikipedia.org/wiki/Paxos_(informatique)
 +
* https://fr.wikipedia.org/wiki/Paxos_(informatique)
−
- https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab+vs.+Paxos
 +
* https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab+vs.+Paxos
−
- https://fr.wikipedia.org/wiki/Consensus_(informatique)
 +
* https://fr.wikipedia.org/wiki/Consensus_(informatique)
−
- http://www.tcs.hut.fi/Studies/T-79.5001/reports/2012-deSouzaMedeiros.pdf
 +
* http://www.tcs.hut.fi/Studies/T-79.5001/reports/2012-deSouzaMedeiros.pdf
  +
* http://blog.xebia.fr/2015/02/24/introduction-et-demystification-de-zookeeper/
−
- https://www-master.ufr-info-p6.jussieu.fr/2012/spip.php?action=acceder_document&arg=209&cle=c9f1b363ce1c738d7ca56551f12a02e50a01f020&file=pdf%2FConsensus-Paxos-ARA.pdf
  
  +
* https://www-master.ufr-info-p6.jussieu.fr/2012/spip.php?action=acceder_document&arg=209&cle=c9f1b363ce1c738d7ca56551f12a02e50a01f020&file=pdf%2FConsensus-Paxos-ARA.pdf
  +
* [http://research.google.com/archive/paxos_made_live.html Paxos Made Live – An Engineering Perspective], PODC '07: 26th ACM Symposium on Principles of Distributed Computing.

Latest revision as of 17:08, 6 November 2015

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

Zookeeper.PNG

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

  1. 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 :

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


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

Références

Retrieved from "https://air.imag.fr/index.php?title=Consesus_Protocol&oldid=25139"