Zstd Compression, in depth: frames and blocks, LZ77 sequences and repeat offsets, Huffman and FSE stages, dictionaries and window limits

The pipeline: matches, literals, entropy

Every LZ-family compressor bets that data repeats itself. At each position it looks for an earlier occurrence of the following bytes; unmatched bytes become literals and a match becomes an offset and a length. Zstd groups these into sequences: literals length (how many literal bytes come first), offset, and match length. The minimum match length in the format is 3 bytes.

Zstd then compresses each of those streams separately. Literals are byte values and go through Huffman coding. The three numbers of each sequence are mapped to codes plus extra bits, and the codes are entropy-coded with FSE, Finite State Entropy, a table-driven form of asymmetric numeral systems (tANS). The entropy coding overview explains why ANS reaches arithmetic-coding efficiency at Huffman-like speed. Splitting the model this way means the decoder runs two tight table-driven loops and one memory-copy loop, which is why decompression speed barely depends on the level.

Frames and blocks

A zstd file is one or more frames, back to back. Each frame begins with the magic number 0xFD2FB528, stored little-endian as the bytes 28 B5 2F FD. The frame header starts with a descriptor byte whose bits say which optional fields follow:

If the single-segment flag is clear, one Window_Descriptor byte follows. Its top 5 bits are an exponent and its low 3 bits a mantissa: windowLog = 10 + exponent, and Window_Size = 2^windowLog plus mantissa eighths of that. The byte 0x58 means a 2 MiB window; 0x5D means 2 MiB plus five eighths, 3.25 MiB. The window is the promise the encoder makes: no match will reach further back than this, so the decoder needs only this much history.

Blocks follow. Each has a 3-byte little-endian header: bit 0 is Last_Block, bits 1-2 the block type, and the top 21 bits the size. A raw block holds that many bytes verbatim. An RLE block holds one byte, repeated size times. A compressed block holds a literals section and a sequences section. Type 3 is reserved and must be rejected as corrupt. No block may exceed the smaller of the window size and 128 KB, so a decoder can size its buffers from the header. Frames can be concatenated, and skippable frames (magic numbers 0x184D2A50 to 0x184D2A5F) let you embed metadata that every decoder steps over.

A decoder for the frame layer

The frame layer is small enough to implement directly, and doing so is the fastest way to understand it. This decoder handles frames made of raw and RLE blocks, which is what zstd emits for incompressible data and long runs, and refuses compressed blocks rather than guessing.

import struct
MAGIC = 0xFD2FB528

def parse_frame_header(buf, pos=0):
    if struct.unpack_from("<I", buf, pos)[0] != MAGIC:
        raise ValueError("not a zstd frame")
    fhd = buf[pos + 4]; pos += 5
    if fhd & 0x08:
        raise ValueError("reserved bit set")
    fcs_flag, single = fhd >> 6, (fhd >> 5) & 1
    window = None
    if not single:
        wd = buf[pos]; pos += 1
        log = 10 + (wd >> 3)
        window = (1 << log) + ((1 << log) // 8) * (wd & 7)
    did_size = (0, 1, 2, 4)[fhd & 3]
    dict_id = int.from_bytes(buf[pos:pos + did_size], "little") if did_size else None
    pos += did_size
    fcs_size = (1 if single else 0, 2, 4, 8)[fcs_flag]
    fcs = None
    if fcs_size:
        fcs = int.from_bytes(buf[pos:pos + fcs_size], "little") + (256 if fcs_size == 2 else 0)
        pos += fcs_size
    return dict(window=window if window is not None else fcs, content_size=fcs,
                checksum=bool(fhd & 4), dict_id=dict_id), pos

def decode_simple_frame(buf, max_window=8 << 20):
    hdr, pos = parse_frame_header(buf)
    if hdr["window"] is not None and hdr["window"] > max_window:
        raise ValueError("window larger than this decoder allows")
    block_max = min(hdr["window"] or (128 << 10), 128 << 10)
    out = bytearray()
    while True:
        bh = int.from_bytes(buf[pos:pos + 3], "little"); pos += 3
        last, btype, size = bh & 1, (bh >> 1) & 3, bh >> 3
        if size > block_max:
            raise ValueError("block exceeds Block_Maximum_Size")
        if btype == 0:
            out += buf[pos:pos + size]; pos += size
        elif btype == 1:
            out += bytes([buf[pos]]) * size; pos += 1
        elif btype == 2:
            raise NotImplementedError("compressed block needs Huffman + FSE")
        else:
            raise ValueError("reserved block type")
        if last:
            break
    if hdr["content_size"] is not None and hdr["content_size"] != len(out):
        raise ValueError("content size mismatch")
    return bytes(out), pos + (4 if hdr["checksum"] else 0)

A hand-built test frame shows every byte. Magic, then descriptor 0x20 (single segment, 1-byte content size), then content size 8, then a raw block header 18 00 00 (size 3, not last) with abc, then an RLE block header 2B 00 00 (size 5, type 1, last) with x:

28 b5 2f fd 20 08 18 00 00 61 62 63 2b 00 00 78   ->   b"abcxxxxx"

Sixteen bytes decode to eight. The point is that you can now read any zstd header in a hex dump: window, content size, checksum flag and dictionary id.

Sequences and repeat offsets

After a compressed block's literals and sequences are entropy-decoded, the decoder executes the sequences: copy literals_length literal bytes to the output, then copy match_length bytes starting offset bytes back. A match may overlap its own output: offset 2 with length 10 after ab produces abababababab, so the copy must go byte by byte, or in chunks no longer than the offset.

Offsets are where zstd adds a clever trick. Structured data repeats at the same distance: fields in fixed-size records, columns in a table. So the decoder keeps the three most recently used offsets, starting at 1, 4 and 8. An offset_value of 1 to 3 means reuse one of them, which costs almost nothing to encode; a value above 3 means a new offset of value minus 3. When literals_length is 0 the meanings shift by one, because repeating the immediately previous offset with no literals in between would just have extended the previous match; value 3 then means the most recent offset minus one byte.

def execute_sequences(literals, sequences, out, reps):
    lit = 0
    for ll, ov, ml in sequences:
        out += literals[lit:lit + ll]; lit += ll
        if ov > 3:                                   # a new offset
            off = ov - 3
            reps[:] = [off, reps[0], reps[1]]
        else:                                        # a repeat offset
            idx = ov if ll == 0 else ov - 1
            if idx == 3:
                off = reps[0] - 1
                reps[:] = [off, reps[0], reps[1]]
            else:
                off = reps[idx]
                if idx:
                    reps[:] = [off] + [r for j, r in enumerate(reps) if j != idx]
        if off == 0 or off > len(out):
            raise ValueError("offset reaches before the start of the window")
        start = len(out) - off
        for i in range(ml):                          # overlap-safe copy
            out.append(out[start + i])
    out += literals[lit:]                            # trailing literals
    return out

We traced it against the rules in RFC 8878 section 3.1.1.5: starting from (1, 4, 8), new offsets 1111, 2222, 1111 and 3333 followed by repeat code 2 give history (1111, 3333, 2222), as the rules require. The bounds check matters more than it looks; a decoder without it reads memory before its buffer when fed a crafted file.

The entropy stages

Literals. The literals section can be raw, RLE, Huffman-compressed with a table in the block, or treeless, which reuses the previous block's Huffman table and saves its description. Huffman codes are capped at 11 bits so decoding uses small, cache-resident tables, and large literal sections are split into 4 streams so a modern CPU can decode them in parallel. The Huffman coding article covers the base algorithm.

Sequences. Each of the three sequence fields has its own FSE table, with four modes: predefined (a default in the spec), RLE (one symbol), FSE-compressed (a distribution in the block, accuracy log at most 9 for length codes and 8 for offset codes), or repeat (reuse the previous block's table).

Read backwards. FSE and Huffman bitstreams are read backwards. The decoder decodes sequences first to last, so the compressor must encode the last sequence first.

Levels, strategies and tool options

The zstd tool exposes the encoder side, which is where all the variation lives:

Behind the levels are nine match-finder strategies, from fast and dfast (hash tables) through greedy and lazy to the binary-tree btopt, btultra and btultra2 parsers. The man page's rule of thumb: compression speed halves about every two levels. Decompression is unaffected.

Dictionaries for small payloads

Small payloads compress badly with any LZ codec: a 400-byte JSON message has nothing earlier in itself to match. A dictionary fixes that by giving both sides shared history before the first byte. Train it on more than 100 representative samples (the man page's advice) with zstd --train samples/* -o dict, then pass -D dict on both ends. The frame header records the dictionary id, so a decoder can refuse the wrong one; --no-dictID drops it and the check with it.

Treat a dictionary as a schema: version it and keep every one that retained data was written with, because losing it makes that data unreadable.

Operational guidance

• Know which memory limit applies. There are three distinct numbers. RFC 8878 recommends decoders support windows of at least 8 MB. RFC 9659 requires HTTP Content-Encoding: zstd decoders to support up to 8 MB, and encoders not to exceed it. The zstd CLI by default refuses to decompress with more than 128 MiB of window unless given --memory or --long. A file written with --long=30 fails on a default decoder.
• Cap the window on untrusted input. A frame can declare a huge window or content size. Set a decoder limit, as max_window does above, and reject before allocating.
• Turn on checksums for storage. --check is the CLI default; library users should set the checksum flag explicitly. Without it, corruption that still parses passes silently.
• Frame for random access. One huge frame must be decompressed from the start to read its end; chunk it.
• Measure on your data. Compare levels 1, 3, 9 and 19 for ratio, compression throughput and decompression throughput with zstd -b1 -e19 file.

Failure modes

Trade-offs

Against gzip, zstd usually gives a better ratio and faster decompression. Against LZ4, fast zstd levels trade some speed for ratio. Against xz, top levels come close in ratio while decompressing far faster. For some text, a Burrows-Wheeler compressor may still win on ratio. For how codec choice plays out in a warehouse, see Hive compression options. Verify each of these on your own data; ratios swing widely with input type.

What to do next

1. Run the frame parser on one of your own .zst files and read its window, content size and checksum flag.
2. Benchmark levels 1 to 19 on a representative sample and pick by your read/write mix.
3. If payloads are small, train a dictionary and measure the gain on a holdout set.
4. Decide a maximum window for every reader you run, browsers included, and enforce it on the writer side.
5. Enable checksums and frame data in chunks sized for your random-access pattern.
6. Read RFC 8878 sections 3 and 4 with the decoder above open beside it.