Single-writer sequencing & matching engines

Forty shares, two buyers

A small exchange lists a stock under the ticker ORCA. Its order book holds the orders that have not traded yet: on the sell side, 40 shares offered at 101.00 and 200 more at 101.05; on the buy side, bids up to 100.95. Two traders send the same order, buy 40 at up to 101.00, a few microseconds apart. Only one of them can have those 40 shares.

The exchange's rule is price-time priority: an incoming order trades against the best price on the other side first, and among orders at the same price, the earlier one goes first. The first buy order takes the 40 shares and a trade is printed. The second finds nothing left at 101.00 or below and rests in the book as the new best bid. Two identical orders, two different outcomes: in a matching engine the order of arrival is the result. So the design has to answer which arrived first?, and answer it the same way every time, after a crash included.

A lock decides, but not by arrival

The familiar design is a pool of order services in front of a database, each order a transaction: lock the best opposing order's row, match, write the trade, commit. Nothing is sold twice. Follow the two buyers, A and B:

1. The gateway receives A, then B three microseconds later, and hands them to two different service instances.
2. Instance 1, holding A, pauses for a garbage collection.
3. Instance 2 locks the row of the 40 shares at 101.00 for B, matches and commits.
4. Instance 1 resumes, locks the row and finds it filled; A rests in the book.

No lock was misused, and B traded although A arrived first. A pause picked the winner, and nothing recorded it as an input: send the same day's orders through again and the trades can come out differently. The open makes it worse. Thousands of orders on ORCA reach for the same few rows and queue on their locks; if each transaction holds its lock for about a millisecond of round trips and commit, the best price passes at most about 1,000 orders a second, however many instances run.

One writer per book

Turn it around. Give ORCA's book a single owner: one thread that holds the book in memory and applies orders one at a time, each to completion before the next starts. This is the single-writer principle. Nothing else writes the book, so nothing needs a lock, and a match is a few memory operations instead of a database round trip; engines built this way measure a match in microseconds. Owning state and taking inputs one at a time is the general model of the Actor Model; here it serves one book.

That still leaves two gaps. The order in which the thread takes inputs from its queue is still set by timing upstream, and nothing records it. And the book lives only in memory: when the process dies, the book dies with it.

Number it, write it down, then match

A sequencer closes both. Before the engine sees an order, the order gets a sequence number that places it in one total order for the book, and it is written to a durable log under that number. The engine reads the log strictly in sequence. Arrived first now means a lower number in the log, decided once, before any matching.

The sequencer can be a process of its own, or the log can play the part, as in the drawing below: a log partition appends entries one after another, and an entry's position is its number. What matters is the order of two steps: the log is set to acknowledge an append only once copies are on several machines, and the engine matches only what the log has acknowledged.

1. The gateway appends A to ORCA's log, which stores it as entry 70,412 and copies it to its replicas.
2. The gateway appends B, which becomes entry 70,413.
3. Once 70,412 is acknowledged, A's trader is told the order is accepted.
4. The engine reads 70,412: A takes the 40 shares at 101.00, and the trade goes out.
5. The engine reads 70,413: nothing is left at 101.00, so B rests as the best bid.

How a log survives a crash is the subject of Write-Ahead Log, and how its replicas keep agreeing on one order when the machine at its head fails, of Consensus.

Same log, same book

The engine's state after entry N now depends only on where it started and on the entries up to N. Two copies started from the same snapshot and fed the same entries hold the same book and print the same trades, provided the engine is deterministic: it reads nothing that could differ between runs. These habits break it quietly:

• Reading the clock. Use the timestamp stored in the entry, not the host's.
• Randomness and unordered iteration. A random tie-break, or a hash map whose order can change between runs.
• Calling out mid-match. A risk service or a database read answers with today's data.
• Replaying with different code. New matching rules over an old log build a different book.

Kept deterministic, the log makes recovery a replay. Every 500,000 entries the engine saves a snapshot of the book with the number of the last entry it includes. After a crash, a fresh engine loads the latest complete snapshot and replays from the entry after it: roughly 500,000 entries at worst, about two seconds at 250,000 a second, plus the time to load the snapshot. Choosing that cadence is the question of Snapshot, and rebuilding state from a recorded history is the idea Event Sourcing applies to business entities; here the history is the engine's inputs. Trade ids derived from entry numbers come out the same on replay, so the market-data feed and the trade store can drop trades they already have, as long as the replay reaches back to the last entry whose trades they confirmed.

The same property gives a hot standby: a second engine that reads the same log holds the same book, usually a few entries behind, and takes over when the active one dies, once the old one is fenced off so it can no longer publish, not merely presumed dead (Leader Election covers how).

Many books, no common order

One writer per book scales by symbol: other symbols run on other threads, many books to a machine. A log keeps order only inside a partition, so all of one symbol's orders must land in the same partition, which keying by symbol ensures; Sequential Convoy covers ordering by key.

There is no order across partitions: ORCA's entry 70,412 and entry 9,031 in another partition cannot be compared. Books that share a partition do share its order, but each is still matched on its own. And in this design one thread matches each book, which caps that book's throughput. Not every contended resource needs this: Worked design: a digital wallet keeps a busy account in a relational ledger with a conditional update, because no rule there makes the earlier payment win.

The price of one writer

Every order pays for a replicated, durable write before it can match, usually the largest share of its latency, and the burst at the open queues in the log, already in order. The sharper cost is that one slow input stalls its whole book.

At 20,000 orders a second on ORCA, one every 50 microseconds, a handler that blocks for 5 ms on a synchronous disk write leaves 100 orders waiting behind it; batching many orders into one replicated write raises throughput but does not shorten that wait. So nothing in the engine's loop waits on a disk write or a remote call: it reads entries, changes memory and hands its results to queues that others drain, the market-data feed and the trade store's writer. An occasional stall like that barely moves the average; it shows in the slowest orders, the part of the distribution Latency percentiles & tail latency teaches you to watch.

On the matching-engine Grid

The Stock Exchange Matching Engine Challenge asks for this book: price-time priority, deterministic sequential processing per symbol, no lost orders, fast recovery. Draw the order path as gateway, sequenced log, engine, and write on the log's edge that an order is durable before it matches. Then show recovery: where snapshots live, which entry a replay starts from, and a standby reading the same log. The Challenge sets a latency and availability target; meet it without moving the durable write after the match.