commitment: evaluate .bt vs .kvi hashmap

[sudeepdino008]

Summary

While validating BTree-leaf interpolation search (#21794), I benchmarked whether the commitment domain — which currently uses the recsplit hashmap accessor (.kvi, Accessors: AccessorHashMap) — could instead use a BTree accessor (.bt) with interpolation. On bloatnet commitment files the .bt+interp accessor is ~4.5× smaller and far more robust to memory pressure, with comparable warm-read latency. Worth evaluating.

All numbers: cold full-Get (key + value), 15k random keys, vmtouch -e, M=256, interp budget 8, commitment Compression: CompressKeys.

Table 1 — accessor cold (index evicted; what a node sees when the index isn't resident)

commitment .kv	.bt M256 size / cold	.bt M64	.kvi size / cold	speed×	size×
14.5 GB	51 MB / 125 µs	70 MB / 106 µs	213 MB / 203 µs	1.6×	4.2×
107.9 GB	800 MB / 100 µs	1.1 GB / 94 µs	3.69 GB / 440 µs	4.4×	4.6×
122 GB	731 MB / 112 µs	980 MB / 97 µs	3.30 GB / 436 µs	3.9×	4.5×
190 GB	1.51 GB / 98 µs	2.1 GB / 93 µs	7.06 GB / 479 µs	4.9×	4.7×

.bt+interp stays ~100 µs at every scale (hot pivots in b.mx + interpolation lands locally → ~1 cold .kv fault). .kvi climbs 203 → 479 µs as its cold MPHF index grows.

Table 2 — both indexes warm (accessor resident, .kv data still cold) — fairness control

commitment .kv	.bt M256 cold	.bt M64	.kvi cold
122 GB	111 µs	97 µs	88 µs
190 GB	100 µs	96 µs	92 µs

With its index warm, .kvi is ~88–92 µs — slightly faster than .bt M256. So .bt is not intrinsically faster on the data read; Table 1's 4–5× gap is "hot .bt pivots vs cold .kvi index."

Interpretation

The real .bt+interp advantage for commitment is memory efficiency and graceful degradation, not warm latency:

• ~4.5× smaller accessor on disk (e.g. 190 GB file: 1.5 GB .bt vs 7.06 GB .kvi).
• Reaches ~100 µs with only the pivot array (b.mx, ~115 MB at M256) RAM-resident, and stays ~100 µs even when the rest of the .bt is cold.
• .kvi needs its full multi-GB MPHF resident to hit ~90 µs; under memory pressure (index evicted) it craters to 440–480 µs (~4–5×).
• So .bt+interp gives near-identical warm latency at ~30× less resident RAM for the hot path, and degrades gracefully — attractive for memory-constrained nodes.

Contingent on interpolation (#21794): binary-search .bt is 2–3× slower than interp on commitment and loses to .kvi on smaller files.

Caveats / open questions

• Measured on bloatnet (storage/commitment-stress) commitment files; mainnet distribution may differ.
• .bt build cost and one-time WarmUp (reads pivots at open) not evaluated here.
• Why .kvi was originally chosen for commitment (build speed? write path? history?) — would inform whether a switch is worth it.
• Harness: db/datastruct/btindex (BUILD_KV/KVIBT_*, vmtouch -e).

Refs: #21794 (BTree-leaf interpolation search).

[AskAlexSharov]

Why .kvi was originally chosen for commitment (build speed? write path? history?) — would inform whether a switch is worth it.

• .bt was new index with many optimization PR’s after release. Bottlenecks changed since that time.
• .kvi has bad thing inside: it has ordered array of “random-sorted numbers from 0 to N”. And I don’t know how to store them more compact. Ordered shuffled array of numbers - is kind-of-bad-for-compression. It using something like 5-bytes per number. Which is bad. MPH - is algo which allowing “to not store keys” but we still wasting tons of space for ordered-shuffled-array-of-key-nums.

[sudeepdino008]

Ordered shuffled array of numbers

https://github.com/ByteHamster/LeMonHash

[sudeepdino008]

Ordered shuffled array of numbers

https://github.com/ByteHamster/LeMonHash

• I think it works like enums=true...but with a difference..
• in enums=true, we're still storing permutation of ranks [0, N) and then an ef (which is compressible)
• the ranks are still shuffled arrays of numbers and high entropy (need ceil(ln n) bits), hardly better than offsets
• lemonhash -- uses insight that there's a almost linear relationship between keys and offsets (i.e. lower keys in lower offset, larger keys in large offsets etc.) and tries to guess a simple linear function between them.
• but approximation is not enough; so it still stores "error"/"deviation from plot" for each key (in the shuffled array), but now the requirements move to ceil(ln 2*error) bits per key, taking the shuffle cost from 25-30 its to 3 bits (for 10^8 entries and uniform distribution of keys)

the linear function is chosen more intelligently; there's not one but multiple linear segments (and each store slope and y-axis interception etc.); but this is the general idea,

for accounts/code it looks something like:

for account/code, the ef term dominates (error ~ 0.9 bits/key; ef ~ 2.0 bits/key)

this also making commitment tricky - -because one contract has 2.6M storage keys - and so they all share 33-byte prefix ( vertical cliff in that section)

not sure of worst case perf. (insert order is not lexicographic etc.)

[AskAlexSharov]

@sudeepdino008 i think in Erigon we adding murmur3(key) to recsplit builder. And reading also by murmur3(key):
offset, ok := reader.TwoLayerLookupByHash(hi, lo)

• maybe it solving "acc with many storage"
• maybe it making us worse (loosing co-location)

[sudeepdino008]

about lemonhash

i prototyped lemonhash - https://github.com/sudeepdino008/erigon/pulls?q=is%3Apr+is%3Aopen+kvi

• it reduced kvi size by 2.
• it solved "acc with many storage" by a recursive scheme

---

lemonhash is ok; but more interesting question is btree vs recsplit. I did some experiments/benchmarking for commitment data files. What i learned is:

• btree256 is 3-4x smaller than recsplit for same size; recsplit has more stuff mmap'ed (so it's heap friendly); btree is more heap resident.
• it's all about page faults - the index/settings that has lesser major page faults will be faster. It's pretty much 99% of the latency.

• experiment design --
  • warm means: make bt or kvi resident in memory (but not kv);
  • cold means: evict everything
• for smaller files, kvi has less majfaults so is faster;
• bt maj-fault is constant (1.5) despite the file size or cold/warm (bt nodes are in memory and ef is small, so ef majfaults amortise over queries)

conclusion:

It's pointing to a mix strategy...

• btree seems great for bigger files. These files have cold pages typically, and btree is 3x faster than kvi (cold) + btree is smaller than kvi
• kvi is faster on smaller files. At those smaller files, the size between kvi and bt doesn't matter.

I think it's a good result. On smaller steprange, relative larger size of kvi doesn't matter. On bigger step range, we get faster cold query and smaller size (bt) compared to kvi.

one issue: btree is more heap resident than kvi, so maybe we'll see more heap usage. For mainnet 0-8192, BtreeM64 stores 440mb in heap.

[AskAlexSharov]

.bt - also mmaped - im-mem only branch-nodes structe, not keys.
.bt - file - it’s just a keys list. Yes, jyst copy/paste 1% of keys from .kv

• .kvi - has Existence filter inside (qnd now it in-app-mem resident. On bloatnet StorageDomain moved to mmap because it’s 7gb and because on bloatnet erigon used sys=40gb - sometime no space for pagecache)

• .kvi - has Enum=true/false (i don’t remember why - i was not able to set False here - but it making .kvi biger)

• lemon - let’s merge prototype (disabled) and iterate on it - maybe it can give us something new

• help me to test/fix/compare new .bt btindex: standalone PrefixIndex with adaptive node distribution (40-62% faster) #20180

[AskAlexSharov]

“it's all about page faults” - yes, thus what i tell people on every meeting: “perf is all about PageFaults. PageFaults are all about - disk format or how code-logic of where-touch-files. Pure code-optimizations will not help much. Even parallel-exec is about PageFaults. On Bloatnet ram-usage-reduction helps - because almost no free ram for page-cache (it’s not about GC).”

[AskAlexSharov]

But also PageCache making us vertical-scalable: can say to user “add more Ram to server if you need more speed”

[AskAlexSharov]

“ one issue: btree is more heap resident” - i’m sure we can optimize it. Alloc all “Node” pointers on 1 array. Replace u64 by u32 somewhere. Reduce amount of branch-nodes. Etc… or #20180 also recently i removed 1 redundant field there.

Also today i will release new .bt format which will be “8-bytes per key” smaller.

[AskAlexSharov]

Good idea!

• small-files .kvi has lower overhead - not 5-bytes per key. There is adaptive fixed-size shuffled-numbers encoding. In my head i lt sounds like: “We did shard Fuse inside Recaplit. But maybe we need to shard Recsplit and it will 2x reduce encoding overhead - less keys per shard - less bytes-per key need to encode shuffled-numbers”

[sudeepdino008]

.kvi - has Enum=true/false (i don’t remember why - i was not able to set False here - but it making .kvi biger)

it has enum=false

lemon - let’s merge prototype (disabled) and iterate on it - maybe it can give us something new
help me to test/fix/compare new .bt #20180

cool

.kvi - has Existence filter inside

you mean kvei, right?

[sudeepdino008]

Alloc all “Node” pointers on 1 array. Replace u64 by u32 somewhere.

nice

[AskAlexSharov]

.kvi - has Existence filter insideR

you mean kvei, right?

no.
.kvi - Recsplit has lessFalsePositives=true config - which enabling "internal Existence fileter"
so domains with .kvi don't have .kvei files