Difference between revisions of "Consesus Protocol"

From air
Jump to navigation Jump to search
Line 92: Line 92:
 
[[File:Paxos2.PNG||600px|thumb|center|Fig. 1 : Exemple d’exécution avec un client]]
  
[[File:Paxos2.PNG||600px|thumb|center|Fig. 1 : Exemple d’exécution avec un client]]
   
−
== Lien avec Zookeeper ==
 +
= Lien avec Zookeeper =
  +
−
Is Zab just a special implementation of Paxos?
  
  +
Zookeper utilise un protocole différent que Paxos mais il partage avec lui quelques aspect clés :
−
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
  
  +
* Un leader propose une valeur à tout les autres process
−
Leaders wait for acknowledgements from a quorum of followers before considering a proposal committed (learned)
  
  +
*le leadear attend les ack d'un maximum d'autres process avant d'envoyer un demande de changement de valeur
−
Proposals include epoch numbers, which are similar to ballot numbers in Paxos
  
  +
* l'utilisation des Ballots
−
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.
  
   
 
== Un exemple d’implémentation ==
  
== Un exemple d’implémentation ==

Revision as of 08:32, 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 leadear 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

tuto zookeeper

Abstract

Synthèse

Conclusion

Références

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