Meilleure réponse
Cet article fournit une explication et une preuve dune clarté saisissante: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Je vais essayer de fournir un résumé clair ici:
Lobjectif de la Lalgorithme de Paxos permet à un certain nombre de pairs de parvenir à un accord sur une valeur. Paxos garantit que si un pair estime quune certaine valeur a été approuvée par une majorité, la majorité jamais daccord sur une valeur différente. Le protocole est conçu de telle sorte que tout accord doit disparaître via une majorité de nœuds. Toute tentative future daccord, si elle réussit, doit également passer par au moins lun de ces nœuds. Ainsi: Tout nœud qui propose une fois quune décision a été prise doit communique avec un nœud majoritaire. Le protocole garantit quil apprendra les ag reed sur la valeur de cette majorité.
Voici comment cela fonctionne:
Supposons que nous ayons 3 nœuds, A, B et C. A aimerait proposer le value « Foo ».
Lalgorithme fonctionne en 3 phases. A chaque phase, laffirmation dune majorité de nœuds doit être atteinte.
Tout dabord, nous avons la phase de préparation. A envoie une demande de préparation à A, B et C. Paxos sappuie sur les numéros de séquence pour réaliser ses garanties. La demande de préparation demande à un nœud de promettre: « Je naccepterai jamais aucune proposition avec un numéro de séquence inférieur à celui de la demande de préparation. » Les nœuds répondent avec toute valeur quils ont préalablement acceptée (le cas échéant). (Et ceci est dune importance cruciale): Le nœud A doit proposer la valeur quil reçoit avec le numéro de séquence le plus élevé. Cette action fournit la garantie que les valeurs précédemment convenues seront préservées.
Ensuite, nous avons la phase dacceptation. A envoie une demande dacceptation à A, B et C. La demande dacceptation indique: » Acceptez-vous foo? » Si le numéro de séquence daccompagnement nest pas en dessous de ce que le nœud avait précédemment promis ou si le nœud a précédemment accepté, il acceptera la nouvelle valeur et le numéro de séquence.
Si le nœud A reçoit accepte de une majorité de nœuds, la valeur est décidée. Cette ronde de Paxos ne sera jamais daccord sur une autre valeur.
La troisième phase nest pas strictement nécessaire, mais est cruciale optimisation dans toute implémentation Paxos en production. Une fois que A reçoit la majorité des acceptations, il envoie les messages décid à A, B et C. Ces messages permettent à tous les pairs de savoir quune valeur a été choisie et accélèrent la fin du processus de décision.
Sans ce message, les autres pairs devraient tenter de proposer une valeur pour prendre connaissance de laccord. Au cours de la phase de préparation, ils « apprendraient la valeur précédemment convenue. Une fois cet accord mené à son terme, le nœud reconnaîtrait laccord.
Jai passé en revue quelques points clés ici:
- Tous les numéros de séquence doivent augmenter de façon monotone et uniques par nœud . Autrement dit, A et B ne peuvent pas tous les deux envoyer un message avec le numéro de séquence k. Tous les messages envoyés dans le protocole incluent des numéros de séquence. Un nœud doit suivre la demande dacceptation la plus élevée quil a vue ainsi que la valeur la plus élevée quil a promise dans la phase de préparation.
- Conditions déchec. Il est tout à fait possible quune série de Paxos échoue. En cas déchec, un nœud tente simplement de proposer à nouveau avec un numéro dordre supérieur.
- Conditions de terminaison. La version de Paxos que jai décrite ne se termine pas nécessairement. Quelques ajustements sont nécessaires pour une preuve formelle de résiliation.
Réponse
Puisque Paxos parvient à un consensus, il peut également être utilisé pour répliquer les écritures dans une base de données distribuée car il peut garantir un ordre cohérent des événements entre tous les nœuds dun groupe. Chubby by Google utilise Paxos pour servir des fichiers fortement cohérents. Cest de là que découle la confusion. Quelle est alors la relation entre la synchronisation des vues et les paxos si les deux peuvent être utilisés pour la réplication?
Petite histoire: Lamport a introduit le concept de réplication de machine détat au début des années 80. La réplication de machine détat signifie quun système délivre des événements dans le même ordre à tous les nœuds et quils sont traités de manière déterministe, garantissant des états cohérents sur tous les nœuds du groupe. Cependant, au moment où ce concept a été introduit, il impliquait toutes sortes dhypothèses, y compris le réseau étant synchrone.La réplication de la machine détat est donc restée simplement un outil théorique sans utilisation pratique. La synchronisation des vues a été introduite à ce stade et visait à assurer la cohérence en ne faisant pas de telles hypothèses. Lobjectif était de disposer dun système pratique offrant de telles garanties.
La publication de Paxos a eu lieu alors que le travail sur la synchronisation des vues était en cours. Paxos pourrait réaliser la réplication de la machine à états car les répliques pourraient désormais convenir de lordre dexécution des demandes des clients à laide de cet algorithme de consensus. Paxos na fait aucune hypothèse de réseau synchrone ou de pannes. Paxos a également fourni un protocole dappartenance au groupe. Les différences qui subsistaient maintenant entre la synchronisation de la vue et Paxos étaient uniquement dans la manière dont les abstractions étaient formulées. Les deux fournissent une adhésion dynamique et gèrent les échecs de la même manière. Les différences ne sont vraiment que dans le modèle. Quelques différences qui peuvent être mises en évidence sont:
- Virtual Synchrony a un protocole dappartenance à un groupe simple par rapport à Paxos. Virtual Synchrony exécute lappartenance au groupe comme un service distinct.
- Paxos peut progresser dans certains cas de partition où la synchronisation virtuelle se bloque.
- Virtual Synchrony est plus rapide que les Paxos contemporains.
Les deux systèmes ont évolué et convergé . Dans létat actuel des choses, il est très difficile de faire des différences significatives entre les deux.
Lalith explique clairement le protocole Virtual Synchrony et souligne à juste titre que Paxos ou toute autre variante de consensus peut être utilisé dans la synchronisation des vues. Outre le consensus, Paxos fournit lappartenance à un groupe et dautres fonctionnalités que la synchronisation virtuelle fournit déjà. Comme la synchronie virtuelle et Paxos offrent les mêmes garanties et ont été développés à peu près au même moment, la spécification de la synchronie virtuelle nutilise pas Paxos pour le consensus. Le modèle de synchronisation virtuelle utilise cependant le protocole denvoi totalement ordonné (également connu sous le nom dABCAST) pour réaliser la diffusion atomique et un autre protocole pour mettre à jour les vues de groupe et ceux-ci peuvent être considérés comme la variante de consensus quil utilise.
Il peut être intéressant de noter que le modèle dexécution ISIS-2 combine le modèle Paxos avec le modèle de synchronisation virtuelle, non pas pour le consensus mais pour la prise en compte de lappartenance à un groupe en tant que service séparé dans Paxos. Cela rend Paxos plus rapide dans les cas où ladhésion ne change pas de manière dynamique. En combinant Virtual Synchrony et Paxos, ISIS2 est capable de sauter certaines étapes que les Paxos typiques doivent effectuer. En substance, Paxos et Virtual Synchrony sont des modèles différents pour obtenir la même fonctionnalité et peuvent être combinés entre eux pour réaliser des variantes ou des optimisations.