How to build an exchange

What an exchange is

An exchange is one data structure and three messages.

The data structure is the limit order book. It holds a list of everyone who currently wants to buy and a list of everyone who currently wants to sell, each entry carrying a price and a quantity.

Buys are sorted highest price first and sells lowest price first. Both are sorted so the best offer sits on top, but the meaning of best differs by side. If you are selling, the best buyer is the one paying the most. If you are buying, the best seller is the one charging the least.

In a resting book the highest buy is always below the lowest sell. If someone were willing to buy at 33.31 while someone else was willing to sell at 33.31, those two would already have traded.

The three messages

A new order says something like buy 500 at 33.29. It is inserted into the book sorted by price, and among orders at the same price, by arrival time, so it is first come first served at a given price.

A cancel pulls an existing order back out of the book.

An execution happens when an incoming order overlaps the other side. If you sell at 33.29 while someone is bidding 33.29 there is no longer a gap between the two sides, so the exchange matches them and reports the trade to both.

Roughly half of all traffic is new orders, another 30 to 40 percent is cancels, and only one or two percent is executions. Most of the work an exchange does is recording prices that people post and then withdraw.

Who gets the better price

When an incoming order overlaps a resting one, two different prices are involved. The convention is that the resting price wins, so the incoming order receives the improvement. If you are bidding 33.29 and someone arrives willing to sell at 33.25, they are filled at 33.29 rather than their own price.

This exists to make people name their real price. If aggressive orders are rewarded for showing their true limit, they will show it, and the book stays informative.

Nigito describes a venue that did the opposite and gave the improvement to a hidden resting order. Traders responded by no longer naming a real price. Instead they probed one price point at a time, walking down until something filled, which produced far more messages for the same amount of trading.

What the system has to survive

US equities peaks at around three million messages per second, with thousands of connected participants, several million live orders and roughly ten thousand symbols.

Everyone also has to learn what happened at the same instant. Nigito illustrates why with an incident from an earlier exchange. Market data was sent over individual TCP connections, and the code looped over the list of connections one at a time, so whoever was first in the list received everything slightly earlier than whoever was last. Participants worked this out. Between the close and the following open there were thousands of connection attempts per second as firms competed for an early position in that list.

Nobody had designed an advantage. It emerged from the order of a loop. Most of the architecture that follows exists so that information arrives everywhere at once as a property of the system rather than as an intention.

Durability matters for a similar reason. Once you tell two participants they have traded, they commit capital elsewhere on the strength of it, so withdrawing the trade later causes damage well beyond your own system.

Finally, one badly behaved participant must not degrade the experience of anyone else. Often such participants are not malicious. They are responding sensibly to an incentive the exchange created without noticing.

The design

A single application called the matching engine holds the entire order book in memory on one machine. It is not a cluster and it is not sharded by symbol.

Around it sit client ports. Each port is a separate process that holds TCP connections to clients, translates their protocol, and forwards transactions to the engine.

Ports exist so the engine only has to match. They validate input, normalise protocol differences, absorb misbehaving clients and provide flow control. They also hold a useful shortcut. When the engine acknowledges an order it returns a locator, which is essentially an index into its own pre-allocated memory. When the client later cancels, the port sends that locator back and the engine goes directly to the order instead of searching for it. The client never sees the value.

The supporting applications

Drop ports serve the firms that clear and guarantee trades. A single clearer may need activity from many different client ports, in whatever combination matches its relationships.

The trade reporter pushes completed transactions to the regulatory reporting facility.

Market data is the public feed. It is close to the raw transaction log with names removed and hidden activity filtered out, published so that anyone can maintain their own copy of the book.

A service Nigito calls the cancel fairy handles clients who want an order cancelled after some delay. The engine has no business tracking timers, so it simply acknowledges the request. A separate small service watches the transaction stream and issues the cancel when the time arrives. Several copies run at once and race each other, so any one of them crashing is harmless. Auctions are separated out for the same reason, since finding the price that maximises matched volume is an optimisation that should not sit near the matching path.

Multicast

All of those applications need the same information at the same time, and sending each of them a copy in sequence would recreate the problem from the market data incident.

Multicast avoids it. A packet is sent to a special address and the network switch replicates it to every subscriber at effectively the same moment, so the duplication happens in hardware rather than in application code.

Fairness becomes a property of the network rather than a promise. When the engine publishes an execution, both traders, the market data feed, the drop port and the trade reporter all receive it at the same moment, and there is no ordering left to compete over.

Multicast runs over UDP, which provides no sequence numbers, acknowledgements or retries, so packets can be lost. Retransmitters exist to cover this. They are servers whose only job is to record every message that passed by, and an application that notices a gap requests the missing message from them. If none of them have it, the engine keeps its recent output in memory and can resend.

State machine replication

Every application on the bus follows the same discipline. It holds some state, reads the ordered stream of transactions from the engine, and applies them one at a time, deterministically. It never acts on anything else, including timers, random values, or whichever thread happened to finish first.

Because of that, state does not have to be stored. It can be recomputed. Any application can be killed, replaced on another machine, and brought back to exactly the state it had by replaying the day from a retransmitter.

A client port that dies rebuilds every open order and every message it had exchanged with its client. When the client reconnects, the two compare positions, the client reports the last message it saw, and the port sends whatever came after.

Rebuilding takes under a minute, which is fast enough that they never added snapshots or state transfer.

The engine itself

The one application that cannot be recovered this way is the matching engine, since it produces the ordered stream that everything else replays. So a second engine runs alongside it.

The passive engine does not listen to the client ports. UDP packets arrive at different machines in different orders, so an engine reading the raw inputs would build a different book. Instead it listens to the primary engine's output, extracts the client-submitted messages from it, and runs identical code over that already-ordered stream.

If the primary produces the first half of a two-execution trade and then dies, the passive engine has already seen the order that caused it and produces the same two executions on its own.

Someone in the audience raises the obvious objection, which is that identical code will fail identically. Nigito agrees that correlated failure is a real weakness and describes the approach as slightly brittle. The mitigations are keeping the state machine very clean, replaying weeks of real market data through a new engine before release, and fuzz testing with generated messages. He notes that consensus algorithms such as Paxos would handle failover properly but cost an additional round trip and hop, and that he is not aware of exchanges using them.

Topics and sequence numbers

Every message carries a topic, which behaves as an independent lock, and a sequence number scoped to that topic separately from the global ordering. A port proposes the next transaction on a topic along with the sequence number it believes comes next.

The engine checks that number. If it is correct, the transaction is accepted and republished. If it is not, meaning another participant got there first, the engine discards the message without replying at all.

This works because delivery is reliable. The port that lost will shortly see the transaction that beat it, recognise that the publisher is not itself, apply that change to its own state, and then reconsider what it had been trying to do.

In this case the cancel arrives after the order has already traded. The port applies the execution, looks again, finds nothing left to cancel, and issues a cancel-reject at the next sequence number.

The reject is sent through the engine rather than straight to the client because the protocol treats cancel-rejects as sequenced messages. Anything sequenced is something the client will see and the port must remember, and anything the port must remember has to come from the global ordered stream or it cannot be rebuilt after a crash. State that is not in the log does not survive, so nothing important is allowed to exist outside it.

Each port also keeps only one transaction in flight at a time. This limits throughput, but it means a port that has to roll back only ever has one message to reconsider.

Why speed matters

Because each port allows one transaction at a time, a port's throughput is a direct function of round-trip latency. Keeping transactions in the low single-digit microseconds means simple flow control is sufficient, and client backpressure is handled by the normal TCP window.

Speed also keeps the recovery design simple. If any application can replay a full day in under a minute, there is no need for snapshotting, checkpoints or state transfer machinery.

Determinism makes the system auditable. When a regulator asks why a particular transaction happened when it did, the answer does not depend on which thread observed which quote first.

Nigito mentions one profiling result worth remembering. In a fast matching engine, roughly a third of the time is spent on a single line of code, the dereference of that order locator, because it is usually a cache miss. Memory latency ends up being the limiting factor.

Summary

• Most exchange traffic is orders and cancels rather than trades.
• Fairness has to come from the architecture. A loop over a list of connections was enough to break it.
• A single deterministic writer with everything else listening is simpler and easier to recover than a distributed system trying to agree.
• Multicast makes simultaneous delivery a property of the network.
• If state can be rebuilt from a log, most failures become uninteresting.
• Keeping the core small means timers, auctions and similar work can live in services that are allowed to crash.
• Performance is not the objective. It is what allows the rest of the design to stay simple.