💻 Consensus Distribué

Un quorum est le nombre minimum de nœuds qui doivent participer à une décision pour garantir que deux quorums quelconques se chevauchent d'au moins un nœud. Pour un cluster de N nœuds, le quorum Raft est floor(N/2) + 1. Avec cinq nœuds, cela donne floor(5/2) + 1 = 3. Cette propriété de chevauchement garantit que deux majorités quelconques partagent un nœud qui a vu l'état validé le plus récent, empêchant deux leaders contradictoires de valider indépendamment des entrées conflictuelles et de briser la cohérence.

Paxos, décrit par Leslie Lamport dans son article de 1989 « The Part-Time Parliament » (publié en 1998), est souvent considéré comme l'algorithme de consensus canonique mais est notoirement difficile à comprendre et à implémenter complètement car de nombreux détails pratiques restent implicites. Raft, conçu par Diego Ongaro et John Ousterhout et publié en 2014, décompose le problème en trois sous-problèmes largement indépendants (élection de leader, réplication de journal, et sûreté) et utilise un leader fort unique pour simplifier le raisonnement. Des études empiriques ont montré que les étudiants et ingénieurs comprennent Raft significativement plus vite que Paxos alors que les deux offrent des garanties de tolérance aux pannes équivalentes.

Les fautes byzantines sont la classe de pannes la plus sévère : un nœud ne se contente pas de planter et de rester silencieux mais envoie des messages activement incorrects, incohérents ou malveillants à différents pairs. Un protocole tolérant aux fautes byzantines (BFT), tel que PBFT ou la variante HotStuff utilisée dans de nombreuses blockchains, peut tolérer jusqu'à floor((N-1)/3) nœuds byzantins, nécessitant au moins 3f+1 nœuds pour gérer f traîtres. Cela est plus coûteux que la tolérance aux pannes de type crash de Raft (qui ne nécessite que 2f+1 nœuds pour f pannes) mais est essentiel dans des environnements ouverts et hostiles comme les réseaux blockchain où les participants ne peuvent pas être fiables.

Raft a été créé par Diego Ongaro dans le cadre de sa thèse de doctorat à l'université de Stanford sous la direction de John Ousterhout. L'article fondateur, « In Search of an Understandable Consensus Algorithm », a été présenté à USENIX ATC en juin 2014 et a remporté le prix du meilleur article. L'objectif déclaré d'Ongaro était explicite : concevoir un algorithme de consensus dont la principale vertu est la compréhensibilité, facilitant la construction d'implémentations correctes par les praticiens par rapport au formalisme dense de Paxos.

Raft est utilisé dans etcd (le magasin clé-valeur qui est l'épine dorsale de l'état des clusters Kubernetes), HashiCorp Consul (maillage de services et configuration), CockroachDB et TiKV (SQL distribué), et InfluxDB. Paxos (ou les protocoles dérivés de Paxos) sous-tend Google Chubby, Google Spanner et Apache Zookeeper. Les variantes de consensus byzantin alimentent des moteurs de consensus blockchain tels que Tendermint (Cosmos), HotStuff (Libra/Diem), et les registres autorisés basés sur PBFT. Amazon DynamoDB utilise une approche de type Raft pour ses groupes de réplication internes.

Une idée fausse courante est que tuer des nœuds pourrait faire perdre des entrées déjà validées. Dans Raft, cela ne peut pas se produire tant qu'un quorum de nœuds survit : une entrée n'est marquée validée qu'après que le leader ait reçu un accusé de réception d'une majorité, et la propriété de sûreté d'élection de Raft garantit que tout futur leader doit avoir au moins un nœud de cette majorité dans son propre quorum, il détiendra donc toujours l'entrée validée. Les données ne peuvent être définitivement perdues que si tant de nœuds tombent en panne simultanément qu'aucun quorum ne survit — pour cinq nœuds, cela signifie perdre trois nœuds ou plus à la fois.

Le théorème CAP d'Eric Brewer (formalisé par Gilbert et Lynch en 2002) énonce qu'un système distribué ne peut pas garantir simultanément la Cohérence, la Disponibilité et la tolérance au Partitionnement : lors d'une partition réseau, vous devez choisir l'un ou l'autre. Raft et Paxos choisissent CP — pendant une partition, le côté minoritaire devient indisponible plutôt que de risquer de servir des données obsolètes ou incohérentes. Les magasins à cohérence éventuelle comme Apache Cassandra choisissent AP, restant disponibles pendant les partitions mais servant potentiellement des lectures obsolètes. Ce simulateur démontre directement le choix CP : la partition isolée N4/N5 cesse de servir des requêtes plutôt que de diverger de la majorité.

La recherche active se concentre sur plusieurs directions : le consensus géodistribué à latence réduite utilisant Flexible Paxos et des variantes optimisées pour le WAN ; les protocoles sans leader tels qu'EPaxos et Atlas qui permettent à n'importe quel nœud de valider des commandes non conflictuelles en parallèle, éliminant le goulot d'étranglement du leader ; les protocoles de reconfiguration qui ajoutent ou suppriment des nœuds en toute sécurité sans arrêter le système ; et l'intégration avec des environnements d'exécution matériels de confiance (Intel TDX, AMD SEV) pour réduire le coût de la tolérance aux fautes byzantines. Dans l'espace blockchain, les protocoles BFT à preuve d'enjeu comme Gasper d'Ethereum continuent d'évoluer vers un débit plus élevé et une vérifiabilité formelle.