Compression Algorithms¶

Why storage engines compress¶

Compression trades CPU time for fewer bytes. In a storage engine, fewer bytes means:

More data per cache byte, if the cache holds compressed blocks (the OS page cache does).
Fewer bytes read and written to disk, which also lowers the cost of write amplification: every compaction rewrite moves compressed bytes.
Less disk space, often the largest cost of a big deployment.

The cost is CPU on every write (compress) and every cache-miss read (decompress). Choosing an algorithm is choosing a point on that trade-off, and that requires knowing how the algorithms work.

Two building blocks¶

Nearly every general-purpose compressor combines two ideas:

Dictionary (LZ77) matching removes repetition: replace a sequence of bytes that appeared recently with a reference (distance back, length).
Entropy coding (Huffman, arithmetic/ANS) removes skew in symbol frequency: give frequent symbols short codes and rare ones long codes.

Algorithm	LZ matching	Entropy coding
LZ4, Snappy	Yes, fast and simple	None
DEFLATE (zlib, gzip)	Yes, 32 KB window	Huffman
Zstandard (zstd)	Yes, large windows, better match finding	Huffman for literals + FSE (tANS) for sequences
LZMA (xz)	Yes, large window, optimal parsing	Range (arithmetic) coding

LZ77: replacing repetition with back-references¶

The compressor walks the input; at each position it looks for the longest earlier occurrence (within a window) of the upcoming bytes.

Worked example. Input (29 bytes):

user:1001,user:1002,user:1003

literals "user:1001,"                 (10 bytes, no earlier match)
match    (distance 10, length 8)      → copies "user:100" from 10 bytes back
literals "2,"
match    (distance 10, length 8)      → "user:100"
literal  "3"

Ten literal bytes plus a few tokens represent the whole string. Decompression is just: copy literals, and for each match copy length bytes from distance bytes back in the output already produced. That is a tight loop of memcpy-like operations, which is why LZ decompression runs at gigabytes per second.

A match may overlap its own output: (distance 1, length 10) after an a produces ten more as — a run-length encoding for free.

Finding good matches is the expensive, compression-side part:

Fast compressors (LZ4, Snappy) hash the next 4 bytes, look up the single most recent position with that hash, and take the match if it exists. One probe per position.
Stronger compressors keep hash chains or binary trees of many candidate positions and search them (zstd's higher levels, zlib -9).
Optimal parsing (zstd's highest levels, LZMA) considers that taking a shorter match now might allow a much longer one later, and chooses the cheapest overall encoding by dynamic programming.

The window size limits how far back matches can reach: 64 KB for LZ4, 32 KB for DEFLATE, up to megabytes or more for zstd and LZMA. For a 4 KB SSTable block compressed on its own, the window is effectively the block itself — which is why per-block compression of small blocks compresses worse than compressing a whole file.

Entropy coding: Huffman¶

After LZ matching, the remaining literals are still bytes from 0–255 with an uneven distribution (in text, e and space are common, Q is rare). Huffman coding builds an optimal prefix code from symbol frequencies:

Make each symbol a leaf weighted by its frequency.
Repeatedly merge the two lightest nodes into a parent whose weight is their sum.
The path from the root to a leaf (left = 0, right = 1) is the symbol's code.

Worked example. Frequencies: a:45, b:13, c:12, d:16, e:9, f:5 (100 symbols).

merge f(5)+e(9)=14; c(12)+b(13)=25; 14+d(16)=30; 25+30=55; a(45)+55=100

codes:  a = 0       (1 bit)
        c = 100     b = 101
        f = 1100    e = 1101    d = 111
total = 45·1 + 12·3 + 13·3 + 5·4 + 9·4 + 16·3 = 224 bits

Fixed 3-bit codes would need 300 bits; Huffman saves ~25%. Huffman must use a whole number of bits per symbol, which wastes space when a symbol's ideal length is fractional (a symbol with probability 0.9 ideally costs 0.15 bits, but gets 1). Arithmetic coding and ANS (asymmetric numeral systems, used as FSE in zstd) encode fractional bits and come within a hair of the entropy limit, with ANS running nearly as fast as Huffman.

The algorithms engines actually use¶

Rough characteristics on typical database blocks (actual numbers vary a lot with data; measure on your own):

Algorithm	Compression speed	Decompression speed	Ratio on text/JSON-like data
LZ4	~500–800 MB/s per core	~3–5 GB/s	~2x
Snappy	~400–600 MB/s	~1.5–2 GB/s	~2x
zstd level 1–3	~300–500 MB/s	~1–1.5 GB/s	~2.5–3x
zstd level 19	~5–20 MB/s	~1–1.5 GB/s	~3.5x+
zlib level 6	~30–80 MB/s	~300–400 MB/s	~3x

Two observations drive most choices:

LZ4 and zstd decompress at roughly the same order of speed no matter the compression level. The level only changes how hard the compressor searches. So data written once and read many times can afford a high level.
zlib is dominated by zstd at almost every point (faster and better ratio), which is why newer systems default to zstd.

Per-level compression in an LSM¶

In leveled compaction, about 90% of the data sits in the bottom level, which is rewritten least often; upper levels are small and rewritten constantly.

Level	Typical choice	Reason
L0–L1	None or LZ4	Rewritten on every compaction; hot for reads; small
Middle levels	LZ4	Cheap CPU per rewrite
Bottom level	zstd (level 3–6)	Holds most bytes; written least often; maximizes space savings

RocksDB exposes this as compression_per_level and bottommost_compression. Since compression happens during flush and compaction — background threads — a heavier algorithm mostly costs background CPU, not foreground latency. Decompression happens on every block-cache miss, in the foreground.

Dictionary compression¶

Small blocks of similar records (4 KB of JSON documents) compress poorly because each block is compressed independently and starts with an empty window: every block repeats the same field names as literals. Dictionary compression primes the compressor with a shared dictionary of common substrings, trained from samples (zstd --train, or RocksDB's max_dict_bytes / zstd_max_train_bytes, which trains a dictionary per SST file from its own data). For small-record workloads, ratios can improve substantially — the field names and common values become references into the dictionary instead of literals.

Lightweight encodings: compressing by structure¶

General-purpose compressors know nothing about the data. Knowing its structure often wins more, at lower CPU cost — this is what columnar formats do before (or instead of) LZ compression:

Encoding	Idea	Good for
Prefix (delta) encoding of keys	Store bytes shared with the previous key once	Sorted keys — every SSTable's data blocks (SSTables and Bloom Filters)
Run-length encoding (RLE)	`(value, count)` for repeated values	Sorted or low-cardinality columns
Dictionary encoding	Replace values by small integer IDs into a table of distinct values	Strings with few distinct values (country, status)
Delta encoding	Store differences between consecutive numbers	Timestamps, sequence numbers, sorted IDs
Bit packing	Use only as many bits as the maximum value needs	Small integers, dictionary IDs
Varint	Small numbers in fewer bytes	Lengths, IDs (Binary Encoding and Checksums)
Gorilla / XOR float encoding	XOR consecutive floats; store only the changed bits	Time-series metrics (Prometheus, Facebook Gorilla)

Worked example — timestamps. 1,000 event timestamps in milliseconds, one per second: 1731229200000, 1731229201000, .... Raw: 8 bytes each = 8,000 bytes. Delta: first value + 999 deltas of 1000. Delta-of-delta: all zeros after the second value. With RLE or bit packing, the column shrinks to a few dozen bytes — far beyond what LZ4 would achieve on the raw bytes.

Where to compress, and costs to keep in mind¶

Block size vs. ratio. Bigger blocks compress better but cost more to read for a point lookup (decompress 64 KB to get one 100-byte value). Point-lookup engines use ~4–16 KB blocks; analytics use much larger units.
Incompressible data. Encrypted or already-compressed values (images, gzip payloads) don't shrink; compressing them wastes CPU. LevelDB stores a block raw if compression saves less than 12.5%.
Compressed vs. uncompressed caching. Caching uncompressed blocks saves CPU per hit; caching compressed blocks holds more data per byte. RocksDB supports both tiers.
Checksums cover the stored (compressed) bytes, so corruption is detected before the decompressor sees malformed input — decompressors should still be treated as parsers of untrusted input.

Common pitfall¶

Picking an algorithm from a published benchmark table instead of from your own data. Compression ratio depends almost entirely on the data: the same zstd level that gives 4x on JSON logs gives 1.05x on UUID keys with random binary values, where it only burns CPU. Before choosing, run zstd -b1 -e19 and lz4 -b on a few real SST files or a dump of real values to see actual ratio and speed per level, and check the block size you will actually use — compressing a 4 KB block is very different from compressing the 1 GB sample file the benchmark used.