perf(read): retrieval-ribbon point-read locator (O(1) point reads, beat RocksDB structurally)

[polaz]

Progress

• Slice 1 (D4 build integration): done. In-memory retrieval ribbon: the BuRR builder gains build_from_hashes_with_values(hashes, locators), solving coeff . solution = locator over the same band placement as membership (shared build_once_core); BurrFilter::recover_value(hash) recovers the stored locator at the first non-bumped layer. Build rejects empty input, length mismatch, and a locator wider than r bits. 6 tests (single/multi-layer exact recovery, full-width r=64, three rejections).
• Slice 2 (D5a wire recovery): done. A retrieval payload carries a new filter_type tag (3) within the existing wire FORMAT_VERSION (NOT a version bump); membership stays tag 2 and byte-identical. recover_value_from_bytes answers key -> locator straight from wire bytes; membership probe and retrieval recover share one walk_first_layer parse so the security-sensitive bounds checks cannot drift. Cross-tag querying is rejected as InvalidTag. 5 tests.
• Slice 3 (D5b-1 write side): done. Per-level LocatorPolicy (off by default; LocatorPrecision Block / Restart / Entry; widths each Option, auto per-SST). The writer accumulates (key_hash, block_id, slot) per unique key at the global new-key boundary, builds the retrieval ribbon at finish, and emits an optional locator section (new Locator BlockType tag 8 + TOC section, in-place V5, no version bump). Disabled levels emit byte-identical SSTs (section absent, zero bytes). Graceful skip (no section) on empty input, width overflow, or ribbon-build failure: never aborts a compaction. Wired at all three write sites (flush / ingest / compaction) via MultiWriter::use_locator with rotation re-apply. End-to-end writer test recovers every inserted key's (block_id, slot) from the real on-disk section; disabled run emits nothing.
• Slice 4 (D5b-2 read path): done. Point read consumes the locator: recover (block_id, slot), resolve block_id to its data block in O(1) via an ordinal -> handle map built at open, and skip the index-block binary search. The located block holds the key's newest version (the run's highest-seqno prefix), so a hit returns the correct MVCC answer and any miss falls through to the sorted-index walk (correct by construction: the block's own point_read verifies key + seqno, so a stray locator only wastes a block read). LocatorPrecision::Block (per-block: block_id only, slot dropped) is the granularity this path resolves; Restart/Entry resolve the same block_id (their in-block slot skip is the remaining follow-up). Integration test: a locator-enabled tree returns byte-identical results to a disabled one across 1500 keys x 3 snapshots x present/absent, with multi-version keys + tombstones, for all three precisions.

Functionally complete end-to-end (opt-in O(1) point read, byte-identical to the index path). Remaining: the in-block slot skip for Restart/Entry (optimization, slot already stored), and the D6 ours-ribbon bench overlay (measurement).

D5 width / precision policy (settled)

The locator is (block_id : block_id_bits) | (slot : slot_bits), both widths configurable.

• slot_precision is configurable A or B (per-level policy, default disabled, off per the Benchmark Symmetry Invariant):
  • A Restart: slot = restart index in the data block; auto slot_bits = ceil(log2(max_restarts_per_block)); read = jump to the restart head (known byte offset) + scan <= restart_interval entries. In-block granularity == RocksDB data-block hash index.
  • B Entry: slot = full entry index; auto slot_bits = ceil(log2(max_entries_per_block)); read = jump to restart head + decode to the exact entry (no key compares); +3-4 bits/key.
  • Data blocks are delta-coded within restart intervals, so only the restart head has a free byte offset; an exact byte offset is not addressable (and was rejected in D1). The structural win over RocksDB is block_id (eliminates the index-block binary search, which no competitor's hash index does); the in-block part is at parity (A) or slightly better (B).
• Widths: block_id_bits / slot_bits each Option; None = auto per-SST minimum, else explicit.
• Overflow (explicit widths too small for an SST's real layout): graceful skip, that SST emits no locator section (zero bytes, point read falls back to the index) + log + metric. Never a build error mid-compaction.

D5b implementation plan (scouted)

Mirrors the optional-block_layout-section precedent, so no format-version bump and zero bytes when off.

1. Config: LocatorPolicy per-level type (mirror FilterPolicy in src/config/filter.rs), default disabled(). Carries slot_precision, optional block_id_bits, optional slot_bits.
2. Writer (src/table/writer/mod.rs): in spill_block (before the parallel path clears the chunk at the submit point), for each unique user key in the block accumulate (key_hash, block_id, slot) into a gated Vec. block_id = running spill counter (matches the ordered registration); slot = first_item_index_of_key / restart_interval (A) or first_item_index (B); newest version = first occurrence in scan order (D2). Same per-key hash source the filter writer uses (register_key).
3. finish (src/table/writer/mod.rs ~ the block_layout emit): if enabled and accumulator non-empty and widths fit, compute auto widths, pack locators, build_from_hashes_with_values, start("locator") + write to_wire_bytes() (+ a small section header carrying block_id_bits/slot_bits/precision so the reader can unpack). Else skip (zero bytes).
4. regions (src/table/regions.rs): add locator: Option<BlockHandle>, parse toc.section(b"locator").
5. Read path (final slice): point read resolves the locator, validates bounds, fetches block_id, resolves slot (A: restart head + bounded scan; B: decode to entry), verifies the key, returns the value or falls back to the index (D2/D3).
6. Bench (D6): ours-ribbon overlay on the existing point_read chart.

Design decided (D1-D6)

The design phase is settled. The membership BuRR ribbon already solves coeff . solution = value for an r-bit value derived from the key hash (src/table/filter/ribbon/); the retrieval ribbon reuses that exact solve with the value set to a per-key locator instead of a hash-derived fingerprint. Implementation is a multi-step effort tracked here.

D1 Locator = block-id + in-block slot, with configurable widths. The locator is (block_id : block_id_bits) | (slot : slot_bits), where block_id_bits and slot_bits are each configurable; the ribbon width is r = block_id_bits + slot_bits. This trades storage vs precision: fewer slot_bits can address the restart head plus a bounded scan within the restart interval instead of the exact entry. It eliminates BOTH binary searches (index-block and within-block), which beats RocksDB structurally (RocksDB's data-block hash index removes only the within-block search and keeps the index-block search).

• Rejected: a direct value byte offset (incompatible with block compression, and with the per-block checksum / ECC / AEAD integrity envelope, both core to the engine).
• Rejected: block-id only (keeps the within-block search, so parity with RocksDB, not a structural win).

D2 MVCC. The ribbon stores the NEWEST version's locator per key. A point read resolves the locator, fetches the block, and verifies; if the located version's seqno is newer than the read's snapshot seqno, fall back to the sorted index for the older version. Compacted SSTs are usually single-version (fast path); L0 may fall back.

D3 Membership subsumed. The verify (key compare at the located slot) is the absent-key check, since the ribbon returns garbage for an absent key. The retrieval ribbon therefore REPLACES the BuRR membership filter (one structure does locate + membership), with the locator bounds-validated before any fetch so a stray locator cannot read out of bounds.

D4 Build integration. Extend the BuRR builder with a build_from_hashes_with_values(hashes, locators) path that solves coeff . solution = locator; the existing hash-derived-fingerprint path becomes the membership special case. Locators are computed during SST write once the data-block layout (block ids + in-block slots) is known.

D5 On-disk layout. A new per-SST locator section, format-version gated and opt-in (off by default per the Benchmark Symmetry Invariant #353), for read-heavy workloads.

D6 Benchmark. An ours-ribbon series overlaid on the existing point_read chart (wire-up documented in the Benchmark overlay section below).

---

Idea

Point reads do not need the sorted index (that exists for range scans). An SST is a static key set after flush, and we already build a BuRR (ribbon) membership filter per SST. Generalize the membership ribbon into an r-bit retrieval ribbon that maps key -> locator (data-block id + in-block offset, or directly the value byte offset).

Point read becomes O(1):

loc   = ribbon.query(key)     // a few XORs over cache lines, no binary search
block = fetch(loc.block)
verify key at loc.offset      // one compare; catches absent keys (subsumes membership)
return value                  // zero-copy slice

This eliminates the two binary searches (index-block + within-data-block) and the per-probe delta/varint key decode that dominate the current read path (~45% of the get), replacing them with one ribbon query + one verify. The sorted index stays for range scans -> best of both, which a single-index LSM like RocksDB cannot do.

Why it can beat RocksDB

RocksDB point reads are structurally O(log B) index + O(log K) in-block with key decode; its per-block hash index only helps within a block. A per-SST retrieval ribbon makes ours O(1) lookup + 1 verify, independent of depth.

Viability vs our features (the open question to settle in design)

• MVCC / multiple versions per key: ribbon points at one location (e.g. the newest version in this SST). If the located version's seqno is newer than the snapshot seqno, fall back to the sorted index for the older version. Within a compacted SST keys are usually single-version; L0 may not be -> needs a policy (locate-newest + fallback).
• Tombstones: the located entry's value_type signals a point delete -> return None. Works directly.
• Merge operands: ribbon locates the newest entry; gathering older merge operands needs the sorted scan -> ribbon serves the fast path, merge falls back. Acceptable.
• Range tombstones: orthogonal (separate range-tombstone map), unaffected.
• Verify is mandatory: ribbon returns garbage for absent keys -> the key compare at the located slot is the membership check (replaces the bloom/BuRR probe).

So: fast O(1) path for the common case (single/newest version, no merge), correctness preserved by a fallback to the sorted index for old-version snapshot reads and merge-operand gathering.

Layering

• New per-SST locator section; off-by-default format feature under the Benchmark Symmetry Invariant (Benchmark Symmetry Invariant: discipline for new format features (cross-cutting design rule) #353); opt-in for read-heavy workloads.
• Build cost amortized: the ribbon is already constructed for the filter, widen its columns to r bits.
• Complements (does not replace) the slice-decode read-path work in perf(table): close the point_read gap vs RocksDB (read-path per-get overhead) #463, which still serves the verify + scan path.

Benchmark overlay (on the EXISTING point_read chart)

The ribbon locator must be measured as a NEW series overlaid on the SAME point_read chart that tools/compare-rocksdb already produces, not a separate chart. That chart already overlays ours / rocksdb (binary-search data-block index) and ours-hash-index / rocksdb-hash-index (data-block hash index, added in #465). Add ours-ribbon (the BuRR-derived retrieval-ribbon locator) as one more line so every index strategy is compared head-to-head on one plot. The series list in point_read_variant is already structured to take an extra overlay (push ("ours-ribbon", Engine::Ours, ..)). The pass criterion: the ours-ribbon line beats rocksdb (and ours / ours-hash-index) on point_read, at parity on every other axis (write throughput, range scan, ratio).

[coderabbitai]

🔗 Related PRs

#269 - feat(filter): replace standard bloom with BuRR [merged]
#397 - perf(table): size-adaptive block index — single-level for small SSTs [merged]
#401 - feat(compaction): parallel block compression [merged]
#455 - refactor(filter): remove dead from-keys BuildHasher path from vendored ribbon [merged]
#465 - perf(table): cut point-read per-get overhead [merged]

---

📝 Issue Planner

_{Check the box below or use the @coderabbitai plan command to generate an implementation plan and prompts that you can use with your favorite coding assistant.}

• Create Plan

---

🧪 Issue enrichment is currently in open beta.

You can configure auto-planning by selecting labels in the issue_enrichment configuration.

To disable automatic issue enrichment, add the following to your .coderabbit.yaml:

issue_enrichment:
  auto_enrich:
    enabled: false

💬 Have feedback or questions? Drop into our discord!