Simulation déterministe : reproduire les pannes rares des systèmes distribués

Un cluster perd parfois une écriture après une succession improbable d’événements : un nœud redémarre, un paquet est retardé, une élection démarre au mauvais moment et un disque répond dans un ordre inattendu. Le test échoue une fois sur plusieurs milliers d’exécutions, puis passe dès qu’un ingénieur active les journaux de diagnostic. Comment corriger une panne que l’on ne peut pas rejouer ?

La simulation déterministe apporte une réponse plus ambitieuse que « relancer le test avec la même graine ». Elle consiste à placer sous le contrôle du banc de test toutes les décisions susceptibles de modifier l’exécution. Le temps, le réseau, le stockage, l’ordonnancement des tâches et le hasard deviennent des entrées pilotables. Une défaillance rare peut alors être rejouée, ralentie et examinée événement par événement. Mais cette reproductibilité n’est utile que si le simulateur sait aussi explorer des scénarios intéressants et reconnaître une violation réelle. C’est l’ensemble de cette architecture qu’il faut comprendre.

Pourquoi une graine aléatoire ne suffit pas

Une graine est la valeur initiale donnée à un générateur pseudo-aléatoire, ou PRNG : un algorithme qui produit une suite de valeurs apparemment aléatoires, mais entièrement déterminée par son état initial. Avec la même graine et les mêmes appels dans le même ordre, le générateur restitue la même suite. Cela permet, par exemple, de choisir à nouveau le même nœud à arrêter ou le même paquet à perdre.

Le contrat se brise toutefois dès qu’une décision échappe à ce générateur. Deux threads peuvent être ordonnancés différemment par le système d’exploitation. Une temporisation peut expirer quelques microsecondes plus tôt. Une lecture de /dev/urandom peut fournir une nouvelle valeur. Le réseau, le système de fichiers ou un service externe peuvent répondre dans un ordre différent. Ce seul décalage modifie ensuite le nombre et l’ordre des appels au PRNG. La graine reste identique, mais l’histoire diverge.

La documentation de FoundationDB sur les tests clients formule précisément cette limite : le rejeu fonctionne lorsque tous les comportements influençant l’exécution sont déterministes. Un workload qui crée des threads ordinaires peut réintroduire une concurrence non maîtrisée et rendre un échec difficile à reproduire.

Il faut donc distinguer deux propriétés. La première est le rejeu : une exécution donnée peut être reproduite. La seconde est l’exploration : le banc de test sait générer de nombreuses exécutions différentes et atteindre des états inhabituels. Une graine peut identifier un chemin, mais elle ne prouve ni que ce chemin sera stable en présence d’entrées externes, ni que l’espace exploré contient les situations les plus dangereuses.

La simulation déterministe doit par conséquent être pensée comme une architecture de contrôle de l’exécution. La graine n’en est que la clé d’entrée.

Contrôler les cinq sources de non-déterminisme

FoundationDB illustre l’approche la plus intégrée. Son véritable code de base de données peut fonctionner avec des charges synthétiques et des fautes injectées dans une simulation à événements discrets. Dans ce modèle, le temps n’avance pas continuellement : le moteur sélectionne le prochain événement planifié, déplace l’horloge jusqu’à sa date, l’exécute, puis recommence. Le papier technique consacré à FoundationDB décrit l’abstraction du réseau, du disque, du temps et du générateur pseudo-aléatoire, avec plusieurs serveurs simulés dans un même processus.

Virtualiser le temps

Lire directement l’horloge de la machine rend le résultat dépendant de la vitesse du processeur, de la charge du système et des pauses imprévues. Une horloge virtuelle remplace cette dépendance. Les temporisations, délais de retransmission, baux et échéances doivent consulter cette horloge contrôlée.

Le simulateur peut alors accélérer les périodes sans activité. S’il ne reste qu’un minuteur prévu dans une heure virtuelle, il n’est pas nécessaire d’attendre une heure réelle : l’horloge saute jusqu’au prochain événement. Cela permet de tester rapidement des mécanismes dont les délais seraient prohibitifs dans un environnement classique.

Le contrôle doit aussi atteindre la logique métier lorsque le temps influence son résultat. L’architecture de TigerBeetle indique que sa machine à états ne lit pas directement l’heure système. Un horodatage déterminé par le protocole lui est injecté, de sorte qu’une même entrée conserve le même résultat logique et le même chemin d’exécution.

Intercepter le réseau et le stockage

Le réseau simulé ne se contente pas de livrer des messages en mémoire. Il doit pouvoir retarder, perdre, dupliquer ou réordonner les communications selon le modèle testé. Il peut également représenter une partition, c’est-à-dire l’impossibilité temporaire pour certains groupes de nœuds de communiquer.

Le stockage exige une abstraction comparable. Les opérations d’entrée-sortie, souvent abrégées en E/S, doivent passer par une interface que le simulateur peut retarder ou faire échouer. Selon les garanties visées par le logiciel, le modèle peut aussi exposer des écritures incomplètes ou des données corrompues. L’objectif n’est pas de reproduire toute la physique d’un disque, mais de rendre explicites les comportements auxquels l’algorithme prétend résister.

Une règle de conception en découle : aucun accès significatif au réseau ou au stockage ne devrait contourner la couche contrôlée. Un simple appel direct ajouté lors d’une refonte peut créer une nouvelle source de divergence.

Maîtriser l’ordonnancement et l’entropie

L’ordonnancement désigne le choix de la prochaine tâche autorisée à progresser. Dans un programme multithread, ce choix dépend normalement du système d’exploitation et du matériel. FoundationDB évite cette difficulté dans son simulateur en utilisant une exécution monothread et le modèle d’acteurs de Flow. Un acteur est une unité logique qui traite des événements et communique par messages ; le moteur peut donc choisir explicitement l’ordre dans lequel les acteurs avancent.

Une autre voie consiste à contrôler l’entrelacement des threads existants. C’est l’un des rôles de l’environnement décrit par Antithesis. Quel que soit le mécanisme, les points où une tâche peut céder la main doivent être visibles par la plateforme.

Enfin, toute entropie, c’est-à-dire toute donnée utilisée comme source de hasard, doit être centralisée. L’environnement Antithesis remplace notamment les périphériques Linux /dev/random et /dev/urandom par une entropie fournie par la plateforme, isole les conteneurs du réseau extérieur et peut accélérer les périodes d’inactivité. Sa documentation déconseille de mettre cette entropie en cache dans un PRNG applicatif : la plateforme aurait alors moins d’occasions de faire bifurquer l’historique pour explorer d’autres chemins.

Explorer les pannes plutôt que rejouer toujours la même histoire

Une simulation parfaitement déterministe peut être parfaitement inutile si elle répète des scénarios triviaux. Le banc doit faire varier la topologie, la charge, la configuration et le calendrier des fautes. C’est ici que le fuzzing entre en jeu : cette technique génère ou transforme automatiquement des entrées afin de provoquer des comportements inattendus.

Dans un système distribué, les dimensions à combiner sont nombreuses : requêtes clientes, taille du cluster, latences, redémarrages, pertes de messages, erreurs d’E/S ou changements de rôle. FoundationDB randomise les configurations, les workloads et les paramètres de fautes. Son approche comprend également la « buggification », qui active volontairement des branches simulant des erreurs, et le swarm testing, où différentes fonctionnalités ou fautes sont activées selon des combinaisons variables. Ces mécanismes sont détaillés dans son article d’architecture et de test.

La génération doit néanmoins respecter un modèle compréhensible. Arrêter tous les nœuds pour toujours démontre seulement qu’un cluster sans machine ne progresse pas. Une panne intéressante place le système près de la frontière de ses garanties : majorité encore disponible, redémarrage pendant une récupération, corruption limitée à une opération ou partition qui se résorbe après une série de décisions concurrentes.

Une stratégie pratique consiste à séparer trois couches. La première produit les actions normales des clients. La deuxième choisit les fautes et leur calendrier. La troisième pilote l’environnement : livraison des messages, avancement du temps et réveil des tâches. Toutes consomment une source de décisions enregistrable. En cas d’échec, le rapport doit au minimum conserver la graine, la configuration, le scénario et la nature de l’oracle violé.

Le rejeu peut ensuite être enrichi par une réduction du scénario. Cette opération cherche une suite plus courte qui conserve l’échec : moins de requêtes, moins de nœuds affectés ou moins de fautes. Même lorsque cette réduction n’est pas entièrement automatisée, le déterminisme permet de retirer un événement puis de vérifier sans ambiguïté si le défaut persiste.

Détecter les erreurs avec des oracles de sûreté et de vivacité

Faire tomber des processus ne constitue pas un test complet. Il faut décider ce qui représente un résultat correct. Un oracle est le mécanisme qui tranche cette question ; il s’appuie souvent sur un invariant, une propriété qui doit rester vraie dans tous les états concernés.

Les propriétés de sûreté expriment que quelque chose d’interdit ne se produit jamais. Selon le produit, un oracle peut vérifier que deux valeurs contradictoires ne sont pas toutes deux validées, qu’une transaction respecte les garanties annoncées ou qu’une quantité comptable est conservée. FoundationDB combine notamment des invariants transactionnels, des assertions locales et des vérifications de récupération du cluster, d’après son papier de référence.

Les propriétés de vivacité posent une autre question : le système finit-il par progresser lorsque les conditions nécessaires sont réunies ? Un cluster peut préserver toutes ses données et rester pourtant bloqué. Il peut aussi entrer dans un livelock : les composants continuent d’exécuter des actions, mais ces actions s’annulent ou se répètent sans produire de progrès utile.

La vivacité ne se teste pas correctement en injectant des perturbations maximales sans limite. Si chaque tentative est systématiquement interrompue, l’absence de progrès est normale. Il faut formuler les hypothèses de l’oracle : par exemple, une connectivité suffisante est rétablie et un quorum, c’est-à-dire le nombre minimal de membres requis pour prendre une décision collective, reste stable pendant une durée virtuelle donnée.

Le simulateur VOPR de TigerBeetle sépare justement ces préoccupations. Son mode de sûreté peut injecter aléatoirement des crashs, des pertes de paquets et des corruptions d’E/S. Pour la vivacité, le scénario stabilise un quorum tout en maintenant certaines défaillances périphériques, puis vérifie que le cœur du cluster continue de progresser. Le retour d’expérience de TigerBeetle sur les tests de vivacité montre pourquoi cette phase contrôlée révèle des blocages qu’un chaos permanent peut masquer.

Cette distinction améliore aussi le diagnostic. Une violation de sûreté doit être signalée dès que l’état interdit apparaît. Une violation de vivacité demande plutôt une fenêtre d’observation et des conditions de stabilité explicites. Mélanger les deux conduit soit à des alertes trompeuses, soit à des attentes infinies.

Deux stratégies : concevoir pour la simulation ou encapsuler l’existant

La première stratégie consiste à rendre le logiciel simulable dès sa conception. Les dépendances non déterministes sont placées derrière des interfaces interchangeables. Le code de production appelle une abstraction du temps, du transport, du stockage ou du hasard ; l’environnement réel fournit l’implémentation normale et le simulateur fournit une version contrôlée.

FoundationDB pousse ce modèle très loin : son code réel s’exécute avec plusieurs serveurs simulés au sein d’un processus déterministe. TigerBeetle fait lui aussi du déterminisme un principe architectural. Son simulateur VOPR peut exécuter un cluster sur un seul thread, accélérer le temps, remplacer les E/S par des modèles fautifs et reproduire un échec à partir de sa graine, comme l’explique sa documentation d’architecture.

Cette approche offre un contrôle fin et rend les frontières du système visibles. Elle impose toutefois une discipline durable. Les bibliothèques utilisées par le code testé ne doivent pas lancer discrètement un thread, consulter l’horloge réelle ou produire leur propre hasard. Les revues de code doivent traiter la simulabilité comme une propriété architecturale, pas comme une commodité réservée aux tests.

La seconde stratégie place un logiciel plus ordinaire dans un environnement déterministe. Un hyperviseur est une couche qui contrôle l’exécution de machines ou d’environnements virtualisés. Dans l’approche présentée par Antithesis, il permet de maîtriser des éléments tels que l’horloge, l’entrelacement des threads, les fautes et les sources de hasard sans réécrire chaque composant autour d’interfaces de simulation.

L’intérêt est évident pour une pile existante, composée de plusieurs services ou dépendante de comportements Linux. Le niveau de contrôle change cependant de forme : au lieu d’injecter directement une interface de disque dans le code métier, la plateforme contrôle l’environnement vu par le logiciel. Cette méthode ne dispense pas d’instrumenter les propriétés à vérifier. L’hyperviseur peut explorer et rejouer une exécution ; il ne peut pas deviner seul qu’un solde, un index ou un protocole a violé sa sémantique.

Le choix n’est donc pas purement technique. Une équipe qui construit un nouveau moteur distribué peut faire du déterminisme une contrainte structurante. Pour un ensemble de services déjà déployés, une enveloppe virtualisée peut réduire le coût d’adoption. Des approches hybrides sont aussi possibles : cœur algorithmique conçu pour la simulation, puis tests de l’assemblage dans un environnement contrôlé plus large.

Construire un banc rejouable sans recréer tout Internet

Le premier travail consiste à dresser l’inventaire des entrées non déterministes. Il faut chercher les lectures d’horloge, générateurs aléatoires, threads, minuteurs, appels réseau, accès au système de fichiers, processus enfants et dépendances externes. Chaque élément doit être soit contrôlé, soit remplacé, soit explicitement exclu du périmètre de rejeu.

Une architecture minimale peut ensuite se construire par étapes :

1. Créer une boucle d’événements centrale. Elle possède l’horloge virtuelle et une file ordonnée des actions à exécuter. Les égalités doivent être départagées par une règle déterministe.
2. Injecter les dépendances. Le code reçoit des interfaces de temps, réseau, stockage et hasard au lieu d’appeler directement le système d’exploitation.
3. Centraliser les décisions. Les choix de charge, de faute et d’ordonnancement doivent dériver d’une source contrôlée et être associés à une graine.
4. Définir les modèles de panne. Chaque faute doit correspondre à une hypothèse utile : message perdu, nœud arrêté, écriture refusée ou réponse retardée. Le modèle doit rester lisible et configurable.
5. Écrire les invariants avant de multiplier les scénarios. Sans oracle, augmenter le nombre d’exécutions augmente surtout la quantité de comportements non analysés.
6. Produire un artefact de rejeu. La graine ne suffit pas toujours à communiquer un incident. Il faut conserver la configuration, les options actives et le scénario ayant échoué.

Il est préférable de commencer par une propriété étroite et un modèle simple. Par exemple, trois nœuds, un type de requête, des retards réseau et des crashs contrôlés. Une fois le rejeu stable, le périmètre peut intégrer les partitions, les erreurs de stockage et des workloads plus riches. Ajouter toutes les fautes dès le départ rend difficile de savoir si une divergence vient du produit ou du simulateur.

Le banc lui-même doit être testé. Une petite erreur dans le modèle de stockage peut produire une garantie irréaliste ; un ordonnanceur qui oublie certains événements peut fabriquer un faux blocage. Des tests ciblés des abstractions, ainsi que des assertions internes sur la cohérence de la file d’événements et de l’horloge, limitent ce risque.

Conclusion : compléter la simulation par des interfaces réelles

La simulation déterministe observe profondément les chemins algorithmiques qu’elle contrôle, mais elle ne reproduit pas automatiquement tous les comportements du monde réel. Une interface simulée du réseau ne valide pas nécessairement la véritable pile de transport. Un modèle de disque ne teste ni le pilote, ni le système de fichiers, ni le comportement exact du matériel. Une exécution monothread ne révèle pas toutes les courses de données d’un client multithread.

TigerBeetle reconnaît explicitement cette frontière. Son test déterministe remplace le transport réseau et l’interface de stockage par des stubs, c’est-à-dire des implémentations simplifiées utilisées à la place des composants réels. Le projet le complète avec Vörtex, un banc non déterministe qui sollicite les binaires compilés, les pilotes clients et les liaisons de langages depuis l’extérieur. Son article consacré à Vörtex présente cette complémentarité comme une réponse aux angles morts du simulateur.

FoundationDB suit une logique voisine. Sa documentation sur les tests clients explique que certains aspects multithread ne conviennent pas à la simulation monothread et sont couverts par des tests d’API de bout en bout sur un cluster réel.

La bonne stratégie est donc une défense en profondeur. La simulation déterministe explore rapidement les enchaînements rares, accélère le temps et transforme une panne fugitive en scénario rejouable. Les tests sur binaires et infrastructures réels vérifient les frontières que le modèle remplace. Les tests de performance, enfin, doivent rester ancrés dans des environnements représentatifs puisqu’un temps virtuel ne mesure pas une latence physique.

Le bénéfice décisif n’est pas seulement de relancer un test avec la même graine. C’est de pouvoir répondre précisément à trois questions : quelles décisions ont mené à l’échec, quelle propriété a été violée et quelles parties du résultat dépendent encore d’un modèle simplifié. Lorsqu’un banc sait y répondre, les pannes distribuées rares cessent d’être des anecdotes impossibles à reproduire. Elles deviennent des cas de test durables.

Équipe Daymain