Zstandard (Zstd) Compression

Overview

Zstandard (Zstd) is a real-time lossless compression algorithm developed by Yann Collet at Facebook (now Meta) and released as open source in 2016. It was designed to overcome the long-standing trade-off between compression ratio and speed that had constrained older algorithms like gzip and zlib. Zstd achieves compression ratios comparable to or better than gzip at levels 1–6, while decompressing at speeds an order of magnitude faster — typically exceeding 1 GB/s on modern hardware without special hardware acceleration.

The algorithm is built around a finite-state entropy (FSE) coder and a modified LZ77 back-reference scheme, combined with Huffman coding for literals. One of its most powerful features is dictionary compression: by training a shared dictionary on a representative corpus of your actual data, small records (a few hundred bytes to a few kilobytes) can be compressed far more aggressively than would be possible with a cold compressor. This is especially important in database workloads where individual SSTable blocks, WAL records, or network-transferred row batches are too small for standard compression to find sufficient redundancy.

In a distributed database ecosystem, Zstd serves as the primary compression codec across three distinct planes: the SSTable storage layer, the write-ahead log (WAL), and the wire protocol used when streaming bulk data between nodes. Understanding how to configure compression levels, when and how to train dictionaries, and how to use the streaming API correctly are all prerequisites for tuning a database’s storage efficiency and network throughput.

Core Concepts

How It Works

Internally, Zstd operates in two passes per block. The first pass runs a hash-chained or binary-tree match finder (depending on the level) over the input to identify back-references into a sliding window. The window size scales with the compression level: at level 1 it is 256 KB; at level 22 it is 128 MB. The second pass entropy-codes the resulting sequence of literals and match descriptors using FSE (a tANS variant) for match lengths, offsets, and literal lengths, and Huffman coding for the literal bytes themselves. This two-layer entropy coding is what gives Zstd its density advantage over zlib at equivalent speeds.

Decompression reverses the process: the FSE and Huffman tables are stored in the frame header and used to decode sequences, then back-references are resolved against the decompressed history buffer. Because decompression only needs to resolve references (no search), it is almost entirely memory-bandwidth bound and achieves multi-GB/s throughput even on a single core. This asymmetry — slow compression, fast decompression — maps perfectly onto database workloads where you write once (compaction) and read many times (queries).

Go: SSTable Block Compression with Dictionary

The following example shows how an LSM-tree SSTable writer trains and applies a Zstd dictionary to compress 4 KB data blocks. It uses the klauspost/compress/zstd package, which exposes the full Zstd C library API through pure Go with cgo-free bindings.

package sstable

import (
    "bytes"
    "fmt"
    "io"

    "github.com/klauspost/compress/zstd"
)

// DictTrainer accumulates sample blocks and trains a Zstd dictionary.
type DictTrainer struct {
    samples [][]byte
    maxSize int // total bytes to collect before training
}

func NewDictTrainer(maxBytes int) *DictTrainer {
    return &DictTrainer{maxSize: maxBytes}
}

// AddSample adds a raw (uncompressed) block to the training set.
func (dt *DictTrainer) AddSample(block []byte) bool {
    dt.samples = append(dt.samples, append([]byte(nil), block...))
    total := 0
    for _, s := range dt.samples {
        total += len(s)
    }
    return total >= dt.maxSize
}

// Train returns a Zstd dictionary of the requested size (typically 32768 bytes).
func (dt *DictTrainer) Train(dictSize int) ([]byte, error) {
    dict, err := zstd.BuildDict(zstd.WithDictSamples(dt.samples...), zstd.WithDictSize(dictSize))
    if err != nil {
        return nil, fmt.Errorf("dict training failed: %w", err)
    }
    return dict, nil
}

// BlockCompressor compresses individual SSTable blocks using a pre-trained dictionary.
type BlockCompressor struct {
    enc *zstd.Encoder
}

func NewBlockCompressor(dict []byte, level zstd.EncoderLevel) (*BlockCompressor, error) {
    opts := []zstd.EOption{
        zstd.WithEncoderLevel(level),
        zstd.WithEncoderDict(dict),
        // Reuse the window across Reset() calls for zero-alloc hot path.
        zstd.WithWindowSize(1 << 17), // 128 KB window for level 3
    }
    enc, err := zstd.NewWriter(nil, opts...)
    if err != nil {
        return nil, err
    }
    return &BlockCompressor{enc: enc}, nil
}

// Compress compresses src into dst, returning the number of bytes written.
// dst must be pre-allocated to at least zstd.CompressBound(len(src)).
func (bc *BlockCompressor) Compress(dst, src []byte) ([]byte, error) {
    return bc.enc.EncodeAll(src, dst[:0]), nil
}

// BlockDecompressor decompresses SSTable blocks using the same dictionary.
type BlockDecompressor struct {
    dec *zstd.Decoder
}

func NewBlockDecompressor(dict []byte) (*BlockDecompressor, error) {
    dec, err := zstd.NewReader(nil, zstd.WithDecoderDicts(dict))
    if err != nil {
        return nil, err
    }
    return &BlockDecompressor{dec: dec}, nil
}

func (bd *BlockDecompressor) Decompress(dst, src []byte) ([]byte, error) {
    return bd.dec.DecodeAll(src, dst[:0])
}

// StreamCompressor wraps a zstd streaming encoder for WAL tail writes.
// Each Flush() call completes a Zstd frame so readers can tail the log.
type StreamCompressor struct {
    enc *zstd.Encoder
    w   io.Writer
}

func NewStreamCompressor(w io.Writer, dict []byte) (*StreamCompressor, error) {
    enc, err := zstd.NewWriter(w,
        zstd.WithEncoderLevel(zstd.SpeedDefault), // level 3
        zstd.WithEncoderDict(dict),
        zstd.WithEncoderConcurrency(1), // single writer; no internal goroutines
    )
    if err != nil {
        return nil, err
    }
    return &StreamCompressor{enc: enc, w: w}, nil
}

func (sc *StreamCompressor) Write(p []byte) (int, error) {
    return sc.enc.Write(p)
}

// Flush closes the current Zstd frame and starts a new one.
// WAL readers can decompress up to this boundary without waiting for more data.
func (sc *StreamCompressor) Flush() error {
    return sc.enc.Flush()
}

func (sc *StreamCompressor) Close() error {
    return sc.enc.Close()
}

// Example: compress a batch of WAL records, flushing after each transaction.
func ExampleWALWrite(compressor *StreamCompressor, record []byte) error {
    if _, err := compressor.Write(record); err != nil {
        return fmt.Errorf("write record: %w", err)
    }
    // Flush after each committed transaction so a tail reader can catch up.
    return compressor.Flush()
}

Zig: Streaming Zstd for Network Transfer

A distributed database’s networking layer can use Zig’s standard library std.compress.zstd (available from Zig 0.12) to compress bulk row batches before writing them to a TCP stream. The following example shows an encoder that wraps an underlying std.net.Stream and compresses data at level 6 for a balance of ratio and CPU cost suitable for LAN transfers.

const std = @import("std");
const zstd = std.compress.zstd;

/// ZstdWriter wraps any std.io.Writer and compresses data on the fly.
/// Caller must call flush() after writing a complete logical message so
/// the remote end can decompress without waiting for more data.
pub fn ZstdWriter(comptime UnderlyingWriter: type) type {
    return struct {
        const Self = @This();

        compressor: zstd.Compressor(UnderlyingWriter),

        pub fn init(
            allocator: std.mem.Allocator,
            underlying: UnderlyingWriter,
            level: zstd.CompressionLevel,
        ) !Self {
            return Self{
                .compressor = try zstd.compressor(underlying, .{
                    .level = level,
                    .allocator = allocator,
                }),
            };
        }

        pub fn writer(self: *Self) zstd.Compressor(UnderlyingWriter).Writer {
            return self.compressor.writer();
        }

        /// Flush finishes the current Zstd frame and begins a new one.
        /// The remote ZstdReader can decompress the completed frame immediately.
        pub fn flush(self: *Self) !void {
            try self.compressor.flush();
        }

        pub fn deinit(self: *Self) void {
            self.compressor.deinit();
        }
    };
}

/// ZstdReader wraps any std.io.Reader and decompresses on the fly.
pub fn ZstdReader(comptime UnderlyingReader: type) type {
    return struct {
        const Self = @This();

        decompressor: zstd.Decompressor(UnderlyingReader),

        pub fn init(
            allocator: std.mem.Allocator,
            underlying: UnderlyingReader,
        ) !Self {
            return Self{
                .decompressor = try zstd.decompressor(underlying, .{
                    .allocator = allocator,
                    .verify_checksum = true,
                }),
            };
        }

        pub fn reader(self: *Self) zstd.Decompressor(UnderlyingReader).Reader {
            return self.decompressor.reader();
        }

        pub fn deinit(self: *Self) void {
            self.decompressor.deinit();
        }
    };
}

/// sendRowBatch compresses and sends a slice of serialized rows over a TCP stream.
/// Each batch is flushed as an independent Zstd frame so partial reads are safe.
pub fn sendRowBatch(
    allocator: std.mem.Allocator,
    stream: std.net.Stream,
    rows: []const []const u8,
) !void {
    const StreamWriter = std.net.Stream.Writer;
    var zw = try ZstdWriter(StreamWriter).init(
        allocator,
        stream.writer(),
        .fast, // corresponds roughly to Zstd level 3
    );
    defer zw.deinit();

    // Write a 4-byte little-endian row count header (uncompressed inside the frame).
    const count: u32 = @intCast(rows.len);
    try zw.writer().writeInt(u32, count, .little);

    for (rows) |row| {
        // Each row is prefixed by its 4-byte length.
        try zw.writer().writeInt(u32, @intCast(row.len), .little);
        try zw.writer().writeAll(row);
    }

    // Flush completes the Zstd frame; the receiver can start decompressing now.
    try zw.flush();
}

/// recvRowBatch decompresses a row batch from a TCP stream.
pub fn recvRowBatch(
    allocator: std.mem.Allocator,
    stream: std.net.Stream,
) ![][]u8 {
    const StreamReader = std.net.Stream.Reader;
    var zr = try ZstdReader(StreamReader).init(allocator, stream.reader());
    defer zr.deinit();

    const count = try zr.reader().readInt(u32, .little);
    var rows = try allocator.alloc([]u8, count);

    for (rows) |*row| {
        const len = try zr.reader().readInt(u32, .little);
        row.* = try allocator.alloc(u8, len);
        try zr.reader().readNoEof(row.*);
    }

    return rows;
}

Go: Dictionary Training Pipeline for WAL Records

In a typical write-ahead log, records share a highly regular structure: a fixed header, a key of bounded length, and a value blob. Training a dictionary on a sample of 1,000–10,000 recent WAL records dramatically improves compression of future records. The following snippet shows the training loop used during compaction when the current dictionary ages out.

package wal

import (
    "encoding/binary"
    "fmt"
    "os"

    "github.com/klauspost/compress/zstd"
)

const (
    DictSize        = 32768  // 32 KB dictionary
    TrainingSamples = 5000   // number of WAL records to sample
    MinSampleBytes  = 50_000 // skip training if corpus is too small
)

// TrainDictionaryFromWAL reads up to TrainingSamples records from the WAL
// segment at segPath and returns a trained Zstd dictionary.
func TrainDictionaryFromWAL(segPath string) ([]byte, error) {
    f, err := os.Open(segPath)
    if err != nil {
        return nil, fmt.Errorf("open WAL segment: %w", err)
    }
    defer f.Close()

    var samples [][]byte
    totalBytes := 0

    for len(samples) < TrainingSamples {
        // WAL record wire format: [4-byte length][record bytes]
        var length uint32
        if err := binary.Read(f, binary.LittleEndian, &length); err != nil {
            break // EOF or truncated segment
        }
        if length == 0 || length > 1<<20 {
            return nil, fmt.Errorf("implausible WAL record length %d", length)
        }
        rec := make([]byte, length)
        if _, err := f.Read(rec); err != nil {
            break
        }
        samples = append(samples, rec)
        totalBytes += int(length)
    }

    if totalBytes < MinSampleBytes {
        return nil, fmt.Errorf("insufficient sample data: %d bytes (need %d)", totalBytes, MinSampleBytes)
    }

    dict, err := zstd.BuildDict(
        zstd.WithDictSamples(samples...),
        zstd.WithDictSize(DictSize),
    )
    if err != nil {
        return nil, fmt.Errorf("dictionary training: %w", err)
    }
    return dict, nil
}

Practical Applications

SSTable Block Compression in an LSM-Tree Engine

An LSM-tree storage engine organizes data into immutable SSTables. Each SSTable is divided into fixed-size blocks (default 4 KB or 16 KB). During compaction, blocks are compressed independently so that point lookups can decompress a single block rather than the entire file. Zstd at level 6 with a dictionary trained on the most recent compaction’s output provides a good balance: ratios of 3x–5x on typical JSON or protobuf values with decompression latencies under 50 microseconds per block on modern hardware.

The dictionary is stored as a metadata block at the beginning of each SSTable file and identified by a 32-bit ID embedded in every compressed block’s Zstd frame header. The block cache stores decompressed blocks, so the decompression cost is paid only on a cache miss. When the cache hit rate is high, upgrading to a more aggressive compression level (e.g., level 12) costs essentially nothing at query time while further reducing disk I/O on cold reads.

WAL Compression

A write-ahead log is a sequential append-only file that records every mutation before it is applied to the memtable. Individual WAL records are small (often 50–500 bytes) and highly repetitive: they share key prefixes, schema field names, and operation codes. Without a dictionary, Zstd achieves only modest ratios on these small inputs because the compressor cannot accumulate enough history within a single record to find redundancy. With a dictionary trained on a recent batch of WAL records, the same records compress at 3x–8x ratio even at level 1, which is fast enough to keep up with multi-GB/s NVMe write throughput.

The WAL writer uses the streaming API so that each committed transaction boundary triggers a frame flush. A tail reader (used for replication or crash recovery) can decompress all fully-flushed frames without waiting for the writer to close the file. The dictionary ID is written into every compressed frame header by the Zstd library automatically, allowing a reader that has multiple dictionaries cached to select the correct one without out-of-band signaling.

Network Transfer Compression

When database nodes transfer bulk data during rebalancing or snapshot shipping, they can wrap the underlying TCP connection in a Zstd streaming encoder at level 3. This reduces network traffic by 60–80% for typical mixed-type row data and more than 90% for write-heavy workloads dominated by repetitive log entries. Level 3 is chosen because it decompresses faster than it compresses, meaning the receiving node’s CPU load from decompression is lower than the sending node’s compression cost — appropriate for scenarios where the receiver is already under query load.

Implementation Patterns

Context Pooling

Both compression and decompression contexts carry significant per-context memory. In a database with many concurrent goroutines or Zig async tasks, a sync.Pool (Go) or a fixed-size free list (Zig) of pre-warmed contexts should be used. The context is Reset() between jobs to clear the previous job’s history, which also clears dictionary references — so the dictionary must be re-applied after each Reset if you want to benefit from it. The klauspost/compress/zstd encoder supports a Reset(writer) method that preserves the encoder options (including the loaded dictionary) while changing the output sink, which is the correct pattern for pooling.

Choosing the Right Level Per Data Tier

Not all data in a distributed database is equally hot. A sensible tiered strategy:

• Level 1: WAL writes, in-memory memtable flush to L0 SSTables. Latency is critical; ratio matters less than throughput.
• Level 3 (default): L1–L2 SSTables, network replication streams. Good ratio with minimal CPU overhead.
• Level 6–9: L3–L4 SSTables that are read infrequently but stored long-term. Compaction is less frequent so higher CPU cost is acceptable.
• Level 12–19: Cold archive tiers, off-site backup snapshots. These are written once and the CPU cost of compression is amortized over months of storage.

Dictionary Lifecycle Management

Dictionaries must be versioned and kept in sync between writers and readers. The recommended pattern is to store the dictionary as a named object in a dedicated metadata table keyed by the dictionary’s Zstd-assigned 32-bit magic ID. When a new compaction cycle trains a fresh dictionary, both the old and new dictionaries remain available until all SSTables or WAL segments using the old dictionary have been compacted away. Only then is the old dictionary entry removed from the metadata table.

Skipping Compression for Already-Compressed Data

Compressing already-compressed data (JPEG images, Parquet files with their own internal compression, encrypted blobs) can expand the output. A storage engine’s block writer can sample the first 512 bytes of each block and check the Zstd compressibility heuristic: if the estimated ratio is below 1.05, the block is stored uncompressed with a single-byte codec flag set to 0x00 (raw) instead of 0x01 (zstd). This avoids wasting CPU and producing larger-than-original blocks for incompressible data.

Frame Size Tuning for Seekable Access

When using the seekable Zstd format for SSTables, the frame size controls the granularity of random access. Smaller frames (4 KB) allow finer-grained point lookups but produce more seek table entries and reduce the compressor’s ability to find cross-block redundancy. Larger frames (64 KB or 256 KB) give better ratios and smaller seek tables but force decompression of more data for point lookups. A typical storage engine defaults to 16 KB frames as a balance, configurable per column family via the block_size and compression_frame_size options.

Common Pitfalls

Using One-Shot API for Unbounded Input

The one-shot CompressAll / EncodeAll API allocates a buffer for the entire output up front. If the input is a full SSTable (potentially hundreds of MB), this causes large, unpredictable GC pressure in Go or a large single allocation in Zig. Always use the streaming API when the input size is unknown or potentially large. The one-shot API is safe only for blocks of known, bounded size (e.g., 4 KB–64 KB SSTable blocks).

Forgetting to Flush the Stream

The Zstd streaming encoder buffers output internally for efficiency. Without an explicit Flush() or Close() call, the compressed data may sit in the internal buffer indefinitely. In a WAL writer this means a crash could lose the most recent records even though they were “written.” Always call Flush() after each transaction boundary, and Close() when the log segment is sealed. In Zig, forgetting deinit() on a compressor that wraps a network writer can produce a truncated final frame that the remote decompressor will reject.

Training Dictionaries on Non-Representative Data

A dictionary trained on data from one schema version will provide poor compression for records from a different schema version. When a database performs a schema migration that significantly changes key or value structure, the dictionary should be retrained immediately rather than waiting for the next scheduled retraining cycle. Monitor the post-compression size of WAL records; a sudden increase in the compressed-to-uncompressed ratio is a reliable indicator that the current dictionary has become stale.

Dictionary ID Collisions

The Zstd library assigns magic IDs to dictionaries in the range 0xEC30A437 to 0xEC30A4FF. If you store multiple dictionaries (one per column family or one per table), the IDs are generated by the library and may collide. Always record the full dictionary bytes alongside the ID in your metadata store, and verify that two dictionaries stored under the same ID are byte-for-byte identical before trusting the ID as a lookup key. A collision will cause silent data corruption: the decompressor will load the wrong dictionary and produce garbled output without returning an error, because the compressed data was valid relative to the dictionary that wrote it.

Decompression Context Reuse Across Goroutines

A ZSTD_DCtx or its Go/Zig wrapper is not goroutine-safe. Sharing a single decompressor across multiple goroutines without a mutex or pool will cause data races and heap corruption. The correct pattern in Go is a sync.Pool of *zstd.Decoder instances; in Zig, use a per-task or per-thread decompressor. This is a common mistake when upgrading a single-threaded prototype to a multi-threaded production path.