Recipe format v3: dictionary plus bit packed slot column instead of one raw digest per slot

[bigerl]

The problem

The recipe is one fixed width entry per slot. Format v1 is a 56 byte header, then slot_count entries of exactly the digest width (16 bytes under xxh3-128), then an 8 byte checksum over the entry area (src/recipe.cpp). recipe::commit serializes the whole file and publishes it by rename on every commit, durable or not.

So the recipe write scales with the number of slots in the store, not with the amount of dirty data. Numbers at 2 MiB blocks:

store size	slots	v1 recipe file
1 TiB	524,288	8.4 MB
10 TiB	5,242,880	83.9 MB
50 TiB	26,214,400	419.4 MB

At 50 TiB a commit that dirties a single 2 MiB slot writes 2 MiB of block file and 419.4 MB of recipe. That is 200x write amplification on the metadata, and it is paid again on the next commit. Commits are frequent, so this becomes the cost of a commit.

The in-memory side is the same shape. recipe::entries is std::vector<block_digest> and sizeof(block_digest) is 33 bytes, so 26.2 million slots cost 865 MB of RAM for the mapping alone.

Measured cost of the current serialization at 26,214,400 slots, one core, Apple M5 Max, Apple clang 21, -O3 -march=native:

• entry fill loop (a 16 byte copy per slot out of the 33 byte block_digest stride): 11.1 ms
• XXH3_64bits over the 419.4 MB entry area: 8.2 ms (51 GB/s)
• reference: memcpy of 419.4 MB: 6.0 ms (70 GB/s)

So about 20 ms of CPU plus a 419.4 MB write and an fsync, on every durable commit, regardless of how many slots changed.

What we want

1. Whole file serialization and load at memcpy class speed, so recipe serialization never becomes the commit bottleneck.
2. A smaller file wherever the data allows it.
3. A layout that later allows rewriting only the touched parts, without changing the crash story (write new, then rename).

Why general purpose byte codecs do not solve this

The payload is xxh3-128 output. As a byte stream it is pseudorandom and incompressible. LZ4 or Zstd can only find two things in a recipe: exact 16 byte repeats produced by dedup, and runs of the zero sentinel. Two problems with that:

• Window. LZ4 matches inside a 64 KiB window. At 16 bytes per slot, 64 KiB is 4,096 slots. A digest shared between slot 0 and slot 20,000,000 sits 320 MB apart and is never matched. Zstd needs long range matching (--long, windowLog 29 or more) to reach that distance, which costs much more time and memory.
• Speed. From LZ4's own benchmark table (Core i7-9700K at 4.9 GHz, single thread, Silesia): memcpy 13,700 MB/s, LZ4 default 780 MB/s compress and 4,970 MB/s decompress. Compressing 419.4 MB at 780 MB/s is about 540 ms, roughly 25x the entire current CPU cost. Decompression at 4,970 MB/s is 36% of memcpy, so even the read path gets slower.

Structural encoding gets the dedup and the empty runs for free, at any distance, with no window and no entropy coder.

Candidate format: dictionary plus a bit packed slot column

Split the file into two parts.

Unique digest table (the dictionary). Every distinct digest once, 16 raw bytes each, in insertion order. This part is incompressible by construction and is written as one contiguous memcpy.

Slot column. One integer per slot, the index of its digest in the dictionary, with a reserved value for the empty sentinel. Width w = ceil(log2(u + 1)) bits, where u is the number of unique digests. This part is highly structured and is bit packed.

Column layout in 1024 value blocks, FastLanes style: 32 lanes of uint32, value i of a block lives in lane i % 32, so the 32 packing chains are independent and the kernel is straight line code with compile time shift amounts. Each block carries a small descriptor and the file carries a block offset directory (25,600 blocks at 50 TiB, 8 bytes each, 205 KB). Per block schemes:

• IDENTITY: the block's indices are base, base+1, ... base+1023. Costs only the descriptor.
• CONSTANT: all slots in the block hold one index. Covers long empty runs and long runs of one shared block.
• BITPACK(w, base): frame of reference base plus w bit packed values.

IDENTITY matters because the dictionary is in insertion order: when there is no dedup, slot i is the i-th new digest, so the column is exactly the identity and collapses to descriptors. That removes the obvious regression case, where indirection would otherwise add a 25 bit index per slot on top of a dictionary that is already as large as the v1 entry array.

Expected file size at 50 TiB, 2 MiB blocks, 26,214,400 slots

case	unique digests u	w	dictionary	column	total	vs v1
no empties, no dedup	26,214,400	25	419.4 MB	0.2 MB (all IDENTITY)	419.6 MB	100%
half the store empty, no dedup	13,107,200	24	209.7 MB	0.2 MB	209.9 MB	50%
10x dedup	2,621,440	22	41.9 MB	72.1 MB	114.2 MB	27%
100x dedup	262,144	19	4.2 MB	62.3 MB	66.5 MB	16%
1024 distinct blocks	1,024	11	0.02 MB	36.0 MB	36.1 MB	9%

The column is the floor: about log2(u) bits per slot when the references are unstructured. A per block frame of reference base cuts it further whenever a block's indices are clustered, which they are when write order and slot order correlate (insertion order follows write order).

Measured kernel throughput

A hand written straight line packer as described above, 26,214,400 values, one core, Apple M5 Max, Apple clang 21, -O3 -march=native:

width	pack	unpack
25 bits	9.4 ms (2.8 G values/s)	5.1 ms (5.2 G values/s)
10 bits	6.6 ms (4.0 G values/s)	3.9 ms (6.8 G values/s)

The same rates hold on a 4 MB cache resident input, so the kernel is compute bound, not bandwidth bound. A naive sequential bit buffer packer reached 1.8 G values/s at 25 bits, so the straight line form is worth the code.

Putting it together for the 10x dedup case: dictionary memcpy 41.9 MB (about 0.6 ms), pack 26.2 M values at 22 bits (about 8.5 ms), checksum over 114 MB (about 2.2 ms). About 11 ms of CPU and 114 MB of I/O, against about 20 ms and 419.4 MB today.

Partial rewrite as a later step

With a block offset directory the column becomes patchable. A commit that touches 1,000 slots repacks at most 1,000 blocks, that is 1.02 M values, measured at 0.37 ms, and needs to write about 2.8 MB of column plus the appended dictionary tail. The dictionary is append only, so new digests go at the end.

This is a follow up, not part of the first change. Writing in place breaks the current write new then rename story and needs its own scheme (a generation flip, or a small log). The first change keeps whole file rewrite and rename.

Implementation notes

The dictionary already exists. block_store keeps refcounts_, a map from digest to reference count, maintained incrementally by add_reference and drop_reference on every recipe entry change. Extend the value to {refcount, dict_index} and keep a parallel std::vector<block_digest> in insertion order plus a free list of dictionary slots whose count fell to zero. Serialization is then a memcpy of that vector.

The in-memory recipe must hold indices, not digests. This is required, not optional. If recipe::entries stays std::vector<block_digest>, serialization needs one hash lookup per slot to find the index: 26.2 million lookups at roughly 10 ns is about 260 ms, worse than the 20 ms it replaces. With entries as std::vector<uint32_t> the commit path already holds the column and serialization is one pack pass. Side effect: the mapping shrinks from 33 bytes per slot to 4, so 865 MB becomes 105 MB at 26.2 M slots, plus 33 bytes per unique digest.

Call sites that consume a digest per slot become one dictionary lookup: the open path that maps each slot (src/region.cpp), the write back path that compares a fresh hash against the current entry, validate_blocks, deep_verify_blocks, and block_store::sweep.

Library or hand rolled. The measured kernel above is about 120 lines for pack and unpack with a compile time width. The engine's dependency set today is small (asio, xxhash, boost headers), and adding a columnar format library for one integer column is out of proportion. Recommendation: hand roll, but keep the on disk layout FastLanes compatible (1024 value blocks, 32 lane transposed order) so a library kernel can replace ours later without a format change.

For reference, the options and their state:

project	license	conan center	note
FastLanes	MIT	no recipe	full file format and kernels, C++, CMake, not header only
FastPFor	Apache-2.0	yes (fastpfor/0.2.0)	SIMD bit packing and PFOR, x86 focused
simdcomp	BSD-3-Clause	no recipe	small C library, SIMD-BP128
streamvbyte	Apache-2.0	yes (streamvbyte/2.0.0)	byte oriented, 1 to 4 bytes per value, so a 1 byte per slot floor and no frame of reference

Open questions

1. Dictionary index reuse. A dictionary slot whose refcount reached zero can be reused, which keeps u near the live unique count but breaks the identity property of the column. When do we compact and renumber instead, and does compaction need a full column rewrite (it does) and therefore a policy?
2. Dictionary order. Insertion order is cheap to maintain, appends only, and gives identity columns. Sorted order would let the dictionary itself shrink (delta on the high 64 bits of sorted 128 bit digests saves roughly 3 of 16 bytes per digest), but a sort of 26.2 M keys per commit is far outside the budget and it destroys the identity property. Confirm insertion order.
3. Empty sentinel. Reserve dictionary index 0, or carry a separate occupancy bitmap. Reserving 0 costs one value of range and shifts the identity column by one. A bitmap is cleaner for CONSTANT empty runs but is a third section.
4. Checksums. Today one xxh3-64 over the whole entry area, 8.2 ms at 419.4 MB. Whole file checksum stays fine for whole file rewrite. Partial rewrite needs per block checksums plus a checksum over the offset directory. Decide now whether v3already carries per block checksums so partial rewrite does not need a v3.
5. Format version. v1 is frozen and the header gate already refuses unknown and newer versions cleanly. v3 is a new version number. Do we keep a v1 writer behind an option for downgrade safety, or is read only support for v1 enough?
6. Block size and width choice. Fixed 1024 values per block, or tie it to the target. Per block width versus one width for the file: per block costs a descriptor and lets empty and identity regions cost nothing.
7. Snapshot staging. The snapshot path writes a recipe into another directory. With insertion order dictionaries that is a copy of the same two sections, worth confirming.
8. Benchmark home. bench/ already has hash_bench and region_bench. A recipe_bench covering serialize, deserialize, pack and unpack at several slot counts and dedup ratios should land with the change so the numbers above become regression tested.

Separate from #47, which is about compressing block file content.

References

• Afroozeh, Boncz. The FastLanes Compression Layout: Decoding > 100 Billion Integers per Second with Scalar Code. PVLDB 16(9), 2023. https://www.vldb.org/pvldb/vol16/p2132-afroozeh.pdf
• FastLanes implementation: https://github.com/cwida/FastLanes
• Lemire, Boytsov. Decoding billions of integers per second through vectorization. Software: Practice and Experience 45(1), 2015. https://arxiv.org/abs/1209.2137
• Lemire, Boytsov, Kurz. SIMD Compression and the Intersection of Sorted Integers. https://arxiv.org/abs/1401.6399 and https://github.com/fast-pack/simdcomp (0.3 cycles per integer on Skylake, more than 8 billion integers per second)
• Lemire, Kurz, Rupp. Stream VByte: Faster Byte-Oriented Integer Compression. https://arxiv.org/abs/1709.08990
• Kuschewski et al. BtrBlocks: Efficient Columnar Compression for Data Lakes. SIGMOD 2023. https://www.cs.cit.tum.de/fileadmin/w00cfj/dis/papers/btrblocks.pdf
• LZ4 benchmark table (memcpy 13,700 MB/s, LZ4 default 780 / 4,970 MB/s, Core i7-9700K, Silesia): https://github.com/lz4/lz4/blob/dev/README.md
• lzbench, for memcpy and codec baselines on one core: https://github.com/inikep/lzbench

[bigerl]

Findings from the #52 investigation that bear on this issue.

Landing order: #52 first. Its manifest carries a per-segment encoding id and a typed section list, so v3 of this issue lands later as a writer change: a new encoding id for segments plus a dictionary section, mixed encodings legal, old raw segments re-encoded lazily as they are dirtied. No format break, no migration. The reverse order freezes a whole-file frame that #52 then replaces immediately.

Two layout rules keep the packed column segmentable, and they should be fixed now:

• block descriptors (scheme, width, base, byte length) live inside the block, not in a file-wide table;
• the offset directory is per segment with segment-relative offsets.

Otherwise a width change or a block that grows dirties every segment after it.

Answers to the open questions, from the #52 side:

1. Index reuse: free-list reuse, preferring holes in the tail chunk and in chunks already dirty this commit. Reuse touches only the dictionary chunk holding the index; no column segment changes (refcount zero means no live slot stores the value). Never compact implicitly: renumbering rewrites every column segment and, under content addressing, unshares every snapshot. Reuse is snapshot-safe only because dictionary chunks are content-addressed and pinned per manifest; with a single mutable dictionary file it would reinterpret every snapshot's column.
2. Order: insertion order, confirmed.
3. Sentinel: reserve index 0, no bitmap. Fully empty segments then have identical bytes, so they dedup to one file, and extend costs manifest records only. A bitmap makes logically identical segments differ in undefined bytes, which kills content-addressed sharing.
4. Checksums: per segment, not per block. Under Recipe writes are O(capacity) per commit: segmented or delta publishing on top of #50 #52 a segment is rewritten whole and its content digest in the manifest is the checksum; per-block checksums add bytes with no partial-rewrite use case.
5. Snapshot staging: a snapshot links the same segment and chunk files; no translation, sharing holds along a lineage.

One warning on splitting the work: do not land the in-memory half (entries as dict indices) before segmentation or before the packed writer. With raw whole-file serialization, indices force one dictionary gather per slot per commit (a 16 byte random read over the dictionary), which regresses the 11 ms fill to an estimated 100 to 200 ms at 50 TiB. Under #52 only dirty segments serialize, so the gather is O(changed) and the pairing is free.