Reconstruire un carnet d'ordres depuis un flux MBO

Un flux MBO (market by order) ne donne pas le carnet d'ordres: il donne tout ce qui lui arrive. Chaque ordre posé, modifié, annulé ou exécuté, un message à la fois. Le carnet, c'est à moi de le reconstruire, et de le reconstruire exactement comme la bourse le voyait.

C'est le cœur d'Orion, mon moteur de trading. Il travaille sur le contrat à terme sur l'or du CME (GC). Ma fenêtre de mesure couvre deux ans, 600 journées et plus d'un milliard de messages ordre par ordre. Voici comment je les transforme en carnet.

Ce que contient un message#

Chaque message décrit un événement sur un ordre, identifié par un numéro unique. Une fois décodé, Orion le réduit à l'essentiel:

pub struct OrderEvent {
  ts: Ts,                   // instant de réception
  contract: ContractSlot,
  order_id: OrderId,
  action: OrderAction,      // ajout, annulation, modification, exécution…
  side: Option<Side>,
  price: Option<Px>,
  size: Option<Tally>,
  flags: EventFlags,        // fin d'événement, instantané, horodatage douteux…
}

Sur la fenêtre complète, les messages se répartissent à peu près ainsi:

Deux détails comptent dès le décodage. D'abord, je trie sur l'instant de réception, jamais sur l'horodatage de la bourse: trier sur ce dernier laisserait une stratégie réagir à un événement avant de pouvoir physiquement le recevoir. Ensuite, les valeurs « non renseignées » du format binaire ne passent jamais telles quelles: elles deviennent une absence (None) ou un refus.

Les structures du carnet#

Un carnet, c'est deux côtés (acheteurs, vendeurs), chacun fait de niveaux de prix, chacun fait d'une file d'ordres servis dans leur ordre d'arrivée. Les opérations à rendre rapides sont claires: retrouver un ordre par son identifiant, l'ajouter au bout d'une file, l'en retirer n'importe où, et connaître le meilleur prix à tout moment.

• Les ordres vivent dans une arène (slab): un grand tableau dont les cases libérées sont réutilisées. Pas d'allocation par ordre.
• Une table de hachage relie chaque identifiant d'ordre à sa case.
• Chaque niveau est une liste chaînée à travers l'arène, avec son total et son nombre d'ordres tenus à jour.
• Les niveaux d'un côté sont triés par prix, et le meilleur prix est gardé dans un champ, relu seulement quand le meilleur niveau se vide.

pub struct Level {
  head: Option<OrderKey>,   // premier de la file
  tail: Option<OrderKey>,   // dernier arrivé
  total: Tally,             // quantité totale au niveau
  orders: u32,
}

Pour la table de hachage, j'ai remplacé le hachage par défaut de Rust (SipHash, résistant aux attaques) par un mélange simple, splitmix64. Les identifiants viennent de fichiers de la bourse, personne ne les choisit pour me nuire. Mesuré sur la journée la plus chargée:

Même qualité de répartition, 10 % plus rapide.

Appliquer chaque action#

• Un ajout place l'ordre au bout de la file de son niveau. Un identifiant déjà présent est refusé.
• Une annulation retire la quantité indiquée. À zéro, l'ordre quitte le carnet et sa case est libérée.

La modification est l'action délicate, parce qu'elle peut faire perdre sa place dans la file. La règle du CME est isolée dans un crate dédié:

if to != shown.price { return Priority::Lost(Requeue::Repriced); }
if shown.executed >= shown.size { return Priority::Lost(Requeue::Refreshed); }
if of > shown.size { return Priority::Lost(Requeue::Enlarged); }
if of < shown.size { return Priority::Kept; }
Priority::Lost(Requeue::Unobservable)

Changer de prix, augmenter sa quantité ou être un ordre « iceberg » qui se recharge fait repasser l'ordre en fin de file. Réduire sa quantité lui garde sa place.

• Une remise à zéro vide tout le carnet: c'est une réinitialisation du canal.
• Les messages d'exécution ne touchent pas au carnet. C'est contre-intuitif, mais sur le CME la quantité exécutée est déjà retirée par les annulations et modifications envoyées avec la transaction. La retirer aussi sur l'exécution la compterait deux fois. Les exécutions sont quand même notées, pour la file d'attente et pour le simulateur d'exécution.

Ne lire le carnet qu'en fin d'événement#

Une seule transaction peut produire une dizaine de messages: la transaction, les exécutions de chaque ordre touché, les retraits correspondants. Entre le premier et le dernier, le carnet est dans un état qui n'a jamais existé pour personne.

Le dernier message d'un événement porte un drapeau de fin d'événement. Orion ne publie le carnet que sur ce message-là:

if !event.flags().is_last_in_event() {
  return Ok(None);          // en plein événement: aucun lecteur possible
}
self.settles(event.ts(), watcher)?;
Ok(Some(EventBook::at(self, event.ts(), replayed)))

Ce n'est pas une politesse. Lire les états intermédiaires introduit un biais systématique, pas aléatoire: on verrait par exemple un niveau vidé avant que l'ordre qui le remplace n'arrive. Ici, lire un carnet incohérent est impossible par construction, le type n'expose rien entre deux fins d'événement.

Les pièges du flux#

Les instantanés. Le flux contient régulièrement un instantané du carnet complet, pour qu'on puisse démarrer sans tout l'historique. La forme décrite dans la documentation ne correspondait pas à ce qui arrivait réellement: il a fallu mesurer la forme réelle sur toute la fenêtre avant d'écrire la règle.

Et quand le carnet est déjà intact au moment d'un instantané, Orion ne l'adopte pas: il le vérifie. Un instantané est lui-même le produit d'un carnet reconstruit par quelqu'un d'autre, qui peut gérer différemment de la bourse des cas fins comme la priorité des icebergs rechargés. Adopter l'instantané reviendrait à remplacer une file juste par une file potentiellement fausse. Sur toute la fenêtre: zéro contradiction entre mon carnet et les instantanés vérifiés.

Les identifiants inconnus. Une annulation sur un ordre que je n'ai jamais vu est refusée, là où on voit souvent l'ordre ajouté silencieusement. Mesuré sur toute la fenêtre: zéro identifiant inconnu, zéro ajout en double, zéro annulation excessive. Le refus ne coûte rien, et il me dirait immédiatement si quelque chose dérivait.

Les trous dans le flux. Un message peut signaler que le carnet a peut-être raté des événements. Le carnet passe alors en état « douteux », et toute estimation de position dans la file devient indisponible, jusqu'à ce qu'un instantané complet le rétablisse.

Les carnets croisés. Hors séance, le meilleur prix acheteur peut dépasser le meilleur prix vendeur: les ordres attendent l'ouverture. Ce n'est pas une erreur, c'est l'état du marché, et c'est le statut de séance publié par la bourse qui dit quand le lire comme un carnet « normal ».

Vérifier que c'est juste#

Un carnet faux ne plante pas: il donne des chiffres plausibles. La vérification est donc la moitié du travail.

• Des invariants, vérifiés après chaque séquence de test: un niveau vide disparaît, chaque ordre est dans exactement une file et indexé une seule fois, le total d'un niveau égale la somme de ses ordres, etc.
• Un carnet de référence naïf: un simple vecteur d'ordres dans leur ordre d'arrivée. Des séquences aléatoires (avec proptest) et toutes les séquences courtes possibles sont appliquées aux deux carnets, qui doivent rester identiques, niveau par niveau et ordre par ordre.
• La comparaison à un carnet publié: sur six journées réelles, à chaque fin d'événement, mes dix meilleurs niveaux de chaque côté (prix, quantité, nombre d'ordres) doivent égaler un carnet à dix niveaux publié indépendamment. Résultat: accord sur 100 % des fins d'événement, plus de quatre millions de comparaisons.
• La file d'attente: pour chaque transaction, les ordres exécutés doivent être ceux en tête de ma file reconstruite. Sur des dizaines de millions de transactions, toutes tombent dans un cas expliqué, et aucune dans la catégorie « inexpliquée ».

Les performances#

Le carnet n'alloue rien sur le chemin normal: l'arène réutilise ses cases, les tampons sont recyclés. Au plus chargé, il tient quelques milliers d'ordres, moins d'un mégaoctet. L'application d'un message coûte de 75 à 89 nanosecondes sur mes journées de test, soit de l'ordre de 11 à 13 millions de messages par seconde, sur un seul cœur.

Ce que j'en retiens#

• Le flux décrit des événements, pas des états. On ne lit le carnet que là où il a réellement existé: en fin d'événement.
• Mesurer le flux réel, pas seulement lire la doc. L'instantané documenté n'apparaissait jamais tel quel.
• Refuser plutôt que deviner. Un identifiant inconnu, une modification incohérente: chaque refus est un signal, pas une gêne.
• Un carnet se prouve. Invariants, implémentation de référence, comparaison à un carnet publié: c'est ce qui me permet de construire des stratégies dessus sans douter des fondations.