Goal: for every active orderbook (and AMM-augmented book), maintain a sticky pointer to the keylet of the best-quality directory page. The path engine reads the top of book by dereferencing one pointer instead of issuing a SHAMap succ() from the book's base keylet.
Scope: a single, narrow optimization at the orderbook semantic layer. Composes with Plan 6 (flat state lookup) — they sit at different layers and stack. No protocol change, no amendment, no consensus impact.
BookTip::step() is the inner loop of offer crossing and pathfinding. The first call after construction does:
// src/libxrpl/tx/paths/BookTip.cpp:29
auto const first_page = view_.succ(m_book, m_end);view_.succ() walks the state index from m_book (the book's base keylet) forward until it finds the next key under m_end — i.e. the directory page holding the best-quality offers for that book. Under SHAMap that is a Merkle-trie successor walk: descend, scan branch arrays for the next populated branch, possibly recurse, fetch each inner node (spinlocked, possibly NodeStore-backed), and eventually emerge with the keylet of the first directory page.
The dominant access pattern for that call is:
- Pathfinder probes — "what's the best price on book X right now?" Called on every payment, every AMM/CLOB interleave decision, every path scoring loop. Hundreds to thousands of times per Payment.
- Offer-crossing first step — every cross opens with one
succ()to find the best page. - RPC
book_offers— first page is the entry point for every page-by-page fetch.
The dominant result of that call is the same keylet, over and over, because the best directory page only changes when an offer at-or-better than the current best is added, or the current best's last offer is removed. For a typical liquid book that change rate is far lower than the read rate.
Plan 6 turns each succ() step's inner-node lookups into hash-map finds. That's a real lift — but it's still a successor walk. The top-of-book cache eliminates the walk: best-price becomes a single pointer dereference.
For each Book, maintain:
struct TopOfBook {
std::optional<uint256> firstPageKey; // keylet of best-quality dir page; std::nullopt = book empty
Quality bestQuality; // cached for fast comparisons on insert
LedgerIndex asOfLedger; // for staleness / debugging
};Owned by a per-ledger cache:
flat_hash_map<Book, TopOfBook> topOfBook_; // keyed by Book (canonicalized currency pair)BookTip::step()'s first iteration becomes:
if (auto const& top = view_.topOfBook(book); top && top->firstPageKey) {
first_page = *top->firstPageKey;
} else {
first_page = view_.succ(m_book, m_end); // fallback / cold path
view_.recordTopOfBook(book, first_page);
}Subsequent iterations (walking past the best page into worse-quality pages) keep using succ() — the cache is only for the first page. That's where the win is; deeper pages are read once per cross and are not hot.
The cache is dirtied by exactly four events on the apply path:
| Event | Action |
|---|---|
Offer inserted at quality ≥ cached bestQuality (or book was empty) |
Update firstPageKey and bestQuality from the new offer's directory page |
Offer inserted at quality < cached bestQuality |
No-op (new offer isn't the new top) |
| Offer removed and it was not the last offer on the best page | No-op (best page still has offers) |
| Offer removed and it was the last offer on the best page | Invalidate; next read repopulates via one succ() |
The "did this empty the best page" check is one read of the directory page's Indexes field, which we already do at offer deletion time. No extra structural walk.
This is the key correctness property: the only writes that can change the top of book are offer insertions and the deletion of the last offer on the current best page. Everything else is an O(1) bestQuality comparison and skip.
AMM pools synthesize a virtual offer at the pool's current spot quality. When a CLOB book has an AMM pool attached, BookStep interleaves CLOB offers and AMM quotes. Two options:
Option A (preferred): the top-of-book cache stores only the CLOB best page. AMM spot quality is computed cheaply from the AMM SLE on demand (already O(1) once Plan 6 lands). BookStep compares cached CLOB top vs. fresh AMM spot. AMM-pool state changes don't invalidate the CLOB cache.
Option B: cache (clob_top, amm_spot) together. Faster reads, but every AMM deposit/withdraw/swap invalidates the cache — and AMM mutations are common. Net loss.
Go with A. The win is on the CLOB side because the CLOB top doesn't move on every tx.
The cache lives on the ledger view, mirroring Plan 6's overlay model:
- Open ledger: mutable
topOfBook_map. Maintained inline as offers are inserted/deleted. - Closed ledger: immutable snapshot of
topOfBook_swapped in atomically at close. RPC and pathfinder reads against a closed ledger see the frozen map. - Eviction: entry is dropped when the book is empty and hasn't been read in N seconds (cheap LRU). Re-populated lazily on next read.
The map is small. Mainnet has on the order of low-thousands of active CLOB books at any time. At ~80 bytes per entry that's well under 1 MB — negligible against the existing memory budget.
- P8.1 Add
TopOfBookCache(src/libxrpl/ledger/TopOfBookCache.{h,cpp}).flat_hash_map<Book, TopOfBook>. Open-ledger overlay + closed-ledger immutable base, mirroring Plan 6's Option D shape. - P8.2 Add
ReadView::topOfBook(Book const&) constand the matchingApplyView::recordTopOfBook(). Default implementation is a no-op so non-orderbook code is unaffected. - P8.3 Wire
BookTip::step()to consult the cache before callingview_.succ(). On cache miss, populate after thesucc()returns. Behavior must be byte-identical with the cache disabled vs. enabled.
- P8.4 In the offer-insert path (AMMCreate, OfferCreate, OfferReplace), after the new offer's directory page is known, do the quality comparison and update cache if the new offer is at-or-better.
- P8.5 In the offer-delete path (offerDelete, expired-offer sweep, crossing consumption), detect whether the deleted offer was the last entry on the current top page. If so, invalidate the cache entry; next read repopulates.
- P8.6 Cover the indirect paths that also produce offer deletions:
BookTip::step()'s ownofferDelete(line 19),cancelOffer, owner-deletion cascades.
- P8.7 Differential CI gate: in debug builds, every
topOfBook()hit is shadow-verified against a freshview_.succ(book_base, quality_next)call. Assert byte-identicalfirstPageKey. Same pattern as Plan 6's P6.5 — divergence is a bug, not a fallback. - P8.8 Replay-test against the mainnet replay corpus. Every offer-crossing and pathfinder probe in the corpus must produce the same top-of-book result with the cache as without.
- P8.9 Property test: random sequences of
OfferCreate/OfferCancel/ consumed crosses against a synthetic book. After each operation, cache state matches a from-scratchsucc()walk.
- P8.10 Counters: cache hits, cache misses, invalidations per ledger, populated-book count. Exposed via the existing
server_infocounters block. - P8.11 Devnet/testnet measurement: pathfinder p50/p99 latency, offer-crossing throughput. Expected: best-price probe cost drops from ~6–10 inner-node touches to one pointer dereference; pathfinder overall improves by the fraction of its time spent in
succ()(workload-dependent — initial estimate is meaningful but not dominant).
- P8.12 Config gate
top_of_book_cache = enabled(default true). Operators with abnormal workloads can disable. Cache is purely auxiliary so this is a safe knob.
These compose cleanly because they sit at different layers:
| Layer | Plan 6 | Plan 8 |
|---|---|---|
| State storage | SHAMap descent → O(1) flat-map find | unchanged |
| Orderbook semantic | unchanged (succ() from book base) |
best-page keylet served from cache, zero traversal |
A best-price probe with both:
- Plan 8 cache hit → keylet in hand (one pointer deref).
- Plan 6 → that keylet's directory SLE in hand (one hash-map find).
- Read first offer's keylet from the directory's
Indexesfield. - Plan 6 → that offer SLE in hand (one hash-map find).
Three hash/pointer operations, zero descents, zero traversal.
The cache's invalidation writes (cache update on offer insert/delete) are independent of Plan 6's flat-map dual-write. They're both on the same apply path and both cheap; there's no shared mutable state between them and no ordering constraint.
If Plan 6 ships first (recommended), Plan 8 is a small additive layer on top. If Plan 8 ships first, Plan 6 still composes — Plan 8's hit path skips Plan 6's lookup for the first page, and its miss path uses Plan 6's faster succ().
- Missed invalidation. The hard case is "an offer was inserted at a better quality but the cache wasn't updated." Mitigation: the differential CI gate (P8.7) catches this on every read in debug, and the invalidation logic sits in exactly two spots (offer insert, offer delete) — both audited.
- Concurrent invalidation under parallel apply (Plan 1 territory). Mitigation: under Plan 1, per-worker overlays for the top-of-book cache, merged deterministically at end of round, identical to Plan 1 / Plan 6's overlay model. Workers with disjoint access sets cannot both be writing the same
Bookentry. - Cache for the wrong ledger.
ReadView::topOfBook()must return the cache associated with that view's ledger, not the open ledger's working copy. Mitigation: cache is owned by the view (same lifetime as the view's SHAMap pointer), not a global.
- Cold-start cost. A node just-restarted has an empty cache. First read on each book pays a normal
succ()(with Plan 6, this is still cheap). Cache warms naturally; no eager populate needed. - Pathological invalidation. A book where the best price churns every transaction would see one invalidation per tx and gain little. Mitigation: even in that case, the cache adds at most one comparison and one optional write per offer event — its cost is bounded; it never makes the system slower than baseline.
- Config knob exists for a reason. If a workload exposes a bug in invalidation logic, operators can disable the cache and fall back to
succ()without restarting. Same shape as Plan 6's operator config.
- Not a price-time-priority cache. It does not cache the offer entries themselves — only the keylet of the best directory page. Walking the page's
Indexesarray still produces offers in protocol-defined order. - Not a multi-page cache. Only the top page is cached. Deeper pages are touched once per cross and aren't hot. A page-N cache would add complexity (more invalidation triggers) for negligible gain.
- Not a quality-bitmap. That's a separate idea with worse cost/benefit (see throughput-audit.md). The top-of-book cache wins on the same dominant operation with cheaper maintenance and no dead-bit memory.
- Best place for the cache to live. Candidates:
OpenLedger,Ledger, or alongsideFlatStateMap(Plan 6). Probably the same place Plan 6 lives so the lifecycle is shared. - Eviction policy. Pure LRU vs. "never evict while populated" vs. fixed-size cap. Mainnet's book count is small enough that "never evict" is probably fine — verify in Phase 4.
- Cross-ledger sharing. Most books' top doesn't change ledger-to-ledger. Worth structural-sharing the cache across closed-ledger snapshots (HAMT-style)? Defer until Phase 4 measurement justifies it.
- Phase 1+2 (2 weeks) — structure, wiring, invalidation. Lands behind
top_of_book_cache = falsedefault so it's exercised in tests but not in production. - Phase 3 (1 week) — validation gate. Flip default to true once differential gate is clean across the replay corpus.
- Phase 4 (overlap rollout) — metrics, devnet/testnet measurement.
Total: ~3–4 weeks of focused work. Single-developer-sized. No protocol risk; ships independently of Plan 6, composes with it, and replaces no existing functionality.