data: storage file access latencies with different values of btree's M

[sudeepdino008]

Summary

State domain reads (GetLatest over .kv snapshots) are dominated by kv touches — the binary search into the .kv at .bt pivot offsets. The accessor's M (pivot density, default 256) sets the cold probe count (≈ log₂ M). Lower values of M produce narrower ranges to search in the kv file and leads to smaller number of potentially cold touches.

This task tries different M-value for the btree and records cold/warm access and bt sizes for M=256(default), 64, 16

Storage domain — .bt size & btnav latency per M

.kv file	steps	.kv size	M256 bt / cold / warm	M64 bt / cold / warm	M16 bt / cold / warm
0-8192	8192	71 GB	1.74 GB / 172 µs / 5 µs	2.80 GB / 111 µs / 3 µs	7.02 GB / 93 µs / 3 µs
8704-8960	256	2.4 GB	68 MB / 160 µs / 3 µs	110 MB / 108 µs / 2 µs	278 MB / 89 µs / 2 µs
8960-9088	128	1.5 GB	42 MB / 161 µs / 3 µs	68 MB / 107 µs / 2 µs	172 MB / 95 µs / 2 µs
9088-9120	32	466 MB	12.6 MB / 157 µs / 2 µs	20 MB / 106 µs / 2 µs	51 MB / 92 µs / 1 µs

Cold = vmtouch -e then random-key Get; warm = cached. btnav isolated from existence-filter (~0.5 µs) and value fetch (~0.25 µs), which are negligible for storage. (8192-8704 omitted — probe harness hits a decompressor quirk on that one file; pattern is identical to the rest.)

Findings

increase M reduces the access cost, and increases the file size. We can leverage this to keep the latest (smallest step ranges) with higher M -- chaintip queries those most often. The oldest step ranges (largest) can continue using M=256

others:

1. btnav is ~99% of a storage read; kvei and kvval are noise.
2. Cold latency depends only on M, not file size (~160/108/92 µs for 256/64/16 everywhere) — it's log₂ M cold probes. Diminishing returns past M64.
3. Warm latency is ~2–5 µs regardless of M — when a file is cache-resident, M is irrelevant to speed.
4. Index size scales with file size, so low-M cost is what differs: M16 is 51 MB on a 466 MB file but 7 GB on the 71 GB file.

[AskAlexSharov]

nice

[VBulikov]

yperbasis added Imp2 as Importance

[sudeepdino008]

Follow-up: per-op fault distribution, and the same study for accounts + commitment

Extending the M-study from average btnav latency to the per-op cold major-fault distribution (getrusage majflt delta around each Get, vmtouch -e cold), across storage / accounts / commitment on mainnet + bloatnet. Proxy used for fast iteration = distinct 4 KB .kv pages touched per Get; it matches real cold major-faults within ~2%.

1. Faults are bounded everywhere — no worst offenders

accessor	domain	file	faults/op	p99	max
.bt	storage	mainnet 0-8192 (71 GB)	1.32	4	11
.bt	accounts	mainnet 0-8192 (12 GB)	1.06	2	7
.bt	accounts	bloatnet (6 GB)	1.05	2	2
.bt	commitment	mainnet v2.1 noref (180 GB)	1.82	7	12
.kvi	commitment	bloatnet (191 GB)	6.00	9	11

Tight distributions, no heavy tail. Two structural facts:

• .bt navigation self-warms: evicting the entire pivot index (madvise DONTNEED + drop_caches) leaves mean faults unchanged (storage 1.32 cold-index = 1.32 warm-index) — the binary-search upper levels are shared pages across queries, so steady-state navigation faults ≈ 0 and the only durable cost is the one .kv data-leaf fault.
• .kvi (recsplit) does not self-warm: each key hashes to non-shared MPHF positions → a durable ~6 faults/op. So for commitment specifically, .bt (1.8) already beats its production .kvi accessor (6.0) on cold faults — the warm-vs-cold complement to "warm kvi is faster than bt".

2. Storage & accounts are already at the floor — M barely matters

This matches this issue's storage finding from the fault angle: storage/accounts sit at ~1.0–1.3 faults (essentially the single data-leaf), so reducing M (or any index work) can't take much off — it only trims the small interp tail. The lever there is real but small.

3. Commitment is the outlier (1.82), and it's the interpolation tail

Commitment .bt is the one domain noticeably above the floor: ~61% of Gets touch 1 page, but a ~10% tail touches 5–12. Cause: commitment keys are Patricia trie paths — non-uniformly distributed inside a leaf — so linear interpolation overshoots and the probes scatter across cold pages. Storage/account keys are hashed (uniform) → interp lands first try → no tail.

4. Two levers for the commitment tail (big v2.1 noref file, 703 M keys, .bt 976 MB)

config	Δ .bt	faults/op	reduction
M256 (baseline)	—	1.82 (real)	—
M256 + K3×4B routing-anchors	+33 MB	1.52 (real)	−16.5%
M128	+86 MB	1.45 (proxy)	−19%
M256 + K7×4B routing-anchors	+77 MB	1.44 (proxy)	−19%
M64	+258 MB	1.28 (real)	−30%

Smaller M works on commitment too (M64: −30%) but, as for storage, costs index size (+258 MB here).

Cheap stored "routing-anchors" are an M-orthogonal alternative: per leaf, store K short prefixes (~4 B) of interior keys — specifically the bytes after the leaf's common prefix (the discriminating bytes), reconstructing the interp bound at read as queryPrefix ++ fragment (the prefix is free). At lookup they do a safe K-way pre-narrow (narrow only on strict byte-order, so the target is never excluded) before interpolation. They only store the bits that decide left/right, not whole keys — so per byte they're ~2–4× more efficient than reducing M at small budgets (K3: −16.5% for 33 MB), converging to ≈ M-reduction at high density. They'd live in the .bt footer (computed at build), are self-warming like the pivot cache, and generalize to any M.

Verified −16.5% is real cold major-faults (1.82 → 1.52, tail p90 4→2 / max 12→9), correctness preserved (found 15001/15001).

Negative results (for the record)

• Interp-budget sweep: flat (1.78–1.81); pure-interp worse, pure-binary 3.7. Probe count isn't the issue — interp is already near-optimal.
• "Deeper bytes on tie": dead code — the common-prefix construction means the pivot window never ties.
• Adaptive anchor placement (anchors at max interp-error positions vs uniform fractions): no better than uniform, and costs an extra stored position. The objective is page-span balance (uniform di-split achieves it directly), not interp-error magnitude.

Takeaway

• Storage/accounts: at the ~1-fault floor; M is a small lever (consistent with this issue).
• Commitment: the real headroom (1.82). Either smaller M (−30% @ +258 MB) or cheap routing-anchors in the .bt footer (−16.5% @ +33 MB, more byte-efficient) — and moving commitment off .kvi to .bt is itself a 6→1.8 cold-fault win.