XRPL Weakness 1 — online_delete is a stop-the-world copying GC + generational NodeStore design

generational-nodestore-design.md

Design: generational (N-segment) NodeStore for online_delete

Concrete implementation design for the fix in online-delete-generational-gc.md. Target: Transia-RnD/rippled, branch dangell7/online-delete-generational-gc (own work off develop).

Problem restated (one paragraph)

Today DatabaseRotating keeps two append-only backends (writable + archive). Every deleteInterval_ ledgers, SHAMapStoreImp::run() walks the entire current state (visitNodes(copyNode)) and re-stores every live node into a fresh writable backend, then drops the old archive. Because the writable is recreated each rotation, the whole live set is re-written every cycle → O(state) stores per rotation, growing without bound → the AcceptLedger stall / the 20–25M cliff. The store (write) side dominates (~5.4 GB written per rotation observed at 1.3M).

Core idea

Replace the 2-backend copy-and-swap with a ring of N append-only generations. New nodes append to the newest generation and stay there — we stop re-storing the whole live set every rotation. A generation is dropped only once it holds no live nodes; the few cold survivors are evacuated forward first. Amortized store cost per rotation drops from O(live) to ≈ O(live / N) (a cold node is re-stored once per N rotations, not every rotation). N is a tunable disk⇄copy tradeoff.

Data model

• generations_: ordered std::deque<Gen> from oldest → newest. Each Gen = one NodeStore::Backend (a NuDB dir rippledb.gNNNNN) + metadata {firstLedger, sealed}.
• Writable = generations_.back(). All store() goes here.
• Reads: fetchNodeObject searches generations_ newest→oldest; first hit wins (a node lives in the generation where first written). Same "search then optionally duplicate" contract as today, generalized from 2 to N.
• Invariant: content-addressed + immutable nodes ⇒ a hash resides in exactly one generation at a time (may be re-stored into a newer gen during evacuation, after which the old copy is droppable).

Generation lifecycle (driven by SHAMapStoreImp::run() per validated ledger)

1. Advance (seal + open): at each rotation cadence (validatedSeq >= lastRotated + deleteInterval_, plus the existing canDelete_/healthWait gates), seal the current writable (mark read-only) and open a fresh writable generation. Cheap, O(1). Each sealed gen ≈ one interval's new nodes.
2. Retire (the GC): while generations_.size() > N, retire the oldest gen:
   • Evacuate its live survivors. Walk the current validated state map (visitNodes). For each node, if it resides in the oldest gen (fetch finds it there and not in a newer gen), store() it into the writable gen. Dead nodes are never visited (not in current state); nodes already in newer gens are skipped. Copy set = cold survivors of the oldest gen only, not the whole live set.
   • Drop the gen: setDeletePath() + close/destroy the backend → physical file removal.
   • freshenCaches() / clearCaches() around the drop so TreeNodeCache / FullBelowCache never reference a removed backend (preserve today's cache invariants; just generalized).
3. SQL side unchanged: clearPrior()/clearSql() (Transactions/AccountTransactions batched + backOff_) is independent of the NodeStore ring; keep as-is.

Why this kills both problems

• Cliff: per-rotation stores ≈ live/N and, more importantly, do not require re-storing the whole live set — a cold account node is touched once per N rotations. Tune N up as accounts grow.
• Stall: the evacuation copy set is a small fraction, so the I/O burst against AcceptLedger shrinks by ~N even before incrementalizing.

v1 → v2

• v1 (this PR): retire on cadence with the full-state walk to find survivors (O(live) reads, mostly cache-served; O(survivors) writes). Correct + big win on the write/I/O side that causes the stall. Gate with healthWait exactly as today.
• v2 (follow-on): make evacuation incremental — a resumable state-walk cursor advancing a sliver per ledger across the interval, so even the O(live) read-walk is spread out and per-ledger overhead is tiny/constant. And add per-generation liveness hints to avoid the full walk entirely.

State persistence (must-get-right)

SavedState today stores {writableDb, archiveDb, lastRotated}. Generalize to persist the ordered list of generation dir names + which is writable + lastRotated, so on restart the node re-opens the whole ring in order. Back-compat: a 2-name legacy state loads as a 2-gen ring. This is the highest-risk correctness area (a wrong ring on restart = missing nodes) → dedicated tests.

Integration points (to confirm from the 3 code-maps in flight)

• DatabaseRotating / DatabaseRotatingImp: 2 backends → deque of N; generalize fetchNodeObject routing and replace rotate(newBackend, callback) with advance() (seal+open) and retireOldest().
• Backend / NuDB: need create/open/close/setDeletePath(physical delete)/for_each; confirm N simultaneous backends' fd + memory cost (fdRequired) is acceptable (bounds N).
• SHAMapStoreImp::run(): swap the copy-and-rotate block for advance()+retireOldest()+evacuate.
• Caches: preserve freshenCaches/clearCaches semantics around a drop.
• SavedStateDB: persist/restore the ring.

Config

• online_delete (unchanged): rotation cadence.
• New: online_delete_generations (N, default e.g. 8) — the ring depth / disk⇄copy knob. Larger N = less copying, more transient disk. Validate the sweet spot on the rig.

Concrete API (pieces 2+3 — land together so it compiles)

DatabaseRotating / DatabaseRotatingImp

• Members: replace writableBackend_ + archiveBackend_ with std::deque<std::shared_ptr<Backend>> generations_ (front = oldest, back = writable) + a std::shared_ptr<Backend> retiring_ (the gen currently being evacuated, or null).
• store/sync/getName/getWriteLoad/importDatabase → generations_.back() (writable).
• fetchNodeObject: snapshot the deque under lock; probe back → front, first hit wins. Copy-forward is scoped to retiring_: on a hit, copy the node into the writable backend iff duplicate AND the hit came from retiring_ (or the existing rotationInFlight_ window). Hits from other sealed gens are NOT copied — that is the whole O(churn) win (we never re-store gens 1..N-2's live nodes, only the retiring gen's survivors).
• forEach: iterate all generations_.
• Replace rotate(newBackend, f2) with:
  • advance(std::unique_ptr<Backend>&& newWritable, RingPersist const& persist) — push newWritable to back(); the prior writable stays in the deque as a sealed read-only gen. Persist the ring.
  • beginRetire() / endRetire() — set/clear retiring_ = generations_.front() around the SHAMapStore evacuation walk (enables the scoped copy-forward).
  • retireOldest(RingPersist const& persist) — front()->setDeletePath(), hold it past the callback, pop_front(), persist the (now shorter) ring; the held shared_ptr's destruction deletes the dir after persistence (same deferred-delete safety as today's rotate()).
  • RingPersist = std::function<void(std::vector<std::string> const& ringNames /*oldest→newest*/)>.
  • std::size_t generationCount() const;
• Ctor: take std::vector<std::shared_ptr<Backend>> (the opened ring) instead of the two backends; sum fdRequired() over all.

SHAMapStoreImp::run() rotation body (replaces the copy+rotate block)

When readyToRotate:

1. clearPrior(lastRotated) — unchanged (SQL side).
2. advance(makeBackendRotating(), persistRing) — seal current writable, open a fresh empty one.
3. If dbRotating_->generationCount() > N: a. beginRetire() (RAII guard, like the existing RotationExposureGuard). b. visitNodes(copyNode) over the validated state — unchanged call, but now copy-forward is scoped to the retiring gen, so only its survivors are stored to writable (O(churn), not O(state)). c. freshenCaches() — still needed, but now only nodes living in the retiring gen get re-stored (the freshenCache fetchNodeObject(duplicate=true) hits the scoped copy-forward). d. clearCaches(validatedSeq) — unchanged (invalidate FullBelow/ledger caches before the drop). e. retireOldest(persistRing); endRetire().
4. lastRotated = validatedSeq.

• persistRing = lambda writing SavedState{ generations=ringNames, writableDb=ringNames.back(), archiveDb=ringNames.front(), lastRotated } via stateDb_.setState(...).

makeNodeStore / dbPaths (open + keep N)

• makeNodeStore: read state.generations; if empty on first run, create the initial ring (2 gens: an empty writable + it as the sole archive, matching today's bootstrap) and persist. Open each generation via makeBackendRotating(name); pass the vector to the ctor.
• dbPaths(): change "delete anything not writableDb/archiveDb, corrupt unless exactly two" to "keep every dir named in state.generations, delete the rest; corrupt unless all N exist."

Config

• Keys::kOnlineDeleteGenerations = "online_delete_generations", parsed in the ctor when deleteInterval_ != 0; member std::uint32_t generations_ = 8; (min 2). N is the disk⇄copy knob.

Validation on the perf rig (the proof)

Reproduced already: rotation cost 5s→85s and AcceptLedger 19s stalls as accounts grew to 1.3M. After this: rotation finished−started duration and evacuation node-count should be flat vs account count (≈ per-interval churn, not total state), and the AcceptLedger multi-second stalls should vanish. Overlay the before/after rotation-cost-vs-accounts curve — that's the deliverable proof.

online-delete-generational-gc.md

Moonshot: online_delete is a stop-the-world copying GC — make it generational

Status: proposal / evidence gathered on the perf network (2026-08-01) Implementation home: Transia-RnD/rippled worktree ~/projects/xrplf/xrpld-online-delete-gc, branch dangell7/online-delete-generational-gc off Transia develop (synced, clean). We build our own collector here — decided against basing on XRPLF ximinez/online-delete-gaps (Ed Hennis' correctness rework) because it's ~268 commits divergent from Transia and too out of sync to build on cleanly. His work is orthogonal anyway (correctness: missingFromCompleteLedgerRange, healthWait deadlock, node-rescue) and Transia develop already carries the rescue logic; we can reconcile later.

Decision: drop the throttle stopgap (PR-1) entirely — only the best solution. The single deliverable is the incremental/generational collector below. Origin: the "XRPL falls over at 20–25M accounts" stress campaign (plan-11c/11d). This is Weakness #1 found by growing a real 5-validator network under sustained live account creation. One-line: online_delete reclaims NodeStore space by copying the entire live state to a fresh NuDB file every deleteInterval ledgers — an O(total-state) operation that runs forever, every cycle, stalls ledger acceptance, and eventually exceeds the rotation interval. That cliff — not memory — is the likely real "20–25M wall." Fix the collector, not the backend.

What online_delete is (the purpose)

The NodeStore is an immutable, content-addressed object store: SHAMap nodes keyed by hash, write-once, never mutated. online_delete is garbage collection — reclaim nodes that no retained ledger (last ledger_history) references, to bound on-disk size. NuDB is append-only (its strength: crash-safe, simple), so it has no in-place delete; reclamation is done by copy-and-swap: copy the live set to a new file, drop the old.

The bug (precisely)

SHAMapStoreImp::run() (src/xrpld/app/misc/SHAMapStoreImp.cpp:312–382), every deleteInterval_ (256) ledgers:

validatedLedger->stateMap().snapShot(false)->visitNodes(   // walk the WHOLE state tree
    std::bind(&SHAMapStoreImp::copyNode, ...));             // copy every node old→new  (:333, :254)
... freshenCaches(); makeBackendRotating(); dbRotating_->rotate(newBackend, ...);

copyNode (:254) fetches each node and duplicates it into the new backend. This is a naïve semi-space copying collector: it copies the entire live set into fresh space and discards the old.

The fatal property: it re-copies the unchanged long-lived account state every cycle. Per-interval churn is a few hundred-k nodes; it copies all ~2M+. Cost is O(total state), every rotation, forever — and it grows without bound as accounts grow.

Secondary: the copy's bulk NuDB I/O contends with AcceptLedger's writes, so ledger acceptance stalls for many seconds (the consensus-liveness symptom). healthWait() (:623) then correctly pauses pruning on the now-unhealthy node, stretching a rotation to tens of minutes.

The evidence (perf net: 5× n2-highmem-16, online_delete=256, ~325 TPS live creation)

Rotation start→finish and nodes copied, from one validator's debug.log:

rotation (validatedSeq)	nodes copied	duration
513 (~0.2M accts)	—	5 s
769	—	52 s
1025	—	61 s
1281 (~1.2M)	1,565,711	21 min (rotation ran through a liveness collapse)
1591	1,745,551	88 s
1847 (~1.3M)	2,168,912	82 s

During the seq-1281 rotation (16:03→16:24): AcceptLedger jobs hit 19,561 ms, converge_time spiked to 19 s, validators spammed Need validated ledger for preferred ledger analysis (RCLValidations.cpp:131), and the network's liveness stalled (soak wedged at 1.24M). 0 LoadMonitor CPU-saturation during it — this is I/O/algorithmic, not compute. This happened on 16-core validators, so it is independent of the earlier 8-core CPU-saturation fork (Weakness #0).

The cliff: rotations fire ~every 15 min; the copy already takes ~85 s at 1.3M copying ~2.2M nodes, and both grow ~linearly with accounts. Rotation time crosses the whole interval in the tens-of-millions range → the node is permanently rotating → cannot stay synced. This is a far more likely explanation of Ripple's "20–25M fall over" than memory (their study ran online_delete OFF, so they never hit this; real validators run it ON and will).

Why the obvious fixes are wrong

• Switch to RocksDB — trades copy-stalls for compaction-stalls + tuning burden (well-documented operator complaints). It swaps the backend to dodge the algorithm; keep NuDB.
• Bigger deleteInterval / disable online_delete — config dodge. Per-rotation work still grows O(state); just rarer or unbounded disk. Not a fix.

The right fix: generational, incremental GC on NuDB

Keep NuDB append-only (crash-safety, simplicity). Fix the collector. Because nodes are immutable and content-addressed, generational GC fits exactly:

• Segment the NodeStore into time-ordered append-only NuDB generations; new nodes append to the current generation.
• Young generations are mostly garbage (transient inner nodes of recent txns) → once no retained ledger references a generation, drop the whole file, O(1), zero copy.
• Evacuate only the small "cold survivor" set when an old generation is finally retired — a long-lived account node is copied forward once per generation lifetime, not once per rotation.
• Result: rotation cost O(churn + cold-promotion), flat vs account count. The cliff disappears.

This is standard generational-GC theory applied to the one place rippled has a copying collector.

Staged delivery (not one giant risky PR)

1. PR-1 — stop the bleeding (small, low-risk): make the existing visitNodes(copyNode) copy incremental across the interval + I/O-throttled (it already checks healthWait every checkHealthInterval_ nodes — extend that to a paced, budgeted copy). Eliminates the AcceptLedger stall / liveness collapse immediately. Still O(state) total, but no burst. Ships fast.
2. PR-2 — the cure (moonshot): generational segmented NodeStore + wholesale young-segment drop + cold-survivor evacuation. O(churn) rotation. The real scalability fix.
3. Validate on this rig: reproduce the cliff (done), apply PR-1 → stalls vanish, apply PR-2 → rotation cost flat vs accounts → then push the growth soak to 25M and proceed to the IOU/MPT phase.

Reproduction

5× n2-highmem-16 validators, online_delete=256, live account creation at a few hundred TPS (loadtester creation.soak). Watch SHAMapStore:WRN rotating/finished rotation durations and LoadMonitor:WRN Job: AcceptLedger run: — both climb with account count; rotations coincide with AcceptLedger multi-second stalls and converge spikes. Full capture per plan-11d.

Code touchpoints

• src/xrpld/app/misc/SHAMapStoreImp.cpp — run() rotate loop (:312), copyNode (:254), healthWait (:623), clearPrior/clearCaches/freshenCaches.
• src/xrpld/nodestore/ — DatabaseRotating / backend rotation; NuDB backend.
• Symptom sources: RCLValidations.cpp:131 (Need validated ledger), LoadMonitor job timing.