Algorithmes de consensus

1) Qu'est-ce qu'un consensus et pourquoi il est nécessaire

Consensus - concilier la même valeur/séquence de valeurs entre plusieurs nœuds en cas de défaillance et de latence. Traditionnellement, le problème de la réplication d'état (State Machine Replication, SMR) est résolu : il y a une machine d'état déterministe et un ordre général des opérations.

• Consensus (SMR) : un ordre de commande total unique → stockage/registre linéarisé, métadonnées de cluster, coordinateurs transactionnels.
• Les opérations de quorum sans ordre total (Dynamo-like, CRDT) : permettent la divergence et la fusion ultérieure ; ne remplacent pas le consensus là où la sérialisation mondiale est nécessaire.

2) Modèle de temps et d'échec

2. 1 Modèle de temps

Réseau asynchrone : les retards sont illimités ; le théorème FLP est ⇒ impossible à garantir à la fois la sécurité et la liveness sans hypothèses supplémentaires.
Partiellement synchrone (souvent en pratique) : après un T inconnu, le système « se comporte » de manière synchrone - la plupart des algorithmes (Raft, Paxos) s'appuient précisément sur cela.
Synchrone : limites de temps de canal strictes (rarement en vente, sauf pour les réseaux spéciaux/PTP).

2. 2 Modèle de défaillance

Crash-fault tolérant (CFT) : les nœuds peuvent tomber/pendre, mais ne se comportent pas de manière malveillante.
Byzantine-fault tolérant (BFT) : les nœuds peuvent mentir/falsifier des messages. Il faut 3f + 1 nœuds pour tolérer f byzantin.

3) Propriétés du consensus

Sécurité (sécurité) : cohérence (deux nœuds corrects ne résoudront pas de valeurs différentes).
Liveness (survie) : si le réseau est « sain », la solution est atteinte.
Linéarité (linéarité) : les opérations sont « vues » comme atomiques dans un seul ordre.
Durabilité : les décisions prises ne sont pas annulées (protection par le journal/quorum).

4) Quorums, majorités et intersections

Dans le monde CFT, le classique : quorum> N/2. Les enregistrements et l'élection du leader utilisent l'intersection des quorums, de sorte que les deux opérations « valides » ne sont pas en conflit.
Dans le monde BFT : les quorums 2f + 1 sur 3f + 1 permettent l'intersection d'un minimum de f + 1 noeuds honnêtes.

Règle d'intersection : tout quorum doit avoir un nœud honnête (CFT) ou un ≥f+1 (BFT) ≥1 commun.

5) Réplication d'état (journal + application)

• Snapshots (une tranche d'état après laquelle les premiers enregistrements peuvent être supprimés/compactés).
• Compaction du magazine et du journal-triim.
• Vérification du déterminisme (même version du code/des configues).

6) Les schémas de leadership et de non-leadership

Leader (Raft, Multi-Paxos, ZAB) : un leader sérialise les enregistrements → plus facilement mentalement et de manière opérationnelle, mieux latitude sur un leader stable.
Sans Lider/Multilider (EPaxos, Caesar) : plus de parallélisme et de tolérance envers le leader, mais plus difficile à mettre en œuvre et à résoudre ; les profits sont visibles avec les petits conflits d'équipe.

7) Algorithmes CFT classiques

7. 1 Paxos/Multi-Paxos (et pratiques)

L'idée : deux phases (prepare/propose), les promesses des accepteurs, les quorums majoritaires. Multi-Paxos laisse un « leader stable » et transforme les opérations en opérations à un seul tour (pour les nouveaux enregistrements) après le « réchauffage ».

• Modèle flexible mais complexe à mettre en œuvre.
• Configurations à l'aide d'enregistrements spéciaux (joint consensus).
• En pratique, les bibliothèques/moteurs (Chubby/Spanner-generation).

7. 2 Raft

Décomposé pour l'apprentissage : sélection du leader, réplication des logs, ré-configuration.

Election : Temporisation aléatoire, vote des termes ; un leader pour un mandat.
AppendEntries : le leader de l'enregistrement, surveille la correspondance du préfixe (index/terme), commit sur la fixation majoritaire.
Read-path : lease-reads (avec un leader fort) ou read-index pour les lectures linéaires.
Reconfig : « co-configuration » (joint) - Les nœuds votent en deux clusters avant la transition.

Avantages : plus facile à développer/débaga, invariants forts de l'ordre. Points négatifs : le leader est le point de pression.

7. 3 ZAB (ZooKeeper Atomic Broadcast) / Viewstamped Replication (VRR)

ZAB : le leader diffuse des transactions, phase de récupération, zxid (epoque + index).
VRR : « espèces » (vues) avec réplicant primaire, semblable à Multi-Paxos dans l'esprit.

8) Non-lider/multilider CFT

8. 1 EPaxos

Pas de leader permanent : n'importe quel nœud peut initier une commande.
Les commandes de conflit reçoivent un ordre partiel ; sans conflit - communiquent en 1-2 RTT localement.
Gagnez en géo-distribution avec un faible conflit, mais des codes de dépendance/graphe complexes.

8. 2 Caesar, Mencius

Variations optimisant les retards/équilibrage et le fonctionnement dans le WAN.

9) algorithmes BFT et famille PoS

9. 1 PBFT (Practical BFT)

Trois phases (pre-prepare/prepare/commit), nécessite 3f + 1 nœuds.
Faible latence sur les réseaux locaux, les routes multidimensionnelles et les messages O (N ²).

9. 2 Tendermint (style BFT-PoS)

Rounds avec proposal et deux votes (prevote/precommit).
Validateur d'offre déterministe, temporisation, synchronisation partielle.
Bon pour les réseaux permissionnés/PoS avec des dizaines/centaines de validateurs.

9. 3 HotStuff (et dérivés)

Le schéma triphasé est unifié en « paquets » avec des certificats de quorum (QC).
La complexité linéaire des communications, le support du package et de la piplainisation parallèle sont faciles à mettre en œuvre dans les blockchain (par exemple, Diem/Move-écosystème).
Avec les signatures de seuil (signatures de seuil), le trafic est réduit.

9. 4 PoW/consensus cumulatif (en résumé)

Pas de BFT au sens strict, mais de convergence probabiliste (chaîne avec le plus de travail). Vertus : simplicité/ouverture ; défauts : énergie, ~ secondes-minutes avant la finale.

10) Lectures : Linéaires, successives et cachées

Lectures linéaires : leader avec lease active ou via l'index de lecture (Raft) → confirmation via quorum.
Cohérent : peut être lu à partir de n'importe quel nœud, mais sans garantie de fraîcheur.
Follower reads : acceptables avec des exigences faibles ; pour les caches - ok.

11) Configuration Re (changement de la composition du cluster)

Nécessite deux configurations se chevauchant (joint consensus) : tout commit passe par les quorums des deux configurations → sans « trous ».
Ajouter/supprimer un à la fois, respecter la taille du quorum.
Le transfert de leadership réduit les pauses.

12) Performance et tuning

12. 1 Retards

Algorithmes de leadership : 1 RTT par écriture (avec leader stable) + réplication.
Géo-distribution : WAN RTT domine → utilise des régions locales + transrégionales ou des approches EPaxos/HotStuff.

12. 2 Laissez-passer

Batching (groupement de commandes), parallèle à AppendEntries, page-cache du journal, application parallèle (lorsque les opérations sont commutées).
Disques : NVMe/Journal sur un périphérique distinct, 'O _ DIRECT '/AIO, grand' fsync' -interval avec des restrictions SLA (compromis durability/latency).

12. 3 Queues p99

Évitez les noeuds chauds (leader constamment seul) : rotation périodique ou read-offload sur les followers.
Surveiller les pauses GC (JVM/Go), les pins CPU, NUMA.

13) Géographie et topologie

1 région, 3 zones : cluster CFT classique (N = 3/5).
2 régions : éviter - ne pas obtenir un quorum fiable lors de la séparation 1-1.
3 + régions : leader dans le « milieu » ou algorithmes sans lien ; des fronts régionaux proxy/locaux avec un journal asynchrone sont possibles.

14) Questions pratiques d'exploitation

14. 1 Snapshots et récupération

Seuil en fonction de la taille du journal/du nombre d'opérations.
La transmission du snapshot aux nouveaux nœuds ; vérification des montants de référence.

14. 2 Surveillance

Leadership : qui est le leader, combien de mandats (term/epoch) ont changé.
Лаги: `append_latency`, `commit_index - applied_index`.

Quorum-santé : « La majorité/2f + 1 est-elle vivante ? »

Taille du journal/vitesse de compaction, file d'attente de snapshots.
Pour le BFT : part des voix, délaissement des signataires, retards de QC.

14. 3 Sécurité/cohérence du code

La versionalité du protocole sur le fil, la migration avec la compatibilité des journaux.
Jetons de fencing sur les effets externes (voir « Verrous distribués ») : période de leadership (term) à transmettre à CRON/jobs.

15) Anti-modèles

Mettre un consensus « pour la mode » là où il y a une base de données ou des lectures de quorum sans sérialisation.
Mélanger CP et AP sans limites claires (CAP) → UX imprévisible.
Surestimer PoW/PoS pour les tâches d'entreprise avec des dizaines de nœuds (difficile/coûteux).
Ignorer la configuration et les « quorums croisés » lorsque vous modifiez la composition.
Absence de lecture-barrier (lease/read-index) → lecture « sale ».
Exécutez des clusters à 2 nœuds (pas de majorité).
Sous-estimation des disques et fsync : « tout vole dans la mémoire » - avant le premier redémarrage.

16) Chèque de sélection

1. Modèle d'échec : CFT (peignes) ou BFT (malveillants) ?
2. Géographie : une région/trois zones ou WAN ? RTT décide.
3. Sémantique des lectures : faut-il des lectures linéaires ? Lease/read-index/follower reads.
4. Charge : attentes pour p50/p99, throughput ; Est-ce que le multi-leadership est nécessaire ?
5. Complexité opérationnelle : bibliothèque/moteur fini (etcd/ZK/Consul/Raft-libs) vs implémentation native.
6. Reconfiguration : fréquente ? J'ai besoin d'un consensus conjoint et d'outils de migration.
7. Intégrations : effets secondaires externes - y a-t-il un fencing par epoch/term ?
8. Sécurité : authentification des nœuds, cryptage des canaux, contrôle des versions du protocole.
9. Test-playbooks : partition, GC-stop, leader kill, slow disk, clock skew.
10. Observabilité : les métriques Leader/Lags/Journal et Alert sont personnalisées.

17) Mini-manuel : Quand prendre quoi

etcd/Raft-cluster pour les configurations/verrous/coordination au sein de DC.
ZooKeeper/ZAB pour les services déjà attachés à ZK (anciennes piles, files d'attente, leadership).
Multi-Paxos via un service/bibliothèque prêt dans des systèmes hautement spécialisés.
EPaxos en cas de géo-distribution et de faible conflit de commandes.
Tendermint/HotStuff pour réseaux autorisés/leyer PoS avec des dizaines à des centaines de validateurs et des exigences de finalité.
Dynamo-like/CRDT lorsque le consensus n'est pas nécessaire, mais la disponibilité/échelle est importante, suivie d'une fusion.

18) Exemples d'interfaces (pseudo)

18. 1 Commit d'enregistrement (style Raft)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18. 2 Index de lecture linéaire (Raft)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18. 3 Configuration collaborative

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18. 4 BFT (HotStuff-approximativement)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) FAQ

Q : Pourquoi ne pas utiliser deux nœuds et un tie breaker ?
R : Deux nœuds sans le troisième arbitre ne donnent pas le quorum à la séparation. Vous avez besoin de ≥3 (CFT) ou 3f + 1 (BFT).

Q : Qu'est-ce que le Raft « plus facile » Paxos ?
A : Décomposition claire, invariants compréhensibles de la loge et de la configuration ; plus facile à mettre en œuvre et à accompagner.

Q : Comment lire vite sans charger un leader ?
A : Follower-reads (successifs) pour les non critiques, ou lease-reads/read-index pour les linéaires ; mettez en cache.

Q : Qu'est-ce qui tue p99 ?
A : WAN-RTT, disques fsync, pieds GC, leader surchauffé, gros snapshots à l'heure de pointe.

Q : Avez-vous besoin d'un consensus pour le cache/catalogue ?
R : Si la consistance eventuelle est suffisante - non. Si des invariants transactionnels sont nécessaires, oui.

20) Résultats

Le consensus est un outil de cohérence et de rationalisation rigoureuses. Choisir un algorithme en fonction du modèle de défaillance et de la géographie ; fournir des intersections de quorum, une ré-configuration correcte, des lectures linéaires là où c'est critique et une observabilité. N'oubliez pas le fencing pour les effets externes, les snapshots et la discipline des magazines. La réplication de l'état sera alors prévisible et les incidents rares et compréhensibles.