Un cluster peut perdre une écriture après une suite d’événements presque impossible à provoquer volontairement : un nœud redémarre, un paquet prend du retard, une élection commence au mauvais moment et le disque répond dans un ordre inattendu. Le test échoue une fois sur plusieurs milliers d’exécutions. Puis il passe dès que les journaux de diagnostic sont activés.
Pour l’équipe, le problème n’est pas seulement de trouver le défaut. Il faut pouvoir le revoir. Sans cette possibilité, chaque correction repose sur une hypothèse et chaque nouvelle exécution risque de raconter une autre histoire.
La simulation déterministe répond à cette difficulté en contrôlant les décisions qui peuvent modifier l’exécution. L’horloge, le réseau, le stockage, l’ordonnancement des tâches et le hasard deviennent des entrées du banc de test. Une panne rare peut alors être ralentie, inspectée événement par événement, puis rejouée à partir des mêmes décisions.
Mais la reproductibilité n’est qu’une moitié du sujet. Un simulateur qui rejoue toujours des scénarios triviaux ne trouvera pas les défauts intéressants. Il doit aussi explorer des combinaisons variées et savoir reconnaître une violation réelle. C’est ce qui distingue une simple répétition contrôlée d’un véritable outil de test distribué.
Une graine ne rejoue que ce qui est contrôlé
Une graine est la valeur initiale fournie à un générateur pseudo-aléatoire, ou PRNG. Ce générateur produit une suite de valeurs qui semble aléatoire, mais qui est entièrement déterminée par son état initial. Avec la même graine et les mêmes appels dans le même ordre, il restitue la même suite. Le banc peut donc choisir à nouveau le même nœud à arrêter, le même paquet à perdre ou la même configuration à appliquer.
Cette promesse cesse dès qu’une décision importante échappe au 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 valeur différente. Le réseau, le système de fichiers ou un service externe peuvent également répondre dans un autre ordre.
Le premier décalage suffit. Il modifie la suite des événements, puis le nombre et l’ordre des appels au PRNG. La graine n’a pas changé, mais l’histoire, elle, a divergé.
La documentation de FoundationDB sur les tests clients précise cette condition : le rejeu fonctionne lorsque tous les comportements susceptibles d’influencer l’exécution restent 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 séparer deux propriétés souvent confondues :
- Le rejeu : une exécution donnée peut être reproduite à l’identique.
- L’exploration : le banc sait produire de nombreuses exécutions différentes et atteindre des états inhabituels.
Une graine peut identifier un chemin précis. Elle ne garantit ni que ce chemin restera stable face aux entrées externes, ni que les chemins explorés contiennent les situations les plus dangereuses. La graine est une clé d’accès à une exécution contrôlée, pas une stratégie complète de test.
La simulation déterministe doit donc être conçue comme une architecture de contrôle. Le générateur aléatoire n’en est que le point de départ.
En clair
Une simulation n’est réellement rejouable que si toutes les décisions capables d’influencer l’exécution passent par des mécanismes déterministes.
Les cinq frontières du non-déterminisme
FoundationDB montre ce que signifie une intégration poussé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. Le temps n’y avance pas continuellement. Le moteur sélectionne le prochain événement planifié, avance l’horloge jusqu’à sa date, exécute l’événement, 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. La documentation de test de FoundationDB présente également l’exécution déterministe monothread, le temps simulé, les modèles de réseau et de machines ainsi que les scénarios de panne rares employés par le projet.
Remplacer l’horloge réelle
Une lecture directe de 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 supprime cette dépendance. Les temporisations, les délais de retransmission, les baux et les échéances doivent tous consulter cette horloge contrôlée.
Le simulateur peut ainsi accélérer les périodes sans activité. S’il ne reste qu’un minuteur prévu dans une heure virtuelle, il n’a pas besoin d’attendre une heure réelle : l’horloge saute jusqu’au prochain événement. Des mécanismes dont les délais seraient prohibitifs dans un environnement classique deviennent alors testables rapidement.
Le contrôle doit atteindre la logique métier lorsque le temps modifie 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é. Une même entrée conserve donc le même résultat logique et le même chemin d’exécution.
Modéliser le réseau et le stockage
Un réseau simulé ne doit pas se contenter de livrer les messages en mémoire. Il doit pouvoir retarder, perdre, dupliquer ou réordonner les communications selon le modèle étudié. Il doit aussi pouvoir représenter une partition : pendant un temps, certains groupes de nœuds ne peuvent plus communiquer.
Le stockage demande une abstraction du même ordre. 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 que le logiciel prétend fournir, le modèle peut exposer des écritures incomplètes ou des données corrompues.
Le but n’est pas de reproduire toute la physique d’un disque. Il est de rendre explicites les comportements auxquels l’algorithme prétend résister. Un accès direct ajouté lors d’une refonte peut contourner cette couche et créer une nouvelle source de divergence.
Rendre l’ordonnancement visible
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. Il peut donc varier d’une exécution à l’autre, même lorsque les entrées applicatives sont identiques.
FoundationDB évite cette difficulté dans son simulateur avec 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 ainsi choisir explicitement l’ordre dans lequel les acteurs avancent.
Une autre approche consiste à contrôler l’entrelacement des threads existants. C’est l’un des rôles de l’environnement décrit par Antithesis. Dans les deux cas, les points où une tâche peut céder la main doivent être visibles par la plateforme.
Centraliser l’entropie
L’entropie désigne ici toute donnée utilisée comme source de hasard. Elle doit être centralisée, ou au moins interceptée. L’environnement Antithesis remplace notamment les périphériques Linux /dev/random et /dev/urandom par une entropie fournie par la plateforme. Il isole également les conteneurs du réseau extérieur et peut accélérer les périodes d’inactivité, comme le décrit sa documentation d’environnement.
Antithesis déconseille de mettre cette entropie en cache dans un PRNG applicatif. La plateforme aurait alors moins d’occasions de faire bifurquer l’historique et d’explorer d’autres chemins. Ce détail illustre une tension importante : la source de hasard doit être rejouable, mais elle doit aussi rester accessible au moteur d’exploration.
Explorer des pannes qui ont un intérêt
Un simulateur parfaitement déterministe peut être parfaitement inutile s’il répète des scénarios évidents. Le banc doit faire varier la topologie, la charge, la configuration et le calendrier des fautes. Le fuzzing intervient à ce niveau : cette technique génère ou transforme automatiquement des entrées afin de provoquer des comportements inattendus.
Dans un système distribué, les dimensions se combinent rapidement : requêtes clientes, taille du cluster, latences, redémarrages, pertes de messages, erreurs d’E/S et changements de rôle. FoundationDB randomise les configurations, les workloads et les paramètres de fautes. Son approche comprend aussi 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écrits dans son article d’architecture et de test.
La génération doit toutefois rester lisible. Arrêter tous les nœuds pour toujours montre seulement qu’un cluster sans machine ne progresse pas. Une panne utile place le système près de la frontière de ses garanties :
- une majorité reste disponible ;
- un nœud redémarre pendant une récupération ;
- une corruption est limitée à une opération ;
- une partition 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 ces couches doivent consommer une source de décisions enregistrable.
Lorsqu’un échec survient, le rapport doit au minimum conserver la graine, la configuration, le scénario et la nature de l’oracle violé. La graine seule ne permet pas toujours à une autre équipe de reconstruire le contexte.
Le rejeu peut ensuite servir à réduire le scénario. La réduction 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 lorsqu’elle n’est pas entièrement automatisée, la déterminisme permet de retirer un événement, puis de vérifier sans ambiguïté si le défaut persiste. Cette étape transforme une trace de plusieurs milliers d’événements en cas de test exploitable.
Le temps, le réseau, le stockage, l’ordonnancement concurrent et les sources d’entropie doivent être virtualisés ou interceptés.
Faire la différence entre sûreté et vivacité
Faire tomber des processus ne constitue pas un test complet. Il faut définir 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, c’est-à-dire une propriété qui doit rester vraie dans tous les états concernés.
Une propriété de sûreté affirme que quelque chose d’interdit ne se produit jamais. Selon le produit, l’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.
La vivacité pose 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 bloqué. Il peut aussi tomber dans un livelock : les composants continuent d’exécuter des actions, mais ces actions se répètent ou s’annulent sans produire de progrès utile.
La vivacité ne se teste pas correctement avec des perturbations maximales et permanentes. Si chaque tentative est interrompue, l’absence de progrès est normale. L’oracle doit donc formuler ses hypothèses. Une connectivité suffisante est-elle rétablie ? Un quorum, soit le nombre minimal de membres nécessaire à une décision collective, reste-t-il stable pendant une durée virtuelle donnée ?
Le simulateur VOPR de TigerBeetle sépare 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é explique pourquoi cette phase contrôlée révèle des blocages qu’un chaos permanent peut masquer.
La distinction améliore directement le diagnostic. Une violation de sûreté doit être signalée dès que l’état interdit apparaît. Une violation de vivacité nécessite 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 qui ne se terminent jamais.
Deux manières de rendre un système simulable
La première stratégie consiste à concevoir le logiciel pour la simulation. 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 dans un même processus déterministe. TigerBeetle fait également 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.
Le gain est un contrôle fin des frontières du système. Le coût est une discipline permanente. Une bibliothèque utilisée par le code testé ne doit pas lancer discrètement un thread, consulter l’horloge réelle ou produire son propre hasard. Les revues de code doivent donc traiter la simulabilité comme une propriété architecturale, et non 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 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 concret pour une pile existante composée de plusieurs services ou dépendante de comportements Linux. Le contrôle change toutefois de niveau. Au lieu d’injecter 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 dépend donc du système. 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. Une approche hybride est aussi possible : concevoir le cœur algorithmique pour la simulation, puis tester l’assemblage dans un environnement contrôlé plus large.
À retenir
Une graine reproduit une exécution contrôlée, mais ne garantit ni une bonne exploration de l’espace d’états ni la détection des erreurs.
Construire un banc rejouable par étapes
Le premier travail est un inventaire des entrées non déterministes. Il faut rechercher les lectures d’horloge, les générateurs aléatoires, les threads, les minuteurs, les appels réseau, les accès au système de fichiers, les processus enfants et les dépendances externes. Chaque élément doit être contrôlé, remplacé ou explicitement exclu du périmètre de rejeu.
Une architecture minimale peut ensuite progresser par étapes :
- 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.
- Injecter les dépendances. Le code reçoit des interfaces de temps, de réseau, de stockage et de hasard au lieu d’appeler directement le système d’exploitation.
- 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.
- 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.
- É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.
- Produire un artefact de rejeu. La graine doit être accompagnée de la configuration, des options actives et du scénario qui a échoué.
Il est préférable de commencer par une propriété étroite et un modèle simple : 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 l’identification de la cause d’une divergence. Le défaut vient-il du produit ou du simulateur ? Le même principe s’applique au banc lui-même. Une 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. Le simulateur est lui aussi un logiciel critique.
Perspective : la simulation ne remplace pas le réel
La simulation déterministe observe en profondeur les chemins algorithmiques qu’elle contrôle. Elle ne reproduit pas automatiquement tous les comportements du monde réel. Une interface réseau simulée 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, 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 stratégie solide repose donc sur 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 les binaires et les infrastructures réels vérifient les frontières que le modèle remplace ;
- les tests de performance restent ancrés dans des environnements représentatifs, car 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 à trois questions précises : 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 répondre à ces questions, les pannes distribuées rares cessent d’être des anecdotes impossibles à reproduire. Elles deviennent des cas de test durables, compréhensibles et vérifiables.
Sources
- FoundationDB: A Distributed Unbundled Transactional Key Value Store — ACM SIGMOD / auteurs FoundationDB, Apple, Snowflake et Antithesis
- Simulation and Testing — FoundationDB ON documentation — Apple et projet FoundationDB
- Client Testing — FoundationDB ON documentation — Apple et projet FoundationDB
- Deterministic simulation testing - how it works and when to use it — Antithesis
- The Antithesis environment — Antithesis
- TigerBeetle Architecture — TigerBeetle
- Simulation Testing For Liveness — TigerBeetle
- A Descent Into the Vörtex — TigerBeetle
Équipe Daymain
