# Order Book Fast Storage (Arena + Ladder)

This document describes the internal storage overhaul for `TwoRunnerBook` and `MultiRunnerBook`.

## Goals

- **Fast cancels/replaces** under bursty load (e.g., live price shocks).
- **Deterministic matching** given a strictly serialized command/event stream.
- **Betfair ladder aware**: fixed 350-tick ladder storage.
- Keep the **public/event-sourced API unchanged** (commands/events; deterministic output).

## Core Idea

Replace the “map of large values + per-price `VecDeque<OrderId>`” layout with:

- An **arena** of orders (`slab`) addressed by small integer keys.
- A fast `OrderId -> key` index for O(1) lookups.
- A **fixed-size tick ladder** (`[Level; 350]`) per runner per side.
- An **intrusive FIFO** per price level (O(1) unlink on cancel/replace).

The implementation lives in `src/book/common/fast.rs` and is used by:

- `src/book/multi_runner.rs`
- `src/book/two_runner.rs`

## Data Structures

### `OrderStore`

Stores `BookOrder` in a `slab::Slab` and maintains:

- `by_id: hashbrown::HashMap<OrderId, OrderKey>` for hot-path lookups.
- `by_id_sorted: BTreeMap<OrderId, OrderKey>` for deterministic iteration and stable snapshots.

`OrderStore` implements `Serialize/Deserialize` as a `BTreeMap<OrderId, BookOrder>` so JSON snapshots
stay stable and deterministic.

### Ladder + Levels

Each runner has a `RunnerBook` with two `SideBook`s (`Back`, `Lay`):

- `levels: [Level; 350]`
- A compact bitset (`Bitset350`) tracking which ticks are non-empty (fast best-price scan).
- `Bitset350::set/clear` safely ignore out-of-range indices (defensive against malformed tick access paths).

Each `Level` stores:

- `head/tail: Option<OrderKey>` of an intrusive linked list
- `total_remaining: Money` used for depth queries and quick liquidity checks

### Intrusive FIFO Links

Each order slot stores `prev/next` pointers so we can:

- Append at tail on placement/remainder insertion
- Unlink in O(1) on cancel/replace/full fill

## Determinism

Determinism requirements are satisfied by:

- **Matching priority** remains: price priority + FIFO within a price level.
- Multi-event commands that scan all orders (`CloseMarket`, `SetMarketPhase`, `RemoveRunner`, etc.)
  use `OrderStore::iter_sorted()` to emit events in deterministic `OrderId` order (matching the
  old `BTreeMap` behavior).

## Snapshots / Serialization

`TwoRunnerBook` and `MultiRunnerBook` now use explicit snapshot structs (see
`TwoRunnerBookSnapshot` and `MultiRunnerBookSnapshot`) and rebuild derived caches on load:

- The ladder structures (`runner_books`) are treated as **derived caches**.
- On `Deserialize`, `rebuild_ladders()` reconstructs per-level FIFO order using:
  - `created_at` (primary)
  - `order_id` (tie-breaker)

This ensures that after a snapshot restore, FIFO ordering is consistent and deterministic.

## Complexity / Performance Notes

- **Cancel**: O(1) average to find the order (`HashMap`), O(1) to unlink from the level (intrusive).
- **Best price queries**: use a bitset to skip empty ticks.
- **Matching iteration**:
  - `MultiRunnerBook`: traverses only non-empty ticks in the matchable range.
  - `TwoRunnerBook`: still builds a temporary matchable list for implied matching, but reads FIFO
    queues via intrusive iteration rather than `VecDeque<OrderId>`.

## Follow-ups (Expected Next Steps)

- Tune `Config.order_store_capacity` (default: 20,000) based on expected live order volume.
- Add targeted micro-benchmarks for:
  - cancel storms
  - sustained matching throughput
  - replace storms
- Consider moving more “cold” per-order fields out of the hot path (hot/cold split).
- Consider a dedicated “trade store” optimized for `VoidTradesFromTime` queries if needed.
