Revision as of 10:02, 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 3 Zookeepers

Tout d'abord, nous allons creer une instance standalone

Après avoir créé un fichier config et choisi le port client

<note> 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=/Users/jbc/Developments/zktest/zookeeper-3.4.6/tmp clientPort=2181 </note>

@@ Line 101: / Line 101: @@
 == Un exemple d’implémentation ==
+=== Principe ===
 "
@@ Line 117: / Line 119: @@
 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 3 Zookeepers ===
+Tout d'abord, nous allons creer une instance standalone
+Après avoir créé un fichier config et choisi le port client
+<note>
+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=/Users/jbc/Developments/zktest/zookeeper-3.4.6/tmp
+clientPort=2181
+</note>
-"
 =Conclusion=

Difference between revisions of "Consesus Protocol"