Skip to main content

Crate kevy_compress

Crate kevy_compress 

Source
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 through decode. 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_budget measures held-out values against a trained dictionary — the shape kevy-vlog produces — and reports, per value:

    pathdecodeDict::decode
    fast0.543 GB/s2.079 GB/s
    compaction0.045 GB/s1.265 GB/s

    kevy-vlog holds one Dict per file, so a cold read takes the right column. decode stays 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.

    pathencodeDict::encode
    fast35.2 us/value0.47 us
    compaction38.4 us/value2.86 us

    The frames are identical either way — examples/decode_budget asserts 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 = 12 alone leaves 43.5 % of the dictionary’s distinct 4-grams unreachable, so a better train cannot cash in what it produces. The train entry 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). With TAG_LZ_DICT offsets 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§

DecodeError
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. dict must be the same bytes the encoder was given — the tag records whether the frame depends on it at all.
encode
Encode input into a frame, using dict as shared history when it pays. The result is never longer than input plus 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.