Paxos et Raft

Paxos et Raft sont les deux protocoles de consensus pratiques les plus influents, assurant un accord tolérant aux pannes par crash sur un journal répliqué qui sous-tend les systèmes de coordination réels.

Definition

Paxos et Raft sont des protocoles basés sur le quorum qui permettent à un ensemble de répliques de s'accorder sur une séquence ordonnée de commandes (un journal répliqué) malgré des pannes par crash, garantissant que les entrées validées ne sont jamais perdues ou réordonnées tant qu'une majorité de répliques restent disponibles.

Scope

Ce sujet couvre la famille Paxos — Paxos à décret unique, Multi-Paxos et ses raffinements d'ingénierie — ainsi que le protocole Raft, qui réorganise les mêmes garanties autour d'un leader explicite, de la réplication de journaux et du changement d'appartenance pour une meilleure compréhensibilité. Il aborde les rôles des proposants/accepteurs et des leaders/suiveurs, l'intersection des quorums, l'élection et les termes du leader, la correspondance des journaux, et les préoccupations pratiques liées aux instantanés et à la reconfiguration.

Core questions

• Comment l'intersection des quorums et la numérotation des propositions assurent-elles la sécurité de Paxos à travers les cycles et les changements de leader ?
• Comment Raft décompose-t-il le consensus en élection de leader, réplication de journal et sécurité ?
• Quels défis d'ingénierie surgissent lors de la transformation de ces protocoles en systèmes de production ?

Key theories

Paxos à décret unique et Multi-Paxos

Paxos parvient à un accord sur une valeur unique à travers des phases de préparation et d'acceptation régies par des numéros de proposition monotones et des quorums majoritaires ; Multi-Paxos amortit la phase de préparation sur un flux de décisions menées par un leader stable pour construire un journal répliqué.

Décomposition de Raft

Raft atteint la même sécurité que Paxos en élisant un leader unique par terme, en faisant en sorte que le leader ajoute des entrées que les suiveurs répliquent, et en imposant une propriété de correspondance des journaux, échangeant délibérément la minimalité contre la compréhensibilité et la facilité d'implémentation.

De la spécification au système en fonctionnement

Le déploiement de Paxos en pratique nécessite la gestion des pannes de disque, des baux de leader, de la compaction des journaux et de la reconfiguration, des détails souvent passés sous silence dans l'algorithme original mais essentiels à la correction et à la performance.

Clinical relevance

Paxos et Raft sont utilisés au sein de services de coordination, de bases de données distribuées et de magasins de configuration largement répandus ; leur compréhension est essentielle pour construire ou exploiter tout système qui doit maintenir une forte cohérence entre les répliques malgré les défaillances.

History

Lamport a décrit Paxos dans son article de 1998 intitulé « part-time parliament » et l'a clarifié dans « Paxos made simple » (2001) ; Chandra et ses collègues ont rapporté les réalités de sa mise en œuvre à grande échelle en 2007 ; et Ongaro et Ousterhout ont introduit Raft en 2014 pour rendre des garanties équivalentes beaucoup plus faciles à enseigner et à implémenter.

Debates

Compréhensibilité versus minimalité dans les protocoles de consensus

Raft a été explicitement conçu pour être plus facile à comprendre que Paxos, ce qui a suscité un débat sur la question de savoir si sa structure additionnelle (un leader fort) sacrifie la flexibilité ; les partisans soutiennent que la compréhensibilité réduit les bogues d'implémentation, tandis que d'autres notent que les variantes de Paxos peuvent être plus générales.

Key figures

• Leslie Lamport
• Diego Ongaro
• John Ousterhout
• Tushar Chandra

Seminal works

• lamport1998
• ongaro2014
• chandra2007

Frequently asked questions

Paxos et Raft sont-ils des algorithmes fondamentalement différents ?

Non — ils résolvent le même problème avec le même noyau de quorum majoritaire et des garanties de sécurité équivalentes. Raft réorganise principalement Paxos autour d'un leader fort et d'un journal explicite pour rendre le protocole plus facile à comprendre et à implémenter.