An engine’s invariants
Conservation, uncrossed book, limits, priority, timestamps, determinism, and the property-based tests that guard them.
Lesson 613 min
By the end of this lesson
- State the six invariants of an engine and recognise a breach
- Spot what threatens the determinism of a matching engine
- Use a property-based test: replay the seed, read the shrinking
In this lesson4
An example test checks one case: "this buy of 8 produces these two executions". An invariant checks a property for every case: "no execution creates or destroys shares". A matching engine is protected above all by its invariants, because nobody can write every possible session by hand.
Invariant
A property that must stay true after every engine operation, whatever the inputs.
Six invariants of an engine
- Conservation of quantities. For each order: quantity executed + quantity resting + quantity cancelled or dropped = quantity received. No share appears or vanishes.
- Uncrossed book. In continuous trading, after each order, the best bid stays strictly below the best ask. Otherwise, two compatible orders are waiting without trading.
- Limits honoured. No execution happens above the buyer's limit or below the seller's.
- Priority honoured. No order is filled while a better-placed, compatible order on the same side is still waiting.
- Monotonic timestamps. The arrival rank strictly increases. It is the basis of time priority; on the BVMAC, each order is timestamped as soon as the brokerage firm receives it (BVMAC General Rules 2025, art. 150).
- Determinism. The same sequence of orders always produces the same sequence of executions. Direct consequence: by keeping the log of inputs, you can replay a session and rebuild the state of the book at any moment.
For one order, writing for the quantity received, for the quantity executed, for the quantity waiting and for the quantity cancelled or dropped, invariant 1 reads:
Invariant 2 is not magic: it follows from the two breaks of the loop read in Continuous trading, line by line. As long as a compatible order rests opposite, the loop goes on; it only stops when nothing matches any more.
From memory, lesson 4: why can the Carnet.passer loop stop at the first incompatible order, and which invariant follows from it?
Determinism
The property of an engine that, given the same sequence of inputs, always produces the same sequence of outputs.
Determinism is easily lost: a call to Date.now() or Math.random() inside the engine, iterating over a structure whose order is not guaranteed, a floating-point calculation. The teaching engine contains none of these: time is a rank supplied from outside, and every tie-break ends on that rank.
We found no high-confidence source describing how real platforms guarantee determinism and replay (total ordering of events, state replication). Invariants 4 to 6 are presented as design principles of the teaching engine. For timestamping, European regulation gives an order of magnitude, without applying in CEMAC: traceability to UTC, and for high-frequency trading a maximum divergence of 100 microseconds (Delegated Regulation (EU) 2017/574).
A property-based test, without a library
A property-based test generates many inputs and checks that an invariant holds for each one. The only requirement: a reproducible generator, driven by a seed, so that a failure can be replayed.
import { Carnet } from '@criee/marche'
import { expect, it } from 'vitest'
it('conserves quantities over 200 random sessions', () => {
for (let graine = 1; graine <= 200; graine++) {
const r = alea(graine) // deterministic generator, for example 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), `seed ${graine}, order ${id}`).toBe(q)
}
}
})
The message seed ${graine} is half the work: when the test fails, it tells you which session to replay.
Determinism is tested by replaying the same log twice:
it('replays a session identically', () => {
const journal = genererSeance(42) // list of orders, without rank
const rejouer = () => {
const c = new Carnet(10000)
return journal.flatMap((o) => c.passer(o))
}
expect(rejouer()).toEqual(rejouer())
})
The same test, in motion: two replays of the same log, event after event, with the fingerprint of executions and book. Then choose "Arrival order not guaranteed": two buys received "at the same time" are processed in the other order in the second replay. The fingerprints diverge from the first event (the ranks change), the executions from the fourth.
Replay 1
- 1. a1 B 30@10,000
- 2. v1 S 20@10,100
- 3. a2 B 25@10,000
- 4. v2 S 40@10,000
- 5. cancel v1
- 6. v3 S 10@9,950
- 7. v4 S 15@10,050
- 8. m1 B 10@mkt
#03e91792
Replay 2
- 1. a1 B 30@10,000
- 2. v1 S 20@10,100
- 3. a2 B 25@10,000
- 4. v2 S 40@10,000
- 5. cancel v1
- 6. v3 S 10@9,950
- 7. v4 S 15@10,050
- 8. m1 B 10@mkt
#03e91792
deterministic
event 1/8
Identical fingerprints
The engine stays deterministic in both cases: it is the order of the log that changed. Determinism therefore assumes a totally ordered log, which is a design choice of the system around the engine. The lesson Logging and replaying a session turns it into a recovery tool.
The bench, live
The bench below runs 200 sessions of 16 operations (limit orders, market orders, cancellations) and checks four invariants after each operation. Change the seed: the sessions change, the invariants hold, and two replays of the same session give the same fingerprint.
- Conservation: executed + resting + cancelled + dropped = quantity received0 checks · 0 violation(s)
- Uncrossed book: best bid < best ask0 checks · 0 violation(s)
- Limits honoured: no price outside either order’s limit0 checks · 0 violation(s)
- Determinism: replaying the session gives the same executions0 checks · 0 violation(s)
From memory: why must a random test generator take a seed?
Going further
Shrinking a counterexample
A random session that breaks an invariant often contains useless orders. Before turning it into an example test, reduce it.
Shrinking
Automatically reducing an input that makes a property-based test fail, down to the smallest counterexample.
Property-based testing libraries do it for you. Without a library, the simplest version fits in a few lines: remove one order, replay, keep the removal if the property still fails, start again until no removal is possible.
import { Carnet, type Ordre, type Sens } from '@criee/marche'
type Entree = Omit<Ordre, 'rang'>
// Property: two resting orders never share an identifier
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
}
// Remove one order as long as the property still fails
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 orders, identifiers drawn from six values: duplicates are likely
function generer(graine: number): Entree[] {
const r = alea(graine) // mulberry32, as above
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 }]
Step by step, on seed 1:
generer(1)produces 12 orders, whose identifiers are drawn from six values.idsUniquesreplays the session and returnsfalse: two resting orders share an identifier.retrecirremoves orders one by one; each removal that leaves the property failing is kept.- Two orders remain:
o2, buy 20 at 10,050, theno2, buy 8 at 10,050. Removing either would make the test pass.
Two orders, one defect: this is known limit no. 3 of the engine contract sheet, identifiers are not checked. The shrunk counterexample becomes an example test; the fix remains a decision to make.
Cost. Each pass tries at most n removals, each attempt replays the whole session, and it may take around n passes: O(n²) replays in the worst case. For 12 orders, it is instant. For a session of 10,000 orders, first remove halves, then quarters, before going down to single orders.
Pitfall. The result is a local minimum, not the smallest possible counterexample: no single-order removal still makes the property fail, but another, shorter combination may exist. Values (quantities, prices) are not reduced either: that is a second pass to write if you need it.
Your turn
Read next: Règlement général de la BVMAC (2025)
A question? Ask your teacher, or an AI assistant, giving it the title of this lesson.