nordisk/skade

skade-katalog — Ragnar Static Index + Metadata Cache (design)

Supersedes the earlier AI-drafted ragnars_iceberg.md spec. That draft had the right two-tier instinct but routed by an id <= cutoff rule that is only correct for immutable, monotonic keys. It implicitly targeted the table-pointer keyspace, which is mutable in place (update_table overwrites the same key, catalog.rs:597) and would therefore go stale instantly under that routing. This document corrects that: we accelerate the immutable keyspaces only (parsed metadata + snapshot/commit ids), where the routing is provably never stale.

Problem statement

The current hot read path is RedbCatalog::load_table (catalog.rs:455):

1. tables_tbl.get(table_key) — redb B-tree lookup. ~1–5 µs. Already fast.
2. TableMetadata::read_from(&fileio, &metadata_location) (catalog.rs:467) — read metadata JSON from object storage + parse. ~150 µs on NVMe, 10–50 ms on S3. This is the real cost.

Optimizing redb (step 1) without addressing step 2 is polishing the wrong surface.

Design: three layers, each immutable-by-construction

                          read load_table / load_table_at(snapshot_id)
                                          │
   L0  Parsed-metadata cache  ───────────┤   Arc<TableMetadata>, byte-bounded 10–1000 MB
       key = metadata_location (immutable, content-addressed)        │  HIT: ~100–300 ns
       value = Arc<TableMetadata> (already deserialized)             │  no FileIO, no parse
                                          │ miss
   L1  Ragnar STree64  ──────────────────┤   snapshot_id (u64) → metadata_location
       cutoff routing: id <= max_id       │  immutable commit log, never stale
                                          │  HIT: ~100–300 ns (7 cache-line probes, AVX2)
                                          │ id > cutoff  OR  miss
   L2  redb live tail  ──────────────────┘   B-tree, ACID, MVCC. ~1–5 µs
       all writes land here; tip pointer for "latest"

Why each layer can never serve a stale value

• L0 is keyed by metadata_location. Iceberg metadata files are content-addressed and immutable — a new commit writes a new file. A cached entry can only be evicted, never wrong. No TTL, no invalidation, no coherence logic.
• L1 is keyed by snapshot_id — monotonic and immutable. The routing id <= cutoff → tree, else → redb is correct because snapshots never mutate. (This is the part the old spec got right only by accident — it applied it to mutable table pointers, where it is wrong.)
• L2 (redb) remains the single source of truth and the durability layer.

Source data structure: Ragnar's static search tree

Reused from znippy/znippy-zoomies/src/stree.rs:

• STree64 — implicit B-tree, branching factor B=8, one cache-line (64 B) per node, i64 keys, AVX2 count_lt (stree.rs:474-499). Build STree64::new (stree.rs:43) is O(n) over a sorted slice. Lookup find_exact (stree.rs:102) is O(log_9 n) ≈ 7 cache-line probes for billions of keys.
• lookup_batch_pipeline::<P> (stree.rs:320) — software-pipelined batch lookups with prefetch; converts random probes into overlapped cache-line walks. This is the win for query-planning-style batch metadata resolution.
• STree64Mmap (stree.rs:139) — keeps only internal nodes in RAM, leaves stay in mmap; relevant only if the commit log grows to billions of entries.

snapshot_id is already u64/i64 → zero hashing, native SIMD fast path. (Had we targeted the string table-pointer keyspace we'd have needed hash64 + side-array key verification + collision fallback — another reason that was the wrong target.)

Work items

L0 — measured (built 2026-06-06, local NVMe, tiny just-created table, single thread)

cold first load (miss)   :  87967 ns   (FileIO read + JSON parse + redb txn + build)
warm load (L0 hit)       :  16181 ns/op
cache disabled (baseline):  27687 ns/op
warm speedup vs disabled :  1.7x

Reading these honestly: on local NVMe with a tiny table, L0 only buys ~1.7×, because the metadata is small and the OS page cache already makes the FileIO read cheap. L0's real payoff is large metadata (many snapshots) and object storage, where the avoided read+parse is 10–50 ms, not ~11 µs → then it's ~100–1000×.

L1 — built 2026-06-06, and what it actually revealed (CORRECTION)

L1 = a lock-free, generation-stamped current-pointer mirror (table_key → metadata_location) published via ArcSwap, shared across catalog clones in Store, built once from a redb scan at open and maintained write-through on every mutation (create/update/drop/rename/register/atomic_release). Reads take no lock and never touch redb; a mirror miss falls back to redb only for genuinely-absent tables.

Measuring it disproved the earlier hypothesis that the ~16 µs warm floor was db.begin_read(). It was not. Removing redb from the read path changed the warm number by <2 µs. The real breakdown (local NVMe, warm, single thread):

full load_table         : 14724 ns/op
iceberg Table::build()  : 13833 ns/op   ← 93% of load_table
resolve_metadata (L1+L0):   414 ns/op   ← our fast path, lock-free, sub-µs

Table::build() allocates a fresh ObjectCache (a moka cache) per call — that is iceberg-rust internal and dominates load_table; it is not redb and not our layers. Our actual resolution (L1 pointer + L0 metadata) is 414 ns. So:

• The catalog's true read speed is exposed via RedbCatalog::resolve_metadata() (returns Arc<TableMetadata>, skips Table::build()): ~414 ns warm. This is the "fastest catalog" path and the basis for the future batch API.
• load_table (the Catalog trait method) is capped by iceberg's per-Table ObjectCache allocation. Options if it matters: a shared/lazy ObjectCache, or TableBuilder::disable_cache(true) for metadata-only callers — both have scan-perf trade-offs; not changed by default. Upstream improvement would let load_table inherit the 414 ns path for free.
• L1's win is concurrency, not single-thread latency: reads are lock-free, so they no longer serialize against writers on the old db.lock().await.

L1 hasher — foldhash (done 2026-06-09)

The mirror map is imbl::HashMap<String, Arc<str>, foldhash::fast::RandomState>. Keys are internal, content-addressed table identifiers — no HashDoS surface — so the std default SipHash was pure latency. foldhash (fast, well-distributed, AES-NI-free) replaces it; reads stay lock-free and the O(1) structural-sharing clone on write-through is unchanged. It only shaves the hash slice of the 414 ns (the rest is HAMT pointer-chasing + the Arc<str> clone), so it's a cheap, no-downside win, not a step change.

Measured (2026-06-09, l1_read_breakdown_and_scaling, single-table warm, 3 runs each): resolve_metadata SipHash ≈ 398–405 ns/op vs foldhash ≈ 390–396 ns/op — ~2–4% faster, never slower. Small because N=1 makes the hash a thin slice; the win grows with table count (deeper HAMT, more hashing) but the structural ceiling is the HAMT itself — which is what the flat-map item below targets.

L1 structure — flat-map swap (PLANNED, profile-gated)

Bigger potential lever, not yet built: if a catalog holds at most a few thousand tables, replace the persistent HAMT with ArcSwap<Arc<HashMap<String, Arc<str>, foldhash>>> — a flat (hashbrown) map swapped wholesale on each write. Reads then cost one hash + one probe with no HAMT node hops; the O(n) rebuild per write is lost in the noise of the redb txn + fsync every mutation already pays. Trade-off: it gives up the HAMT's O(1) copy-on-write, so it only wins if reads are the proven bottleneck. Decision rule: build it only behind a before/after resolve_metadata microbench (tests/pointer_cache.rs::l1_read_breakdown_and_scaling) showing the HAMT traversal — not the hash — is the dominant cost. Until then, foldhash + HAMT stands.

L1.5 — built-Table handle cache (built 2026-06-06, and a correction)

The note above claimed load_table was upstream-capped by Table::build()'s per-call ObjectCache allocation and that disable_cache(true) would let it inherit the resolve_metadata path. An A/B (bench/examples/cache_ab.rs) disproved the second half:

load_table (full)            p50  14.30 us
Table::build default         p50  14.21 us   ← ~all of load_table
Table::build disable_cache   p50  13.47 us   ← disable_cache barely helps (~5%)
Table::clone (cached)        p50   0.10 us   ← 140x cheaper than build
resolve_metadata (floor)     p50   0.39 us

disable_cache does not avoid the cost: it still constructs a capacity-0 moka cache, and the ~14 µs is moka construction (sharded concurrent structures + housekeeping), independent of capacity. There is no public way to inject a pre-built cache. But Table is Clone, and cloning shares the Arc<ObjectCache> — ~100 ns. So L1.5 (src/table_cache.rs, TableHandleCache) builds a Table once per metadata_location (immutable, content-addressed → never stale, same invariant as L0) and hands out clones. Sharing one ObjectCache across the clones is a bonus: iceberg's per-call throwaway manifest cache becomes a shared one. load_table is also location-first: it resolves just the location via the lock-free pointer mirror and, on a handle-cache hit, clones the built Table without touching L0 at all (the cached handle already carries the metadata); only a miss parses metadata + builds. Measured after wiring it into load_table + load_table_at:

load_table p50           : 15.1 us  -> 1.5 us   (~10x, at the resolve_metadata floor)
load_table throughput t8 : 74k      -> 2.07M ops/s  (~28x)
load_table throughput t32: 276k     -> 1.92M ops/s  (~7x)

Knob: RedbCatalogBuilder::table_handle_cache_bytes / prop redb.table-handle-cache-bytes (default 256 MiB, 0 disables). load_table now scales concurrently (lock-free clones don't contend) instead of flattening on the moka build.

table_exists via the pointer mirror (built 2026-06-06)

table_exists used to take the tokio mutex + a redb begin_read on every call. But the L1 pointer mirror already knows every live table (full scan at open, write-through after). So table_exists now answers from the mirror (pointers.get(key).is_some()), falling back to redb only on a mirror miss (to confirm absence). Measured embedded: p50 1.31 µs → 0.32 µs (~4×), 668k → 2.11M ops/s, and it no longer serializes against writers.

Cold-miss path: use znippy's fast gzip

Iceberg metadata files may be gzip-compressed (*.metadata.json.gz); read_from sniffs the gzip magic and inflates inline. Manifest lists can be gzipped too. The fast gzip decompressor in znippy/znippy-zoomies should front the cold/miss decompress path (read bytes → znippy-inflate → serde_json), shrinking the one-time miss cost that L0 can't help with (L0 only helps after the first miss). This means bypassing TableMetadata::read_from with our own read+inflate+parse — gated/tested carefully because read_from also handles the uncompressed and version-hint cases.

L0 metadata cache details

• crate: moka::sync::Cache (W-TinyLFU, byte weigher). quick_cache acceptable if we want a lighter dep.
• key metadata_location: String; value Arc<TableMetadata>.
• capacity metadata_cache_bytes, default 128 MB, range 10 MB – 1 GB, set via RedbCatalogBuilder::metadata_cache_bytes(n).
• get_with coalesces concurrent misses on the same key (a hot table is parsed once).
• correctness: immutable content-addressed key → eviction only, no invalidation.
• L0.5 (later): cache parsed manifest lists / manifests (also immutable, content-addressed) — the layer that query planning hammers and where the high-bandwidth network + batch lookups actually pay off.

Rebuild triggers (compactor)

• write-driven: update_counter >= N (default ~10k commits, tunable),
• miss-driven: live_tail_misses >= M (snapshots asked about that weren't yet in the tree),
• time ceiling: rebuild at least every T so a quiet catalog still folds in.

Batching strategy — how to actually harness Ragnar's batch speedup

The pipelined batch lookups (lookup_batch_pipeline::<16>, stree.rs:320) win by hiding one key's memory latency behind compute on the others. That only helps with many keys at once. There are two sources of "many keys", and they call for opposite handling.

1. Intrinsic batches — the slam dunk (no coalescing, no added latency). Iceberg scan planning is already a batch: one logical "plan this scan" resolves snapshot → manifest list → many manifests → many data files — hundreds to millions of u64 id lookups in a single operation. Feed those straight into lookup_batch_pipeline::<16> via a resolve_many(ids: &[u64]) API. The batch is free — it exists in the workload. This is where the ~40× lives. (Targets L1 / the future L0.5 manifest+file index.)

2. Cross-request coalescing — right pattern, wrong window. Collecting independent concurrent loadTable/resolve calls and batching them is valid, but a 1-second window is wrong: it adds up to 1 s of latency to every read, turning a ~16 µs read into ~1,000,000 µs and destroying the whole point. Use opportunistic, self-tuning micro-batching instead:

• a worker drains whatever is already queued the moment it's free (no fixed timer);
• batch size self-scales — big under load (throughput), size-1 when idle (low latency);
• bound it with max_batch (~256) and a tiny max_wait (~50–200 µs), never seconds.

And coalesce only when it pays: cross-request batching of cold/mmap STree64Mmap lookups is a big win because lookup_batch's madvise(WILLNEED) (stree.rs:275) turns N random page faults into one sequential readahead (4–8×). For warm in-RAM point lookups, skip it — the ~300 ns saved per key is less than the channel/wake/scatter cost, so coalescing is net-negative.

3. L0's equivalent of batching = single-flight + concurrent I/O. For the metadata cache, the batching that matters is already done: moka try_get_with coalesces concurrent misses on the same key into one read_from, and distinct misses can issue their FileIO reads concurrently. No request window needed.

Build order

1. L0 metadata cache + builder option + embedded warm-vs-cold microbench. (~90% of the win for ~20% of the work.)
2. Benchmark harness skeleton (nornir-only), then Nessie-RocksDB container, then Polaris.
3. Commit log + STree64 L1 + ArcSwap + compactor; add load_table_at + batch scenarios.
4. axum REST shim for the fair REST-vs-REST benchmark column.

L1 earns its keep specifically on time-travel / historical snapshot resolution and batch manifest-style lookups — not on small single "latest" reads, where L0 + redb already win. Scope it as phase 3, after L0 is measured.

Benchmark: skade-katalog vs Nessie vs Polaris

Mirrors the holger/ vs Nexus harness exactly (holger/bench-scenarios/src/lib.rs, holger/xtask/examples/nornir-bench.rs, container pattern in holger/agent/cli/tests/integration_nexus_load.rs, gates in workspace_holger/release/nornir.toml:64-77).

Uniform interface: Nessie and Polaris both speak the Iceberg REST protocol, so we drive them through iceberg-rust's RestCatalog; nornir uses RedbCatalog. All workload code is generic over Arc<dyn iceberg::Catalog> — identical across competitors.

Competitors (in containers, via testcontainers)

• Nessie-RocksDB ("the fast one"): ghcr.io/projectnessie/nessie:latest, nessie.version.store.type=ROCKSDB, REST at :19120/iceberg.
• Apache Polaris: apache/polaris (Quarkus JVM) + Postgres sidecar; also an in-memory config as a second data point. REST endpoint.
• JVM args (heap, direct mem, threads) tuned to host cores/RAM like integration_nexus_load.rs:188-237.

nornir reported two ways (per review decision: both columns)

• embedded — in-process RedbCatalog, no network (the real deployment).
• REST-fronted — RedbCatalog behind a thin axum shim, same HTTP path as the JVM catalogs, for an apples-to-apples REST-vs-REST number.

Workloads (ST + MT32, 100-iter warmup, barrier-synced threads — holger pattern)

Metrics (holger Throughput + latency percentiles)

pub struct CatalogResult {
    pub ops: u64, pub ops_sec: f64,
    pub p50_us: f64, pub p99_us: f64, pub p999_us: f64,
    pub mb_per_sec: f64, pub bytes: u64,
}

Recorded JSONL → nornir Iceberg bench_runs table → auto-generated README headline. Gates: nessie_floor (nornir ops_sec ≥ Nessie), no_regression (>10% drop).

Invocation (implemented — see bench/)

BENCH_QUICK=1 cargo run --release -- embedded      # in-process RedbCatalog
BENCH_QUICK=1 cargo run --release -- nornir-rest   # nornir behind axum Iceberg-REST shim
./containers/nessie_up.sh && cargo run --release -- nessie http://localhost:19120/iceberg warehouse
./containers/polaris_up.sh # prints OAuth + catalog bootstrap, then:
BENCH_REST_PROPS="credential=root:s3cr3t,scope=PRINCIPAL_ROLE:ALL" cargo run --release -- polaris …

Measured so far (this dev box, BENCH_QUICK, local NVMe)

Pure catalog read RPC (table_exists/HEAD) — ran on ALL FOUR (Nessie and Polaris both reject/insecure-block local file: warehouses for the table write path, so loadTable/createTable couldn't be exercised there; iceberg-rust 0.9.1 ships only LocalFs/Memory FileIO — no S3 — so MinIO is blocked client-side too. table_exists is the clean storage-free comparable run on every backend.)

Full four-way run (2026-06-06, this box, full 10k-table scale) — Polaris row now landed (this is the current table; an earlier smaller-scale run was dropped to avoid two conflicting number sets — the README headline tracks this one):

RESULT — REST-vs-REST, nornir-rest is ~8.0× lower p50 / ~9.2× higher throughput than Polaris, and ~4.1× / ~4.4× vs Nessie (native axum vs Quarkus JVM); embedded is ~218× vs Polaris, ~112× vs Nessie. Polaris is slower than Nessie (per-request OAuth/RBAC). The JVMs' multi-ms p999 is the GC tail; nornir-rest's p999 stays at 87 µs. Sits squarely in the predicted 5–40× REST band. Polaris bootstrap recipe (the missing piece) is now automated in bench/containers/polaris_up.sh: FILE storage needs three quoted-key feature flags passed as JVM -D props (SUPPORTED_CATALOG_STORAGE_TYPES, ALLOW_INSECURE_STORAGE_TYPES, ALLOW_SPECIFYING_FILE_IO_IMPL) plus polaris.readiness.ignore-severe-issues=true.

Write durability (implemented, measured)

RedbCatalogBuilder::durability(Immediate|Eventual|None) wired through all write paths. Measured: it barely changes create_table (the metadata-file write dominates, not the redb fsync) — see REDB_WISHLIST.md.

Expected speed difference (estimates — to be replaced by measured values)

A catalog loadTable is latency-bound, not bandwidth-bound (payload is a few KB). An 800 Gb network barely helps the catalog control plane; it helps the data plane (manifests/Parquet) — i.e. the future L0.5 manifest cache, not these RPCs.

• Embedded nornir warm read ≈ 100–1000× lower latency than a JVM REST catalog — by deleting the network hop + JVM + double JSON serialization, not because redb is special.
• REST-fronted nornir ≈ 5–20× faster than Nessie/Polaris (native axum vs Quarkus JVM, no per-request metadata re-parse thanks to L0).
• 800 Gb NIC: flat benefit for KB-sized catalog RPCs (latency-bound); real benefit for bulk manifest/data transfer.

No public Nessie/Polaris loadTable latency tables exist — these are engineering estimates. The harness above replaces them with measured numbers.

Sources

• Nessie version-store backends (RocksDB/in-memory/JDBC), Quarkus REST: https://projectnessie.org/nessie-0-83-2/configuration/ , https://projectnessie.org/develop/
• Polaris architecture + Gatling benchmark harness (apache/polaris-tools): https://github.com/apache/polaris , https://www.dremio.com/blog/benchmarking-framework-for-the-apache-iceberg-catalog-polaris/

HANDOFF

The detailed session handoff (what's built, where, and the gotchas) lives in HANDOFF.md — it is the single source of truth for status. A second copy used to live here and drifted out of date (it still claimed the Ragnar STree64 layer was "NOT built" long after it shipped). Removed.

Current reality: the Ragnar L1-historical layer (commit log → StaticIndex STree64 → background compactor → load_table_at/resolve_metadata_at/ resolve_many) is built, wired, and green. See HANDOFF.md for the table and src/static_index.rs / src/store.rs / src/catalog.rs for the code.

Write path — concurrent-ingest analysis & group-commit (2026-06-06)

Question: is skade-katalog's "write slowness" fixed? Honest answer: not on the concurrent-ingest workload — because that workload is storage-bound, not catalog-bound. Details:

Where there was never a problem

Single-threaded writes: nornir was already far faster than the JVM catalogs (embedded redb commit vs REST+JVM). Not the issue.

Where nornir trailed

Concurrent ingest over the shared RustFS S3 warehouse (32 writers, real OSM / synthetic). Measured (3.2M rows, 32 writers, NVMe):

Over S3 under concurrency, Nessie's ingest rows/s and commits/s exceeded nornir-s3. That is the "write slowness".

What group-commit did (and didn't)

Implemented Store::group_commit (src/store.rs): concurrent mutations enqueue their redb work as a closure, race for the db lock, and the winner coalesces all queued ops into ONE redb write txn + ONE commit()/fsync, then publishes each op's mirror update. Optimistic conflicts stay isolated (a failing op writes nothing). update_table (the fast_append path) commits through it. Validated: under a commit-dense burst it coalesced batches of 2–16 into a single fsync; test group_commit_lands_all_concurrent_commits covers correctness.

But it did NOT change the ingest numbers (145 vs 148 commits/s — noise). Why, measured directly: in ingest, each commit is spaced out by its own slow Parquet-encode + S3-upload, so the group-commit queue is almost always size 1 → nothing to coalesce → no fsync to amortise. Group-commit pays off only for commit-bursty workloads (many small/metadata-only commits arriving faster than fsync latency), not for storage-bound bulk ingest.

The real bottleneck (next lever)

Concurrent ingest is dominated by the storage write path — Parquet encode + S3 PUTs — which is shared by every backend, so it isn't a nornir-specific catalog slowness. The catalog commit is a small fraction of ingest time. To actually raise nornir's concurrent ingest throughput:

• bench/src/s3_storage.rs writer: today S3FileWrite buffers the whole file and does a single put_object on close. Switch to streaming multipart upload and cut round-trips per commit (data file + metadata.json). This is where the gain is — NOT the catalog.
• Investigate per-commit S3 round-trip count vs Nessie (client-side metadata write vs server-side).
• Group-commit remains the right fix for commit-bursty (small-commit) concurrency; group-commit + WriteDurability::Eventual would amortise further.

Verdict: group-commit is shipped, correct, and helps commit-bursty loads; the concurrent ingest number is unchanged because it's storage-bound. Fixing that is storage-path work (multipart S3), tracked above.

⚠️ The single-writer/many-processor pipeline is backend-agnostic (read this)

The "use all cores to encode Parquet, one thread to write" model is a client-side change: in the harness every backend (nornir, Nessie, …) is driven through the same data.rs ingest, and the encode + warehouse write run client-side in iceberg-rust — only the commit RPC differs. So that pipeline:

• lifts all boats — run Nessie through it and Nessie's ingest rows/s rises too. It is not a nornir-vs-Nessie lever; it's a harness-optimality fix. To stay fair it MUST be applied to every target, not just nornir.
• does not explain why Nessie looked faster at writing data. That was the commit path (Nessie commits concurrently server-side; nornir serialized on the single redb-writer mutex). The nornir-specific fix for that is group-commit (shipped), which Nessie does not share.
• is primarily an NVMe lever (sequential, uncontended writes beat N contending writers). For S3, object stores often scale with parallel connections, so a single writer can be slower than several parallel multipart uploaders — measure before assuming the single-writer topology wins on S3.

Net: the catalog differentiator vs Nessie lives on the commit path (group-commit, commit-bursty workloads), not the encode/write topology. Build the pipeline to make the harness's write path optimal and to model the topology — not as a way to "beat" Nessie on storage-bound ingest.

Open levers / future work (TPC-H read path)

The big read-path win (2026-06-08) was the parallel per-file Iceberg scan: stock iceberg-datafusion 0.9.1 scans a table as a single DataFusion partition (UnknownPartitioning(1) + one flattened to_arrow() stream) → single-threaded Parquet decode, ~3 of 32 cores, SF100 ~28 min. The vendored patch (bench/vendor/iceberg-datafusion, relative-path [patch]) exposes one partition per file → SF100 FILE query 1651→198 s (8.3×), cores 3→~17-32. Remaining levers:

• Push core utilization past ~60% — utilization is capped by files per table (N files → N scan partitions). Big tables (lineitem = 32 files) fill the cores; small tables don't. Lever: ingest with a smaller target file size (more, smaller files) so every table yields ≥ cores partitions. Trade-off vs more metadata.
• Full 3.75 B Europe OSM ingest — the streaming-window ingest is validated (per-window file prefix fixed); not yet run at full scale. NB its scan-back verify (data::scan_count) uses iceberg's own serial TableScan::to_arrow, not the patched iceberg-datafusion path, so verifying 3.75 B is single- threaded/slow — either cap the verify or port scan_count to a parallel reader.
• Upstream the parallel-scan patch — it's an iceberg-datafusion backlog item (scan output-partitioning). When it ships, drop bench/vendor/ + the [patch].
• S3 is settled — h2c / object_store / OpenDAL / RustFS tuning are dead ends (HTTP/1.1 loopback ~900 MB/s/stream is inherent; cancels in the comparison). The ~3.7 min FILE vs ~6.6 min S3 gap at SF100 is the honest object-store cost, now visible because the parallel scan no longer hides it.