On this path · Financial Systems 2. Order Matching Engine Internals
Order Matching Engine Internals
Limit-order book structure, price-time matching, and the correctness guarantees a high-frequency engine must defend.
Learning outcomes
The documented Trade Republic system-design prompt is to design an order matching engine with price-time priority that updates accounts and holdings. Most candidates can describe matching in the abstract. Fewer can defend the data structure, the determinism guarantee, and the consistency model when the trade must also move money and positions. This page teaches the engine as a correctness problem first and a performance problem second, because that is the order in which a real brokerage cares about it.
After studying this page, you can:
- Explain why the limit-order book has the shape it has, and justify the choice of structure against alternatives.
- Match an incoming order by hand through price-time priority and account for every share and every cent.
- Decide when a brokerage routes to an external venue versus internalizes, and name the regulatory and risk tradeoffs of each.
- Defend the determinism guarantee the engine must provide, and explain why sequence numbers, not timestamps, define order.
- Describe how a match must atomically update the book, the accounts, and the holdings, and where the dual-write hazard lives.
- Avoid the documented mistakes, including missing transaction rollbacks, that sink the matching-engine design round.
Before we dive in
Two people want to trade the same security at the same time. If they are in the same room, they find each other and agree on a price. At the scale of a modern market, with millions of participants who never meet, they need a trusted intermediary that accepts intents, ranks them, and decides who trades with whom on terms no one can later dispute. That intermediary is the matching engine, and the difficulty of building one is not speed. The difficulty is producing an outcome that every participant agrees was correct, even when the inputs arrived in a burst and the system crashed halfway through.
The matching engine exists because markets demand a single, deterministic rule for who trades and at what price. Without such a rule, disputes are inevitable: two sellers at the same price would each claim to be first, and the broker would have no defensible answer. Price-time priority is the rule the industry settled on because it is simple, fair, and auditable. The engine’s job is to apply that rule exactly, every time, under load, and to never let a half-finished match leave the book and the accounts out of sync.
The reason this is a hard interview prompt, and a hard engineering problem, is that the engine has two obligations that pull against each other. It must be deterministic, meaning identical inputs always produce identical orderings, which argues for a single thread and a strict sequence. It must also move money and positions as it matches, which argues for transactional safety across multiple data stores. A senior candidate is expected to hold both obligations at once and explain the design that reconciles them, rather than optimizing one and pretending the other does not exist.
Breaking it down
1. The problem the matching engine solves
Strip the engine to its essence. Orders arrive. Each order is an intent to buy or sell a quantity at a limit price, or at the market. The engine must decide, for each incoming order, whether it crosses an existing order on the opposite side, and if so, execute a trade at the best available price until the incoming order is filled or no more crossing orders remain. Any unfilled remainder sits on the book, waiting for a future counterparty.
The engine solves three sub-problems at once. It ranks resting orders so the best counterparty is always found first. It executes trades that are mathematically correct in quantity and price. And it records those trades so that the accounts and holdings of both parties change exactly as the trade dictates. The first two are a data-structure and algorithm problem. The third is a distributed-systems problem, because the accounts and holdings live in a database that is not the matching thread. The prompt that asks you to update accounts and holdings is testing whether you notice the third problem, not just the first two.
2. The limit-order book as a data structure
The limit-order book is the structure that holds resting orders and lets the engine find the best counterparty quickly. The natural shape is two sorted collections, one for bids and one for asks, each ordered by price with the best price at the front. Within a single price level, orders are ordered by arrival sequence, so the earliest order is served first. This two-sided, price-then-time structure is the book.
The implementation choice matters because the engine performs two hot operations continually: find the best price, and insert or remove an order at a known price. A sorted map keyed by price, with each price level holding a queue of orders in arrival order, gives logarithmic lookup of the best price and constant-time insert and remove at a level. For a single-symbol, single-threaded engine, this is the standard shape. Some exchanges use a more elaborate structure, an array of price levels for a fixed tick range, to push the best-price lookup to constant time, because at exchange latency every logarithm matters.
The decision a candidate is often pushed on is whether to share one book across all symbols or to shard by symbol. The answer is to shard by symbol, because orders in different symbols never match each other, so there is no reason to serialize them through one structure. Sharding by symbol lets each symbol run on its own thread or its own instance, which is how an exchange scales horizontally without giving up the single-threaded determinism that each symbol’s matching requires.
3. Price-time matching, a worked example
Walk a concrete match through the engine so the rule becomes mechanical. The book for some symbol has these resting asks: two hundred shares at one hundred and two euros, then three hundred shares at one hundred and three euros. A buy order arrives for two hundred and fifty shares at a limit of one hundred and three euros. The buy crosses the best ask, because the buyer is willing to pay up to one hundred and three and the cheapest seller wants one hundred and two.
Price priority sends the buy to the one hundred and two euro ask first. The buyer takes all two hundred shares at one hundred and two euros. Fifty shares remain on the buy. The next best ask is three hundred shares at one hundred and three euros, still within the buyer’s limit, so fifty shares fill there at one hundred and three euros. The buyer is filled completely. The ask side now has two hundred and fifty shares left at one hundred and three euros, and the bid side is empty.
Two subtleties surface in this example and an interviewer will probe both. The first is the trade price. The buyer filled at the resting ask prices, one hundred and two and one hundred and three, not at the buyer’s limit. The trade happens at the resting order’s price, which is the standard continuous-matching convention. The second is partial fills on the resting side. The three-hundred-share ask was reduced to two hundred and fifty, not removed, because it was only partially consumed. The engine must update the resting order’s remaining quantity atomically with recording the trade, or a concurrent lookup could see a stale quantity.
4. Route to venues or internalize
A brokerage has a choice when it receives a customer order. It can route the order to an external exchange or dark pool and let that venue match it, or it can internalize, meaning the broker itself takes the other side of the trade, often by matching the customer order against the broker’s own inventory or against an offsetting hedge. The choice is not purely technical; it has regulatory and risk dimensions that a senior engineer must understand.
Routing to a venue gives the customer the exchange’s published price and subjects the trade to exchange and clearing rules. It is the clean choice for transparency and for best-execution obligations, because the price is independently observable. Its cost is the exchange fee, the network latency to the venue, and dependence on the venue’s availability.
Internalization gives the broker control of timing and price and can reduce fees, but it creates conflicts of interest. The broker is now the customer’s counterparty, so the broker must demonstrate it gave the customer a price at least as good as the best available on exchanges, the best-execution duty under MiFID II. Internalization also puts market risk on the broker’s balance sheet until the position is hedged, which is a risk-management concern that touches the engine’s design: an internalizing engine must update the broker’s own position and risk limits in the same atomic step as the customer trade, or the broker’s risk view goes stale.
The pragmatic pattern at scale is smart order routing, where the router evaluates multiple venues and internalization in real time and sends the order wherever the net price is best after fees. The matching-engine design round does not require you to build a full smart router, but it does expect you to know that routing is a separate stage from matching, and that the choice of venue changes whose books the trade updates.
5. Determinism and the ordering correctness guarantee
The engine’s hardest requirement is not throughput, it is determinism. Given the same sequence of orders, the engine must always produce the same sequence of trades. Any non-determinism is a correctness bug, because it means two runs disagreed about who traded, and one of them was wrong.
Determinism is threatened by three things in practice. The first is concurrent input. If two orders can be processed in parallel, their relative order is non-deterministic, which breaks time priority. The fix is a single matching thread per symbol, so orders are serialized. The second is timestamp-based ordering. As the order-lifecycle concept established, wall clocks across pods are skewed, so using an arrival timestamp to break ties produces non-deterministic order. The fix is a monotonic sequence number assigned by the single matching thread. The third is non-deterministic data structure iteration, such as iterating a hash map whose order varies by run. The fix is to use ordered structures whose iteration order is defined by the priority rule itself.
The deep lesson is that order in a matching engine is a logical property, not a physical one. The sequence number is the logical clock of the engine. Two orders are ordered by their sequence numbers, full stop, and the wall-clock time is a metadata field that must never drive a decision. This is identical to the outbox-lesson that a database sequence id, not a created_at timestamp, is the correct ordering key across pods with skewed clocks.
The interviewer will test this by asking what happens if the engine crashes and restarts. The answer is that the engine replays orders from a durable input log in sequence-number order and produces exactly the trades it produced before, because determinism is preserved by replaying the same sequence. This is why the input log, often an append-only journal of orders with their assigned sequence numbers, is a first-class component of the engine design, not an afterthought.
6. Accounts and holdings, the consistency problem
The prompt says the engine must update accounts and holdings, and this is where most designs break. Matching the book is an in-memory operation on the matching thread. Updating the buyer’s cash balance, the seller’s position, the trade history, and any internalization position happens in a database that is a different process. The hazard is the dual-write: if the match is recorded in memory and the database update is sent separately, a crash between the two leaves the book updated and the accounts stale, or vice versa.
This is precisely the dual-write problem documented in Trade Republic’s outbox work, where a service updates a balance and publishes a Kafka event in two separate steps, and a crash between them leaves the database up to date but downstream unaware. In the matching engine the same hazard appears as the book and the accounts diverging after a crash. The correct fix is the same: make the trade record and the account updates a single transactional unit. In practice, the matching thread writes a trade record and the resulting account and holding deltas to the database in one transaction, so either all of it commits or none of it does, and the in-memory book is updated only after the commit succeeds, with the trade’s sequence number guarding against duplicate application on retry.
The structure above is the defensible answer to the consistency follow-up. The trade, the account deltas, and the outbox event for downstream notification are one transaction. The in-memory book commits only after the database transaction succeeds, so a crash leaves either a fully committed trade or no trace of one, never a half-applied match. The sequence number on the trade makes the append idempotent, so retrying after a transient failure cannot double-apply a trade.
Common mistakes candidates make
- Designing only the in-memory book and ignoring the database. The prompt explicitly says update accounts and holdings. A design that matches in memory but treats persistence as a footnote fails the round, because the consistency problem is the point.
- Missing the transaction rollback on failure. If the account update fails after the match, the book must roll back. Candidates who skip the rollback leave the book and the accounts permanently diverged. This is a documented failure mode in the Trade Republic feedback.
- Ordering by wall-clock timestamp. Timestamps across pods are skewed and break time priority. Use a monotonic sequence from the single matching thread.
- Sharing one book across all symbols. Orders in different symbols never match, so serializing them through one structure sacrifices parallelism for no correctness gain. Shard by symbol.
- Assuming the trade happens at the incoming order’s limit price. The trade happens at the resting order’s price. Getting this wrong in an example signals the candidate has not worked a match by hand.
- Treating internalization as free money. Internalization puts market risk and best-execution obligations on the broker. A design that internalizes without updating the broker’s own position and risk ignores the hazard.
Expect to be pushed on crash recovery. The question: the engine crashes after matching but before the account transaction commits. What happens on restart? The strong answer is that the durable input log and the sequence number let the engine replay from the last committed sequence, re-matching deterministically and re-applying idempotently, so no trade is lost and none is doubled. A second follow-up: how do you scale beyond one thread? The answer is symbol sharding, each shard a single-threaded engine with its own sequencer and input log, preserving per-symbol determinism while scaling total throughput.
Mastery Questions
Question
Why is the limit-order book sharded by symbol rather than held as one shared structure?
Answer
Orders in different symbols never match each other, so serializing them through one structure gains no correctness and sacrifices parallelism. Sharding by symbol lets each symbol run on its own thread or instance, scaling total throughput while preserving the single-threaded determinism that each symbol's price-time matching requires.
Sources & evidence5 claims · 3 cited
Limit-order book structure, price-time matching worked example, route-vs-internalize, determinism via sequence numbers, accounts-and-holdings consistency with outbox fix. Grounded in src_tr_interview (matching prompt, rollback failure), src_tr_outbox1 (sequence ordering), src_tr_debezium (dual-write outbox fix). Internalization tradeoffs marked internal-reasoning.
- The documented system-design prompt is to design an order matching engine with price-time priority that updates accounts and holdings.verified
- Wall clocks across pods are skewed by jitter and drift, so a production matching engine assigns a monotonic sequence number rather than ordering equal-priced orders by arrival timestamp; this mirrors the outbox lesson that a database sequence id is the correct ordering key.verified
- The dual-write hazard, a match recorded in memory while the database account update is sent separately so a crash between leaves book and accounts diverged, is the same balance-update plus Kafka-publish problem the outbox pattern solves by writing the event row in the same transaction as the business change.verified
- A documented candidate failure mode is missing transaction rollbacks when the account update fails after the match, leaving the book and the accounts permanently diverged.verified
- A brokerage may route customer orders to external venues for transparent best-execution or internalize by taking the other side itself, the latter creating best-execution duties and market risk that require updating the broker position and risk limits in the same atomic step.internal reasoning
Cited sources
- How to Pass the Trade Republic Software Engineer Interview (JobMentis) · JobMentis (interview outcome database)
- PostgreSQL + Outbox Pattern Revamped Part 1: Incidents and a new design pattern · Trade Republic Engineering (Sadeq Dousti)
- Streaming Outbox Events from Postgres to Kafka with Debezium · Trade Republic Engineering (Andrei Sukharev)