Dans les algorithmes de consensus comme par exemple PAXOS et RAFT, une valeur est proposée, et si un quorum est d'accord, elle est écrite durablement dans le magasin de données. Qu'arrive-t-il aux participants qui n'étaient pas disponibles au moment du quorum? Comment finissent-ils par rattraper leur retard? Cela semble être laissé comme un exercice pour le lecteur où que je regarde.
3 Réponses :
Jetez un œil au protocole Raft. Il est simplement intégré à l’algorithme. Si le leader suit l'index le plus élevé ( matchIndex ) et le nextIndex à envoyer à chaque abonné, et qu'il envoie toujours des entrées à chaque abonné en commençant par le de cet abonné nextIndex , il n'y a pas de cas particulier nécessaire pour gérer le rattrapage d'un suiveur qui manquait lorsque l'entrée a été validée. De par sa nature, lorsque le redémarrage, le leader commencera toujours à envoyer des entrées à ce suiveur en commençant par la dernière entrée de son journal. Ainsi, le nœud est rattrapé.
Le leader est donc responsable de savoir quels clients manquaient, quel était leur état, etc., puis de le transmettre aux clients?
Avec les articles originaux de Paxos, il s'agit en effet d'un exercice pour le lecteur. En pratique, avec Paxos, vous pouvez envoyer des messages supplémentaires tels que des accusés de réception négatifs pour propager plus d'informations autour du cluster en tant qu'optimisation des performances. Cela peut être utilisé pour faire savoir à un nœud qu'il est en retard en raison de messages perdus. Une fois qu'un nœud sait qu'il est derrière, il doit rattraper ce qui peut être fait avec des types de messages supplémentaires. Cela est décrit comme Retransmission dans le Trex multi -paxos moteur que j'ai écrit à démystifier Paxos .
Le document Google Chubby paxos Paxos Made Live critique Paxos pour avoir laissé beaucoup de soin aux personnes chargées de la mise en œuvre. Lamport a suivi une formation de mathématicien et essayait de prouver mathématiquement que vous ne pouviez pas avoir de consensus sur les réseaux avec perte quand il a trouvé la solution. Les articles originaux fournissent une preuve qu'il est possible plutôt que d'expliquer comment construire des systèmes pratiques avec. Les papiers modernes décrivent généralement une application de certaines nouvelles techniques soutenues par des résultats expérimentaux, alors qu'ils fournissent également une preuve formelle, à mon humble avis, la plupart des gens la sautent et la prennent en confiance. La manière inaccessible dont Paxos a été introduit signifie que de nombreuses personnes qui citent le document original mais n'ont pas vu qu'elles décrivent élection de chef et multi-Paxos . Malheureusement, Paxos est toujours enseigné de manière théorique, pas dans un style moderne qui amène les gens à penser que c'est difficile et à en manquer l'essence.
Je soutiens que Paxos est simple mais il est difficile de raisonner sur les échecs d'un système distribué et de tester pour trouver des bogues. Tout ce qui reste au lecteur dans les articles originaux n'affecte pas l'exactitude mais affecte la latence, le débit et la complexité du code. Une fois que vous comprenez ce qui rend Paxos correct car il est mécaniquement simple, il est facile d'écrire le reste de ce qui est nécessaire d'une manière qui ne viole pas la cohérence lorsque vous optimisez le code pour votre cas d'utilisation et votre charge de travail.
Par exemple, Corfou et CURP donnent des résultats extrêmement élevés performances, l'un utilise Paxos uniquement pour les métadonnées, l'autre n'a besoin de faire Paxos que lorsqu'il y a des écritures simultanées sur les mêmes clés. Ces solutions ne se complètent pas directement avec Raft ou Multi-Paxos car elles résolvent des scénarios spécifiques de haute performance (par exemple, les magasins k-v). Pourtant, ils démontrent qu'il vaut la peine de comprendre que pour les applications pratiques, vous pouvez effectuer une énorme quantité d'optimisations si votre charge de travail particulière vous le permet tout en utilisant Paxos pour une partie de la solution globale.
Ceci est mentionné dans Paxos made Simple:
En raison de la perte de message, une valeur pouvait être choisie sans qu'aucun apprenant ne le découvre jamais. L'élève peut demander aux accepteurs quelles propositions ils ont acceptées, mais l'échec d'un accepteur pourrait rendre impossible de savoir si une majorité a accepté ou non une proposition particulière. Dans ce cas, les apprenants ne découvriront la valeur choisie que lorsqu'une nouvelle proposition est choisie. Si un apprenant a besoin de savoir si une valeur a été choisie, il peut demander à un proposant d'émettre une proposition, en utilisant l'algorithme décrit ci-dessus.
Et aussi en papier Raft:
Le leader gère un nextIndex pour chaque abonné, qui est l'index de la prochaine entrée de journal qu'il enverra à cet abonné.
Si le journal d'un suiveur n'est pas cohérent avec celui du leader, la vérification de cohérence AppendEntries échouera dans le prochain RPC AppendEntries. Après un rejet, le leader décrémente nextIndex et réessaye le RPC AppendEntries. Finalement, nextIndex atteindra un point où les journaux du leader et du suiveur correspondent. Lorsque cela se produit, AppendEntries réussit, ce qui supprime toutes les entrées en conflit dans le journal du suiveur et ajoute les entrées du journal du leader (le cas échéant).
Si un abonné ou un candidat plante, les futurs RPC RequestVote et AppendEntries qui lui seront envoyés échoueront. Raft gère ces échecs en réessayant indéfiniment; si le serveur en panne redémarre, le RPC se terminera avec succès.