lob — a single-instrument limit order book in Rust

This project implements a full vertical slice of a matching venue for one instrument: an order book core with three interchangeable price-level data structures (benchmarked against each other), pluggable matching policies (FIFO and pro-rata), a segmented write-ahead log with crash recovery, an account/escrow ledger, a single-threaded engine actor, and an axum HTTP + WebSocket gateway with HMAC-signed auth tokens and a snapshot-plus-delta market-data protocol.

The goal was not to build a production exchange, but to learn why real matching engines are built the way they are — and to measure the difference the data structures make.

                        ┌───────────────────────────────────────────────┐
   HTTP / WS clients    │                 axum gateway                  │
  ────────────────────► │  POST /users      POST /order   POST /order_faf│
                        │  GET /ws/market   GET /ws/user   (HMAC auth)  │
                        └───────┬───────────────────▲───────────▲───────┘
                                │ bounded mpsc      │ broadcast │ per-user
                                │ (Command)         │ (frames)  │ channels
                        ┌───────▼───────────────────┴───────────┴───────┐
                        │        engine actor (dedicated OS thread)     │
                        │                                               │
                        │   authorize ─► match ─► settle ─► publish     │
                        │  ┌──────────┐  ┌─────────────────────────┐    │
                        │  │ Accounts │  │ OrderBook<S, M>         │    │
                        │  │ balances │  │  S: Storage (BTreeMaps) │    │
                        │  │ escrow   │  │     └─ PriceLevel impls │    │
                        │  │ owners   │  │  M: MatchingEngine      │    │
                        │  └────┬─────┘  └───────────┬─────────────┘    │
                        └───────┼────────────────────┼──────────────────┘
                                ▼                    ▼
                        accounts_wallog/       book_wallog/
                        (bincode WAL)          (bincode WAL)

Highlights

• Three price-level implementations behind one trait, from a naive VecDeque baseline to a slab-arena intrusive linked list with O(1) cancel/modify — with Criterion benchmarks that show exactly what that buys you.
• Zero-lock hot path. All matching state is owned by one OS thread; the async world talks to it through a bounded channel. No Mutex anywhere near the book.
• Serialize-once fan-out. Market-data frames are serialized to JSON a single time on the engine thread, wrapped in Arc<Bytes>, and broadcast to every WebSocket subscriber by reference-count bump.
• Write-ahead logging + deterministic replay. Both the book and the account ledger append length-prefixed bincode records to segmented logs and rebuild their full state on restart.
• Gap-free market data. Snapshot-then-delta protocol keyed by a monotonic sequence number, with the classic subscribe-before-snapshot ordering to avoid missing events.
• Escrow-based settlement. Funds/shares are moved to escrow when an order rests, released on cancel, and settled maker↔taker on every fill.
• 66 tests, including property-based tests (proptest) and Rc-leak tests that prove the hand-rolled linked list frees its nodes.

---

Table of contents

1. The order book core
2. Price levels: three data structures, one trait
3. Book storage
4. Matching engines: FIFO and pro-rata
5. Durability: the write-ahead log
6. Accounts, escrow and settlement
7. Concurrency model: the engine actor
8. The network layer
9. HTTP / WebSocket API
10. Benchmarks
11. Testing
12. Running it
13. Project layout
14. Known limitations & future work

---

1. The order book core

OrderBook<S, M> (src/order_book.rs) is generic over its storage backend and matching policy:

pub struct OrderBook<S, M> {
    storage: S,          // S: Storage      — where price levels live
    engine: M,           // M: MatchingEngine — how fills are allocated
    log: Option<WALWriter>,
    base_info: BaseInfo, // cached best bid / best ask / spread
    next_order_id: u64,
    seq: u64,            // monotonic sequence number, bumped per command
}

Everything is composed through traits and resolved with static dispatch — swapping the level implementation or the matching policy is a one-line change at construction time and costs nothing at runtime:

let book = OrderBookBuilder::new()
    .storage(DefaultStorage::<SlabPriceLevel>::new())
    .engine(FifoEngine)
    .with_log("./book_wallog")     // append every accepted command
    .with_replay("./book_wallog")  // rebuild state from the log on startup
    .build()?;

Four command types flow through process_order (src/core/order.rs):

Command	Behaviour
Limit { price, size, side }	Rests on the book. Crossing the opposite best price is rejected (OrderPriceOverlap) — in this design, taking liquidity is done explicitly with market orders.
Market { size, side }	Sweeps the book level by level from the best price. side names the book side being consumed (the maker side): Market { side: Ask } is a buy that eats the ask side. Partial fills happen when liquidity runs out.
Cancel { order_id }	Removes a resting order; empties and prunes the level if it was the last one.
Modify { order_id, new_size }	Resizes in place. Whether the order keeps or loses time priority is delegated to the matching engine: size down keeps queue position, size up sends it to the back (the standard exchange rule).

Every accepted command produces an Ack:

pub struct Ack {
    pub seq: u64,                             // sequence of this command
    pub order_id: Option<OrderId>,
    pub order_updates: Arc<Vec<OrderUpdate>>, // OrderAccepted / Fill / Cancelled / Modified
    pub depth_updates: Arc<Vec<DepthUpdate>>, // (price, side, new_total_qty) per touched level
}

The update vectors are Arc-wrapped on purpose: the same allocation is shared by the reply to the caller, the market-data broadcast, and the per-user event fan-out — nothing is cloned on the hot path.

2. Price levels: three data structures, one trait

This is the heart of the project. A price level is a FIFO queue of resting orders at one price that must also support cancel and modify by order id — and in real markets, cancels/modifies vastly outnumber trades. The PriceLevel trait (src/price_level/mod.rs) captures the interface (add, cancel, modify-with-optional-reprioritize, pop/push front, peek, iterate — iteration uses a generic associated type type Iter<'a>), and three implementations explore the design space:

SlowPriceLevel — the honest baseline

src/price_level/slow_price_level/mod.rs

VecDeque<OrderData> + HashSet<OrderId> for membership. Cancels and modifies do a linear scan and an O(n) VecDeque::remove. Simple, correct, and exactly what you'd write first — it exists to be measured against.

FastPriceLevel — classic intrusive queue, safe-Rust edition

src/price_level/fast_price_level/

The textbook exchange design: a doubly-linked list holding the FIFO queue, plus a hash map from OrderId straight to the list node, giving O(1) cancel, modify, and move-to-back. The list is hand-written in safe Rust (Rc<RefCell<Node>> forward links, Weak back links to break reference cycles — linked_list.rs), and the test suite includes explicit leak checks that downgrade nodes to Weak and assert the strong count reaches zero after every removal path.

The trade-off it demonstrates: asymptotics won, but every node is a separate heap allocation, every hop chases a pointer, and every access pays RefCell bookkeeping.

SlabPriceLevel — the arena version (default)

src/price_level/slab_price_level/

Same doubly-linked-list idea, but nodes live in a slab arena and links are plain usize indices instead of pointers (linked_list.rs). Freed slots are recycled, so a busy level reaches a steady state with no allocator traffic at all; nodes sit in contiguous memory, and there's no Rc/RefCell overhead. The lookup map is FxHashMap<OrderId, NodeIndex> (rustc-hash — a much cheaper hash than SipHash for trusted keys, used throughout the project). This is the implementation the server binary runs.

	add	cancel by id	modify by id	pop front	memory profile
SlowPriceLevel	O(1)*	O(n)	O(n)	O(1)	contiguous ring buffer
FastPriceLevel	O(1)	O(1)	O(1)	O(1)	per-node heap allocs, pointer chasing
SlabPriceLevel	O(1)*	O(1)	O(1)	O(1)	arena, slot reuse, index links

* amortized

3. Book storage

DefaultStorage (src/storage/default_storage.rs) keeps the two sides in ordered maps so the best price is always the first key:

bids: BTreeMap<Reverse<Price>, P>, // Reverse: highest bid first
asks: BTreeMap<Price, P>,          // lowest ask first
order_lookup: FxHashMap<OrderId, (Price, Side)>, // id -> where it rests

The Reverse<Price> trick gives both sides the same "best = first_key_value()" access pattern. The side-wide order_lookup map is what lets a cancel/modify jump straight to the right level without searching. The Storage trait also serves depth queries (get_depth) for snapshots, so alternative backends (e.g. a flat array of price buckets) could be dropped in without touching the book logic.

4. Matching engines: FIFO and pro-rata

Matching policy is deliberately decoupled from the data structures: a MatchingEngine (src/matching_engine/mod.rs) is handed one price level and a quantity, fills against it, and reports what happened. It also owns the priority rule for modifies (loses_priority).

FifoEngine (fifo.rs) — price-time priority: peel orders off the front of the queue, emitting a Fill per maker; the last maker touched may be partially filled in place.

ProRataEngine (pro_rata.rs) — size-proportional allocation, the policy used in many futures/options markets. Points of interest:

• Sweep fast path: if the incoming size covers the whole level, skip the math and drain the queue.
• Two-phase fill: a read-only pass computes every maker's share (incoming * maker_size / level_total, in u128 to dodge overflow), then a mutating pass applies them by id — sidestepping iterator-invalidation entirely.
• Remainder distribution: integer division under-allocates, so leftovers are handed out one contract at a time from the front (FIFO tiebreak), capped by each order's headroom.
• Scratch buffer reuse: the allocation table lives in a Vec owned by the engine and is clear()ed, not reallocated, on every fill.

5. Durability: the write-ahead log

src/wal/mod.rs is a small, generic, segmented WAL used by both the book and the ledger:

• Record format: [u32 big-endian length][bincode payload], where the payload is (timestamp_nanos, T) for any T: bincode::Encode.
• Segmented files: 1.log, 2.log, … in a directory; a segment rotates past 1 MiB (tracked with a byte-counting BufWriter wrapper, so no stat calls on the hot path).
• Flush policy: buffered writes with a periodic flush every 1 ms, plus flush-on-drop for clean shutdown — a deliberate latency/durability trade.
• Replay: a lazy iterator walks the sorted segments and decodes records one at a time; OrderBookBuilder::with_replay feeds them back through process_order_at(order, ts), reusing the original timestamps so recovery is deterministic. Encode buffers are reused across appends.

The WAL round-trip is tested by writing a real 10k-order fixture through the writer, reopening the directory, and asserting every (ts, order) pair replays byte-for-byte identical.

6. Accounts, escrow and settlement

src/accounts/mod.rs implements a minimal clearing ledger for a two-asset market (money vs shares). Each user holds four balances:

pub struct Balance {
    pub money_free: u64,   pub money_escrow: u64,
    pub shares_free: u64,  pub shares_escrow: u64,
}

The lifecycle mirrors a real exchange:

1. Authorize (read-only, before the book sees the order): does the user exist, do they have the free balance, do they own the order they're cancelling/modifying? Market buys are authorized against the current best price.
2. Escrow on accept: a resting bid locks size × price money; a resting ask locks size shares (free → escrow).
3. Settle on fill: for each Fill the maker's escrowed asset moves to the taker and payment flows back — both legs settled atomically on the engine thread.
4. Release on cancel/modify: escrow is returned or adjusted by the delta.

Accounts also maintains order_owner: OrderId → UserId (how a fill finds the maker to pay) and per-user open-order sets (served in user snapshots). Every mutation is expressed as an AccountCommand, appended to the accounts WAL, and replayed on startup — the same event-sourcing pattern as the book.

7. Concurrency model: the engine actor

src/engine/actor.rs is where the design commits to the classic exchange architecture: one thread owns everything, everyone else sends messages.

• spawn_engine_actor moves the OrderBook and Accounts onto a dedicated OS thread (lob-engine) that loops on blocking_recv — matching never touches the async runtime and never takes a lock.
• Axum handlers talk to it via a bounded mpsc channel (8192) of Commands, using try_send: if the engine falls behind, submission fails fast instead of queueing unboundedly — backpressure by construction. Request/response commands carry a oneshot reply channel.
• Each SubmitOrder runs the full pipeline atomically with respect to other commands: authorize → match → settle → publish. There is no window where the book and the ledger disagree.
• Market data out: the engine serializes each DepthDelta to JSON once, wraps it as Arc<Frame { seq, json: Bytes }>, and pushes it into a tokio::broadcast channel. A thousand WebSocket subscribers cost a thousand Arc clones, not a thousand serializations.
• Private events out: UserChannels (src/engine/user_events.rs) is a registry of per-user broadcast channels, created lazily on first subscribe, reference-counted, and removed when the last subscription drops — emitting to a user with no open socket is a no-op, so idle users cost nothing. Fills emit both legs: the maker gets role: Maker, the taker role: Taker, and every affected user receives a closing BalanceUpdated for that sequence number.

8. The network layer

src/server/ wires the engine to the outside world with axum:

• Auth (src/auth.rs): stateless HMAC-SHA256 signed tokens. POST /users returns base64url(user_id ‖ issued_at ‖ HMAC(payload)); an AuthedUser extractor verifies the signature (constant-time) and injects the UserId into handlers. Tokens ride in Authorization: Bearer … or, for WebSocket clients that can't set headers, ?token=….
• Two submission paths: POST /order awaits the engine's reply (you learn your order id / rejection synchronously); POST /order_faf is fire-and-forget — enqueue and return 202 immediately, 503 if the engine queue is full. Rejections still reach the user asynchronously as OrderRejected events on their private stream.
• Market WebSocket: on connect the handler subscribes first, then requests a snapshot — the ordering that guarantees no gap — sends the full DepthSnapshot, then streams deltas, discarding any with seq ≤ snapshot.seq (dedup instead of gap). A client that lags the broadcast buffer is disconnected (slow-consumer policy) and is expected to reconnect for a fresh snapshot. Idle sockets are reaped after 15 s without traffic.
• User WebSocket: same snapshot-then-delta pattern for private state — a UserSnapshot (balances + open orders + seq) followed by the live UserEvent stream.
• Ops: structured tracing with #[instrument] spans throughout; the server binary logs human-readable output to stdout and JSON to daily-rolling files in ./logs via a non-blocking appender; CORS configured for a local UI.

9. HTTP / WebSocket API

Orders use serde's externally-tagged enum encoding:

{"Limit":  {"price": 10000, "size": 10, "side": "Bid"}}
{"Market": {"size": 5, "side": "Ask"}}      // side = book side consumed: Ask ⇒ buy
{"Cancel": {"order_id": 42}}
{"Modify": {"order_id": 42, "new_size": 25}}

Endpoint	Auth	Description
POST /users	–	Create a user with demo balances; returns {user_id, token, …}
POST /order	Bearer	Submit and await the result; 202 + order id (or null for market orders), 4xx on rejection
POST /order_faf	Bearer	Fire-and-forget submit; 503 when the engine is saturated
GET /ws/market	–	Public depth: one DepthSnapshot, then DepthDelta frames
GET /ws/user?token=…	token	Private stream: one UserSnapshot, then UserEvents

# create a user, submit a resting bid, then lift the ask side
TOKEN=$(curl -s -X POST localhost:3001/users | jq -r .token)

curl -s -X POST localhost:3001/order \
  -H "Authorization: Bearer $TOKEN" -H 'Content-Type: application/json' \
  -d '{"Limit":{"price":10000,"size":10,"side":"Bid"}}'

curl -s -X POST localhost:3001/order \
  -H "Authorization: Bearer $TOKEN" -H 'Content-Type: application/json' \
  -d '{"Market":{"size":3,"side":"Bid"}}'   # consumes bid liquidity (a sell)

Sample private stream after a fill:

{"type":"Fill","seq":7,"order_id":3,"price":10000,"qty":3,"side":"Bid","role":"Maker"}
{"type":"BalanceUpdated","seq":7,"balance":{"money_free":970000,"money_escrow":70000,"shares_free":1000003,"shares_escrow":0}}

10. Benchmarks

Criterion benchmarks (benches/lob_bench.rs) replay pre-generated order flow through a fresh book and compare all three price-level implementations on two workload shapes:

• Mixed flow (generate_orderflow.py): a mean-reverting random walk around a mid price, ~60% limits / 15% markets / 15% cancels / 10% modifies, log-normal sizes, depth spread over ~40 ticks — a "normal market" where levels stay shallow.
• Single-level stress (generate_single_level.py): seed up to 200k limit orders within ±2 ticks of one focal price, then hammer that level with 40% cancels / 25% modifies / 20% markets / 15% limits. This is the adversarial case for the VecDeque baseline: cancels by id in the middle of a deep queue.

python3 generate_orderflow.py 1000000 data/bench_orders_1M.json
cargo bench

Measured results, 50k-operation datasets on an Apple M5 Pro (mean whole-dataset replay time, lower is better):

workload	SlowPriceLevel	FastPriceLevel	SlabPriceLevel
mixed flow, 50k ops	5.43 ms	5.51 ms	4.95 ms
single-level stress, 50k ops	5.62 ms	3.66 ms	3.41 ms (~68 ns/op)

The results make the trade-offs concrete:

• On mixed flow the naive VecDeque baseline is not slow — levels stay shallow, so its O(n) cancel scans a handful of elements in contiguous memory, and it actually edges out the Rc<RefCell> linked list, which pays allocation and pointer-chasing costs on every operation without deep queues to amortize them.
• On the single-level stress test the O(1) structures win decisively (~1.6×), because cancels and modifies land in the middle of a queue thousands of orders deep.
• The slab arena beats the Rc list on both workloads — same asymptotics, better memory layout and no per-node allocation.

In short: asymptotics start mattering when queues get deep, and memory layout matters everywhere. Making that visible is the main thing this project was built for.

11. Testing

cargo test runs the full suite (66 tests):

• Per-implementation level tests: all three price levels pass an identical battery — cancel front/middle/back, modify with and without reprioritization, total_contracts consistency through mixed operation sequences, zero-size and duplicate-id rejections.
• Property-based tests (proptest): total_contracts equals the sum of random order sizes for arbitrary insert sequences.
• Memory-safety tests: the Rc-based linked list is checked for leaks by downgrading node handles to Weak and asserting they fail to upgrade after every pop/remove path — proving no Rc cycle survives.
• Book-level integration tests: market orders sweeping multiple levels, partial fills, base-info (best bid/ask/spread) maintenance, and the priority semantics of modify (size-down keeps queue position and is filled first; size-up loses it).
• WAL round-trip: a real 10k-order fixture written, reopened, and replayed record-for-record.

12. Running it

cargo test                    # full test suite
cargo bench                   # criterion comparison of the three price levels

cargo run --release --bin lob-server   # HTTP/WS gateway on 0.0.0.0:3001
# WALs land in ./book_wallog and ./accounts_wallog and are replayed on restart —
# kill the server, start it again, and the book + balances come back.

cargo run --release --bin lob data/bench_orders_50k.json  # offline replay of a JSON order-flow file

13. Project layout

src/
├── core/                 # domain types: Price, Side, Order, OrderUpdate, Ack, depth types
├── order_book.rs         # OrderBook<S, M>: validation, sequencing, WAL hook, builder
├── price_level/
│   ├── slow_price_level/ # VecDeque + HashSet baseline (O(n) cancel)
│   ├── fast_price_level/ # Rc<RefCell> doubly-linked list + id→node map (O(1))
│   └── slab_price_level/ # slab-arena linked list, index links (O(1), default)
├── storage/              # Storage trait + BTreeMap-based DefaultStorage
├── matching_engine/      # MatchingEngine trait, FifoEngine, ProRataEngine
├── wal/                  # segmented length-prefixed bincode WAL: writer, reader, replay
├── accounts/             # balances, escrow, authorization, settlement, accounts WAL
├── engine/               # engine actor thread, Command/EngineHandle, per-user channels
├── server/               # axum router, handlers (REST + WS), app state
├── auth.rs               # HMAC-SHA256 token signing/verification, AuthedUser extractor
└── bin/
    ├── lob-server.rs     # full server: WAL replay + accounts + gateway
    └── lob.rs            # offline order-flow replayer
benches/lob_bench.rs      # criterion: 3 price levels × 2 workload shapes × N sizes
generate_orderflow.py     # mixed-market dataset generator
generate_single_level.py  # single-level stress dataset generator

14. Known limitations & future work

Deliberate simplifications, in the spirit of keeping the learning surface honest:

• Crossing limit orders are rejected, not matched — the book is maker-only and all taking happens via market orders. Supporting marketable limits (match the crossing part, rest the remainder) is the natural next step.
• Single instrument — there is no symbol dimension; scaling out would mean one engine actor per instrument.
• Market-order authorization uses the best price only, so a sweep through deeper, worse-priced levels can exceed the amount pre-authorized (fine for a bid sweep where price only improves the buyer; imprecise for the general case).
• FastPriceLevel::iter() is a stub (returns an empty iterator), so the pro-rata engine — which iterates a level — should be paired with the slab or slow implementations.
• WAL flushes are buffered, not fsync'd — durability is "flushed to the OS every millisecond", not power-loss-proof.
• Auth tokens never expire and there is no rate limiting; auth here demonstrates the stateless-HMAC pattern, not a hardened perimeter.
• Prices and balances are plain u64 ticks — no fixed-point/decimal layer.