erigontech / erigontech/erigon

commitment: evaluate .bt vs .kvi hashmap

Open
#21,795 18 comments 0 reactions 1 assignee Claimed by @sudeepdino008 View on GitHub
performance
Dominant language
Go
Stars
3.6k
Forks
1.5k
Avg merge
1d 16h
Merged PRs (30d)
455

Description

### 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).

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.