Starcraft et Event Sourcing

Vous vous rappelez des biiiip crouuuiiiic cliiiiing du modem 56k de la fin des années 90 ? (oui je le fais hyper bien)

Cette sonnorité carctéristique d'une tentative de connexion internet était aussi, pour certains synonyme de stracraft en ligne.

Depuis que je suis informaticien, je me suis toujours demandé comment une connexion aussi famélique arrivait a suffire pour supporter une synchronisation temps reél entre 2,3 ou 4 joueurs

Autre bizarrerie, Un fichier de replay de StarCraft: Brood War, pour une partie de vingt minutes, pèse quelques dizaines de kilo-octets.

Prenez une seconde pour mesurer ce que ça implique. Vingt minutes de jeu, deux joueurs, des centaines d'unités, des milliers d'ordres, des combats, une économie complète. Dans le poids d'une image un peu lourde.

Parce que ce n'est pas une vidéo.

C'est le journal des commandes, rejoué dans le moteur.

Et ce détail raconte une décision d'architecture qui a trente ans, qui permettait de jouer à huit sur un modem 56k, et qui est exactement celle que je prends aujourd'hui majoritairement sur mes systèmes métier.

On invente jamais rien en développement logiciel.

Le calcul qui a tout décidé

En 1996, Ensemble Studios développe Age of Empires avec une contrainte simple : ça doit tourner à huit joueurs sur des modems.

L'approche naturelle serait de synchroniser l'état du monde. Chaque machine envoie la position de ses unités, les autres appliquent. C'est ce que fait un jeu de tir moderne, avec un serveur autoritatif.

Bettner et Terrano ont fait le calcul, et ils l'ont publié au GDC en 2001 dans un article devenu classique, « 1500 Archers on a 28.8 ». Le résultat est sans appel : en transmettant seulement les coordonnées, le statut, l'action, l'orientation et les dégâts de chaque unité, ils plafonnaient à environ 250 unités mobiles.

Or ils voulaient des batailles épiques. Des catapultes, des archers, des trirèmes qui assiègent une cité grecque. Deux cent cinquante unités, ce n'était pas le jeu qu'ils avaient en tête.

Alors ils ont retourné le problème.

Plutôt que de transmettre ce que le monde est, transmettons ce que les joueurs décident. « Les unités 12, 47 et 88 se déplacent en x, y. » Quelques dizaines d'octets, et surtout : un coût indépendant du nombre d'unités concernées. Sélectionnez douze ouvriers ou deux cents, l'ordre pèse pareil.

Chaque machine fait alors tourner la simulation complète, en local. Le réseau ne véhicule plus que les intentions.

Pourquoi le tuyau ne saturait jamais

Le budget devient dérisoire. Ensemble avait mesuré une commande toutes les une à deux secondes par joueur en moyenne, avec des pointes pendant les combats.

Même en Brood War à trois cents actions par minute, l'écrasante majorité de ces actions sont des sélections purement locales, qui ne traversent jamais le réseau. Il reste quelques centaines d'octets par seconde. Sur un modem à cinq kilo-octets par seconde, on utilise quelques pour cent du tuyau.

Et Battle.net ne relayait rien. Matchmaking et salon d'attente, puis les machines se parlaient directement. Pas de détour par un centre de données, ce qui à l'époque changeait tout.

Le tour, et le mensonge poli

Reste à synchroniser. La solution est le tour : le temps est découpé en pas, et les ordres émis au tour N ne s'exécutent qu'au tour N+2 ou N+3. Toutes les machines exécutent le même lot d'ordres, dans le même ordre, au même tour.

Ce décalage est un tampon. Il absorbe la latence du réseau. C'est le réglage que Brood War expose sous le nom de « latency », et qui échange du délai de commande contre de la tolérance au jitter.

Mais alors, pourquoi n'a-t-on jamais eu l'impression de jouer avec deux cents millisecondes de retard ?

Parce qu'on nous ment poliment.

Le clic produit un retour immédiat. Le curseur change, le son de sélection part, le marine répond « Yes sir! ». Tout ça est local et instantané. L'ordre, lui, ne s'appliquera que dans une fraction de seconde.

Ce n'est pas un artifice cosmétique, c'est le cœur du modèle. Et ça ne marche que parce que la sémantique d'un RTS le permet : on exprime une intention à moyen terme, pas une visée à la frame près. Le même délai dans un jeu de tir serait injouable.

Le prix : le déterminisme absolu

Voilà la facture, et elle est salée.

Si chaque machine calcule sa propre simulation à partir des mêmes ordres, alors les simulations doivent produire exactement le même résultat. Pas « à peu près ». Bit pour bit.

Ce qui interdit beaucoup de choses. Pas de virgule flottante, dont le comportement varie selon le compilateur et l'unité de calcul : on travaille en virgule fixe. Un générateur pseudo-aléatoire à graine synchronisée. Un calcul de chemin déterministe. Un ordre d'itération sur les entités qui ne varie jamais.

La moindre divergence est fatale, et elle est insidieuse. Une unité qui emprunte un chemin très légèrement différent sur une machine arrive une fraction de seconde plus tôt à une bataille. Elle tire en premier. L'issue du combat change. À partir de là, les deux parties racontent deux histoires différentes.

D'où les sommes de contrôle périodiques, et l'éjection du joueur qui a divergé.

Et surtout, la conséquence la plus brutale : la simulation avance à la vitesse du plus lent. Si un ordre manque, personne n'extrapole. Tout le monde attend. C'est le fameux « Waiting for players ».

Ce que ça dit de l'event sourcing

À ce stade, ça devrait vous rappeler quelque chose.

Un journal de commandes ordonné, une machine à états répliquée, un état dérivé par rejeu déterministe. C'est de l'event sourcing appliqué au temps réel, vingt ans avant que le terme ne devienne à la mode dans les conférences d'architecture.
( En réalité on peut aussi voir ça comme du command sourcing, d'ou le nécessaire déterminisme, mais passons )

Le replay n'est pas un enregistrement du résultat. C'est la source, rejouée. Voilà pourquoi le fichier est minuscule : il ne contient pas ce qui s'est passé, il contient ce qui a été décidé. Le reste est recalculé.

Et il y a un détail que je trouve savoureux. Chez Ensemble, l'enregistrement des parties est né comme un outil de débogage. Un moyen de reproduire un bug. C'est devenu une fonctionnalité à part entière, adorée des joueurs, qui a créé toute une culture d'analyse de parties ( NB: et qui a été le fondement des travaux d'IA menés sur Starcraft, mais c'est un autre sujet )

Le journal d'événements construit pour comprendre ce qui s'est passé devient le produit. Ça aussi, ça devrait parler à ceux qui font de l'event sourcing.

Là où l'analogie avec l'informatique de gestion s'arrête

Maintenant, la partie honnête, parce qu'une belle analogie mérite qu'on lui cherche ses limites.

Par exemple, le projet Kreek est pajoritairement event-sourcé, mais la différence est le déterminisme.

En lockstep, le déterminisme est une contrainte de vie ou de mort, parce que plusieurs machines doivent converger à l'identique en permanence. Chez moi, le rejeu sert à reconstruire un état, pas à le synchroniser avec quelqu'un d'autre. Dit autrement dans le cas d'accès concurrent, on peut se permettre d'avoir une donnée temporairement fausse - c'est la perte de consistence. Le métier me permet ça où un RTS s'effondrerait.

J'insiste deux secondes là dessus, cette possibilité de perte de consistence doit provenir du métier. Il y a des contextes ou la perte de consistence est beaucoup plus problématique. Le trading haute fréquence, ou la réservation en ligne par exemple.

Deuxième différence, et elle est de nature politique. Le lockstep tient parce que tous les participants sont symétriques et qu'un désaccord se règle brutalement : on éjecte le divergent. Le consensus n'a besoin ni de leader ni de quorum, il est garanti par l'ordonnancement et vérifié après coup.

Dans un système métier, on n'éjecte pas un utilisateur parce que son état a divergé. Il faut réconcilier, compenser, expliquer. C'est beaucoup moins élégant, et c'est infiniment plus fréquent.

Par exemple que se passe-t-il sur amazon quand deux personnes commandent le même dernier article dans le même temps ?
On reçoit un mail d'excuse à posteriori en disant que finalement notre article n'est plus disponible. Un exemple de réconciliation de l'état basé sur une décision métier.

Ce que j'en retiens

Le choix fondamental n'a pas changé depuis 1996 : transmettre l'état, ou transmettre les décisions.

Transmettre l'état, c'est robuste et tolérant, mais le volume explose avec la taille du monde. Transmettre les décisions, c'est d'une économie stupéfiante, mais ça exige que tout le monde calcule la même chose de la même façon.

Un stockage par événements, c'est le second choix. Avec ses cadeaux, dont le premier est qu'on peut toujours répondre à la question « comment en est-on arrivé là », et avec sa facture, qui est que le rejeu doit rester fidèle sur la durée.

Ceux qui ont conçu ça n'avaient pas de vocabulaire d'architecte. Ils avaient un modem à 56k et l'envie de faire s'affronter mille cinq cents archers.