nordisk/znippy
.nornir/zoomies-design.md
# znippy-zoomies — design
> **Class:** `design` · **Function axis:** `f0` (zoomies as one system) + the parts: `linflate` core · the decoder family · the candidate-offset output model (B6) · the `gatling` engine · `stree`.
> Strict: this file states *only the shape we run*. Every *why*, every alternative, lives in [`zoomies-reasoning.md`](zoomies-reasoning.md); the how-to in [`zoomies-guide.md`](zoomies-guide.md); the measured numbers in [`benchmarks.md`](benchmarks.md).
## f0 — zoomies as one system (the whole)
`znippy-zoomies` is a **sibling repo consumed as path deps**: pure-Rust parallel decoders and
fast primitives that znippy leans on. One invariant runs through everything: **a decoder takes a
borrowed `&[u8]` and never copies its input.** That single rule is what lets a 164 GB planet file
stream through on *one* read-copy — bytes are read into a slot once, sliced, decoded in place, and
stitched, with no intermediate owning buffer.
The workspace is **tokio-free** except the `iceberg` crate (and the async `gatling::io` sibling).
The pieces, and what each `uses`:
| part | crate/file | role |
|---|---|---|
| **linflate** | `linflate/` | the shared SIMD DEFLATE core — every decoder inflates through it |
| **decoder family** | `ljar` `lgz` `lbzip2` `lzip-parallel` | format front-ends (JAR / gzip / bzip2 / ZIP), all on `linflate` |
| **candidate-offset model (B6)** | `ljar/src/chunk.rs`, `ljar/src/bin/ljar.rs` | the zero-copy parallel decode layout |
| **gatling** | `src/gatling.rs`, `src/gatling_io.rs` | generic no-barrier streaming engine (sync + async) |
| **stree** | `src/stree.rs` | static search tree for id→position lookup, re-exported into `osm-katana` |
Consumed *by*: znippy proper (decompress path), and `osm-katana` (OSM→GeoParquet/PBF), whose
xml→pbf path rides `gatling` and whose node store uses `stree` (re-exported as `stree64`).
## linflate — the shared inflate core
`linflate/` is a **pure-Rust, full-buffer, SIMD DEFLATE** decoder: the libdeflate full-buffer model
(no streaming window) fused with zlib-ng branchless tricks. Hot working set ≈ **13 KB** — it fits in
L1-D. Files:
| file | holds |
|---|---|
| `bitreader.rs` | 64-bit shift register; branchless refill guaranteeing **≥56 bits** after refill, **one refill per symbol** |
| `tables.rs` | packed-`u32` Huffman; **11-bit litlen** first-level table; thread-local table pool |
| `fixed.rs` | the static fixed-Huffman tables |
| `copy.rs` | const-generic `copy::<N>` SIMD match copy → `vmovdqu` |
| `fastloop.rs` | the hot loop: preload-before-copy, 3-literal unroll, `#[cold]` slow paths |
| `lib.rs` | the API |
**API** (`linflate/src/lib.rs`):
| fn / const | signature | note |
|---|---|---|
| `OVERWRITE_HEADROOM` | `pub const = copy::CHUNK_SIZE + 258` (`:43`) | **part of the API contract** — every output region must include it so SIMD copies never scribble into a neighbour; undersized ⇒ `OutputOverflow`, *not* UB |
| `inflate_into` | `(data, &mut [u8]) → Result` (`:81`) | decode into a caller buffer |
| `inflate_segment` | `(…)` (`:93`) | decode a slice that **need not end on `BFINAL=1`** |
| `inflate_segment_with_prefix[_limited]` | `(:108`, `:120`) | segment decode with a back-reference prefix window |
| `inflate_to_vec` | `(data, expected) → Vec<u8>` (`:206`) | allocates `expected + OVERWRITE_HEADROOM`, `set_len(expected)` |
| error | `InflateError::OutputOverflow` (`:53`) | undersized output |
`inflate_segment` decoding a slice that does **not** require `BFINAL=1` is the linchpin of parallel
decode: mid-stream segments — split at `Z_FULL_FLUSH` boundaries by `deflate_scan` — are each
independently decodable.
## the decoder family
Four format front-ends, one shared core. Each takes a borrowed `&[u8]`:
| crate | format | parallelism |
|---|---|---|
| `ljar` | JAR | parallel (per-entry + per-chunk) |
| `lgz` | gzip | parallel (flush-marked, concatenated members, **and** arbitrary markerless via speculative resync) |
| `lbzip2` | bzip2 | parallel over BWT blocks |
| `lzip-parallel` | ZIP | parallel over entries |
All four inflate through `linflate`; none owns a second DEFLATE implementation.
## the candidate-offset output model (B6)
The **zero-copy parallel decode layout**. One pre-allocated buffer; the flow:
1. **Candidate offset per segment** = prefix sum of *generous caps* (not true sizes).
2. **Decode all segments in parallel, in place**, each at its candidate offset — **zero per-segment
allocation** (`ljar/src/chunk.rs:220`, `output.resize(acc, 0)` pre-allocates the whole candidate region once).
3. **Forward-seek compaction** (`chunk.rs:267`): walk segments in order, moving each *down* to its
true cumulative offset. Because `actual ≤ cap`, every move is **leftward**, so nothing not-yet-moved
is ever clobbered. Then `set_len(total)`.
4. **Spill path** (`chunk.rs:258`): a segment that outgrows its cap spills to an owned `Vec` (rare) →
sequential rebuild. It never corrupts; output is byte-identical.
Two implementations of this model:
| impl | where | shape |
|---|---|---|
| library | `ljar::chunk::decode_chunk_into` (`ljar/src/chunk.rs:173`) | rayon fork-join per chunk |
| binary | `ljar/src/bin/ljar.rs` | woven into the no-barrier **5-thread pipeline** `Reader → Main(carry+split) → N Workers → Collector → Writer` (232 MB ring slots) |
## the gatling engine
`src/gatling.rs` — a **generic, no-barrier streaming engine**. A `Read` source is split into segments
in a bounded zero-copy slot ring; N worker threads transform each segment with **no cross-worker
barrier**; an ordered collector reassembles in stream order and hands to a `Sink`. Two modes:
| mode | driver | workers produce | collector |
|---|---|---|---|
| byte | `run` + `Codec` (`:68`) / `Sink` (`:83`) | `Vec<u8>` | concatenate + `safe_end` cut |
| typed | `run_typed` + `TypedCodec` (`:99`) / `TypedSink<T>` (`:127`) | arbitrary `Output` | forward each in order, no reassembly (split pre-cuts logical segments) |
`Config` (`:156`): `chunk_size`, `carry_headroom`, `ring_slots`, `initial_carry`, `slot_fill`
(slot size = `carry_headroom + chunk_size`). `SlotFill` (`:141`): **`Incremental`** grows a slot to
the bytes read (small/partial inputs); **`Big`** sizes once and reuses without re-zeroing (planet-scale).
**Async sibling** `src/gatling_io.rs` (`gatling::io`) — same invariants on tokio: `run` /
`run_ordered`, bound by `max_in_flight`; payloads are `bytes::Bytes` **moved, never cloned**. For
I/O-bound work (e.g. S3 multi-PUT).
The **1→32→1 principle**: 1 reader only reads (a cheap `O(n_workers)` candidate-offset split, no CPU
work); N workers carry a unit through **all** heavy stages — boundary-find, decode, parse, encode,
sort — with no barrier and self-dispatch; 1 writer only stitches in order. Heavy work on a 1-end is
the serial ceiling.
## stree
`src/stree.rs` — a **static search tree** for id→position lookup under the OSM node store, re-exported
into `osm-katana` as `stree64`. A cache-line **S⁺-tree** with **branchless SIMD compare** and
**prefetched batch traversal**.
| type / fn | signature | note |
|---|---|---|
| `STree64` | `pub struct` (`:55`) | in-memory tree |
| `STree64Mmap` | `pub struct` (`:175`) | internal nodes only; mmap is the leaf layer |
| `find_exact` | `(q) → Option<usize>` (`:123`) | serial lookup |
| `batch_stream::<P>` | `(&[i64]) → Vec<Option<usize>>` (`:773`) | software-pipelined + prefetched |
| `lookup_batch_pipeline::<16>` | `(&[i64], mmap) → Vec<…>` (`:387`) | mmap-backed batch |
| `count_lt` | AVX2, dispatched once per query/batch (`count_lt_avx2`) | branchless node compare |
| `advise_hugepage` | `(&[T])` (`:487`) | THP hint for the RAM-bound regime |
Derived from **Ragnar Groot Koerkamp**'s `static-search-tree` (MIT, © 2025) — acknowledged in
`stree.rs:3`. Our contribution at i64 width: `B=16` (two cache lines) internal nodes.