Matching Engine Architecture

A matching engine is the exchange component that pairs compatible buy and sell orders. It owns the active order book and applies one execution policy, commonly price-time priority: the best price wins, then the earliest accepted order at that price wins. A buy order crosses when its limit price is equal to or higher than the lowest sell price. A sell crosses when its limit is equal to or lower than the highest buy price. The engine consumes resting orders until the incoming quantity is filled, its price no longer crosses, or the book has no compatible liquidity.

The difficult part is preserving causality. If a partial fill updates the book but the trade event is lost, balances and charts disagree with the engine. If a retry enters twice, the customer may trade twice. If two workers mutate one market concurrently, arrival order becomes ambiguous. Good matching engine architecture reduces these cases to a single rule: accept commands in a total order, mutate authoritative state once, and derive every external view from the resulting event sequence.

Suppose the sell side contains 2 BTC at $100 from order A, then 3 BTC at $100 from order B, followed by 4 BTC at $101. A new limit buy for 4 BTC at $101 arrives. Price priority selects $100 before $101. Time priority selects A before B because A entered the $100 queue first. The engine fills 2 BTC against A, closes A, then fills the remaining 2 BTC against B. B stays open with 1 BTC. The incoming buy is complete, so it never rests. Both trades execute at the resting orders' $100 price under the policy documented by Coinbase Exchange. Here A and B are makers because their orders supplied liquidity before the buy arrived. The incoming buy is the taker. Recording both sides, the matched quantity, resting price, fees, and engine sequence gives settlement and audit systems one exact trade fact to consume.

Now change the incoming limit to $99. Nothing crosses because the buyer will not pay the best ask of $100. The 4 BTC buy joins the bid side at $99. Change it to a market buy instead and price protection disappears: the engine consumes $100 liquidity first, then continues to $101 if quantity remains. This is why a matching engine must use fixed-point integers for price and quantity, state rounding rules explicitly, and reject values outside the market's tick and lot sizes. Binary floating-point has no place in the financial core.

The book needs two ordered maps of price levels: bids sorted from highest to lowest, asks from lowest to highest. Each price level holds a FIFO queue of orders. The top keys give the best bid and ask; the queue preserves time priority among equal prices. A separate order-id index points to each live order so cancellation does not scan the whole book. Depending on the language and workload, the ordered map may be a balanced tree, skip list, radix structure, or bounded price array.

Big-O notation is only the start. Memory layout, allocation rate, cache locality, queue churn, and cancellation patterns decide the tail latency users feel. An array indexed by tick can be excellent for a narrow, dense price range and wasteful for sparse markets. A tree handles sparse prices but adds pointer chasing. Benchmark with a realistic mix: new limits, aggressive orders crossing several levels, partial fills, cancels near and far from the touch, and traffic bursts. A benchmark made entirely of tiny orders at one price is theatre.

The main matching engine architectures differ in where authoritative state lives and how they recover. There is no universally best technology. The correct design follows the fairness policy, latency target, number of independent markets, durability requirement, and operational skill of the team.

For most continuous stock and cryptocurrency markets, a single-writer in-memory core with a durable journal is the clearest default. Database-centric and Redis-backed designs trade some latency for simpler integration or atomic persistence. Active-active shared writers promise scale but make deterministic price-time priority substantially harder to prove.

• Single-writer in-memory book — lowest and most predictable matching latency; requires a journal, snapshots, replay, and disciplined failover.
• Partitioned matching cells — scales across independent symbols and bounds failures; hot symbols still have a single-writer ceiling and partition movement needs an explicit migration.
• Redis or Valkey-backed state — convenient atomic state, idempotency, and outbox transactions; network and persistence round trips reduce command throughput.
• Database-centric matching — straightforward durability and auditing at modest volume; row locks and index churn usually make it a poor low-latency core.
• Active-active writers on one book — may help specialized batch auctions; for continuous price-time matching, coordination cost and ambiguous ordering usually outweigh parallelism.

A matching engine should usually be single-threaded at the decision point for one market. One writer gives every command an unambiguous position, avoids locks in the hot path, and makes replay deterministic. Adding threads to the same BTC-USD book does not automatically add useful throughput: the threads must still agree which order arrived first and commit one resulting sequence.

The system around that loop should be parallel. Gateways validate connections concurrently; independent symbols run on separate partitions; outboxes, settlement, WebSocket delivery, candles, surveillance, and analytics consume events independently. In the Bitsten cell design, pairId maps deterministically to a partition, and each partition owns one quorum command queue, conductor, Redis-compatible cell, and outbox. Scale comes from more independent cells on isolated CPU and disk—not multiple writers racing inside one order book.

Stock and cryptocurrency matching engines share the same core mechanics: an ordered command stream, bid and ask books, a priority policy, fixed-point quantities, fills, cancels, and an authoritative execution log. A stock exchange may use price-time, pro-rata, or venue-specific allocation rules; a crypto exchange commonly uses continuous price-time matching but must publish its exact policy rather than assume it.

The operational environment differs. Stock venues inherit trading sessions, opening and closing auctions, regulatory halts, market-wide controls, consolidated-market obligations, and formal surveillance. Cryptocurrency exchanges commonly operate continuously across many pairs, integrate custody and blockchain deposits or withdrawals, manage fragmented external liquidity, and face 24/7 recovery without a nightly maintenance boundary. Those differences change risk, operations, and settlement, but they do not justify weakening deterministic order priority.

A restart plan is part of the algorithm. The engine needs a durable command or event journal, periodic snapshots, monotonic sequence numbers, and idempotent consumers. Recovery loads a verified snapshot, replays subsequent records in sequence, and checks that the reconstructed book reaches the expected checksum or state marker before trading resumes. An acknowledgement policy must say exactly when a client may believe an order exists.

Sequence numbers turn silent corruption into a detectable gap. If a market-data consumer receives event 8402 after 8400, it pauses, retrieves 8401 or a fresh snapshot, then resumes. The same principle applies to balances and candles. Exactly-once delivery is often a marketing phrase; durable at-least-once delivery plus idempotent application is easier to prove. The business invariant is not that a message moved once. It is that each accepted trade changes financial state once.

Command idempotency alone does not prevent every double match. A broker can redeliver the same command ID, but an API retry may create a new command ID for the same order. The engine therefore needs two durable identities: a processed-command record and a permanent accepted-order marker. In the Bitsten design, the order marker remains after the live order closes, so a new command identity cannot place and match that order again.

The marker, book mutation, stable event IDs, processed-command result, and outbox append commit in one partition-local transaction. A quorum queue with a single active consumer enforces one writer, while the service also serializes local entry points. This prevents the engine from executing the same order twice. It does not create exactly-once delivery across Redis and RabbitMQ: downstream balance and order consumers still need a transactional inbox keyed by event ID so a repeated outbox publication cannot apply financial effects twice.

Test duplicate submissions, cancel-versus-fill races, insufficient reserved funds, partial fills across many price levels, self-trade prevention, market halts, expired orders, invalid increments, journal write failures, downstream backpressure, reconnecting consumers, and snapshot corruption. Property-based tests can generate command sequences and assert invariants: total executed buy quantity equals total executed sell quantity; remaining quantity never becomes negative; FIFO order is preserved within a price; and replay produces the same final book.

Chaos tests should kill the process between journal append, book mutation, event publication, and acknowledgement. Then recover and compare every order, fill, balance movement, and sequence number with an uninterrupted reference run. If the team cannot state what happens at each interruption point, the engine is not ready for real funds. Happy-path throughput does not compensate for ambiguous recovery.

Report the latency boundary before reporting the number. Engine latency may mean time inside the match loop, gateway-to-engine time, or client round-trip time; these figures are not interchangeable. Measure p50, p95, p99, and p99.9 under a declared order mix, book depth, market count, payload size, persistence mode, and hardware profile. Record throughput at the same time because a low median at low load says little about saturation.

The boundary changes the result dramatically. Bitsten's production matching loop processed more than 4,000 orders per second with sub-millisecond engine latency. In the later architecture benchmark, pure matching exceeded 100,000 calculations per second, the conductor with Redis sustained roughly 300–380 commands per second, and the original confirmed full pipeline reached about 106 commands per second. A synthetic Dragonfly state transaction reached 25,621 transactions per second in memory mode; durable Valkey with AOF and replica acknowledgement reached 3,254. These numbers describe different workloads and cannot be compared as one leaderboard.

Two cells sharing one Docker Desktop host were 9–10 percent slower than one because they competed for the same CPU and disk. Distributed Redis increases matching throughput only when independent partitions receive independent resources and traffic. Watch queue depth, reject rate, journal flush time, event-consumer lag, allocation rate, and the distance between median and tail latency. Require a sustained workload and zero invariant violations before calling horizontal scaling successful.

Market data is a projection. WebSocket messages can be delayed, batched, dropped, or received after a reconnect; they should never become the authoritative input for accounting or OHLCV generation. At Bitsten, deriving candles from WebSocket delivery caused drift under load. Rebuilding them from the matching engine's ordered trade log fixed the causality error and made historical regeneration possible.

This separation also makes observability useful. Each command, execution, and projection update can carry market, order, trade, and sequence identifiers. Operators can trace a customer's request from gateway acceptance to book mutation, ledger posting, and public feed without placing logging calls inside the hottest comparison loop. Alerts should focus on invariants and lag: sequence gaps, negative quantities, crossed books after processing, ledger mismatches, journal failures, and consumers falling behind.