On this path · System Design 2. Design an Order Matching Engine
Design an Order Matching Engine
Full architecture, accounts and holdings consistency, high-frequency correctness, and the defense a Staff engineer expects.
Learning outcomes
The real Trade Republic prompt is to design the backend for an order matching engine: high-frequency, match buy and sell by price-time priority, update user accounts and holdings accurately, and discuss the trade-offs. The prompt is deliberate in pairing the two halves. Matching is an in-memory data-structure problem; updating accounts and holdings is a distributed-transaction problem; and the documented candidate failure is to solve the first and pretend the second does not exist. This page teaches you to hold both halves at once and defend the seam between them.
After studying this page, you can:
- Justify the in-memory limit-order book, its data-structure shape, and why the engine is sharded by symbol and single-threaded per shard.
- Walk a match by hand through price-time priority and account for every share and cent.
- Defend the determinism guarantee and explain why sequence numbers, not timestamps, define order.
- Design the atomic trade that writes the book, the ledger, the holdings, and the outbox event in one transaction, and roll back on failure.
- Choose between single-engine and distributed-engine designs and name what each costs.
- Recover from a crash with no double-matching and no lost trade, using event sourcing and snapshots.
- Anticipate the Staff-engineer probes on failover, exactly-once, and scaling beyond one thread.
Before we dive in
A market is a meeting place for people who never meet. Millions of participants submit intents to buy and sell, and they need a neutral party that ranks those intents by a rule everyone agrees is fair, decides who trades with whom, and records the outcome so no one can later dispute it. That neutral party is the matching engine, and its difficulty is not speed. Its difficulty is producing an outcome that every participant, every regulator, and every internal ledger agrees was correct, even when inputs arrived in a burst and the process crashed halfway through.
The rule the industry settled on is price-time priority. Among orders on the same side, the best price ranks first; among orders at the same price, the earliest arrival ranks first. The rule is simple, fair, and auditable, which is why it is universal. The engine’s job is to apply that rule exactly, every time, under load, and to never let a half-finished match leave the order book and the customer accounts out of sync.
What makes this a hard interview prompt, and a hard engineering problem, is that the engine carries two obligations that pull against each other. It must be deterministic, because identical inputs must always produce identical orderings, and that argues for a single thread and a strict sequence. It must also move money and positions as it matches, and that argues for transactional safety across multiple stores. A senior candidate is expected to hold both obligations at once, design the seam that reconciles them, and name the documented failure mode where a non-atomic update leaves accounts and holdings diverged. The deeper internals of the book itself are taught in Order Matching Engine Internals; this page owns the architecture and the consistency seam.
Order types the engine must support
The engine handles at minimum three order types, each with different matching semantics. A limit order specifies a maximum buy price or minimum sell price and either crosses immediately against the opposite book or rests until crossed. A market order has no price limit and crosses immediately against the best available opposite orders until filled, consuming liquidity at multiple price levels if necessary. An iceberg order is a limit order that shows only a portion of its total quantity publicly, refreshing the visible quantity when consumed, which hides the trader’s full intent from the market.
Each type has an edge case that the data structure must handle. A market order that arrives when the book is thin may consume all available liquidity and leave a partial fill, which is acceptable for a market order. An iceberg order that refreshes its visible quantity at the same price level must not change its position in the time priority queue: the refreshed portion inherits the original order’s arrival time, not the refresh time. The book data structure must track the total quantity hidden behind the visible portion and decrement it atomically with each fill, without moving the order’s position in the queue.
The engine also handles cancellations and modifications. A cancellation removes the order from the book if it has not been filled, and the next match for that symbol skips the cancelled order. A modification, such as changing the limit price or the quantity, is implemented as a cancellation of the old order and submission of a new one with a new sequence number, so it loses its original time priority. This is a deliberate design choice: allowing a modification to preserve time priority would be unfair to other traders, because a trader could observe the market and adjust their price without losing queue position. The sequence-number-based ordering makes this rule automatic: a modified order gets a new sequence number and starts at the back of its price level.
Clarify requirements and the numbers behind them
Functional requirements first. The engine accepts orders, each an intent to buy or sell a quantity at a limit price or at the market. It matches incoming orders against resting orders on the opposite side by price-time priority. It executes trades at the resting order’s price. It updates each trader’s cash balance and security position. It publishes a durable record of every trade to downstream systems, the user notification path, the ledger, and risk.
Non-functional requirements. Throughput must be high enough to absorb a volatile-session burst, and latency per match must be low, single-digit milliseconds end to end. Correctness is non-negotiable: a trade must never be lost, never be doubled, and never leave the book and the accounts in disagreement. Availability matters but is secondary to correctness, because a broker that matches wrongly is worse than a broker that matches slowly. Auditability is a regulatory requirement: every order and every trade must be reconstructable from durable logs.
A round number for sizing: a large European neobroker processes a few thousand customer trades per second at peak. That is the customer-facing trade volume. The internal matching rate is higher, because each customer order may generate several fills against multiple resting orders, and the engine also handles cancellations and modifications. Size the engine to a few tens of thousands of matches per second per symbol shard, with headroom for bursts.
High-level architecture
The engine has four subsystems, each with a single responsibility, and the boundaries are where the correctness arguments live.
The intake receives orders from the trading API, assigns each a monotonically increasing sequence number per symbol, and appends it to the durable input journal. The sequence number is the logical clock of the engine; it is what makes the engine deterministic and replay-safe. The intake is the only place a sequence is assigned, which is why it must be single-threaded per symbol.
The matcher holds the in-memory limit-order book for the symbol and applies price-time matching. It is pure with respect to the book: given a sequence of input orders and an initial book state, it always produces the same sequence of trades. Purity is the property that makes event-sourced recovery possible.
The settler takes the trades the matcher produced and applies them atomically to the ledger: it debits and credits cash, moves security positions, records the trade rows, and writes an outbox event for downstream. This is the transactional seam, and it is where the documented rollback hazard lives.
The publisher streams committed trades out of the system: to the notification service for the customer, to the market-data feed for the tape, and to risk and compliance. It reads from the outbox through Debezium, so publication is decoupled from settlement and cannot break the trade’s atomicity.
The sharding rule is by symbol, because orders in different symbols never match each other, so serializing them through one structure sacrifices parallelism for no correctness gain. Each symbol shard is a single-threaded engine with its own sequencer, its own journal, and its own book, and the whole system scales by adding shards as symbol count grows. This is the standard exchange scaling model, and it preserves per-symbol determinism while scaling total throughput.
Shard assignment and rebalancing
Each symbol is assigned to a shard by a deterministic mapping from the symbol identifier to a shard id. The mapping is a configuration that the intake reads to route incoming orders. When symbols are added, the mapping is updated and the new symbol’s orders route to its assigned shard from the first order onward. When a shard instance fails, its symbols are reassigned to surviving shards by an orchestration layer that updates the mapping and drains the journal from the failed shard before replaying on the new owner.
The deterministic mapping avoids double-matching during reassignment. Because the mapping is recorded in a durable configuration store, and the journal for each shard is an append-only log keyed by sequence number, the new owner of a symbol can replay only the journal entries after the last committed sequence for that symbol. The old owner is fenced by the orchestration layer before the new owner starts: the intake stops routing to the old owner, waits for in-flight orders to settle, and only then updates the mapping. The window of ambiguity, when two shards believe they own the same symbol, is closed by the fencing step and the sequence-number-based idempotency of the settler.
The intake protocol and order validation
The intake is the gateway through which every order enters the engine. It exposes a gRPC endpoint that accepts an order intent and returns an order id and the assigned sequence number. The intake validates the order before journaling: it checks that the symbol is known, the quantity is within bounds, the price is not negative for a limit order, and the client-generated idempotency key is present. An order that fails validation is rejected before journaling, and the client receives a deterministic error.
The idempotency key is critical for the intake because the client may retry the submission if the response is lost. The intake deduplicates by the client-supplied key: if the key has been seen before, the intake returns the existing order id and sequence number without creating a duplicate order. The dedup table is a small, fast table in the journal database, partitioned by a hash of the idempotency key to avoid contention. The dedup entry is retained for a configurable window, typically a few minutes, which covers the network retry window. After the window expires, the dedup entry is purged, and the client must not retry with a key older than the retention window.
The intake also applies rate limiting per client or per symbol. A client that submits orders faster than a configured rate is throttled: the intake returns a 429 status, and the client must back off. The rate limit is in the intake because it is the first line of defense against a runaway client, and it is per-symbol to prevent a client from flooding a specific symbol’s shard. The rate limit is a local token bucket per client, not a global counter, because global rate limiting requires a coordination service and the intake is stateless and horizontally scalable. The token bucket is sized per intake instance and the per-client limit is divided by the instance count, so the aggregate rate across all instances respects the limit.
The input journal as the source of truth
The input journal serves two purposes: it is the durable record of every order the engine has seen, and it is the source from which the engine recovers after a crash. The journal is an append-only table in Postgres, keyed by (symbol, sequence), with each row carrying the full order payload. The sequence is assigned by the sequencer, which is a single-threaded component per shard that reads from a sequence id generator, either a database sequence or an atomic counter on a coordinator. The sequence is the logical clock of the shard, and all downstream ordering depends on it.
The journal must be written before the order is processed by the matcher. The intake persists the order to the journal and reads back the assigned sequence, then passes the sequenced order to the matcher. This write-first, process-next ordering guarantees that any order the matcher acted on is durably recorded and can be reconstructed on recovery. The cost is one database write per order before matching begins, which adds latency. The alternative, journal after matching, risks losing an order that was matched but whose journal write failed before commit. For a broker where every matched trade must be auditable, the write-first design is the correct one, and the latency cost is accepted as the price of auditability.
Scaling beyond a single shard per symbol
A symbol that saturates its single-threaded shard requires breaking the single-threaded model within the symbol. The approach is to partition the symbol’s order book by price range: the book is split into multiple sub-books, each owned by a separate matcher instance, and a coordinator routes orders to the appropriate sub-book based on the limit price. An order at a price that spans two sub-books, because the sub-books overlap, must be handled by a cross-sub-book matching protocol that involves two sub-books and a coordinator.
This approach is complex and error-prone. It breaks the property that the matcher is deterministic within a single sub-book, because the sub-books can interact through the coordinator. The price-range partitioning is rarely implemented in practice for retail brokers, because a single symbol saturating a modern core is extraordinary. The standard answer is to accept the single-threaded bottleneck and design the system to degrade gracefully by queuing at the intake. Naming this option shows the senior has thought about the limit and knows when complexity ceases to be worth its cost.
Deep dive: the in-memory book and its durability
The book is two sorted collections, one for bids and one for asks, each ordered by price with the best price at the front, and within a price level ordered by arrival sequence so the earliest order is served first. The hot operations are finding the best price and inserting or removing an order at a known price, and a sorted map keyed by price, each level holding a queue of orders in sequence order, gives logarithmic best-price lookup and constant-time work at a level. This shape is taught in detail in the internals concept; here the point is that the book lives in memory and is rebuilt on restart.
Work a concrete match. The book has asks of two hundred shares at one hundred and two euros and three hundred shares at one hundred and three euros. A buy arrives for two hundred and fifty shares at a limit of one hundred and three euros. The buy crosses the best ask, so it takes two hundred shares at one hundred and two euros, leaving fifty. The next ask is at one hundred and three, still within the limit, so fifty fill there at one hundred and three. The buyer is complete. The ask side now has two hundred and fifty shares left at one hundred and three. Two facts an interviewer probes: the trade happens at the resting order’s price, not the buyer’s limit, and a partially consumed resting order is reduced, not removed.
The in-memory book is fast but volatile, so the engine must reconstruct it on restart. Two mechanisms combine. The input journal is an append-only log of every sequenced order, so replaying it rebuilds the exact sequence of inputs the matcher saw. A snapshot is a periodic checkpoint of the book state at a known sequence number, so recovery replays only the journal entries after the snapshot rather than from the beginning. This is event sourcing applied to the order book, and it is what makes the engine recoverable in seconds rather than minutes.
Determinism is what makes replay correct. Given the same input sequence, the pure matcher always produces the same trades, so replaying the journal from the last snapshot reconstructs the book and the trade history exactly as they were before the crash. The guarantee depends on three things: a single sequencer per symbol, sequence-number ordering rather than timestamp ordering, and ordered data structures whose iteration follows the priority rule. Break any of the three and replay diverges, which is a correctness bug.
Snapshot mechanism and cadence
The snapshot is a serialization of the in-memory book at a known sequence number. It is stored in a database table or object storage, keyed by (symbol, sequence). On recovery, the engine loads the latest snapshot and replays the journal from the snapshot’s sequence number forward. The recovery time is proportional to the journal tail length, so the snapshot cadence decides the recovery time budget.
Choosing the cadence is a tradeoff. A snapshot every few minutes keeps the journal tail short and recovery fast, but each snapshot is a write of the full book state, which briefly pauses the matching to capture a consistent view. A snapshot every hour keeps the write overhead low but risks a long recovery if the engine crashes near the end of the hour. The production choice is a snapshot every few hundred thousand orders or every few minutes, whichever comes first. The snapshot cost is the consistent-read pause, which is sub-millisecond for an in-memory structure, and the serialization write, which is a few kilobytes per active price level.
The snapshot itself must be consistent with the sequence number it claims. If the snapshot is taken at sequence 1000 but includes trades that happened at sequence 1001, the replay from snapshot+1 will apply trade 1001 twice. The snapshot is captured at a quiescent point: the matcher finishes processing the current order, records the sequence, serializes the book, and then resumes. This quiescent capture is the standard approach for event-sourced systems and is verified by a consistency check on recovery: the engine validates that the snapshot’s sequence matches the highest committed sequence in the journal up to that point, and if they disagree, it discards the snapshot and replays from the previous one.
Recovery time objective and cold start latency
The time from shard crash to resumption of matching is the recovery time objective. Each component contributes its own latency. The orchestrator detects the failure and initiates failover, typically within a few seconds given a health-check interval of one second with three missed checks. The new instance starts, which may be a cold JVM start or a warm pool instance; a warm pool cuts the startup time from seconds to sub-second. The instance loads the latest snapshot for each assigned symbol, which is a read from object storage and takes tens of milliseconds per symbol. The instance replays the journal from the snapshot’s sequence to the journal’s tail, which takes milliseconds for a typical journal tail of a few hundred entries. The total recovery time is on the order of low seconds, dominated by the orchestrator detection and the instance startup, not by the snapshot load or the journal replay.
The recovery time objective must be consistent with the product’s expectations during an outage. If the matching engine is unavailable for several seconds, the trading API returns errors or stalls, and customers see failed orders. The product accepts this for a rare event; the senior’s job is to minimize the recovery time and to communicate the expected outage window so that the product team can set appropriate customer expectations. A senior who promises sub-second recovery without a warm pool and a fast orchestrator is over-promising.
Failover and the fencing protocol
When a shard instance fails, the failover protocol must ensure that the new instance does not double-match orders that the old instance already committed but whose outbox events had not reached all downstream consumers. The protocol has three steps.
First, the orchestrator detects the failure, either through a health-check timeout or a lease expiry in a coordination service such as etcd or ZooKeeper. The orchestrator marks the old instance as dead and stops routing new orders for its symbols to it.
Second, the orchestrator updates the symbol-to-shard mapping to point to the new instance. The new instance loads the latest snapshot for each symbol and replays the journal from that point. The replay applies every sequenced order through the pure matcher and the idempotent settler, so any trade that the old instance already committed is skipped because its sequence number is already in the ledger and the settler’s idempotency check skips it. Any trade that the old instance started but did not commit is now committed by the new instance.
Third, the orchestrator verifies that the old instance has stopped accepting orders. This is the fencing step. The old instance may be running but partitioned from the orchestrator, in which case it still thinks it owns the symbols and continues processing. Fencing revokes the old instance’s lease, shuts down its intake connection, or kills the process. Until fencing completes, there is a window where two instances believe they own the same symbol. The window is closed by the combination of fencing and idempotent settlement: even if both instances process the same order sequence, the settler’s idempotency on the sequence number ensures that only one commit takes effect. The outbox events carry the same sequence number, so downstream consumers deduplicate on the sequence key.
Deep dive: the atomic trade and the rollback hazard
The matcher produces trades in memory. The settler must turn those trades into committed changes to cash and positions, and this is where most designs break. The hazard is the dual-write: if the matcher updates the in-memory book, the settler writes the ledger, and somewhere in between a crash or a constraint violation occurs, the book and the accounts diverge. The documented Trade Republic failure mode is exactly this, a transaction that does not roll back cleanly, leaving a matched trade with no corresponding account update or vice versa.
The correct design makes the trade, the ledger deltas, the position deltas, and the outbox event one transactional unit. The settler writes all of it in a single Postgres transaction; either all commit or none commit. The in-memory book is updated only after the transaction succeeds, and on failure the book is rolled back to its pre-match state. The trade carries the sequence number, so a retry after a transient failure is idempotent and cannot double-apply.
The rollback is the half candidates forget. If the ledger transaction fails, because a balance went insufficient or a deadlock aborted the transaction, the matcher’s changes to the in-memory book must be undone. A design that commits the book optimistically and then writes the ledger has no way to un-match: the trade has already affected the book’s price levels, and the next incoming order would match against a phantom fill. The safe order is the reverse: derive the deltas, attempt the transaction, and only on success mutate the book. On failure, restore the book from the pre-match copy. This is the documented lesson in Consistency, Transactions, and Rollbacks, applied to the engine.
The outbox row is part of the transaction for the same reason it is part of any dual-write fix, as taught in The Outbox Pattern, Deeply. The trade and its downstream event must commit together, or a crash between them leaves a committed trade that downstream systems never learn about. Kafka cannot join a Postgres transaction, so the event is written as an outbox row that Debezium streams to Kafka with the trade’s atomicity guaranteed by the database. The customer notification, the risk update, and the market-data tape all flow from that single outbox event, decoupled from the settlement transaction.
Cross-exchange routing
Many retail broker orders are not matched internally; they are routed to external exchanges or market makers for best execution. The matching engine design must handle both internal matches, where both sides of the trade are customers of the same broker, and external routing, where the order is sent to an exchange or a market maker and the fill comes back asynchronously.
The routing decision is made after the limit-order book check but before settlement. If the engine can match the order internally at a price at least as good as the external best bid and offer, it matches internally. If not, it routes the order to an external venue through a gateway that translates the internal order format to the venue’s protocol. The fill from the external venue arrives on a callback or a fill topic, and the engine processes it as if it were an internal match: the fill is applied to the ledger and the outbox through the same settlement transaction.
The gateway is a separate service from the matching engine because each venue has its own protocol, format, and connectivity requirements. The gateway normalizes the fill into the internal trade format, assigns it a sequence number that preserves ordering within the symbol, and publishes it to a fill-received topic. The matching engine consumes this topic and applies the fill through the same settlement path as an internal match. This design isolates venue-specific complexity in the gateway, keeping the matching engine pure.
The existence of external routing creates a latency asymmetry that the engine must handle. An internal match settles in milliseconds. An external match may take hundreds of milliseconds to round-trip through the venue. During that window, another internal order may arrive and match against the same resting order that the external fill is about to consume. The defense is to reserve the resting order at match time: when a match is sent to an external venue, the resting order is marked as pending and cannot be consumed by another match. If the external fill arrives, the pending order is consumed; if the external fill fails, the pending order is released back to the book and its time priority is preserved. The reservation is an in-memory flag in the book, not a database write, because the window is millisecond-scale and the cost of persisting the reservation is too high.
Data model
The data model separates the order book, which is transient and in memory, from the durable ledger, which is the source of truth for money and positions.
The trade’s sequence number is the field that ties everything together. It is the matcher’s logical clock, the settler’s idempotency key, and the outbox event’s ordering key. Downstream consumers order by it, so the notification a customer receives and the risk update the risk service applies are sequenced exactly as the engine produced them, regardless of consumer restarts or redelivery.
Order status model
Every order tracked through a status lifecycle the engine owns. An order starts as NEW when it is journaled. After the intake accepts it and before the matcher processes it, it is PENDING. When the matcher begins matching, the order enters MATCHING, and after settlement either it is FILLED if fully matched, PARTIALLY_FILLED if partially matched and the remainder rests, or REJECTED if the settlement transaction fails. A cancellation transitions the order to CANCELLED, which prevents any further matching.
The order status is the source of truth for the customer, and opacity here is a support incident magnet. If the customer sees their order as NEW for longer than expected, they call support. The order status is exposed through the trading API and is updated atomically with the settlement transaction. A partially filled order shows the filled quantity and the remaining quantity, and the customer can cancel the remaining portion. The status update is idempotent and the API caches the latest status for a short TTL, because reading the status through the ledger on every request would overload the database.
Regulatory audit trail
The matching engine must maintain an audit trail that a regulator can inspect. The audit trail is the input journal plus the committed trades. The regulator takes the journal, replays it through a reference engine implementation, and compares the output to the committed trades. A mismatch is a regulatory violation.
The audit trail imposes two requirements on the engine design. First, the journal must be immutable: once an order is journaled at a sequence number, it can never be changed or deleted. Even a correction is a new journal entry that supersedes the old one, never a modification of the old entry. Second, the engine’s implementation must be versioned so that the regulator can replay against the version that was running at the time of the trades. A change to the matching logic, even a bug fix, must be accompanied by a version bump and a documented description of the change, and the journal must record which version processed each sequence range.
The versioning requirement means that the engine’s code is subject to a formal change management process that is stricter than the rest of the platform. A senior engineer at Trade Republic must be comfortable operating inside this process. The matching engine is not a service that can be changed freely; it is a regulated system, and every change carries the cost of reverification by the compliance team. Naming this awareness in the interview shows that the candidate understands the broader operating context, not just the data structures.
Tradeoffs and alternatives
Single-engine versus distributed-engine is the first tradeoff. A single matching engine for all symbols is simplest to reason about, because there is one sequencer and one book, and determinism is trivial. It does not scale: one thread cannot absorb the burst load of a volatile session across thousands of symbols, and it is a single point of failure. The distributed design, one single-threaded engine per symbol shard, scales horizontally and isolates failures per symbol, at the cost of cross-symbol coordination, which a matching engine never actually needs because symbols are independent. The distributed design is correct for a broker of any size, and the single-engine design is only defensible for a tiny operation or a prototype.
In-memory book versus database-resident book is the second. A database-resident book, where every order and every match is a row update, is durable by construction but slow by construction: the latency of a Postgres round trip per match is orders of magnitude above the target. The in-memory book with event-sourced recovery is the production choice, because it makes matching fast and recovers correctness from the journal. The cost is the recovery code path, which must be tested, because a buggy replay is a silent correctness bug.
Synchronous settlement versus asynchronous is the third. Synchronous settlement, where the trade commits to the ledger before the matcher proceeds, is safest but adds the ledger round trip to every match. Asynchronous settlement, where the matcher produces trades into a queue and a settler applies them later, is faster but introduces a window where the book has advanced and the ledger has not, which is exactly the divergence hazard. The production answer is synchronous settlement within the shard, because correctness is non-negotiable for a broker, and the latency is acceptable because the ledger is local and the transaction is short.
Optimistic book commit then settle, versus settle then commit, is the fourth and most dangerous. Optimistic commit then settle is faster on the happy path but has no rollback path, because the book has already mutated. Settle then commit, the design above, is slower by one transaction per match but is always recoverable. For a broker, the recoverable design is the only defensible one.
Failure modes and what breaks at scale
A crash mid-match is the primary failure mode and the one the architecture is built around. If the engine dies after the matcher mutated the in-memory book but before the settler committed, the in-memory book is lost with the process, and on restart the journal is replayed from the last snapshot. Because the matcher is pure and deterministic, replay produces the same trades up to the crash, and the settler applies them again idempotently using the sequence number, so no trade is doubled and none is lost. The recovery story is the architecture’s reason for being.
A failover to a standby is the harder case. If the primary shard fails over to a replica, the replica must not double-match orders the primary already matched but whose outbox events had not yet flushed. The safe pattern is for the standby to recover from the journal and the snapshot, applying trades idempotently by sequence number, and for the intake to fence the old primary so it cannot accept new orders after failover. This is distributed-systems territory, and the key insight is that sequence-number idempotency plus journal replay plus fencing makes double-matching impossible even when both primaries are briefly alive.
A ledger constraint violation, such as an insufficient balance on a cash account, must roll back the match. The settler catches the failure, restores the in-memory book from its pre-match copy, and returns the order to the intake as rejected. The temptation to partially apply a match, taking the trades that fit the balance and rejecting the rest, is wrong, because it produces a non-deterministic outcome that depends on the ledger state rather than the order sequence. The whole match commits or none of it does.
A hot symbol that saturates its shard is the scaling limit. Because each shard is single-threaded, one symbol cannot use more than one core. The mitigation is to split the symbol’s order flow across sub-shards by a deterministic key, but this breaks the single-book property and is rarely worth it; the usual answer is that a single symbol saturating a core is an extraordinary event and the engine degrades gracefully by queueing at the intake. Naming this limit shows you understand the architecture’s ceiling.
Outbox lag is an operational failure mode. If Debezium falls behind, downstream systems see trades late. The trades themselves are correct and committed; only the downstream notification is delayed. The mitigation is monitoring the outbox depth and alerting on lag, because a delayed customer notification for a fill is a support incident even if the trade is internally correct.
A journal partition failure, where the database partition holding the input journal is unavailable, blocks the engine from accepting new orders for the affected symbols. The mitigation is to journal in a highly available Postgres cluster with synchronous replication and automatic failover, and to treat the journal as the source of truth that must survive a single-node loss. The journal table itself is critical infrastructure, and its availability is monitored separately from the rest of the trading system. A senior insists on journal-cluster independence from the ledger cluster, because a ledger cluster issue must not prevent the engine from journaling incoming orders, even if those orders cannot be settled until the ledger recovers.
An outbox poison pill, where a malformed outbox row blocks the entire outbox publish batch, stalls the delivery of all subsequent trade events downstream. The Trade Republic outbox design documented in src_tr_outbox1 explicitly calls out poison-pill handling: the publisher groups messages by key and retries failing groups independently, so a malformed row for one trade does not block the publication of other trades. The matching engine must adopt the same poison-pill isolation at the outbox level, because a corrupt trade event, however unlikely, must not stall all trade events behind it.
A clock skew across shards is not a correctness issue because the engine orders by sequence number, not by timestamp. However, clock skew does affect operational monitoring: metrics that compare wall-clock timestamps across shards, such as end-to-end latency from order submission to fill, are skewed by the clock difference. The mitigation is to use the sequence number as the primary ordering axis in monitoring and to treat wall-clock timestamps as advisory for cross-shard comparisons. A senior knows that monitoring a sequence-gap metric is more reliable than monitoring a timestamp-delta metric.
Latency measurement and the end-to-end timing contract
The end-to-end latency of the matching engine is measured from the moment the intake receives the order to the moment the outbox row commits. This captures the full critical path: validation, journaling, matching, settlement, and outbox write. The target is single-digit milliseconds for a match that does not require external routing and low double-digit milliseconds for a match that routes to an external venue.
Latency measurement must account for queueing effects within the shard. The shard processes orders sequentially, so a burst of orders increases the queue depth and each order waits behind the ones ahead of it. The observed latency for an order is the sum of the processing time per order times the queue depth at arrival. The monitoring system tracks both the processing time per order, which should be stable, and the queue depth, which grows under burst. A growing queue depth without a corresponding change in per-order processing time means the shard is saturated, and adding shards or splitting the hot symbol is the answer.
A subtle latency concern is the garbage-collection pause in the JVM running the engine. The matching engine is latency-sensitive and runs with a low-pause garbage collector such as ZGC or Shenandoah. Even with a low-pause collector, a concurrent cycle can still add milliseconds to a single match if the order arrives during a particularly unlucky phase. The mitigation is to measure GC pause impact on the p99 match latency and to size the heap generously enough that GC cycles are infrequent. If the engine runs on a GraalVM native binary, the GC concern is eliminated entirely because there is no JIT warmup or GC pause.
Testing and verification
The matching engine is the hardest system to test because its outputs are not just values; they are ordered sequences of trades that must be correct for every possible order combination. The testing strategy has three layers.
Unit tests verify that the matcher produces the correct trades for a given book state and a given input order. The test covers every order type: limit crosses, market order consumes multiple levels, iceberg refresh preserves time priority, cancellation removes the order, and partial fill reduces but leaves the order. Each test asserts the exact trades produced, the final book state, and the sequence number assignment.
Integration tests verify the full settle-and-apply cycle against a real Postgres instance. They submit orders through the intake, confirm the trades commit in the ledger, confirm the outbox row is written, and confirm that a simulated crash after the commit but before the book update does not leave the book in an inconsistent state. The integration test also verifies the rollback path: it injects a constraint violation in the ledger and confirms the book is restored.
Chaos tests verify the recovery story. They crash a shard mid-match, bring up a new instance, and confirm that no trade is lost and none is doubled by comparing the sequence of committed trades before and after the crash against the journal replay. The chaos test is the only way to build confidence in the failover protocol, because the recovery code path is exercised rarely in production and a latent bug in the replay or the idempotency check would be catastrophic.
A senior insists on the chaos test being part of the release pipeline, because every change to the matching engine, the journal schema, or the snapshot format risks breaking the recovery path. A change that passes all unit tests and integration tests but breaks replay is a correctness bug that will be found only during an actual crash, which is the worst time to discover it.
Operational concerns
Observability keys off the sequence number. Track the gap between the highest sequence the matcher produced and the highest sequence the settler committed; a growing gap means the settler is falling behind or retrying. Track the end-to-end latency from intake to outbox flush. Track the replay duration on restart, which should be seconds, not minutes, given a recent snapshot.
Idempotency is verified, not assumed. Inject duplicate sequence numbers in testing and confirm the settler collapses them rather than double-applying. Inject a mid-transaction crash and confirm the book rolls back. These failure-injection tests are how a broker earns confidence in the recovery story, because the recovery code path is exercised only rarely in production.
Snapshots must be frequent enough that replay is bounded. The tradeoff is snapshot cost, which briefly pauses the shard, against replay cost, which grows with the journal tail. A common cadence is a snapshot every few minutes or every few hundred thousand orders, whichever comes first, tuned so replay completes within the recovery-time objective.
Capacity planning keys off the per-symbol burst rate and the symbol count. The fleet size is the number of shards, each pinned to a core, with headroom for the hottest symbols. The ledger database is sized off the trade write rate, which is the settler’s transaction rate, and the outbox depth under load.
The key metric for capacity is the per-shard match rate under burst, not the average rate. A shard that handles a few thousand matches per second on average may see a burst of tens of thousands when the market opens or when a corporate action triggers a flurry of orders. The shard must be sized for the burst, with headroom, because the single-threaded model means it cannot borrow capacity from another shard during a burst. The headroom is typically 2x to 3x the expected peak, sized by load testing the specific symbol’s data structure and match rate.
The journal database is sized off the journal insert rate, which is the order submission rate, not the match rate. Every order is journaled before matching, so the journal insert rate is higher than the match rate, especially during volatile sessions when many orders are submitted but few match because prices move quickly. The journal is the bottleneck by write throughput, and the ledger is the bottleneck by transaction complexity, and they must be sized independently. A common error is to size the journal from the match rate and run out of journal insert capacity during a volatile session where orders far outnumber matches.
Deployment safety means a rolling shard restart must not double-match. Each shard is drained before restart: the intake stops accepting orders, the settler flushes all pending trades, the journal is fsynced, and only then does the process exit. On startup, the shard replays from the snapshot and resumes. A rolling restart thus looks to the outside world like a brief pause per symbol, not a gap or a duplication.
Defending the design to a Staff engineer
A Staff engineer will probe the consistency seam, and you should preempt it. State the rule plainly: a trade is one atomic unit that writes the trade record, the cash and position deltas, and the outbox event in a single Postgres transaction; the in-memory book commits only after the transaction succeeds and rolls back on failure; the sequence number makes retry idempotent. This collapses the dual-write hazard and the rollback hazard into one recoverable design.
The durability defense is the combination of the input journal and the snapshot. The journal records every order before matching, so no order is ever lost even if the engine crashes before the match. The snapshot bounds recovery time. The journal and the snapshot live in different storage tiers, journal in Postgres for high-frequency write and snapshot in object storage for bulk serialization, so a failure in one does not affect the other. A senior never claims the engine is durable without naming both mechanisms.
The determinism defense is more than a correctness argument; it is an audit argument. A deterministic engine produces the same output from the same input regardless of when or where it runs. This means the regulator can take the journal, replay it through the engine, and verify that the trades the regulator sees match the trades the broker reported. Non-deterministic elements like clock time or random tics break that auditability. A senior names this regulatory property explicitly, because it shows awareness that the matching engine is not just a through put machine; it is a compliance instrument.
The latency versus correctness tradeoff in the matching engine is the hardest question a Staff engineer asks. The question is: when the engine is under maximum load and a trade arrives that would match against a resting order whose cash balance a concurrent check just found insufficient, do you match or reject? The senior answer is that the matching engine does not check balances at all. The engine is a pure matcher; it matches if the prices cross and the order is rest and the resting order is still in the book. The balance check happened at the risk stage before the order was sequenced. If the balance was sufficient at sequence time but is no longer sufficient by settle time, the settlement transaction fails, the match is rolled back, and the resting order remains in the book. The price of this design is a small number of rolled-back matches during high contention. The benefit is that the matching engine stays fast and simple, because it does one thing, and the risk check is a separate stage that owns its correctness independently. A senior separates concerns, even when combining them would be faster on the happy path, because separation is what makes each concern auditable.
The scaling defense is sharding by symbol. Each shard is a single-threaded engine with its own sequencer, journal, book, and settler, so per-symbol determinism is preserved while total throughput scales with the shard count. Symbols are independent, so there is no cross-shard coordination, which is why the distributed design has no hidden cost over the single-engine design at a broker’s scale.
The recovery defense is event sourcing plus snapshots. On crash, replay the journal from the last snapshot; the pure matcher reproduces the same trades; the settler applies them idempotently by sequence number; the book is reconstructed. No trade is lost, because every sequenced order is in the journal; no trade is doubled, because the settler is idempotent on the sequence. The failover story adds fencing of the old primary so a split brain cannot double-match.
The engine is a pure, single-threaded, per-symbol matcher whose output is applied by a transactional settler that writes the book, the ledger, and the outbox in one transaction and rolls back on failure. Determinism from sequence numbers makes it replay-safe, so a crash loses no trade and doubles none.
Common mistakes candidates make
- Designing only the in-memory book and ignoring the ledger. 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 in-memory book must roll back. Candidates who skip the rollback leave the book and the accounts permanently diverged. This is the documented Trade Republic failure mode.
- Committing the book before settling. Optimistic book commit then settle has no rollback path, because the book has already mutated. Settle then commit, so the book mutates only after the transaction succeeds.
- Ordering by wall-clock timestamp. Timestamps across pods are skewed and break time priority. Use a monotonic sequence from the single sequencer per symbol.
- 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 a worked example signals the candidate has not matched by hand.
- Treating outbox publication as separate from the trade. Writing the Kafka event outside the trade transaction is the dual-write bug. The outbox row commits with the trade.
- Ignoring failover double-matching. A standby that does not fence the old primary can match the same order twice. Fencing plus sequence-number idempotency is the defense.
What the interviewer asks next
Expect to be pushed on crash recovery. The question: the engine crashes after the matcher mutated the book but before the settler committed. What happens on restart? The strong answer is that the in-memory book is lost with the process, the journal is replayed from the last snapshot, the pure matcher reproduces the same trades, and the settler applies them idempotently by sequence number, so no trade is doubled and none is lost.
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 journal, preserving per-symbol determinism while scaling total throughput. Cross-symbol coordination is never needed because symbols are independent.
A third, deeper probe: how do you prevent double-matching when the primary fails over to a standby while the old primary is still alive? The answer has three parts. The standby recovers from the journal and applies trades idempotently by sequence number, so any trade the old primary already committed is not re-applied. The intake fences the old primary, for example by revoking its lease, so it cannot accept new orders after failover. And the outbox is the source of truth for what was committed, so downstream consumers deduplicate by trade id. Together these make split-brain double-matching impossible in effect, even if briefly two primaries are alive.
A fourth probe: a regulator asks how you audit the matching engine. The answer names the input journal as the immutable source that a regulator can replay through a reference engine, the sequence-number-based ordering that makes replay deterministic, the versioned engine code that lets the regulator match trades to the engine version that produced them, and the snapshot mechanism that proves the engine’s state at any point in time. A senior states the audit trail as naturally derived from the architecture rather than retrofitted, because the journal and the sequence number exist for correctness, and auditability is a free benefit.
A fifth probe: what happens when a settlement transaction times out because the Postgres transaction is slow? The answer is that the transaction timeout is set to a value well above the expected transaction duration, typically a few hundred milliseconds. A timeout indicates a systemic problem: a deadlock, a contention spike, or a disk stall. The engine’s response is to abort the transaction, roll back the book, and return the order to the intake with a transient error status. The client is expected to retry with the same idempotency key. The intake sees the idempotency key, skips the journal write, and returns the original sequence number, which causes the matcher to re-process the order against the unmodified book. The net effect is a brief latency spike for that order but no loss of correctness. A senior does not try to recover from a timeout within the same transaction; they abort and let the idempotency layer handle the retry.
The outbox partitioning and index design specific to the matching engine
The matching engine’s outbox has a different write profile than a general-purpose outbox. Trade-execution events are written in bursts when a match produces multiple fills, and the outbox must absorb these bursts without degrading. The Trade Republic outbox design documented in src_tr_outbox1 and src_tr_outbox2 addresses the specific failure modes of a high-volume outbox: partial indexes on published_at IS NULL bloat under high insert rates, the id sequence must be int8 to avoid overflow, and the outbox must be partitioned by published_at so that the unpublished partition is always small and the published partition can be archived.
For the matching engine, the outbox is also the recovery point for downstream consumers. If the outbox is published but the downstream consumer crashes before processing, the consumer restarts from its last committed offset and replays the events. If the outbox is not published because the engine crashed after the settlement transaction committed but before Debezium read the WAL entry, the downstream consumer sees a gap in the event stream. The gap is closed by the outbox’s durability: the outbox row committed with the trade, Debezium will capture it when it resumes, and the downstream consumer will receive the event at that point. The downstream consumer must be able to handle late-arriving events, which means it must be idempotent on the trade sequence number and must not assume event ordering is equivalent to event arrival time.
The practical lesson from the Trade Republic outbox incidents is that the outbox is not a set-and-forget pattern. It requires ongoing operational attention: monitoring the unpublished partition size, the Debezium connector lag, the id sequence usage, and the autovacuum pressure on the outbox table. A senior who designs a matching engine must design its outbox as a subsystem with its own on-call runbook, not as a table that happens to be there.
Mastery Questions
Question
After a match, the ledger transaction fails on a constraint violation. What must happen to the in-memory book, and why?
Answer
The in-memory book must roll back to its pre-match state. If the book had already committed the match, there would be no way to un-match: the trade would have affected the price levels and the next incoming order would match against a phantom fill. The safe order is to derive the deltas, attempt the transaction, and mutate the book only on success. On failure, restore the pre-match book and reject the order. This is the documented rollback failure mode.
Sources & evidence5 claims · 4 cited
Design based on real Trade Republic interview prompts and engineering blog sources (src_tr_interview, src_tr_outbox1, src_tr_debezium, src_tr_partitioning); design reasoning beyond sources is internal-reasoning and carries no claim.
- The Trade Republic order matching engine is designed as a per-symbol, single-threaded engine with its own sequencer, input journal, in-memory limit-order book, and settler that writes trades, ledger deltas, and outbox events in one PostgreSQL transaction.verified
- The documented candidate failure mode for an order matching engine is designing only the in-memory book and ignoring the ledger consistency problem: a non-atomic update between the match and the account update leaves the book and the accounts permanently diverged.verified
- The matching engine's outbox row commits in the same PostgreSQL transaction as the trade and the ledger deltas, so Debezium streams the trade event to downstream systems atomically with the trade itself, preventing dual-write failures.verified
- Symbol sharding enables horizontal scaling of the matching engine: each symbol runs on its own single-threaded engine instance, preserving per-symbol determinism while total throughput scales with the shard count, and symbols are independent so no cross-shard coordination is needed.verified
- The matching engine's recovery from a crash uses event sourcing: replay the input journal from the last snapshot through the pure deterministic matcher, and the settler applies trades idempotently by sequence number, so no trade is lost and none is doubled.verified
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)
- Postgres partitioning performance: Hash vs. List · Trade Republic Engineering (Sadeq Dousti)
- Streaming Outbox Events from Postgres to Kafka with Debezium · Trade Republic Engineering (Andrei Sukharev)