Design a stock exchange matching engine

Prices and quantities are whole numbers, in ticks and shares, never floating-point, so there is no rounding and results are identical on every machine.

Each price level holds a first-in, first-out queue of resting orders. That is the time priority. The book keeps the levels in a sorted structure, or in an array indexed by tick when the price band is bounded. A hash map from order ID to the order's place in its queue makes a cancel a single step, with no search.

Matching a limit order. An incoming buy at price P looks at the best ask. While it has quantity left and the best ask is at or below P, it trades with the oldest order at that level. The trade happens at the resting order's price. Whatever is left rests at the back of its own level.

A worked example. The asks are 100 shares (A) at 10.02, 50 (B) at 10.02, and 200 (C) at 10.03. A buy of 220 at 10.03 arrives. It trades 100 with A and 50 with B, both at 10.02. It then trades 70 with C at 10.03, leaving C with 130. The buyer asked to pay up to 10.03 but got 150 shares at the better price of 10.02.

A market order has no price. It takes whatever the book offers until it is filled or the book is empty, and any rest is cancelled; it never rests. A cancel finds the order by ID and unlinks it. If the order was already filled, the cancel is rejected as too late. Whichever of the two was sequenced first wins, which is what makes the answer fair.

Cutting the quantity of a resting order keeps its place in the queue. Raising it, or changing the price, sends it to the back. Matching costs time in proportion to the number of trades it makes. Cancels, which are most of the traffic, are constant time.

If the order of events is fixed, the result is fixed. So one component, the sequencer, decides the order. It stamps every message with the next sequence number. That is the answer to 'who was first', and it removes ties.

One thread per symbol. With a single writer there are no locks and no races. The book fits in the core's cache, about 256 KB, and the loop avoids memory allocation and system calls. At about 5 microseconds a message, one thread handles 200,000 a second, against 25,000 needed for the busiest symbol. To scale, spread symbols over many engine threads or machines. Never share one symbol between threads.

The replicated log. The sequencer appends each event to a log that is copied to three nodes, and it counts as written when two have it. The engine does not release a result until its input is safe. The engine's state is just a cache of the log. A snapshot of the book plus its sequence number is saved every few minutes, so recovery replays only the tail.

The hot standby reads the same log and applies every event in the same order, so its book is identical. It discards its outputs while it is not in charge. If the primary stops answering for, say, 200 ms, the standby takes over. First fence off the old primary: every output carries an epoch number, and a lower epoch is ignored downstream, so a primary that is only slow cannot emit stale results. Then replay any events past what it applied. Because the engine is deterministic, the results it regenerates are byte for byte what the old primary produced, and anything already published is dropped by its sequence number.

Do not read the wall clock in the matching code. Timestamps are assigned by the sequencer and carried in the event, so a replay is exact. The sequencer is a single point too, so run it as a primary and a backup with the same epoch rule, continuing from the last sequence number in the log.

They are in-memory counters per participant, so each check takes microseconds.

• Fat-finger limits. Reject a price far from a reference, say outside 10% of the last trade, or a quantity above a cap, say 1 million shares.
• Exposure. Keep a worst-case figure per participant. For buys, it is the open buy quantity times each order's limit price, plus the value of the current position at the last trade price. Add the new order's quantity times its price, and reject it if the total passes the participant's limit. Sells are checked the same way against short exposure. A fill turns open quantity into position at the fill price, and a cancel or a sell lowers the figure.
• Rate caps. Limit messages a second per connection, so one runaway program cannot flood the engine.
• Self-trade prevention. Do not match a participant against itself. Cancel the older or newer order by a stated rule.
• A kill switch. One command cancels all of a participant's orders and blocks new ones.

Market data. The publisher turns the sequenced events into two streams. The incremental stream carries every change to the book and every trade, each with a sequence number. A snapshot stream repeats the top levels of each book every second or so, so a late joiner can catch up.

Sending 25 MB a second to each of 1,000 subscribers one by one is 200 Gbit/s, which no single publisher can do. Instead send each update once to a network that copies it, such as multicast inside the data centre, with a distribution tier beyond it. Subscribers watch the sequence numbers. On a gap, they ask a resend server for the missing range or wait for the next snapshot.

Fairness. Everyone should see events in the same order and at about the same time. Because outbound events also pass through the sequencer, there is one global order for reports and public data alike. Give co-located participants cables of equal length, so geography does not decide who is first. The event log doubles as the audit trail, kept for as long as regulators require.