Concevoir un matching engine en Rust : price-time priority sans pauses GC

Un matching engine de bourse spot a un rôle étroit. Il prend un flux ordonné de commandes - nouvel ordre, annulation, remplacement - les applique à un order book sous price-time priority, et émet un flux ordonné d'événements : trades, mises à jour du carnet, rejets, accusés de réception.

Toute la difficulté vient de trois contraintes empilées par-dessus ce rôle : le résultat doit être identique à chaque replay de la même entrée, le reliquat d'un ordre partiellement exécuté doit garder sa place dans la file, et la queue de latence ne doit pas bouger quand une rafale arrive.

L'order book est un index trié de niveaux de prix au-dessus de files FIFO

Le carnet, c'est deux côtés, chacun une collection de niveaux ordonnée par prix. Un niveau n'est pas un nombre - c'est une file d'ordres en attente à ce prix, dans l'ordre d'arrivée. L'appariement touche constamment le meilleur niveau et rarement les niveaux profonds : la structure est choisie pour ce schéma d'accès plutôt que pour l'élégance.

• Les prix sont des entiers en ticks, jamais des flottants - un tick est l'unité de l'instrument, et comparaison et arithmétique sur les entiers sont exactes
• Chaque côté garde ses niveaux ordonnés par prix, le meilleur prix étant atteignable sans recherche - le haut du carnet est lu à chaque commande
• Un niveau contient une file FIFO d'ordres en attente, plus la quantité en attente agrégée, pour que l'agrégat n'ait pas à être recalculé en parcourant la file
• Les ordres sont conservés dans un slab préalloué et référencés par des handles d'index, et la file est intrusive : les liens suivant et précédent vivent dans l'enregistrement d'ordre lui-même
• Une table séparée de l'id d'ordre client vers le handle de slab fait de l'annulation et du remplacement une recherche directe : une annulation ne parcourt jamais le carnet
• Le retrait d'une file se fait par handle, pas par recherche - annuler un ordre en attente profond coûte autant qu'annuler en haut du carnet

La conséquence des files intrusives et des handles d'index est qu'un ordre en attente ne bouge jamais en mémoire tant qu'il vit. Sa position dans la file est une propriété de ses liens, pas de l'endroit où il se trouve, et c'est ce qui rend les exécutions partielles peu coûteuses ensuite.

La price-time priority est une boucle sur les niveaux, puis sur une file

Un ordre agressif entrant parcourt le côté opposé depuis le meilleur prix vers l'intérieur. À chaque niveau, il parcourt la file FIFO depuis la tête. Il s'arrête quand le prix du niveau n'est plus acceptable pour l'ordre entrant ou quand la quantité entrante atteint zéro.

• Prendre le meilleur niveau opposé ; si son prix ne croise pas le prix limite entrant, s'arrêter
• Prendre l'ordre en tête de la file de ce niveau - c'est le plus ancien à ce prix, et la priorité temporelle veut qu'il soit exécuté en premier
• La quantité échangée est la plus petite des deux quantités restantes ; le prix du trade est celui de l'ordre en attente, car c'est lui qui a posé les conditions
• Décrémenter les deux reliquats, émettre l'événement de trade, et décrémenter l'agrégat du niveau
• Si le reliquat de l'ordre en attente atteint zéro, le retirer de la file et rendre son emplacement de slab ; si le niveau devient vide, supprimer le niveau
• Répéter jusqu'à ce que la quantité entrante soit nulle ou qu'il ne reste aucun niveau acceptable

La sémantique des types d'ordres relève de décisions prises à la frontière de cette boucle, pas à l'intérieur. Immediate-or-cancel abandonne le reliquat au lieu de le poser. Fill-or-kill fait d'abord une passe à blanc et exécute en entier ou rejette. Post-only rejette si l'ordre croiserait à l'arrivée. Garder cela hors de la boucle fait que la boucle reste le seul endroit où l'état du carnet change.

La prévention du self-trade, les quantités minimales et la validation du tick et du lot ont aussi leur place avant la boucle. Un ordre qui atteint l'appariement a déjà été prouvé bien formé : la boucle n'a donc aucune branche d'erreur pour la ralentir ou prêter à désaccord.

Le déterminisme rend la queue de latence prévisible, et l'allocation la casse

La latence moyenne est rarement le problème. Le problème, c'est la pire observation pendant une rafale, au moment où le moteur compte le plus et où une pause stop-the-world a le plus de chances de tomber. Sous un runtime managé doté d'un garbage collector, cette pause est planifiée par le collecteur et non par vous, et elle tombe au milieu de la rafale qui a produit les déchets.

L'allocation manuelle est une version réduite du même problème. Un allocateur généraliste peut parcourir des free lists, prendre un verrou ou demander plus de mémoire au noyau, et c'est cet appel-là qui apparaît dans la queue de latence. Le remède est le même dans les deux cas : ne pas allouer du tout sur le hot path.

• Les enregistrements d'ordres, de niveaux et les tampons d'événements viennent d'arènes dimensionnées au démarrage - en régime établi, le nombre d'allocations sur le chemin d'appariement est zéro
• Les emplacements libérés retournent dans une free list au sein de l'arène : un instrument actif recycle la même mémoire toute la session
• Les structures ont une forme et une taille fixes, les limites de capacité étant appliquées comme un rejet et non comme un agrandissement
• Les événements sortants sont écrits dans un ring buffer préalloué qu'un autre thread vide - le thread d'appariement ne se bloque jamais sur un consommateur
• Le thread d'appariement est un écrivain unique sur le carnet : il n'y a ni verrou sur l'état du carnet ni ambiguïté d'ordre à trancher
• Les entrées sont séquencées avant d'atteindre le moteur, et c'est le numéro de séquence, pas l'heure d'arrivée, qui décide de l'ordre

Un moteur est déterministe quand la même séquence d'entrée produit la même séquence de sortie, octet pour octet, sur une autre machine et un an plus tard. Tout ce qui lit l'horloge murale, l'ordonnancement des threads ou l'ordre d'itération d'un hash à l'intérieur du chemin d'appariement brise cette propriété.

Les horodatages sont donc une entrée, pas quelque chose que le moteur lit de lui-même. Le séquenceur horodate une commande quand il l'accepte, et la boucle d'appariement traite l'horodatage comme une donnée. L'aléa, s'il en faut, vient d'un générateur à graine dont la graine fait partie du journal.

Le journal est l'état du moteur, et le carnet en est un cache

La reprise n'est pas une fonctionnalité ajoutée une fois l'appariement au point. Le moteur écrit un journal en append-only des commandes acceptées dans l'ordre de séquence, et le carnet en mémoire n'est rien d'autre que le résultat du repliement de ce journal. Reconstruire après un crash, c'est le rejouer.

• Une commande est journalisée et durable avant d'être appariée : un ordre accepté ne peut donc pas être perdu par un crash entre l'accusé de réception et l'exécution
• Le journal est la séquence d'entrée, pas la sortie - les sorties sont dérivées, et les re-dériver est exactement ce que fait le replay
• Les instantanés périodiques du carnet portent le numéro de séquence auquel ils ont été pris : la reprise charge un instantané et ne rejoue que la fin du journal
• La concordance entre instantané et replay est vérifiée plutôt que supposée : rejouer depuis l'instantané précédent doit reproduire le suivant
• Le flux d'événements porte les mêmes numéros de séquence : les consommateurs en aval - risque, règlement, données de marché - peuvent reprendre depuis un point connu au lieu d'être resynchronisés à la main

Le moteur écrit le journal, mais la durabilité est une propriété du chemin de stockage et du nombre de machines qui détiennent l'enregistrement avant que l'accusé de réception ne parte. C'est une décision de réplication et de matériel, et c'est là que le temps de reprise se gagne ou se perd réellement.

Les tests, c'est du replay déterministe plus des invariants qui doivent toujours tenir

Le déterminisme est ce qui rend le moteur testable. Comme la même entrée donne la même sortie, une session capturée est un test de non-régression, et une défaillance trouvée une fois se reproduit exactement au lieu d'être pourchassée.

• Harnais de replay : injecter une séquence de commandes enregistrée, comparer le flux d'événements émis à celui stocké, et échouer à la première divergence en donnant le numéro de séquence
• Vérification des invariants après chaque commande dans les builds de test - files triées par arrivée, agrégats de niveau égaux à la somme de leur file, carnet non croisé, quantité totale conservée sur chaque trade
• Des tests basés sur les propriétés, qui génèrent des séquences de commandes aléatoires mais bien formées et vérifient les invariants plutôt que des résultats précis
• Un modèle de référence différentiel : une implémentation lente et manifestement correcte, à structures de données naïves, exécutée sur la même entrée, tout écart étant traité comme un bug de la version rapide
• Fuzzing à la frontière du décodeur, là où une entrée malformée arrive de l'extérieur et où un panic ferait tomber le thread d'appariement
• Mesure de latence sous la forme de rafale qui vous inquiète, en enregistrant la distribution plutôt qu'une moyenne, puisque la queue est le chiffre qui décide de la conception

Ce que Rust apporte ici, et ce qu'il n'apporte pas

Rust supprime une catégorie de problème plutôt que d'accélérer la boucle par lui-même. Il n'y a pas de garbage collector, donc aucune pause n'est planifiée dans votre dos. L'ownership fait de la discipline d'écrivain unique quelque chose que le compilateur impose au lieu de quelque chose qu'une revue de code doit remarquer. Les handles de slab et les liens intrusifs, sources d'erreurs dans un langage sans lifetimes, sont vérifiables ici. Les panics sur dépassement d'entier dans les builds de debug attrapent une classe de bug qui corrompt silencieusement un carnet.

La limite honnête, c'est que l'essentiel de ce qui détermine la latence de queue n'est pas le langage :

• L'ordonnancement du noyau, la gestion des interruptions, le pinning CPU et la gestion d'énergie déplacent la queue de latence plus que le code d'appariement
• L'interface réseau, le kernel bypass ou son absence, et le chemin physique vers la place de marché fixent un plancher sous lequel le moteur ne peut pas descendre
• La sérialisation et le protocole de transport à la frontière sont souvent le coût dominant, pas l'appariement lui-même
• La sémantique d'appariement, les types d'ordres, les règles de frais et de rebates et les phases de marché sont des décisions métier - une règle fausse implémentée vite reste fausse
• Les contrôles de risque, les limites de position et le chemin de règlement vivent hors du moteur et ont leur propre latence et leurs propres modes de défaillance
• L'exploitation - déploiement, supervision, runbook pour un replay raté - décide si les garanties survivent au contact d'un incident de production

Rust coûte aussi quelque chose. Le borrow checker ralentit les premières semaines d'une conception encore mouvante, l'écosystème pour les protocoles spécifiques aux places de marché est plus mince que dans des langages plus anciens, et les blocs unsafe autour des structures lock-free demandent la même discipline de revue que le code équivalent ailleurs. Le choisir est une décision sur la queue de latence et sur la sûreté mémoire dans un cœur à écrivain unique, pas une décision de confort pour les développeurs.

amBrain construit des infrastructures de trading à Erevan, en Arménie, depuis 2019, avec des hot paths en Rust - données de marché livrées en moins de 5 ms, contrôles de risque pre-trade en moins de 1 ms. Si vous concevez un matching engine et voulez parcourir la structure du carnet, le format du journal ou le harnais de replay, cette conversation vaut la peine d'être tenue avant la première ligne du hot path.