Consensus et algorithmes répartis¶

Comment N machines se mettent d'accord sur une valeur quand le réseau est impredictible — le problème du consensus et ses solutions pratiques.

Le problème du consensus¶

Le consensus distribué est la capacité pour un ensemble de nœuds a s'accorder sur une valeur unique malgre les pannes. Il faut satisfaire trois propriétés :

• Validity — la valeur décidée a été proposee par un nœud participant (pas une valeur sortie de nulle part)
• Agreement — tous les nœuds corrects décident la même valeur
• Termination — tous les nœuds corrects finissent par décider

Le théorème FLP : l'impossibilite fondamentale¶

En 1985, Fischer, Lynch et Paterson ont prouve qu'il est impossible de résoudre le consensus de manière deterministe dans un système asynchrone ou même un seul nœud peut tomber en panne. Ce résultat, dit "FLP impossibility", est contre-intuitif mais fondamental.

Intuitivement : dans un système asynchrone pur, on ne peut pas distinguer un nœud lent d'un nœud mort. Si on attend indéfiniment une réponse, on ne termine pas (violation de Termination). Si on décidé sans la réponse, le nœud "lent" pourrait revenir avec une valeur différente (violation d'Agreement).

Contournements pratiques :

Le théorème CAP en complement¶

CAP (Brewer, 2000) etablit qu'un système distribué ne peut garantir simultanément que deux des trois propriétés suivantes : Consistency (tous les nœuds voient la même donnée), Availability (chaque requête reçoit une réponse), Partition tolérance (le système fonctionne même si le réseau se partitionne).

Les partitions réseaux sont incontournables en production — CAP se réduit a choisir entre CP (Consistency + Partition tolérance, ex: etcd, HBase) et AP (Availability + Partition tolérance, ex: DynamoDB, Cassandra).

Election de leader¶

Avant tout protocole de consensus, il faut souvent désigner un nœud coordinateur — le leader — charge d'orchestrer les décisions. L'election de leader est elle-même un problème de consensus.

L'algorithme de Bully¶

L'algorithme de Bully (Garcia-Molina, 1982) elit le nœud avec l'identifiant le plus élevé encore actif. Quand un nœud détecté l'absence du leader, il lance une election :

1. Il envoie un message ELECTION a tous les nœuds avec un ID supérieur au sien
2. Si aucun ne répond dans un timeout : il se déclaré leader et broadcast COORDINATOR
3. Si un nœud supérieur répond : il prend la main et recommence à l'étape 1
4. Tout nœud qui reçoit un COORDINATOR met à jour son leader local

Complexité : O(n²) messages dans le pire cas. Adapté aux clusters de taille modeste (< 100 nœuds). Utilisée historiquement dans certaines implémentations de MongoDB et de systèmes de base de données embarqués.

Problèmes :

• Un nœud qui redémarrage fréquemment peut continuellement se proclamer leader (il à le plus grand ID)
• Ne toléré pas les pannes de type "réseau lent mais nœud vivant" — le nœud peut être evince a tort

Ring election¶

Variante ou les nœuds sont arranges en anneau logique. Chaque nœud passe un token d'election a son voisin. Plus légère (O(n) messages) mais plus lente a converger.

Paxos : le protocole fondateur¶

Paxos, introduit par Lamport en 1989 (publie en 1998), est le premier protocole de consensus formellement prouve correct. Il est notoire pour être difficile à comprendre — Lamport lui-même a écrit un article appelé "Paxos Made Simple" après que sa version originale fut jugee trop formelle.

Les trois rôles¶

Proposer — propose une valeur. Orchestre le protocole en deux phases. Acceptor — vote pour accepter ou rejeter des propositions. Learner — apprend la valeur décidée sans participer au vote.

En pratique, chaque nœud joue les trois rôles simultanément.

Une ronde Paxos détaillée¶

Phase 1 : Préparé

1. Le proposer choisit un numéro de proposition n unique et croissant
2. Il envoie Prepare(n) a une majorité d'acceptors
3. Chaque acceptor répond Promise(n, v_accepte) ou v_accepte est la dernière valeur acceptee (si elle existe), et promet de ne plus accepter de proposition < n

Phase 2 : Accept 4. Si le proposer reçoit des promesses d'une majorité :

• Si un acceptor a déjà accepte une valeur, le proposer DOIT proposer cette valeur

• Sinon, il peut proposer sa propre valeur

• Il envoie Accept(n, v) a une majorité d'acceptors

• Chaque acceptor accepte si n est toujours le plus grand numéro vu

Décision : quand une majorité d'acceptors ont accepte la même valeur, elle est décidée.

Raft : le consensus lisible¶

Raft, introduit par Ongaro et Ousterhout en 2014, vise les mêmes garanties que Paxos mais avec une conception délibérément plus comprehensible. La these de doctorat d'Ongaro comprend même une animation interactive du protocole.

Raft decompose le consensus en trois sous-problèmes indépendants :

1. Election de leader — choisir un leader unique
2. Log réplication — le leader accepte les entrees et les répliqué
3. Safety — garantir qu'une entree commitee ne peut jamais être perdue

Termes et état¶

Raft divise le temps en termes (terms) numerotes. Chaque terme commence par une election. Un nœud peut être dans l'un de trois états : Follower, Candidate, ou Leader.

Chaque nœud maintient un log — une sequence d'entrees numerotees. Une entree est "commitee" quand elle a été répliquée sur une majorité de nœuds.

Election de leader dans Raft¶

sequenceDiagram
    participant F1 as Follower-1
    participant F2 as Follower-2 (candidat)
    participant F3 as Follower-3
    participant L as Nouveau Leader

    Note over F2: Timeout election expire\n(pas de heartbeat du leader)
    F2->>F2: Passe en Candidate\nIncremente le terme
    F2->>F1: RequestVote(terme=2, log_index=5)
    F2->>F3: RequestVote(terme=2, log_index=5)
    F1-->>F2: Vote accorde
    F3-->>F2: Vote accorde
    Note over F2: Majorite atteinte (2/3)\nDevient Leader
    F2->>F1: Heartbeat(terme=2)
    F2->>F3: Heartbeat(terme=2)
    Note over F2: F2 est maintenant L

Règles d'election :

• Un follower devient candidat après un timeout aléatoire (150-300ms typiquement)
• Il vote pour le candidat dont le log est au moins aussi à jour que le sien
• Un candidat ayant reccu des votes d'une majorité devient leader
• Les timeouts aléatoires évitent les elections simultanées répétées

Réplication de log dans Raft¶

Une fois leader elu, le flux normal est :

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower-1
    participant F2 as Follower-2

    C->>L: Requete d'ecriture ("set x=5")
    L->>L: Ajoute au log (index 42, terme 2)
    L->>F1: AppendEntries(index=42, terme=2, entry="set x=5")
    L->>F2: AppendEntries(index=42, terme=2, entry="set x=5")
    F1-->>L: Succes (replique en index 42)
    F2-->>L: Succes (replique en index 42)
    Note over L: Majorite (2/2 followers)\nEntree commitee
    L->>L: Applique "set x=5" a la state machine
    L-->>C: Reponse succes
    L->>F1: Prochain heartbeat avec commitIndex=42
    L->>F2: Prochain heartbeat avec commitIndex=42
    F1->>F1: Applique "set x=5"
    F2->>F2: Applique "set x=5"

Garantie de safety¶

Raft garantit qu'une entree commitee ne peut jamais être perdue, même après des elections. Cela repose sur la propriété Log Matching : si deux logs ont une entree avec le même index et le même terme, tous les entrees précédentes sont identiques.

Un candidat ne peut devenir leader que si son log est au moins aussi à jour que celui de la majorité. Si une entree est commitee (répliquée sur une majorité), tout futur leader aura necessairement cette entree dans son log.

Raft vs Paxos¶

Horloges vectorielles¶

Dans un système distribué, il n'y a pas d'horloge globale. Les horloges physiques des nœuds divergent. Lamport a propose en 1978 les horloges logiques pour établir une relation de causalite entre événements.

Horloges de Lamport¶

Chaque nœud maintient un compteur L. Règles :

• Avant chaque événement local : L = L + 1
• Avant d'envoyer un message : inclure L dans le message
• À la reception d'un message avec timestamp T : L = max(L, T) + 1

Si l'événement A précédé causalement l'événement B, alors timestamp(A) < timestamp(B). Mais la reciproque est fausse : deux événements avec timestamps ordonnes peuvent être concurrents (non causalement lies).

Horloges vectorielles¶

Les horloges vectorielles (Fidge, Mattern, 1988) capturent la concurrence exactement. Chaque nœud maintient un vecteur de N compteurs, un par nœud du système.

from dataclasses import dataclass, field

@dataclass
class VectorClock:
    node_id: str
    nodes: list
    clock: dict = field(default_factory=dict)

    def __post_init__(self):
        self.clock = {n: 0 for n in self.nodes}

    def tick(self):
        """Evenement local."""
        self.clock[self.node_id] += 1
        return dict(self.clock)

    def send(self) -> dict:
        """Incrementer avant envoi."""
        self.clock[self.node_id] += 1
        return dict(self.clock)

    def receive(self, remote_clock: dict):
        """Merger l'horloge recue."""
        for node, ts in remote_clock.items():
            self.clock[node] = max(self.clock.get(node, 0), ts)
        self.clock[self.node_id] += 1

    def happens_before(self, vc_a: dict, vc_b: dict) -> bool:
        """True si vc_a -> vc_b (a precede causalement b)."""
        return (
            all(vc_a[n] <= vc_b[n] for n in self.nodes) and
            any(vc_a[n] < vc_b[n] for n in self.nodes)
        )

    def concurrent(self, vc_a: dict, vc_b: dict) -> bool:
        """True si vc_a et vc_b sont concurrents."""
        return (
            not self.happens_before(vc_a, vc_b) and
            not self.happens_before(vc_b, vc_a)
        )

nodes = ["A", "B", "C"]
vc_a = VectorClock("A", nodes)
vc_b = VectorClock("B", nodes)

# A fait un evenement
t1 = vc_a.tick()        # A: {A:1, B:0, C:0}

# A envoie a B
msg = vc_a.send()       # A: {A:2, B:0, C:0}
vc_b.receive(msg)       # B: {A:2, B:1, C:0}

# B fait un evenement local concurrent
t_b_local = vc_b.tick() # B: {A:2, B:2, C:0}

# A fait un evenement independant
t_a_local = vc_a.tick() # A: {A:3, B:0, C:0}

# Ces deux evenements sont concurrents :
# t_b_local = {A:2, B:2} vs t_a_local = {A:3, B:0}
# Ni l'un ne precede l'autre causalement

Les horloges vectorielles sont utilisées dans les bases de données distribuées pour détecter les conflits d'écriture concurrents. DynamoDB utilise des "version vectors" (variante des horloges vectorielles) pour identifier les conflits et les retourner au client pour résolution.

Détection de pannes¶

Savoir qu'un nœud est mort est crucial — et difficile. Dans un système asynchrone, un nœud "lent" et un nœud "mort" sont indiscernables sans timeout.

Heartbeat¶

Le mécanisme le plus simple : chaque nœud envoie périodiquement un signal de vie. Si on ne reçoit pas de heartbeat dans un délai T, le nœud est considéré mort.

Problèmes du heartbeat simple :

• Trop agressif : un pic de charge réseau ou CPU généré de faux positifs d'échec
• Trop conservateur : la détection est lente, allongeant le temps de recovery

Phi Accrual Failure Detector¶

Utilisé par Cassandra (emprunte a Akka), le phi accrual failure detector remplacé le seuil binaire "mort/vivant" par une valeur continue phi (φ) représentant la probabilite d'échec.

L'algorithme maintient un historique des intervalles entre heartbeats. En supposant une distribution normale (ou exponentielle) des intervalles, il calcule la probabilite que le nœud soit mort etant donne le temps ecoule depuis le dernier heartbeat.

• phi < 1 : nœud certainement vivant
• phi ~ 8 : probabilite d'échec de 99.999999%
• phi > seuil configuré (typiquement 8-12) : nœud marque comme mort

L'avantage : le detecteur s'adapté automatiquement aux variations de latence réseau. Un réseau lent généré des intervalles plus longs, le modèle s'ajuste, et le seuil effectif de détection s'adapté sans reconfiguration manuelle.

SWIM Protocol¶

SWIM (Scalable Weakly-consistent Infection-style Membership, Das et al., 2002) est une alternative gossip-based utilisée par HashiCorp Consul, Serf et la couche membership de Kubernetes.

Principe :

1. Chaque nœud choisit périodiquement un nœud aléatoire et lui envoie un ping direct
2. Si pas de réponse dans un délai, il demande a K autres nœuds de faire un ping indirect (ping-req)
3. Si le ping indirect échoué aussi, le nœud est marque "suspect"
4. Après un timeout sans confirmation de vie, le nœud est declared "dead" et l'info se propagé en gossip

Avantages de SWIM :

• Complexité O(log n) pour la propagation de l'information de panne
• Robuste aux pertes de paquets (ping indirect)
• Scalable a des milliers de nœuds (pas de messages broadcast)

Applications en production¶

etcd : Raft comme primitive¶

etcd est un store clé-valeur distribué utilisant Raft nativement. C'est le cerveau de Kubernetes — il stocke l'état complet du cluster (pods, services, configmaps). Chaque écriture dans etcd passe par un round Raft complet : proposee au leader, répliquée sur une majorité des membres etcd, puis commitee.

Un cluster etcd standard a 3 ou 5 membres (jamais pair — la majorité doit être un entier). Avec 3 membres, le système toléré 1 panne. Avec 5 membres, il en toléré 2.

ZooKeeper : ZAB ~ Paxos¶

Apache ZooKeeper utilisé ZAB (ZooKeeper Atomic Broadcast), un protocole similaire à Paxos avec des propriétés d'ordre total. ZooKeeper garantit que tous les nœuds voient les updates dans le même ordre. Utilisé par Kafka (jusqu'à la version 2.8) pour le metadata management et les elections de contrôleur.

Depuis Kafka 3.x, KRaft (Kafka Raft) remplacé ZooKeeper, éliminant cette dépendance externe et reduisant la complexité opérationnelle.

Kafka : ISR et election de leader¶

Kafka maintient un ISR (In-Sync Replicas) — l'ensemble des répliqués dont le log est à jour avec le leader. Une écriture est commitee quand toutes les répliqués de l'ISR l'ont confirmee (configurable via acks=all).

Si le leader tombe, un nouveau leader est elu parmi les ISR — garantissant qu'aucune entree commitee n'est perdue. Si toutes les ISR sont mortes, Kafka peut être configuré pour attendre (garantie forte) ou elire n'importe quelle répliqué (disponibilité au prix de possibles pertes de données).

CockroachDB : Raft par range¶

CockroachDB divise les données en ranges de ~64 MB chacun. Chaque range est géré par son propre groupe Raft indépendant. Un cluster de 10 nœuds peut avoir des milliers de groupes Raft actifs simultanément — chacun avec son propre leader, son propre log, ses propres elections.

Cette architecture permet de paralliser massivemen le throughput (chaque range progresse independamment) tout en maintenant des garanties de consistency fortes (chaque range est ACID via Raft).

Recap¶