Aller au contenu
Criée

Les invariants d’un moteur

Conservation, carnet non croisé, limites, priorité, horodatage, déterminisme, et les tests par propriétés qui les gardent.

Leçon 613 min

À la fin de cette leçon

  • Énoncer les six invariants d’un moteur et reconnaître leur violation
  • Repérer ce qui menace le déterminisme d’un moteur de cotation
  • Exploiter un test par propriétés : rejouer la graine, lire le rétrécissement
Dans cette leçon4

Un test d'exemple vérifie un cas : « cet achat de 8 produit ces deux exécutions ». Un invariant vérifie une propriété pour tous les cas : « aucune exécution ne crée ni ne détruit de titres ». Un moteur de cotation se protège surtout par ses invariants, parce que personne ne peut écrire à la main toutes les séances possibles.

Invariant

Propriété qui doit rester vraie après chaque opération du moteur, quelles que soient les entrées.

Six invariants d'un moteur

  1. Conservation des quantités. Pour chaque ordre : quantité exécutée + quantité en attente + quantité annulée ou abandonnée = quantité reçue. Aucun titre n'apparaît ni ne disparaît.
  2. Carnet non croisé. En cotation continue, après chaque ordre, le meilleur achat reste strictement inférieur à la meilleure vente. Sinon, deux ordres compatibles attendent sans s'échanger.
  3. Limites respectées. Aucune exécution ne se fait au-dessus de la limite de l'acheteur ni au-dessous de celle du vendeur.
  4. Priorité respectée. Aucun ordre n'est servi tant qu'un ordre mieux placé du même côté, et compatible, attend encore.
  5. Horodatage monotone. Le rang d'arrivée croît strictement. C'est lui qui fonde la priorité de temps ; à la BVMAC, chaque ordre est horodaté dès sa réception par la société de bourse (RG BVMAC 2025, art. 150).
  6. Déterminisme. La même suite d'ordres produit toujours la même suite d'exécutions. Conséquence directe : en conservant le journal des entrées, on peut rejouer une séance et reconstruire l'état du carnet à n'importe quel instant.

Pour un ordre, en notant QrQ_r la quantité reçue, QeQ_e la quantité exécutée, QaQ_a la quantité en attente et QxQ_x la quantité annulée ou abandonnée, l'invariant 1 s'écrit :

Qe+Qa+Qx=QrQ_e + Q_a + Q_x = Q_r

L'invariant 2 n'a rien de magique : il découle des deux break de la boucle lue dans La cotation continue, ligne à ligne. Tant qu'un ordre compatible attend en face, la boucle continue ; elle ne s'arrête que lorsque plus rien ne convient.

De mémoire, leçon 4 : pourquoi la boucle de Carnet.passer peut-elle s'arrêter au premier ordre incompatible, et quel invariant en découle ?

Déterminisme

Propriété d'un moteur qui, pour la même suite d'entrées, produit toujours la même suite de sorties.

Le déterminisme se perd facilement : un appel à Date.now() ou à Math.random() dans le moteur, un parcours de structure dont l'ordre n'est pas garanti, un calcul en flottants. Le moteur pédagogique n'en contient aucun : le temps y est un rang fourni de l'extérieur, et tout départage finit sur ce rang.

Nous n'avons trouvé aucune source de haute confiance décrivant comment les plateformes réelles garantissent le déterminisme et le rejeu (ordonnancement total des événements, réplication d'état). Les invariants 4 à 6 sont présentés comme des principes de conception du moteur pédagogique. Pour l'horodatage, la réglementation européenne donne un ordre de grandeur, sans s'appliquer en CEMAC : traçabilité par rapport à l'UTC, et pour le trading à haute fréquence un écart maximal de 100 microsecondes (règlement délégué (UE) 2017/574).

Un test par propriétés, sans bibliothèque

Un test par propriétés génère beaucoup d'entrées et vérifie qu'un invariant tient pour chacune. La seule exigence : un générateur reproductible, piloté par une graine, pour qu'un échec puisse se rejouer.

import { Carnet } from '@criee/marche'
import { expect, it } from 'vitest'

it('conserve les quantités sur 200 séances aléatoires', () => {
  for (let graine = 1; graine <= 200; graine++) {
    const r = alea(graine) // générateur déterministe, par exemple mulberry32
    const c = new Carnet(10000)
    const recu = new Map<string, number>()
    const execute = new Map<string, number>()
    for (let k = 0; k < 16; k++) {
      const id = `o${k}`
      const quantite = 1 + Math.floor(r() * 50)
      recu.set(id, quantite)
      const sens = r() < 0.5 ? 'achat' : 'vente'
      for (const e of c.passer({ id, sens, quantite, limite: 9900 + 25 * Math.floor(r() * 9) })) {
        execute.set(e.achat, (execute.get(e.achat) ?? 0) + e.quantite)
        execute.set(e.vente, (execute.get(e.vente) ?? 0) + e.quantite)
      }
    }
    const { achats, ventes } = c.ordres()
    const enAttente = new Map([...achats, ...ventes].map((o) => [o.id, o.quantite]))
    for (const [id, q] of recu) {
      expect((execute.get(id) ?? 0) + (enAttente.get(id) ?? 0), `graine ${graine}, ordre ${id}`).toBe(q)
    }
  }
})

Le message graine ${graine} est la moitié du travail : quand le test échoue, il dit quelle séance rejouer.

Le déterminisme se teste en rejouant deux fois le même journal :

it('rejoue une séance à l’identique', () => {
  const journal = genererSeance(42) // liste d'ordres, sans rang
  const rejouer = () => {
    const c = new Carnet(10000)
    return journal.flatMap((o) => c.passer(o))
  }
  expect(rejouer()).toEqual(rejouer())
})

Le même test, en mouvement : deux rejeux du même journal, événement après événement, avec l'empreinte des exécutions et du carnet. Choisissez ensuite « Ordre d'arrivée non garanti » : deux achats reçus « en même temps » sont traités dans l'autre ordre au second rejeu. Les empreintes divergent dès le premier événement (les rangs changent), les exécutions à partir du quatrième.

Rejouer deux fois la même séance1/8

Rejeu 1

  1. 1. a1 A 30@10 000
  2. 2. v1 V 20@10 100
  3. 3. a2 A 25@10 000
  4. 4. v2 V 40@10 000
  5. 5. annuler v1
  6. 6. v3 V 10@9 950
  7. 7. v4 V 15@10 050
  8. 8. m1 A 10@marché

#03e91792

Rejeu 2

  1. 1. a1 A 30@10 000
  2. 2. v1 V 20@10 100
  3. 3. a2 A 25@10 000
  4. 4. v2 V 40@10 000
  5. 5. annuler v1
  6. 6. v3 V 10@9 950
  7. 7. v4 V 15@10 050
  8. 8. m1 A 10@marché

#03e91792

déterministe

événement 1/8

Empreintes identiques

Même journal, même moteur, mêmes sorties : l’empreinte des exécutions et du carnet est identique à chaque événement.

Le moteur reste déterministe dans les deux cas : c'est l'ordre du journal qui a changé. Le déterminisme suppose donc un journal totalement ordonné, ce qui est un choix de conception du système autour du moteur. La leçon Journaliser et rejouer une séance en fait un outil de reprise.

Le banc, en direct

Le banc ci-dessous lance 200 séances de 16 opérations (ordres limités, ordres au marché, annulations) et vérifie quatre invariants après chaque opération. Changez la graine : les séances changent, les invariants tiennent, et deux rejeux de la même séance donnent la même empreinte.

Banc d’invariants0/200 séances
  • Conservation : exécuté + en attente + annulé + abandonné = quantité reçue0 contrôles · 0 violation(s)
  • Carnet non croisé : meilleur achat < meilleure vente0 contrôles · 0 violation(s)
  • Limites respectées : aucun prix hors limite d’un des deux ordres0 contrôles · 0 violation(s)
  • Déterminisme : rejouer la séance redonne les mêmes exécutions0 contrôles · 0 violation(s)

De mémoire : pourquoi un générateur aléatoire de test doit-il prendre une graine ?

Plus loin

Rétrécir un contre-exemple

Une séance aléatoire qui fait échouer un invariant contient souvent des ordres inutiles. Avant d'en faire un test d'exemple, réduisez-la.

Rétrécissement

Réduction automatique d'une entrée qui fait échouer un test par propriétés, jusqu'au plus petit contre-exemple.

Les bibliothèques de tests par propriétés le font pour vous. Sans bibliothèque, la version la plus simple tient en quelques lignes : retirer un ordre, rejouer, garder le retrait si la propriété échoue toujours, recommencer jusqu'à ce qu'aucun retrait ne soit possible.

import { Carnet, type Ordre, type Sens } from '@criee/marche'

type Entree = Omit<Ordre, 'rang'>

// Propriété : deux ordres en attente ne partagent jamais un identifiant
function idsUniques(seance: Entree[]): boolean {
  const c = new Carnet(10000)
  for (const o of seance) c.passer(o)
  const { achats, ventes } = c.ordres()
  const ids = [...achats, ...ventes].map((o) => o.id)
  return new Set(ids).size === ids.length
}

// Retirer un ordre tant que la propriété échoue encore
function retrecir(seance: Entree[], echoue: (s: Entree[]) => boolean): Entree[] {
  let courant = seance
  let progres = true
  while (progres) {
    progres = false
    for (let k = 0; k < courant.length; k++) {
      const candidat = [...courant.slice(0, k), ...courant.slice(k + 1)]
      if (echoue(candidat)) {
        courant = candidat
        progres = true
        break
      }
    }
  }
  return courant
}

// 12 ordres, identifiants tirés parmi six valeurs : des doublons sont probables
function generer(graine: number): Entree[] {
  const r = alea(graine) // mulberry32, comme plus haut
  return Array.from({ length: 12 }, () => ({
    id: `o${Math.floor(r() * 6)}`,
    sens: (r() < 0.5 ? 'achat' : 'vente') as Sens,
    quantite: 1 + Math.floor(r() * 50),
    limite: 9900 + 50 * Math.floor(r() * 5),
  }))
}

const seance = generer(1)
idsUniques(seance) // false
retrecir(seance, (s) => !idsUniques(s))
// [{ id: 'o2', sens: 'achat', quantite: 20, limite: 10050 },
//  { id: 'o2', sens: 'achat', quantite: 8, limite: 10050 }]

Pas à pas, sur la graine 1 :

  1. generer(1) produit 12 ordres, dont les identifiants sont tirés parmi six valeurs.
  2. idsUniques rejoue la séance et renvoie false : deux ordres en attente partagent un identifiant.
  3. retrecir retire les ordres un à un ; chaque retrait qui laisse la propriété en échec est gardé.
  4. Il reste deux ordres : o2, achat 20 à 10 050, puis o2, achat 8 à 10 050. Retirer l'un ou l'autre ferait passer le test.

Deux ordres, un défaut : c'est la limite connue n° 3 de la fiche du contrat du moteur, les identifiants ne sont pas vérifiés. Le contre-exemple réduit devient un test d'exemple ; la correction reste une décision à prendre.

Coût. Chaque passe essaie au plus n retraits, chaque essai rejoue toute la séance, et il peut falloir de l'ordre de n passes : O(n²) rejeux dans le pire cas. Pour 12 ordres, c'est instantané. Pour une séance de 10 000 ordres, retirez d'abord des moitiés, puis des quarts, avant de descendre à l'ordre près.

Piège. Le résultat est un minimum local, pas le plus petit contre-exemple absolu : aucun retrait d'un seul ordre ne fait plus échouer la propriété, mais une autre combinaison plus courte peut exister. Les valeurs (quantités, prix) ne sont pas réduites non plus : c'est une seconde passe à écrire si vous en avez besoin.

À toi de jouer

Après un ordre en continu, le meilleur achat vaut 10 050 et la meilleure vente 10 000. Que concluez-vous ?

1Après un ordre en continu, le meilleur achat vaut 10 050 et la meilleure vente 10 000. Que concluez-vous ?

Lequel de ces appels menace le déterminisme d'un moteur ?

2Lequel de ces appels menace le déterminisme d'un moteur ?

Un test par propriétés échoue sur la graine 137. Que faites-vous d'abord ?

3Un test par propriétés échoue sur la graine 137. Que faites-vous d'abord ?

Le rétrécissement réduit une séance fautive de 12 ordres à 2. Ce résultat est...

4Le rétrécissement réduit une séance fautive de 12 ordres à 2. Ce résultat est...

Deux rejeux divergent parce que deux événements du journal ont changé d'ordre. Le moteur est...

5Deux rejeux divergent parce que deux événements du journal ont changé d'ordre. Le moteur est...

À lire ensuite : Règlement général de la BVMAC (2025)

Une question ? Posez-la à votre enseignant, ou à un assistant IA en lui donnant le titre de cette leçon.

Partager :WhatsAppLinkedIn

Pour aller plus loin