Stock exchange (matching engine)

01 · CONTEXT

The heart of an exchange

An electronic stock exchange revolves around the order matching system, the matching engine: the component that crosses buy and sell orders and produces trades. The classic exercise asks for the design of this core, with participants sending orders, the order book being updated, and trades being published. The source describes it as the core of every electronic exchange, usually part of a larger system that includes settlement and a central depository.

The market works in two states. In continuous trading, orders are matched as soon as they arrive; in an auction, matching happens at fixed intervals, such as at the market open, when orders have accumulated. This case covers the continuous state, which takes up most of the day.

The dominant requirement is latency. A trading platform needs to process orders very quickly because the market moves fast, and each processed order changes the conditions for the next ones. Being fast is not enough: orders must be processed in a well-defined order.

02 · ORDER BOOK

Who gets served first

The order book holds the limit orders not yet executed, split into buys and sells and organized by price. An incoming order either crosses with the other side of the book and generates a trade, or waits in the book. When several orders have the same price, a priority rule decides which is served first.

The most common matching algorithms are Pro-Rata and Price/Time, the latter also called FIFO. Each creates different incentives for those who trade.

Whatever the rule, it must be deterministic: the same sequence of orders must always produce the same trades. This property will be the basis of failure recovery later on.

03 · ONE THREAD

Why not parallelize matching

The instinct is to parallelize: several threads processing orders at the same time. The LMAX team, a retail financial trading platform, tried that path first, with an actor-based exchange prototype, and measured. The processors spent more time managing queues than executing application logic.

They ended up with the business logic for all clients and all markets in a single thread, which processes millions of orders per second on commodity hardware. The source itself cautions that the number comes from a two-socket server of the time, and that each order requires checks and a choice of matching policy, that is, it is not a trivial operation.

1. The participant's order arrives over the network at the gateway, which receives it and converts it to the system's internal format.

2. The sequencer gives each order a unique place in the global queue. This total order is what makes the result reproducible.

3. Before the order is processed, the event is written to a durable log, so the state can be rebuilt later.

4. The matching engine reads the events in sequence, on a single thread and in memory only, applies the priority rule, and updates the order book.

5. The trades generated and the changes to the book go out as output events, published asynchronously to market participants.

Running only in memory and sequentially gives speed: there is no slow database access and no transactional behavior to execute. That leaves the question of how to survive a crash, addressed later.

04 · INPUT

Sequence, record, and replicate

Before an order reaches the business logic, it has to be taken off the gateway and deserialized, replicated, and recorded in a journal. The replicator and the journaler do I/O and are relatively slow, but they are independent of each other and can therefore run in parallel, as long as they all finish before the business logic processes the message.

LMAX's journal is not a database, just the file system. Replication, on the other hand, is needed even with multicast, because messages may arrive in a different order at different nodes; that is why the leader node provides the deterministic sequence that everything else follows.

05 · FAILURES

Rebuilding state and switching replicas

Keeping everything in memory has an obvious consequence: what happens if everything goes down? The answer is event sourcing: the processor's state is entirely derivable from the input events. As long as the event stream is in durable storage, reprocessing it is enough to recreate the state.

Reprocessing all the events would take too long to bring up a new processor, so LMAX also takes snapshots of the state, every night, during a low-activity period. And since even that is not enough for a mid-day crash, it keeps several processors running at all times: all of them process every input event, but the output of all but one is ignored. If the active processor fails, the system switches to another.

1. The leader sequencer writes every input event to the journal, which is the source of truth for everything the system has ever accepted.

2. The same input sequence is replicated to all the processors, which apply it in the same order and reach the same state.

3. Only the active processor's output goes to the output channel; the others' is discarded.

4. Periodically the state is saved in a snapshot, so a new processor does not need to reprocess the entire journal.

5. When the active one goes down, an already up-to-date replica takes over publishing the output, without needing to rebuild the state from scratch.

When the leader goes down, another node takes over leadership, starts processing input events, and starts its replicator. The election and the agreement on who the leader is are the domain of consensus algorithms, and keeping replicas ready is a matter of disponibilidade.

06 · MODEL

Constraints and when to use it

The model imposes rules on the business logic. You cannot call external services from inside it, because a slow call would stop all processing; the interaction ends with an output event and only resumes when another input event arrives. And there is no automatic rollback, so the team validates events in full before changing the in-memory state.

In exchange, determinism brings operational gains. To diagnose a problem, the team copies the event sequence to the development environment and replays it. Heavy computations that are not part of order processing run in a replicated model, without interfering with the core.

The source sees this processor as a natural choice for the command side of a system using CQRS. It also points out the condition that favors the design: a connected domain, in which processing one transaction can change the outcome of the following ones. When transactions are more independent, parallel processors become more attractive.