Expand description
kevy-compress — corpus-aware LZ for the tiered value log.
§Why this exists
PostgreSQL compresses per datum and skips values under ~2 KB entirely; a 400 B row’s redundancy lives across rows (field names, enum members, shared prefixes) where a per-datum window cannot see it. kevy’s vlog is a corpus — a contiguous sample of one keyspace — so a dictionary trained on the file reaches the redundancy PG structurally cannot (RFC the premise was measured before a line was written: on identical 400 B values a shared dictionary encodes N values as O(dictionary)
- N × ~9 B while per-datum pays 89 B each, forever).
§The three measured constraints this crate is shaped by
-
Decode ≥ ~1 GB/s: at 100 MiB/s a 4 KiB cold read spends 38 % of its p99 budget in decode; a token + wildcopy design measured ~8 GB/s in its naive form. Speed is a requirement of the design, not a later optimisation.
Met through
Dict, missed throughdecode. The cause was never the token grammar: the dictionary is per-file state and every entry point took it as a per-call argument.examples/decode_budgetmeasures held-out values against a trained dictionary — the shapekevy-vlogproduces — and reports, per value:path decodeDict::decodefast 0.543 GB/s 2.079 GB/s compaction 0.045 GB/s 1.265 GB/s kevy-vlogholds oneDictper file, so a cold read takes the right column.decodestays for callers with nothing to hold it in, and is honest about what it costs.The earlier “order of magnitude above” reading came from
examples/k1_sanity, which trains the dictionary on the same value it compresses; that decodes one long match out of the dictionary at a 41x ratio, which no stored value ever does.The write side had the same shape and is fixed the same way: seeding the match table walks every dictionary position, so encode time was flat in input size — an 8-byte value cost more than a 6 KiB one, because almost none of the work was about the value.
path encodeDict::encodefast 35.2 us/value 0.47 us compaction 38.4 us/value 2.86 us The frames are identical either way —
examples/decode_budgetasserts that before it reports a number, because a speedup that changed what was written would be a different change. -
Never expand: per-datum zlib on random 400 B values grows them by 11 B. The raw-frame fallback is therefore part of the format, not an optimisation.
-
The dictionary carries the corpus claim: match-finding refinements move little; dictionary construction decides how much of the corpus ceiling is captured. Measured, this is the wrong way round on the templated corpus: a brute-force oracle over the same grammar reaches 181.8 B/value where the shipped single-probe finder reaches 220.7 — 17.6 % of frame bytes — and
HT_BITS = 12alone leaves 43.5 % of the dictionary’s distinct 4-grams unreachable, so a bettertraincannot cash in what it produces. Thetrainentry point is deliberately a replaceable policy behind a stable signature.
§Format
A frame is [tag: u8][orig_len: LEB128][payload].
TAG_RAW: payload is the input verbatim. Chosen whenever LZ would not save a byte — never-expanding is structural, not tuned.TAG_LZ/TAG_LZ_DICT: LZ4-style token stream (4-bit literal and match-length nibbles with 255-continuation bytes, 16-bit little-endian offsets, minimum match 4). WithTAG_LZ_DICToffsets may reach back past the start of output into the caller-supplied dictionary, which is virtually prepended history.
The dictionary is a parameter, never a dependency: this crate knows only bytes. Lifecycle (one dictionary per vlog file, seeded across rotation, disposable with the file) belongs to the caller.
use kevy_compress::{encode, encode_high, decode, train};
// No dictionary: an empty one is the ordinary LZ path.
let value = b"user:1 name=ada user:1 name=ada user:1 name=ada";
let frame = encode(b"", value);
assert_eq!(decode(b"", &frame).unwrap(), value);
assert!(frame.len() < value.len(), "repetition should compress");
// Corpus-aware: a dictionary trained on samples that share a shape
// lets a SHORT value reference bytes it never carries itself.
let samples: Vec<&[u8]> = vec![
b"{\"user\":1,\"role\":\"admin\"}",
b"{\"user\":2,\"role\":\"admin\"}",
b"{\"user\":3,\"role\":\"guest\"}",
];
let dict = train(&samples, 4096);
let one = b"{\"user\":9,\"role\":\"admin\"}";
assert_eq!(decode(&dict, &encode(&dict, one)).unwrap(), one);
// `encode_high` spends more time for a smaller frame; both decode
// with the same dictionary.
assert_eq!(decode(b"", &encode_high(b"", value)).unwrap(), value);
// A frame decoded against the WRONG dictionary is refused or wrong —
// never a silent half-value. Truncation is refused outright.
assert!(decode(b"", &frame[..frame.len() / 2]).is_err());Structs§
- Decode
Error - Decode failure: the frame does not decode to exactly what its header promises. Corrupt and truncated frames land here — they are rejected, never mis-decoded.
- Dict
- A dictionary, parsed once.
Constants§
- MAX_
OFFSET - Longest back-reference the 16-bit offset can express, which also bounds how much trailing dictionary is reachable.
- TAG_LZ
- Frame tag: LZ token stream, history is the output alone.
- TAG_LZH
- Frame tag: high (compaction) level — literals Huffman-coded as one block, byte-aligned sequence stream after it.
- TAG_
LZH_ DICT - Frame tag: high level with dictionary history.
- TAG_
LZ_ DICT - Frame tag: LZ token stream, history is
dict ++ output. - TAG_RAW
- Frame tag: payload is the original bytes verbatim.
Functions§
- decode
- Decode one frame produced by
encode.dictmust be the same bytes the encoder was given — the tag records whether the frame depends on it at all. - encode
- Encode
inputinto a frame, usingdictas shared history when it pays. The result is never longer thaninputplus the frame header: when LZ cannot save a byte — incompressible input, adversarial input, anything — the frame stores the bytes raw. - encode_
high - Encode at the compaction level: same match finder, literals pulled
into one Huffman-coded block (zstd’s shape). Strictly
smallest-wins: the result is the smaller of high / fast / raw, so
never-expanding holds here exactly as for
encode. Costs roughly a second serialization pass at encode time — which is the point: a value re-encoded by compaction has proven cold (RFC §3). - train
- Build a dictionary from sample values under a byte budget.