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
- 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.
- 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.
- Limites respectées. Aucune exécution ne se fait au-dessus de la limite de l'acheteur ni au-dessous de celle du vendeur.
- Priorité respectée. Aucun ordre n'est servi tant qu'un ordre mieux placé du même côté, et compatible, attend encore.
- 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).
- 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 la quantité reçue, la quantité exécutée, la quantité en attente et la quantité annulée ou abandonnée, l'invariant 1 s'écrit :
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.
Rejeu 1
- 1. a1 A 30@10 000
- 2. v1 V 20@10 100
- 3. a2 A 25@10 000
- 4. v2 V 40@10 000
- 5. annuler v1
- 6. v3 V 10@9 950
- 7. v4 V 15@10 050
- 8. m1 A 10@marché
#03e91792
Rejeu 2
- 1. a1 A 30@10 000
- 2. v1 V 20@10 100
- 3. a2 A 25@10 000
- 4. v2 V 40@10 000
- 5. annuler v1
- 6. v3 V 10@9 950
- 7. v4 V 15@10 050
- 8. m1 A 10@marché
#03e91792
déterministe
événement 1/8
Empreintes identiques
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.
- 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 :
generer(1)produit 12 ordres, dont les identifiants sont tirés parmi six valeurs.idsUniquesrejoue la séance et renvoiefalse: deux ordres en attente partagent un identifiant.retrecirretire les ordres un à un ; chaque retrait qui laisse la propriété en échec est gardé.- Il reste deux ordres :
o2, achat 20 à 10 050, puiso2, 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
À 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.