Systèmes distribués : latence, partitions, cohérence

La question de départ

Vous envoyez un fichier de 5 Mo à un serveur lointain. Votre connexion annonce 40 Mbit/s. Combien de temps cela prendra-t-il ? Beaucoup répondent : « 5 Mo = 40 mégabits, donc une seconde ». C'est faux dès que le serveur est loin. Il manque la latence.

Deux grandeurs différentes

• Le débit (bandwidth) : combien de bits passent par seconde, en Mbit/s. C'est la largeur du tuyau.
• La latence : le temps pour qu'un message aille d'un point à l'autre. Souvent on parle du temps aller-retour (RTT, round-trip time). C'est la longueur du tuyau.

Un camion peut transporter une énorme quantité de données (grand débit) mais mettre une journée (grande latence). Un SMS est petit mais arrive vite.

Une limite physique

La lumière dans une fibre optique se propage à environ 200 000 km/s, soit à peu près les deux tiers de sa vitesse dans le vide. Ce n'est pas un défaut des opérateurs : cette limite vaut pour la fibre classique ; seule la vitesse de la lumière dans le vide est une borne absolue (des liaisons hertziennes ou à fibre creuse s'en approchent, sans la dépasser). Prenons deux centres de données hypothétiques distants de 6 000 km :

• aller simple : au minimum 6 000 ÷ 200 000 = 0,03 s = 30 ms ;
• aller-retour : au minimum 60 ms, en réalité davantage, car la fibre ne suit pas la ligne droite et les routeurs ajoutent des délais.

Exemple détaillé : le modèle simplifié de l'atelier

Durée totale = (nombre d'allers-retours d'établissement) × RTT + taille × 8 ÷ débit. Pour 5 Mo, 40 Mbit/s, RTT = 120 ms et 2 allers-retours d'établissement :

• transmission : 5 × 8 ÷ 40 = 1 s = 1 000 ms ;
• établissement : 2 × 120 = 240 ms ;
• total : 1 240 ms.

Divisez la taille par 10 (500 Ko) : la transmission tombe à 100 ms mais l'établissement reste à 240 ms. Pour les petits messages, c'est la latence qui domine ; pour les gros fichiers, le débit. Un message de consensus est petit : toute la vie d'un protocole de consensus est donc rythmée par les allers-retours.

Explorez l'outil request-path : DNS, TCP, TLS puis HTTP enchaînent plusieurs échanges avant que le premier octet utile ne circule. Le modèle est volontairement simplifié (il ignore par exemple les connexions réutilisées).

Le point essentiel : lent ou mort ?

Un nœud A envoie une demande à B et attend. Au bout de 2 secondes sans réponse, que sait A ? Rien de certain. B peut être en panne, le réseau peut avoir perdu le message, ou la réponse peut arriver dans 3 secondes. Depuis A, ces trois cas sont indiscernables. La seule arme est le délai d'attente (timeout), qui est une hypothèse, non une preuve : l'ajuster trop court déclare « mort » un nœud simplement lent ; trop long, il retarde toute réaction.

Ce que cela ne garantit pas

Un faible RTT mesuré ce matin ne garantit pas celui de demain. La latence varie (congestion, route modifiée) ; un protocole sérieux ne suppose pas de borne, ou l'assume explicitement comme hypothèse.

En bref

• Débit = largeur du tuyau, latence = sa longueur ; les petits messages sont dominés par la latence.
• La lumière dans la fibre impose un minimum d'environ 1 ms d'aller-retour par 100 km (ordre de grandeur).
• On ne peut pas distinguer un nœud lent d'un nœud mort ; un timeout est un pari.

La question de départ

Pour qu'un registre survive à la panne d'une machine, on le réplique : trois copies, A, B et C, sur trois sites. Un jour, le câble entre A et les deux autres est coupé. A, B et C fonctionnent toutes, mais A ne reçoit plus rien de B et C, et inversement. Que doit faire le système ?

Le concept : la partition

Une partition réseau est une situation où les nœuds sont divisés en groupes qui ne peuvent plus échanger de messages, alors que chaque nœud fonctionne. Elle peut venir d'un câble coupé, d'un routeur saturé, d'un pare-feu mal configuré, ou d'un attaquant. Vue de A, elle est semblable à une panne de B et C (leçon 1).

Exemple détaillé : un solde répliqué

Un compte de solde 100 est répliqué sur A, B, C. Partition : A est seule d'un côté ; B et C ensemble de l'autre.

• À 10:00, Aminata retire 80 en s'adressant à A.
• À 10:01, Bello, qui partage le compte, retire 80 en s'adressant à B.

Option 1 : tout le monde répond (disponibilité). A accepte (solde local 20), B accepte (solde local 20 sur B et C). Le réseau se rétablit : les deux retraits sont dans le journal, le solde « devrait » valoir 100 − 160 = −60. L'invariant « pas de solde négatif » est brisé ; il faut réconcilier (annuler un retrait ? découvert ?).

Option 2 : seule la majorité répond (cohérence). Une règle de quorum exige que 2 répliques sur 3 confirment toute opération. B et C (2 sur 3) ont le quorum et acceptent le retrait de Bello. A (1 sur 3) ne l'a pas : elle refuse de répondre à Aminata (« réessayez plus tard »). Aucun solde négatif, mais Aminata est bloquée.

Pourquoi les quorums fonctionnent : se chevaucher

Avec N répliques, si une écriture doit être confirmée par W répliques et une lecture interroge R répliques, avec R + W > N, toute lecture rencontre au moins une réplique à jour. Ici N = 3, W = 2, R = 2 : 2 + 2 > 3. Deux ensembles de 2 parmi 3 se chevauchent toujours (en un nœud au moins). Attention : R + W > N garantit seulement le chevauchement entre une lecture et une écriture. Pour interdire aussi deux écritures concurrentes sur des ensembles disjoints, il faut en plus 2W > N (ici 2 × 2 > 3, c'est le cas). Avec N = 5, W = 2 et R = 4, on a bien R + W > N, mais deux écritures de 2 répliques chacune peuvent être disjointes. Dans notre exemple, deux groupes disposant chacun d'un quorum d'écriture ne peuvent donc pas exister côte à côte.

Ce que chaque option sacrifie

Aucune option ne donne à la fois « tout le monde est servi » et « un seul état unique ».

À vous

Reproduisez le tableau avec un autre scénario : 5 répliques, une partition 2 | 3. Quelle moitié a le quorum (3 sur 5) ? Combien de répliques peuvent tomber en panne avant de perdre le quorum ?

Ce que cela ne garantit pas

Un quorum de lecture et d'écriture avec R + W > N garantit qu'une lecture voit la dernière écriture confirmée sous des hypothèses simples (pas de nœud fautif, protocole de lecture correct). Cela ne règle pas à lui seul les écritures concurrentes, ni les pannes qui surviennent en cours d'écriture : c'est le rôle des protocoles de consensus.

En bref

• Une partition coupe le réseau sans arrêter les machines ; chaque côté croit l'autre en panne.
• Soit on répond partout (et on réconcilie plus tard), soit on exige une majorité (et on bloque la minorité).
• Avec R + W > N, tout quorum de lecture rencontre un quorum d'écriture ; avec 2W > N, deux quorums d'écriture se rencontrent aussi.

La question de départ

On résume souvent CAP par « choisissez deux parmi trois : Cohérence, Disponibilité, tolérance aux Partitions ». Ce slogan est trompeur. Que dit réellement le théorème ?

L'énoncé précis

Les trois mots ont un sens strict :

• Cohérence (au sens de CAP) : la linéarisabilité. Le système se comporte comme s'il n'y avait qu'une seule copie, et toute lecture renvoie la dernière écriture terminée.
• Disponibilité : toute requête reçue par un nœud non défaillant reçoit une réponse (pas une erreur, pas un silence).
• Partition : le réseau peut perdre ou retarder arbitrairement des messages entre nœuds.

Le théorème (conjecture de Brewer, démontrée par Gilbert et Lynch en 2002 dans un modèle de réseau asynchrone) dit : lors d'une partition, un système ne peut pas être à la fois cohérent et disponible. Les deux options de la leçon 2 sont exactement ces deux branches.

Les erreurs de lecture classiques

1. « Partition » n'est pas un choix. Dans un réseau réel, les partitions arrivent. On ne choisit pas de les « tolérer » ou non : on choisit, quand elles arrivent, entre cohérence et disponibilité.
2. Sans partition, on peut avoir les deux. CAP ne dit rien de l'état normal.
3. Ce n'est pas binaire. Entre « linéarisable » et « tout diverge » existe un spectre de garanties.
4. Même sans partition, il y a un coût : garantir la cohérence exige de communiquer, donc de payer des allers-retours (leçon 1). Cet arbitrage latence / cohérence est formalisé dans des travaux ultérieurs sur CAP (Abadi les nomme PACELC).

Deux familles de garanties

Exemple détaillé : réconciliation par « dernier écrit gagne »

Deux répliques acceptent chacune une modification du même champ pendant une partition : la réplique A écrit « adresse = Douala » à l'heure locale 10:00:05, la réplique B écrit « adresse = Yaoundé » à 10:00:03. Règle « le dernier écrit gagne » (LWW, last write wins) : on garde 10:00:05, donc Douala. Mais si l'horloge de A avançait de 4 secondes, l'écriture de A a en réalité eu lieu à 10:00:01, avant celle de B : on a gardé la mauvaise. La règle dépend d'horloges qui ne sont pas fiables (leçon 4). Elle est simple mais fait perdre des écritures.

Où placer les blockchains ?

• Les réseaux à preuve de travail comme Bitcoin se comportent, pendant une partition, plutôt comme des systèmes disponibles : chaque côté continue à produire des blocs, puis, à la réparation, la chaîne de plus grand travail cumulé l'emporte et l'autre côté est abandonné. C'est une cohérence à terme avec finalité probabiliste. Cette caractérisation est courante mais simplificatrice.
• Les protocoles à finalité déterministe de type BFT exigent plus de deux tiers de votes : sans eux, ils s'arrêtent plutôt que de se contredire (vous le verrez en détail à l'atelier 108).

Ce que cela ne garantit pas

Ranger un système sous une étiquette « CP » ou « AP » est une simplification : la même base de données peut se comporter différemment selon sa configuration, ses opérations et ses pannes. L'étiquette sert à poser les bonnes questions, pas à conclure.

En bref

• CAP : pendant une partition, cohérence linéarisable et disponibilité de tous ne coexistent pas.
• La partition n'est pas une option ; ce que l'on choisit, c'est la réaction.
• Cohérence forte = pas de divergence mais indisponibilité possible ; cohérence à terme = réponses partout mais réconciliation.

La question de départ

Deux machines affirment : « j'ai reçu la transaction à 10:00:05 » et « j'ai reçu l'autre à 10:00:04 ». Laquelle est arrivée en premier ? Si on pouvait se fier aux horloges, la réponse serait immédiate. On ne le peut pas.

Pourquoi il n'existe pas d'horloge globale fiable

1. Dérive. Chaque machine a son oscillateur à quartz. Un quartz ordinaire peut dériver de quelques dizaines de parties par million : 20 ppm font 20 × 10⁻⁶ × 86 400 s ≈ 1,7 seconde par jour. L'écart croît tant que personne ne corrige.
2. La synchronisation est imparfaite. Des protocoles comme NTP ramènent l'écart vers quelques millisecondes à quelques dizaines de millisecondes sur Internet public, mais l'écart reste inconnu et variable, car il dépend des délais du réseau, eux-mêmes asymétriques et incertains (leçon 1).
3. On ne peut pas lire une horloge distante instantanément. Même une horloge parfaite ne peut pas être lue à distance sans délai : le message qui transporte l'heure a un délai inconnu et peut être asymétrique.

Conséquence pratique : si deux événements sont séparés de moins que l'incertitude des horloges, leur ordre selon les horloges n'a pas de sens.

Ordonner sans l'heure : la relation « s'est produit avant »

Un ordre sûr existe tout de même, par la causalité : l'événement a s'est produit avant b si (1) a et b sont sur la même machine et a est antérieur, ou (2) a est l'envoi d'un message dont b est la réception, ou (3) par transitivité. Deux événements sans chaîne de ce type sont concurrents.

Les horloges logiques de Lamport (Lamport, 1978) donnent à chaque événement un compteur :

1. avant chaque événement local ou envoi, incrémenter son compteur de 1 ;
2. joindre le compteur aux messages envoyés ;
3. à la réception, régler le compteur à max(compteur local, compteur reçu) + 1.

Exemple détaillé

• P1 : événement local a → 1 ; envoi de m1 → 2 (m1 porte 2).
• P2 : événement local → 1 ; réception de m1 → max(1, 2) + 1 = 3 ; envoi de m2 → 4.
• P3 : cinq événements locaux → 5 ; réception de m2 → max(5, 4) + 1 = 6.

Propriété garantie : si a s'est produit avant b, alors L(a) < L(b). La réciproque est fausse : L(a) < L(b) n'implique pas que a ait précédé b ; ils peuvent être concurrents. Deux événements concurrents peuvent même avoir le même compteur (on les départage par l'identifiant du nœud pour obtenir un ordre total arbitraire mais cohérent).

Et les blockchains ?

Un bloc porte un horodatage, mais ce n'est pas une horloge fiable : dans Bitcoin, la règle de consensus exige que le temps d'un bloc dépasse la médiane des 11 blocs précédents et ne dépasse pas de plus de deux heures l'heure du réseau telle que le nœud la calcule (le détail du calcul de cette heure dépend du client). Une fenêtre de plusieurs heures montre que l'horodatage est une borne grossière, pas un chronomètre. Ce qui ordonne vraiment les blocs, c'est leur chaînage (chaque bloc cite le précédent) et la règle de choix de la chaîne.

Ce que cela ne garantit pas

Une horloge logique ne dit rien de la durée réelle entre deux événements, ni de l'heure civile. Pour de la facturation, de la conformité ou un journal légal, il faut des horodatages d'une source de confiance, avec leur marge d'erreur.

En bref

• Les horloges dérivent et leur synchronisation a une marge d'erreur ; il n'existe pas d'heure globale fiable.
• La causalité (envoi avant réception) donne un ordre partiel sûr ; Lamport en fait un compteur.
• L(a) < L(b) n'implique pas « a avant b » ; seule la réciproque est garantie.