matching-engine

A limit order book matching engine in Go: price-time priority, REST and WebSocket APIs, and a command log that replays to the same book.

  • Go
  • Order book
  • WebSocket
  • Write-ahead log
  • Load testing
The engine's order book page following BTC-USD while cmd/loadgen sends 2,000 requests per second.

Key metrics

commands per second through the matching core on one symbol, measured on a noisy VM, where runs of one benchmark differ by up to 1.96 times
6.25M–8.88M
p99 from order to trade push at 10k requests/s
1.76 ms
matching core heap with 1M resting orders
124 MiB
of statements covered by tests
93%

The latency figure was measured on one 4 vCPU cloud VM with Go 1.24.7, and the throughput and memory figures on a second 4 vCPU cloud VM with Go 1.27.4, at earlier commits; in the end-to-end runs the engine shares the first VM with the load generator. The project now builds with Go 1.27.4, and the end-to-end runs predate later changes to the engine, including its API code and matching core; the repository holds no end-to-end run on the first VM after them. Benchmark report

Problem and goals

A matching engine takes orders and cancels, matches them by price and then by time, and streams the results to clients. Matching is sequential, every result has to be reproducible from the log, and an acknowledged order must survive a crash of the process.

The project set three targets: more than 1M operations per second in the core on one symbol, a p99 under 5 ms from a REST order to its trade push at 50,000 orders per second, and a measurement of memory use with 1M resting orders.

The core meets its target 6 to 9 times over. The end-to-end target, about 71k requests/s in this order flow, is out of reach on the first 4 vCPU VM, where the p99 stays under 5 ms up to 15k requests/s. At 50k requests/s, near saturation, the p99 was 41 ms, a figure that depends on the machine.

Architecture

Clients send orders, cancels and queries to the HTTP and WebSocket API. Each symbol has a bounded queue feeding one market goroutine, which writes each batch of commands to the command log before applying it to the order book. Its events return through the API, which pushes snapshots, deltas and trades to clients.

Key decisions

  • D003 One goroutine per symbol

    Matching is sequential, so each symbol's book and log belong to one goroutine. The book needs no locks, and replaying the log rebuilds exactly the same book. Requests reach the goroutine through a bounded queue; when it is full, orders and cancels get a 503 at once instead of piling up latency.

  • D004 A red-black tree, chosen by benchmark

    A red-black tree, a skip list and a sorted slice ran the same model tests and benchmarks. At 10,000 price levels, removing one level and adding one near the top took 250 ns in the tree against 405 ns in the skip list, and across sizes the skip list's writes were 26% to 101% slower. The tree also has a guaranteed worst case and needs no random seed: in testing, prices chosen by someone who knew the skip list's seed raised its average lookup steps near the top of the book from 18 to 517.

  • D017 Write ahead, fsync every 10 ms

    Each batch of commands is written to the log before it is applied, and the log is fsynced every 10 ms. A process crash loses no acknowledged command, which a test checks by killing the engine under load; a machine crash can lose the last interval and the commands taken during an fsync in progress. Syncing before every reply was measured too: it raised the p99 by 1 to 10 ms up to 30k requests/s.

  • D030 Open-loop load testing

    cmd/loadgen schedules request i for t0 + i/rate whatever the replies, sends it over one of 64 keep-alive connections, and counts latency from that due time, so a stall is charged to every request it delays. A closed-loop generator waits for replies and quietly sends less, so its p99 can look met while the rate falls short.

Decision log

Challenges

  • The order book was not the bottleneck

    A CPU profile at 25k requests/s put the matching goroutine, book included, at about 10%, against about 19% for HTTP system calls and 14% for decoding request bodies, 9 points of which went to checking their keys. Checking the keys in one scan instead of through a json.Decoder took the check from 5.79 µs and 79 allocations to 0.51 µs and none, and cut the engine's CPU per request by 5% to 8%. In the profiles before and after the optimizations, Book.Apply is 1.4% to 2% of the engine's CPU. The book has since gained its own order index and now reuses the nodes of orders that leave it; the end-to-end figures were measured before that and have not been measured again.

  • An fsync stalled every command

    Every 10 ms the symbol's goroutine stopped for its fsync, 0.8 ms on average and tens of milliseconds at times, and every command waited. A helper goroutine now runs the fsync, as Redis, Kafka and PostgreSQL flush their logs on a background thread (D031). The median p99 at 10k requests/s fell from 5.32 to 3.82 ms, and the three runs at 25k/s went from 20.0, 36.4 and 215 ms to 19.6, 19.8 and 28.7 ms. These sweeps ran at earlier commits on a slower VM of the first VM's type, so they compare only with each other.

  • Proving every trade arrives

    A run counts only if every trade reaches the client once and in order. loadgen checks that the trade stream's sequence numbers run without gaps, that the pushes, the trades in REST replies and the engine's trade counter agree in number, and that the pushes and replies agree in content by a sum of 64-bit hashes (D036). The run must also send 99% of the target rate with no failed request.

  • Compared with other engines on one VM

    The flash1-dev matching engine benchmark ran the matching core, Liquibook, CppTrader and geseq on one 4 vCPU VM in ten rounds, one engine after another, and checked every run's reports against a published hash. The core was faster than CppTrader, the fastest of the three there, in 46 of 50 paired runs, with a median ratio of 1.28 to 1.60 per scenario. One engine's runs of a scenario vary by up to 2.09 times, so this ranks the engines on that VM and makes no claim about absolute throughput. The core takes messages in runs, while CppTrader's adapter takes one per call. No geseq run passes the benchmark's rule on probe time.