Engineering Atlas › System Design Fundamentals

Shrinking data: how compression works

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Back-references

An LZ77-style compressor slides a window over recent input. At each position it searches the window for the longest earlier match and emits a token "go back d bytes and copy n" instead of the bytes themselves. Repetitive data (logs, JSON keys, HTML tags) shrinks dramatically. Larger windows find more matches but need more memory on both sides; gzip's window is 32 KB (RFC 1951), while zstd can use windows of many megabytes.

Entropy coding

After matching, the remaining literals and token fields are encoded by frequency. Huffman coding assigns shorter bit strings to common symbols. Newer codecs such as zstd use asymmetric numeral systems (ANS), which approach the theoretical limit with fast table-driven decoding. Entropy coding is why already-random data (encrypted bytes, JPEG, video) does not compress: there is no skew left to exploit.

Levels and asymmetry

Higher levels search harder for matches. Compression slows sharply while decompression speed stays roughly constant, which is why "compress once, read many" data (static assets, archived logs, data lake files) can use high levels cheaply. As a rough single-core guide: LZ4 compresses at several hundred MB/s and decompresses at multiple GB/s; zstd at low levels compresses at a few hundred MB/s with ratios close to gzip's; gzip at its default level manages tens of MB/s. The zstd project's own lzbench run on the Silesia corpus shows the shape: zstd level 1 reaches ratio 2.90 at 510 MB/s compress and 1,550 MB/s decompress, zlib level 1 reaches 2.74 at 105 and 390 MB/s, and LZ4 reaches 2.10 at 675 MB/s and 3,850 MB/s (zstd README). Benchmark on your own data before trusting any table.

Encodings that exploit structure

Columnar formats (Parquet, ORC, ClickHouse) store each column together, so values are similar and small. They apply dictionary encoding (replace a repeated string with a small integer), run-length encoding (store "US" x 4,000 once), delta encoding (store differences between sorted timestamps), and bit packing (store values 0 to 15 in 4 bits). A general codec then runs on top. Ratios of 10x or more on event data are common.

Small messages and dictionaries

A 300-byte JSON message barely compresses alone because the window is empty at the start. Trained dictionaries (zstd supports these) pre-load common substrings, so small payloads compress well. Both sides must agree on the dictionary version. The web now has a standard way to do this: RFC 9842 (September 2025) lets a server mark a response with Use-As-Dictionary, and later requests that send its hash in Available-Dictionary can receive dcb (Brotli) or dcz (zstd) responses compressed against it, so a new version of a JavaScript bundle ships as a small delta (RFC 9842).

Down the stack

Layer 1The contract

A lossless codec promises exact round trips: decompressing the output yields the input byte for byte. It promises nothing about ratio, and random input can grow slightly. Container formats add integrity checks: gzip ends with a CRC32 and the uncompressed length modulo 2^32 (RFC 1952), and zstd frames can carry a content checksum, the low 4 bytes of an XXH64 hash (RFC 8878). A frame header also declares the window size, which bounds how much memory a decoder needs; a decoder that honours a configured maximum can refuse frames that would need more.

Layer 2The mechanism

DEFLATE (used by gzip and zlib) finds LZ77 matches of 3 to 258 bytes at distances up to 32,768, then Huffman-codes literals, lengths and distances per block, with either fixed or block-specific code tables. LZ4 skips entropy coding: each sequence starts with a token byte holding a 4-bit literal length and a 4-bit match length, followed by the literals and a 2-byte offset into a 64 KB window, which is why it decodes so fast (LZ4 block format). zstd splits input into blocks of up to 128 KB, Huffman-codes the literals, and codes each sequence (literal length, match length, offset) with Finite State Entropy, a table-driven ANS coder. It also keeps recent offsets as "repeat codes", supports levels from negative (faster) up to 22, with 3 as the default, and can use trained dictionaries. The format is RFC 8878 (2021), which replaced RFC 8478. On HTTP, clients advertise Accept-Encoding: gzip, br, zstd and servers reply with Content-Encoding. Chrome 123 turned on zstd in March 2024 (zstd v1.5.6 release), and RFC 9659 (September 2024) then required that a zstd response never need a window above 8 MB, because browsers that capped memory were failing to decode larger ones (RFC 9659). A server that compresses at high zstd levels for HTTP must cap the window, or some clients will fail.

Layer 3The machine

Match finders hash the next 4 to 8 bytes into a table of recent positions; keeping that table within L2 cache (a few hundred KB) is what separates hundreds of MB/s from tens. Decoders avoid bit-by-bit tree walks by using lookup tables indexed by the next 8 to 12 bits, so decoding is mostly sequential memory copies. Memory is per stream: a compressor at a mid level can use several MB, and a server holding 10,000 concurrent compressed streams can spend gigabytes on codec state. Throughput must be compared with the link: a 10 Gbps NIC carries about 1.25 GB/s, so a single-core gzip at 50 MB/s becomes the bottleneck long before the network does. Storage engines compress per block (a 16 KB database page, a 128 KB filesystem record), and each block restarts the window, so small blocks compress worse.

Why it's built this way

  1. Real data repeats itself, so back-references to earlier bytes remove most redundancy.
  2. Searching for matches is the expensive part, so levels trade search effort for ratio, and decoding stays cheap.
  3. What remains after matching is skewed, so entropy coding spends fewer bits on common symbols.
  4. Memory and caches are finite, so windows and hash tables are bounded, which limits how far back a match can reach.
  5. Random access needs independent blocks, so storage compresses per block and accepts a lower ratio.

Diagram

flowchart LR
    IN["Raw bytes"] --> M["Match finder (window search)"]
    M --> T["Tokens: literals + (distance, length)"]
    T --> E["Entropy coder (Huffman / ANS)"]
    E --> OUT["Compressed frame"]
    OUT --> D["Decoder"]
    D --> C["Copy from history"]
    C --> RAW["Original bytes"]

Worked example

A logging pipeline ships 2 TB per day of JSON logs from 500 hosts to object storage, then queries them with a warehouse. Raw, that is about 185 Mbps sustained across the fleet, and storage at roughly 0.02 dollars per GB-month costs about 1,200 dollars per month for every month retained.

The decision: zstd on the wire, Parquet at rest, and keep raw text only for the last 24 hours.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
LZ4 / SnappyVery fast both ways, low CPUModest ratioHot paths, RPC, database pages, caches
zstdWide level range, dictionariesNot universal in old clientsDefault for new systems and storage
gzip / deflateSupported everywhereSlow, mediocre ratioCompatibility with any client
BrotliBest ratio for web text at high levelsSlow compression at high levelsStatic assets compressed at build time
Columnar encodings10x or more on structured dataBatch-oriented, not for point writesAnalytics and data lakes

Pitfalls in production

Leadership lens

Check yourself

  1. Why does a bigger compression level barely slow decompression?

    Show answer

    Extra effort goes into searching for better matches; the decoder just follows the chosen tokens, so its work stays about the same.

  2. Why do 300-byte messages compress poorly, and what helps?

    Show answer

    The match window starts empty, so there is little history to reference; a shared trained dictionary supplies that history.

  3. Why must you compress before encrypting?

    Show answer

    Good encryption output looks random, and random data has no repeats or skew for a compressor to exploit.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →