Les pièges des systèmes distribués

Sur un seul ordinateur, un programme se comporte d'ordinaire de façon prévisible (déterministe) : soit il fonctionne, soit il échoue. Quand le matériel marche, la même opération produit toujours le même résultat ; en cas de panne, on préfère un crash total — un noyau qui panique, un écran bleu — à un résultat faux et sournois. C'est un choix de conception délibéré : l'ordinateur cache la réalité physique floue sur laquelle il repose et présente un modèle idéalisé, d'une perfection mathématique. Dès qu'on relie plusieurs machines par un réseau, ce confort disparaît.

Travailler avec des systèmes distribués est fondamentalement différent : la nouveauté, c'est la multitude de manières inédites dont les choses peuvent mal tourner. Ce chapitre adopte volontairement le pessimisme maximal — tout ce qui peut échouer échouera — et passe en revue les pièges du réseau, des horloges et des processus, avant d'examiner comment raisonner sur l'état d'un système où aucun nœud ne connaît la vérité avec certitude. L'objectif n'est pas de désespérer, mais de comprendre sur quoi on peut et ne peut pas compter avant d'aborder, au chapitre suivant, les algorithmes qui offrent des garanties malgré tout.

Les défaillances partielles : le mal originel

Dans un système distribué, certaines parties peuvent être cassées de façon imprévisible alors que d'autres fonctionnent parfaitement. C'est ce qu'on appelle une défaillance partielle (partial failure), et toute sa difficulté tient à son caractère non déterministe : dès qu'une opération implique plusieurs nœuds et le réseau, elle peut parfois réussir, parfois échouer sans raison apparente. Pire encore, comme nous le verrons, vous ne saurez parfois même pas si elle a réussi ou non.

Deux philosophies y répondent à l'opposé. Le calcul haute performance (high-performance computing) — les superordinateurs — laisse la défaillance partielle dégénérer en défaillance totale : on sauvegarde l'état (checkpoint), et si un nœud tombe, on arrête tout le cluster, on répare, puis on reprend depuis le dernier point ; cela ressemble plus à un ordinateur unique qu'à un système distribué. À l'inverse, les services internet doivent rester disponibles en permanence, tournent sur du matériel ordinaire (commodity) au taux de panne plus élevé, et grandissent au point qu'il est raisonnable de supposer qu'une partie est toujours cassée. Abandonner à la moindre erreur n'est pas une option : il faut construire un système fiable à partir de composants peu fiables.

Cela n'a rien d'une contradiction. Les codes correcteurs d'erreurs transmettent des données correctes sur un canal qui corrompt parfois des bits ; TCP bâtit un transport fiable au-dessus d'IP, qui perd, retarde, duplique et réordonne les paquets. La fiabilité gagnée a toujours une limite — TCP ne peut pas effacer les délais réseau — mais elle suffit à rendre les fautes restantes plus simples à traiter.

Des réseaux peu fiables

Les systèmes étudiés ici sont des architectures sans partage (shared-nothing) : des machines qui ne communiquent que par le réseau, chacune gardant pour elle sa mémoire et son disque. Internet et la plupart des réseaux de centres de données sont des réseaux à paquets asynchrones (asynchronous packet networks) : un nœud peut envoyer un paquet à un autre, mais le réseau ne garantit ni le délai d'arrivée, ni même l'arrivée tout court.

Si vous envoyez une requête et attendez une réponse, une foule de scénarios peuvent se produire, et le drame est qu'ils sont indiscernables :

1. la requête a pu être perdue (câble débranché) ;
2. elle attend dans une file et sera traitée plus tard (destinataire surchargé) ;
3. le nœud distant est tombé (crash, coupure) ;
4. le nœud distant est temporairement figé (longue pause de ramasse-miettes) mais répondra plus tard ;
5. le nœud a traité la requête, mais la réponse s'est perdue sur le réseau ;
6. le nœud a traité la requête, mais la réponse est seulement retardée.

L'émetteur ne peut même pas savoir si son paquet est arrivé : la seule preuve serait une réponse, qui peut à son tour se perdre ou se retarder. La seule information dont vous disposez, c'est que vous n'avez pas encore reçu de réponse. Impossible d'en déduire pourquoi.

Détecter les pannes par délai d'expiration

La parade habituelle est le délai d'expiration (timeout) : passé un certain temps, on renonce et on suppose que la réponse n'arrivera pas. Mais cela ne dit toujours pas si le nœud distant a reçu la requête — et si elle traîne dans une file quelque part, elle peut encore être livrée alors même que l'émetteur a abandonné.

Reste la question piège : combien de temps attendre ? Il n'existe pas de réponse simple, c'est un compromis franc.

Délai d'expiration	Avantage	Risque
Long	Peu de faux positifs : on ne déclare mort qu'un nœud vraiment mort.	Attente prolongée pour les utilisateurs ; pannes détectées tard.
Court	Détection rapide des pannes.	Déclarer mort un nœud seulement ralenti, transférer sa charge, et déclencher une défaillance en cascade (cascading failure).

Déclarer un nœud mort prématurément est dangereux : ses responsabilités sont transférées ailleurs, ce qui ajoute de la charge au réseau et aux autres nœuds. Sur un système déjà sous tension, cela peut tout aggraver — au pire, tous les nœuds se déclarent mutuellement morts et plus rien ne fonctionne.

Pourquoi les délais sont imprévisibles

Dans un monde idéal où chaque paquet arriverait en au plus d et chaque nœud traiterait toute requête en au plus r, on pourrait fixer le délai d'expiration à 2d + r. Hélas, les réseaux asynchrones ont des délais non bornés (unbounded delays) : ils livrent au plus vite, sans aucune limite supérieure. La cause principale est la mise en file d'attente (queueing), exactement comme les embouteillages routiers :

• si plusieurs nœuds visent la même destination, le commutateur met les paquets en file ; si la file déborde, le paquet est jeté et doit être réémis ;
• à l'arrivée, si tous les cœurs CPU sont occupés, le système d'exploitation met la requête entrante en file pour une durée arbitraire ;
• dans un environnement virtualisé, une machine virtuelle peut être suspendue des dizaines de millisecondes pendant qu'une autre utilise le cœur ;
• TCP applique un contrôle de flux et retransmet les paquets perdus, ajoutant encore des délais que l'application subit sans les voir.

Ces délais s'envolent surtout quand le système approche de sa capacité maximale. Dans les clouds publics multilocataires, où réseau, commutateurs et CPU sont partagés, un voisin bruyant (noisy neighbor) peut à lui seul rendre vos délais erratiques.

La fiabilité du réseau téléphonique classique vient de ce qu'il établit un circuit : une bande passante fixe est réservée de bout en bout pour toute la durée de l'appel, ce qui donne un délai borné (bounded delay). Mais Ethernet et IP sont à commutation de paquets, optimisés pour le trafic en rafale (bursty) : une page web n'a pas de débit constant, on veut juste que cela aille au plus vite. TCP adapte dynamiquement son débit à la capacité disponible, maximisant l'utilisation du lien — au prix de files d'attente et de délais variables. Ceux-ci ne sont donc pas une fatalité physique, mais le résultat d'un arbitrage coût/bénéfice : la réservation statique garantit la latence mais coûte cher en sous-utilisation.

Des horloges peu fiables

Le temps est délicat en distribué, car la communication n'est pas instantanée et chaque machine possède sa propre horloge matérielle — un oscillateur à quartz, jamais parfaitement exact. On peut les synchroniser par le protocole de temps réseau (Network Time Protocol, NTP), mais imparfaitement. Avant tout, il faut distinguer deux horloges aux usages opposés.

Type d'horloge	Fonction	Piège
Horloge murale (time-of-day clock)	Renvoie la date et l'heure courantes selon un calendrier (depuis l'époque UNIX).	Synchronisée par NTP, elle peut sauter en arrière si elle dérive trop, et ignore les secondes intercalaires. Inadaptée à la mesure de durées.
Horloge monotone (monotonic clock)	Mesure une durée (un délai, un temps de réponse).	Garantie de toujours avancer ; sa valeur absolue n'a aucun sens et ne se compare pas entre machines.

Pour mesurer un temps écoulé — un délai d'expiration, par exemple — l'horloge monotone est le bon choix : elle ne suppose aucune synchronisation entre nœuds. NTP peut ajuster sa vitesse (le slewing, plafonné à 0,05 %), mais ne la fait jamais sauter.

La synchronisation n'est jamais parfaite

Compter sur des horloges murales synchronisées est risqué, car les erreurs passent inaperçues : un CPU défectueux plante vite et bien, mais un quartz qui dérive « marche » en apparence tout en s'éloignant silencieusement de la réalité. Quelques sources d'erreur citées par Kleppmann :

• la dérive (drift) du quartz : Google retient 200 ppm, soit 6 ms en 30 secondes ou 17 secondes par jour sans resynchronisation ;
• une horloge trop décalée que NTP réinitialise de force, faisant bondir le temps en avant ou en arrière ;
• la précision de NTP, limitée par le délai réseau : 35 ms au mieux sur internet, avec des pics d'une seconde en cas de congestion ;
• les secondes intercalaires, qui ont déjà fait planter de grands systèmes.

Le danger du « dernier écrit gagne »

Le piège classique consiste à ordonner des événements entre nœuds avec des horloges murales. Considérons une base à réplication multi-maître où chaque écriture est étiquetée du timestamp local de son nœud d'origine. Le client A écrit x = 1 sur le nœud 1, cette écriture est répliquée, puis le client B incrémente vers x = 2 sur le nœud 3 — donc causalement plus tard. Et pourtant, à cause d'un décalage de quelques millisecondes entre horloges :

écriture x = 1   →  timestamp 42.004   (nœud 1)
écriture x = 2   →  timestamp 42.003   (nœud 3, mais survenue APRÈS)

Quand le nœud 2 reçoit les deux, il conclut à tort que x = 1 est la plus récente et jette l'écriture x = 2. L'incrément du client B est silencieusement perdu. Cette stratégie de résolution de conflit, le dernier écrit gagne (last write wins, LWW), est utilisée par Cassandra et Riak. Ses défauts sont structurels :

• des écritures disparaissent mystérieusement : un nœud à l'horloge lente ne peut écraser les valeurs d'un nœud à l'horloge rapide tant que le décalage n'est pas résorbé ;
• LWW ne distingue pas des écritures séquentielles rapprochées d'écritures réellement concurrentes : il faut un suivi de causalité (par vecteurs de version) ;
• deux nœuds peuvent générer le même timestamp, exigeant un départage qui peut lui-même violer la causalité.

Les horloges logiques (logical clocks), fondées sur des compteurs et non sur un quartz, sont une alternative plus sûre pour ordonner des événements : elles ne mesurent pas l'heure, seulement l'ordre relatif.

Intervalles de confiance et TrueTime

Une exception notable expose l'incertitude au lieu de la cacher : l'API TrueTime de Google Spanner. Au lieu d'un instant, elle renvoie deux valeurs, [earliest, latest] : l'heure réelle est forcément dans cet intervalle. Spanner s'en sert pour l'isolation par instantané (snapshot isolation) répartie sur plusieurs centres de données. L'observation est simple : si deux intervalles ne se chevauchent pas, leur ordre est certain.

A = [A_earliest, A_latest]    B = [B_earliest, B_latest]

A_earliest < A_latest < B_earliest < B_latest
   →  B s'est forcément produit APRÈS A (aucun doute)

intervalles qui se chevauchent  →  ordre incertain

Pour garantir que les timestamps reflètent la causalité, Spanner attend délibérément la durée de l'intervalle de confiance avant de valider une transaction en lecture-écriture, le temps que les intervalles cessent de se chevaucher. Pour que cette attente reste courte, Google déploie récepteurs GPS et horloges atomiques dans chaque centre de données, et synchronise à environ 7 ms près.

Des processus qui se figent

Reprenons un usage dangereux des horloges. Un leader détient un bail (lease), sorte de verrou à expiration, qu'il renouvelle périodiquement pour rester le seul à accepter des écritures. La boucle naïve ressemble à ceci :

while (true) {
  const request = getIncomingRequest();

  // Garder au moins 10 s de marge sur le bail
  if (lease.expiryTimeMillis - now() < 10_000) {
    lease = lease.renew();
  }

  if (lease.isValid()) {
    process(request); // et si une pause survenait ICI ?
  }
}

Outre la dépendance aux horloges synchronisées, ce code suppose qu'il s'écoule très peu de temps entre la vérification du bail et le traitement de la requête. Or un thread peut être suspendu arbitrairement longtemps, sans s'en apercevoir. Si la pause dure 15 secondes autour de lease.isValid(), le bail aura expiré, un autre nœud sera devenu leader, et ce thread traitera quand même la requête — une action devenue dangereuse.

Une telle pause n'a rien d'absurde. Les causes abondent : un ramasse-miettes « arrêt du monde » (stop-the-world) qui peut durer plusieurs minutes, une machine virtuelle suspendue puis migrée à chaud, un portable dont on rabat l'écran, une commutation de contexte, une lecture disque synchrone (parfois cachée, comme le chargement paresseux de classes en Java), un défaut de page (page fault) qui déclenche la pagination (swap), voire un simple SIGSTOP envoyé par erreur. Pendant la pause, le reste du monde continue d'avancer et peut déclarer le nœud mort.

Les outils de la programmation concurrente sur une seule machine — mutex, sémaphores, compteurs atomiques — ne se transposent pas aux systèmes distribués, car il n'y a aucune mémoire partagée, seulement des messages sur un réseau peu fiable. Garantir des délais de réponse exigerait un système temps réel strict (hard real-time) : ordonnanceur dédié, fonctions au pire-cas documenté, allocation mémoire bridée. C'est très coûteux et réservé aux dispositifs critiques embarqués — un airbag, pas un serveur de données.

Connaissance, vérité et mensonges

Toutes ces difficultés sont désorientantes : un nœud ne peut rien savoir avec certitude, seulement faire des suppositions à partir des messages qu'il reçoit — ou ne reçoit pas. Comme un problème réseau est indiscernable d'un problème de nœud, l'absence de réponse ne dit rien. La parade est de formaliser nos hypothèses dans un modèle de système (system model), puis de concevoir des algorithmes prouvés corrects dans ce modèle.

La vérité est décidée par la majorité

Imaginez un nœud parfaitement sain, mais dont toutes les réponses sortantes sont perdues : les autres ne l'entendent pas et le déclarent mort — il a beau hurler « je ne suis pas mort ! », personne ne l'écoute. Même scénario avec une longue pause de ramasse-miettes : le nœud revient à la vie en croyant qu'à peine un instant s'est écoulé, alors qu'on l'a déjà enterré.

La morale est qu'un nœud ne peut pas se fier à son propre jugement. C'est pourquoi de nombreux algorithmes s'appuient sur un quorum (quorum) : les décisions sont prises par une majorité de nœuds. Si une majorité déclare un nœud mort, il doit s'effacer, même s'il se sent en pleine forme. La raison est subtile : avec un nombre fixe de nœuds, il ne peut exister qu'une seule majorité à la fois, donc jamais deux décisions contradictoires simultanées.

Le leader zombie et les jetons de cloisonnement

Souvent le système exige l'unicité : un seul leader par partition, un seul détenteur d'un verrou, un seul propriétaire d'un nom d'utilisateur. Le danger : un nœud peut se croire « l'élu » alors que la majorité l'a destitué entre-temps. Ce leader zombie peut alors corrompre des données — bug réel ayant affecté HBase. Si un client détenant un bail est figé trop longtemps, son bail expire, un autre client en obtient un, et au réveil le premier écrit malgré tout : les écritures se télescopent.

La parade élégante est le jeton de cloisonnement (fencing token) : à chaque attribution de verrou, le service renvoie un numéro strictement croissant. Toute écriture doit porter son jeton, et la ressource elle-même rejette tout jeton inférieur à ce qu'elle a déjà vu.

// Côté ressource (le service de stockage) : seul un jeton
// supérieur ou égal au plus grand déjà vu est accepté.
class StockageProtege {
  private dernierJeton = 0;

  ecrire(jeton: number, donnees: Buffer): void {
    if (jeton < this.dernierJeton) {
      throw new Error(
        `Jeton périmé : ${jeton} < ${this.dernierJeton}`,
      );
    }
    this.dernierJeton = jeton;
    this.persister(donnees);
  }

  private persister(_donnees: Buffer): void {
    /* écriture effective sur disque */
  }
}

Ainsi, si le client 1 (jeton 33) revient d'une pause après que le client 2 (jeton 34) a écrit, son écriture est rejetée. Avec ZooKeeper, le zxid ou le numéro de version cversion font de parfaits jetons, car ils sont monotones. Point essentiel : c'est la ressource qui doit vérifier, pas le client. Il est imprudent de supposer que les clients seront toujours bien élevés — leurs priorités diffèrent souvent de celles de l'opérateur du service.

Fautes byzantines : les nœuds menteurs

Le jeton de cloisonnement bloque un nœud qui se trompe de bonne foi. Mais un nœud peut aussi mentir : envoyer des réponses fausses, prétendre avoir reçu un message qu'il n'a jamais reçu, forger un faux jeton. C'est une faute byzantine (Byzantine fault), du nom du problème des généraux byzantins (Byzantine Generals Problem) : n généraux doivent s'accorder alors que des traîtres parmi eux envoient des messages mensongers, sans qu'on sache lesquels sont déloyaux.

Tout au long du livre, Kleppmann suppose des nœuds peu fiables mais honnêtes : lents ou muets, peut-être périmés, mais disant la vérité de leur point de vue quand ils répondent. La tolérance aux fautes byzantines reste pertinente dans des cas précis — l'aérospatiale (corruption mémoire par radiation) ou les systèmes entre organisations qui se méfient, comme la blockchain Bitcoin. Mais on l'ignore en général, pour de bonnes raisons :

• dans votre centre de données, tous les nœuds sont sous votre contrôle et présumés dignes de confiance ;
• les protocoles byzantins sont très complexes et coûteux à déployer ;
• déployer le même logiciel partout n'aide pas : un même bug frappe tous les nœuds à la fois, et la plupart de ces algorithmes exigent qu'une super-majorité de plus des deux tiers des nœuds fonctionnent correctement ;
• contre un attaquant, qui compromet souvent tous les nœuds d'un coup, ce sont l'authentification, le chiffrement et les pare-feux qui protègent.

Modèles de système et réalité

Pour qu'un algorithme soit utile, il doit tolérer les fautes décrites ici sans dépendre des détails du matériel. On formalise donc les fautes attendues dans un modèle. Deux axes se combinent : les hypothèses de synchronisation temporelle et le mode de défaillance des nœuds.

Modèle temporel	Hypothèse
Synchrone (synchronous)	Délai réseau, pauses et erreur d'horloge tous bornés. Irréaliste en pratique.
Partiellement synchrone (partially synchronous)	Système bien élevé la plupart du temps, mais qui dépasse parfois les bornes. Réaliste.
Asynchrone (asynchronous)	Aucune hypothèse temporelle ; pas d'horloge, donc pas de délais d'expiration. Très restrictif.

Modèle de défaillance	Hypothèse
Crash-arrêt (crash-stop)	Un nœud ne peut échouer qu'en crashant, et ne revient jamais.
Crash-reprise (crash-recovery)	Un nœud peut crasher puis revenir ; son stockage stable survit, sa mémoire vive est perdue.
Byzantin (Byzantine)	Un nœud peut faire n'importe quoi, y compris tromper les autres.

Pour modéliser des systèmes réels, le modèle partiellement synchrone avec fautes crash-reprise est le plus utile. On définit alors la correction d'un algorithme par ses propriétés. Par exemple, pour des jetons de cloisonnement : unicité (jamais deux fois le même jeton), séquence monotone (si x se termine avant que y commence, alors tx < ty), et disponibilité (un nœud qui demande un jeton et ne crashe pas finit par recevoir une réponse).

Sûreté contre vivacité

Il est crucial de distinguer deux familles de propriétés :

• une propriété de sûreté (safety) dit que rien de mauvais ne se produit : si elle est violée, on peut pointer l'instant précis où elle l'a été, et le dommage est irréversible (un jeton dupliqué reste dupliqué). L'unicité et la séquence monotone sont des propriétés de sûreté ;
• une propriété de vivacité (liveness) dit qu'une bonne chose finit par arriver — le mot « finit par » la trahit. Elle peut ne pas tenir à un instant donné, mais il reste toujours l'espoir qu'elle soit satisfaite plus tard. La disponibilité, comme la cohérence à terme (eventual consistency), sont des propriétés de vivacité.

Ces modèles abstraits ne sont pas parfaits : un disque réputé « stable » peut être corrompu, un serveur peut ne plus reconnaître ses disques au redémarrage. Une vraie implémentation doit donc parfois gérer l'« impossible », quitte à appeler un humain à la rescousse. Mais prouver un algorithme correct dans un modèle reste un excellent premier pas : l'analyse théorique révèle des défauts qui resteraient cachés des années, jusqu'à ce que vos hypothèses temporelles cèdent. Théorie et tests empiriques sont également importants.

À retenir

• En distribué, la difficulté maîtresse est la défaillance partielle : non déterministe, elle fait qu'une opération peut réussir, échouer ou — pire — laisser l'émetteur incapable de savoir si elle a abouti.
• Le réseau est asynchrone à délais non bornés : on ne détecte une panne que par délai d'expiration, dont la valeur est un compromis franc et se règle expérimentalement, jamais par une « bonne » constante.
• Les horloges murales peuvent sauter et dériver : ordonner des événements avec elles est dangereux (le dernier écrit gagne perd des données). Réservez l'horloge monotone aux durées, et raisonnez en intervalles de confiance (TrueTime).
• Un processus peut se figer arbitrairement (ramasse-miettes, pagination, suspension de VM) puis reprendre sans s'en apercevoir, après avoir été déclaré mort : ne supposez jamais qu'un délai court sépare deux lignes de code.
• La vérité se décide à la majorité (quorum), pas par un nœud isolé qui peut être un zombie ; les jetons de cloisonnement croissants, vérifiés par la ressource, bloquent un écrivain périmé. Les fautes byzantines sont en général ignorées hors aérospatiale et systèmes inter-organisations.
• Formalisez vos hypothèses dans un modèle de système — en pratique, partiellement synchrone, crash-reprise — et distinguez sûreté (toujours garantie, violation irréversible) et vivacité (garantie sous réserve que le réseau se rétablisse).