CAP, PACELC & Au-Delà : Les Théorèmes Qui Façonnent les Systèmes Distribués

Chaque base de données distribuée, file de messages et architecture microservices est contrainte par une poignée de théorèmes fondamentaux. Les comprendre évite de poursuivre des conceptions impossibles et permet de faire des compromis explicites.

Le Théorème CAP

Formulé par Eric Brewer (2000), prouvé par Gilbert & Lynch (2002).

Un système de stockage distribué peut fournir au plus deux des trois garanties simultanément :

• Cohérence — chaque lecture retourne l'écriture la plus récente (linéarisabilité)
• A (Availability) Disponibilité — chaque requête reçoit une réponse sans erreur (pas de timeout)
• P (Partition tolérance) Tolérance aux partitions — le système continue de fonctionner malgré les partitions réseau

Pourquoi « choisissez-en deux » est trompeur

Les partitions réseau vont se produire. Vous ne choisissez pas de les tolérer — vous devez. Le vrai choix pendant une partition est donc :

Quand il n'y a pas de partition (le cas normal), vous pouvez avoir C et A. CAP ne contraint le comportement que pendant une panne.

        Fonctionnement normal     Pendant une partition
        ┌───────────┐            ┌───────────┐
        │  C + A    │            │  C ou A   │
        │  (les 2!) │            │(choisir 1)│
        └───────────┘            └───────────┘

Idées reçues courantes

Le Théorème PACELC

Daniel Abadi (2012) a étendu CAP pour couvrir le cas normal (pas de partition) :

S'il y a une Partition, choisir entre A (Disponibilité) et Cohérence. E (sinon), choisir entre Latence et Cohérence.

C'est plus pratique car la plupart du temps il n'y a pas de partition, et le vrai compromis est latence vs cohérence.

L'insight clé

La plupart des bases de données vous permettent d'ajuster votre position sur ce spectre par requête ou par table. DynamoDB propose des lectures éventuellement cohérentes (rapides, pas chères) et des lectures fortement cohérentes (plus lentes, 2x le coût). Le niveau de cohérence de Cassandra peut être défini par requête.

Modèles de Cohérence

« Cohérence » signifie différentes choses selon le contexte. Voici la hiérarchie de la plus forte à la plus faible :

Stricte / Linéarisabilité

Le standard absolu. Chaque opération semble s'exécuter atomiquement à un point entre son invocation et sa réponse, et tous les processus voient le même ordre.

Coût : Nécessite de la coordination (protocoles de consensus). Haute latence. Qui la fournit : Spanner (TrueTime), CockroachDB, etcd, ZooKeeper.

Cohérence Séquentielle

Tous les processus voient les opérations dans le même ordre, et les opérations de chaque processus apparaissent dans l'ordre du programme. Mais l'ordre global peut ne pas correspondre à l'ordre en temps réel.

Coût : Moins cher que la linéarisabilité, nécessite encore un ordonnancement.

Cohérence Causale

Si l'opération A précède causalement l'opération B (A happened-before B), alors tous les processus voient A avant B. Les opérations concurrentes (pas de lien causal) peuvent être vues dans n'importe quel ordre.

Coût : Modéré. Peut être implémentée sans coordination globale. Qui la fournit : MongoDB (sessions causales), certains systèmes basés sur les CRDTs.

Cohérence Éventuelle

Si aucune nouvelle mise à jour n'est faite, toutes les répliques convergent éventuellement vers la même valeur. Aucune garantie d'ordonnancement pendant la convergence.

Coût : Le moins cher. Disponibilité et performance maximales. Qui la fournit : Cassandra (ONE), DynamoDB (défaut), DNS, caches CDN.

Cohérence Read-your-writes

Un client voit toujours ses propres écritures. Les autres ne les voient pas forcément immédiatement.

Coût : Faible. Peut être obtenue avec du session stickiness. Qui la fournit : La plupart des bases de données peuvent être configurées pour cela.

Plus forte ────────────────────────────────── Plus faible

Linéarisable → Séquentielle → Causale → Read-your-writes → Éventuelle

Plus de coordination ──────────────── Moins de coordination
Plus haute latence ────────────────── Plus basse latence

Protocoles de Consensus

Comment des nœuds distribués se mettent-ils d'accord sur une valeur ? C'est le problème du consensus.

Le Résultat d'Impossibilité FLP

Fischer, Lynch, Paterson (1985) : Dans un système asynchrone, aucun protocole de consensus déterministe ne peut garantir la terminaison si même un seul processus peut tomber en panne. C'est pourquoi tous les protocoles de consensus pratiques utilisent des timeouts (hypothèse de synchronie partielle).

Paxos

Leslie Lamport (1989). Le protocole de consensus fondateur :

1. Prepare — le proposeur envoie un numéro de proposition aux accepteurs
2. Promise — les accepteurs promettent de ne pas accepter de propositions plus anciennes
3. Accept — le proposeur envoie la valeur, les accepteurs acceptent si aucune proposition plus récente
4. Learn — la valeur est choisie quand une majorité d'accepteurs est d'accord

Paxos est correct mais notoirement difficile à implémenter. Multi-Paxos l'étend pour un journal de valeurs.

Utilisé par : Google Chubby, Spanner original.

Raft

Diego Ongaro & John Ousterhout (2014). Conçu pour être compréhensible — mêmes garanties que Multi-Paxos mais avec une structure plus claire :

1. Élection du leader — les nœuds votent, un devient leader
2. Réplication du journal — le leader ajoute des entrées, les réplique aux suiveurs
3. Sûreté — les entrées committées ne sont jamais perdues

                 ┌──────────┐
       ┌────────►│ Suiveur  │
       │         └──────────┘
┌──────┴───┐     ┌──────────┐
│  Leader   │────►│ Suiveur  │
└──────┬───┘     └──────────┘
       │         ┌──────────┐
       └────────►│ Suiveur  │
                 └──────────┘
Le leader réplique les entrées du journal vers tous les suiveurs.
Commit quand la majorité acquitte.

Utilisé par : etcd, CockroachDB, TiKV, Consul, RabbitMQ Quorum Queues.

Viewstamped Réplication (VR)

Similaire à Raft (antérieur), utilisé par certains systèmes en interne. Même modèle basé sur un leader.

Tolérance aux Fautes Byzantines (BFT)

Gère les nœuds qui mentent activement ou se comportent de manière malveillante (pas seulement crash). PBFT (Practical BFT) nécessite 3f+1 nœuds pour tolérer f nœuds défaillants. Beaucoup plus coûteux — principalement utilisé dans la blockchain et les systèmes haute sécurité.

Le Problème des Deux Généraux

L'illustration la plus simple de l'impossibilité d'un accord distribué avec une communication non fiable :

Deux généraux doivent s'accorder sur l'heure d'une attaque. Ils communiquent par messager à travers le territoire ennemi (les messages peuvent être perdus). Aucun protocole avec un nombre fini de messages ne peut garantir l'accord.

C'est pourquoi TCP utilise un three-way handshake — il ne résout pas le problème, il rend simplement l'échec suffisamment improbable pour un usage pratique.

Horloges Vectorielles & Happened-Before

La relation « happened-before » de Leslie Lamport (1978) définit l'ordonnancement causal dans les systèmes distribués :

• Si A et B sont dans le même processus et A survient avant B, alors A → B
• Si A est l'envoi d'un message et B sa réception, alors A → B
• Si A → B et B → C, alors A → C (transitivité)

Les horloges vectorielles tracent cette relation :

Processus P1 : [2, 0, 0]  — P1 a fait 2 événements
Processus P2 : [1, 3, 0]  — P2 a vu l'événement 1 de P1 et fait 3 des siens
Processus P3 : [1, 2, 1]  — P3 a vu P1:1, P2:2, et fait 1 des siens

Si le vecteur A ≤ vecteur B composante par composante → A est arrivé avant B. Si ni A ≤ B ni B ≤ A → les événements sont concurrents (pas de relation causale).

Utilisé pour : Détection de conflits dans les bases Dynamo-style, CRDTs, suivi de versions.

CRDTs — Types de Données Répliquées Sans Conflit

Structures de données qui peuvent être répliquées entre nœuds et fusionnées sans conflits, quel que soit l'ordre de réception des mises à jour.

Utilisé dans : Redis CRDT (Redis Enterprise), Riak, Automerge (édition collaborative), Figma, Apple Notes.

Quand les CRDTs brillent

• Applications offline-first qui synchronisent plus tard
• Bases de données multi-régions avec écritures locales
• Édition collaborative (texte, outils de design)
• Edge computing où la coordination est coûteuse

Le Théorème CALM

Consistency As Logical Monotonicity (Hellerstein, 2010) :

Un programme peut être rendu éventuellement cohérent (sans coordination) si et seulement si il est monotone — il ne fait qu'ajouter de l'information, jamais en retrancher.

Monotone : Compteurs, ensembles (ajout seul), journaux, accumulateurs. Non monotone : Garbage collection, contraintes globales, livraison « exactly once ».

Cela vous dit quelles parties de votre système peuvent être AP (tout ce qui est monotone) et lesquelles doivent impliquer de la coordination (tout ce qui nécessite négation ou rétractation).

Cadre de Décision Pratique

Choisir la cohérence pour votre service

Ajustement par opération

De nombreux systèmes permettent de choisir la cohérence par requête :

# DynamoDB — forte vs éventuelle par lecture
table.get_item(Key={"id": "123"}, ConsistentRead=True)   # forte
table.get_item(Key={"id": "123"}, ConsistentRead=False)  # éventuelle (défaut, 2x moins cher)

# Cassandra — cohérence par requête
session.execute(query, consistency_level=ConsistencyLevel.QUORUM)  # forte
session.execute(query, consistency_level=ConsistencyLevel.ONE)     # rapide

Ressources

• Designing Data-Intensive Applications — Chapitres 5, 7, 8, 9 couvrent tout cela
• L'algorithme de consensus Raft — Visualisation interactive
• [Jepsen.io](�0� — Tests de systèmes distribués de Kyle Kingsbury (vérifications de réalité pour chaque base de données)
• CAP Twelve Years Later — La propre revisitation d'Eric Brewer
• Modèles de cohérence — Diagramme de la hiérarchie de cohérence de Jepsen
• CRDTs: The Hard Parts (Martin Kleppmann)

:::