System Design Internals

Compression Algorithms for Systems

A region ships multi-GB JSON logs across a constrained cross-AZ link while SSTables eat disks and Kafka fills disks with chatty events. Compression is not a checkbox—it is a CPU-for-bytes trade you place carefully on the path.

This note covers , LZ and entropy stages, columnar encodings, where to compress in a stack, and how to pick codecs by versus .

Design questions

If yes, pick codec family next.

Where on the path?

Wire, page, column, or archive.

Compress once; decompress many.

Delta / dict before general LZ.

What actually happens

Modern general-purpose compressors combine (find matches) with (spend fewer bits on common tokens). Frames add metadata: window size, dictionary ID, and a checksum so bit flips do not silently corrupt reads.

Systems often compress shaped data, not raw objects. Time-series stores apply ; analytics files use and . HTTP uses so browsers accept br/zstd without the app reinventing codecs.

The design question is rarely “gzip or not.” It is whether CPU on the compress path beats network, disk, or memory bandwidth—and whether decompress sits on the user-facing p99.

How to choose a codec

1. Hot path or cold archive? Hot: LZ4/Snappy/Zstd fast levels. Cold: Zstd high levels or xz.

2. Many small similar messages? Train a or compress batches, not tiny one-offs.

3. Structured columns? Prefer type-aware encodings first; general LZ second.

Simple rule of thumb

Skip encrypted and already-compressed payloads. Prefer Zstd as a default balanced codec, LZ4 when decompress latency dominates, and columnar/dictionary encodings before throwing general compression at tables. Measure ratio and CPU on your data.

Compress pipeline

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

flowchart TD
    Raw[Raw bytes] --> Dec{Already compressed / encrypted?}
    Dec -->|Yes| Skip[Skip or pass-through]
    Dec -->|No| Shape[Optional shaping: dictionary / delta / bit-pack]
    Shape --> LZ[LZ match finder]
    LZ --> Ent[Entropy stage: Huffman / ANS]
    Ent --> Out[Compressed frame + checksum]
    Out --> Use[Disk / network / cache]
    Use --> Dec2[Decompress on read path]
    Dec2 --> Verify[Checksum / CRC]
    Verify --> App[Application bytes]

plaintext

Rough mental model:
  residual entropy ≤ original entropy
  LZ reduces redundancy by references into a window
  entropy coder approaches Shannon for the residual symbol stream

Do not expect wins on:
  TLS ciphertext, JPEG/PNG/MP4, high-quality random keys
  already zstd'd Kafka batches re-gzipped at HTTP

Always:
  checksum the frame (xxHash/CRC)
  version the codec + dictionary ID
  bound max decompressed size (zip-bomb / expansion attacks)

Where compression sits in the stack

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

flowchart LR
    C[Client] -->|HTTPS body br/zstd| E[Edge / CDN]
    E -->|optionally recompress| O[Origin]
    O --> Q[Queue / Kafka compressed batches]
    O --> DB[(Pages / SSTables / Parquet)]
    DB --> Bak[Cold archive: higher ratio]
    Q --> W[Workers decompress once]

Layer	Typical codecs	Notes
HTTP / CDN	br, zstd, gzip	Text assets; honor Accept-Encoding
RPC / queues	LZ4, Zstd	Batch small messages; shared dicts
DB pages / WAL	LZ4, Snappy, Zstd	Page-sized units; fast decompress
Analytics files	Dict + RLE + Zstd	Column/page codecs in Parquet
Cold backup	Zstd-19, xz	CPU offline; maximize ratio

CPU versus network versus disk

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

sequenceDiagram
    autonumber
    participant App as App CPU
    participant Net as NIC / WAN
    participant Disk as Disk

    Note over App,Disk: 1 GB JSON log, 4:1 ratio, 250 MB compressed
    App->>App: compress @ 400 MB/s → 2.5 s CPU
    App->>Net: send 250 MB @ 100 MB/s → 2.5 s
    Note over App,Net: Uncompressed send 1 GB @ 100 MB/s → 10 s
    App->>Disk: write 250 MB cheaper on space and often on IO

plaintext

Break-even sketch:
  compress_time + transfer_time(compressed) + decompress_time
    < transfer_time(raw)   // network case

  or compressed_bytes * storage_cost + CPU_cost
    < raw_bytes * storage_cost   // storage case

Order-of-magnitude (illustrative, measure yours):
  LZ4:   ~GB/s compress/decompress, modest ratio
  Zstd-3: hundreds of MB/s, strong ratio on text
  gzip:   slower; legacy interop
  xz:     slow compress; cold data only

Read-heavy tip:
  pay compress on write; optimize decompress for queries
  store compressed pages; decompress only touched pages

Codec field guide

LZ4 / Snappy: prioritize speed. Ideal for database pages, real-time pipelines, and in-memory frames where ratio is secondary. Snappy is common in Hadoop/Cassandra ecosystems; LZ4 dominates many modern stores.

Zstd: tunable levels, excellent ratio/speed Pareto, optional trained dictionaries. Default recommendation when you control both ends.

Deflate / gzip / zlib: universal HTTP and file interop. Usually dominated by Zstd or Brotli on ratio/speed, but everywhere.

Brotli: strong on static web text; slower compress makes it better for precompressed assets than for dynamic ultra-hot paths unless levels are capped.

plaintext

Selection cheat sheet:
  dynamic API JSON over WAN     → zstd or br (edge), skip if tiny
  Kafka / Pulsar batches        → lz4 or zstd (broker + client agree)
  RocksDB / LSM data blocks     → lz4 or snappy; zstd if cold tier
  Parquet page                  → encoding (dict/delta) + zstd/gzip
  container image layers        → gzip/zstd as format dictates
  cross-region backup           → zstd high level or xz

Shaping: dictionary, delta, RLE

Dictionary

Low-cardinality strings → int IDs. Huge win before bit-packing or LZ.

Delta / XOR

Monotonic timestamps and counters become small integers; then varint or bit-pack.

RLE / bit-pack

Runs of nulls or bools collapse. Bit-packing packs 10-bit IDs without padding to 32.

stacks these per page. A row-oriented JSON blob of the same table rarely matches Parquet ratios even under Zstd-19, because types never get specialized treatment.

Small messages and shared dictionaries

LZ needs a window of history. A 200-byte protobuf has little self-overlap, so naive per-message compression can expand or barely help. Fix by batching many messages into one frame, or by shipping a trained that both peers load. Version that dictionary like a schema: mismatch means hard failure or a negotiated fallback.

plaintext

Patterns:
  1. Batch 100 metrics → one zstd frame
  2. Train dict on 10k sample records; embed dict id in envelope
  3. Static schema prefix compression (strip repeated field tags carefully)

Anti-patterns:
  gzip each 80-byte log line independently
  compress under TLS and also store ciphertext compressed (usually useless)
  unbounded decompress allocation from untrusted frames

HTTP and caching pitfalls

must interact with caches correctly. Store variants by encoding, set Vary: Accept-Encoding, and prefer precompressed static assets at the CDN so origins do not recompress every hit. Do not double-compress images. For APIs, compress large JSON responses; skip sub-kilobyte bodies where overhead dominates.

SD use cases

LSM / block stores

Compress data blocks; keep indexes less aggressively compressed if they are latency-critical. Pick LZ4/Snappy for hot levels; Zstd for colder levels. Compaction is a great place to recompress at a higher level offline.

Streaming pipelines

Producer batch compression cuts broker disk and replication bandwidth. Consumers pay decompress once per batch. Align codec across languages; measure CPU on both sides before raising the level.

Data lake / warehouse

Column encodings dominate. Sort or cluster by filter columns to improve runs and dictionary locality. Footers and bloom filters stay small so planning stays cheap.

Edge APIs

Let the edge terminate br/zstd for browsers. Keep origin responses uncompressed or similarly encoded to avoid decompress/recompress loops. Watch CPU during traffic spikes—compression is a natural overload amplifier.

Worked example: cross-AZ log shipper

Service emits 200 MB/s of JSON logs. Cross-AZ bandwidth budget is 80 MB/s. Uncompressed shipping is impossible; naive per-line gzip burns CPU and barely helps.

plaintext

Plan:
  1. Buffer 4–16 MB batches (or 1–2 s) of logs
  2. zstd level 3 on each batch (expect ~4–6× on JSON logs)
  3. 200 MB/s → ~40 MB/s on the wire → under budget
  4. Checksum frames; drop/DLQ corrupt batches
  5. On CPU pressure: fall back to lz4 or shed debug-level logs

Do not:
  - gzip each line
  - compress after encrypting the batch
  - raise zstd to 19 on the request path

Verify:
  compress CPU %, wire MB/s, end-to-end delay from emit to searchable

Trade-offs

Choice	Gain	Cost
LZ4 / Snappy	Tiny latency tax	Weaker ratio on hard data
Zstd (mid level)	Best general Pareto	More CPU than LZ4; versioning
High-ratio archive	Cheapest long-term storage	Slow compress; poor for hot reads
Columnar encodings	Huge analytic ratios	Write path complexity; row rebuild cost
Shared dictionaries	Small-message wins	Dict distribution & version skew
HTTP edge compress	Less WAN egress	Edge CPU; cache variant bugs
Skip compression	Predictable CPU; simple	Burns bandwidth and disk

Choosing and explaining compression in system design

A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.

Explain the core idea

State whether the goal is wire savings, disk savings, or memory density—and who pays CPU.

Prefer shaping (dictionary/delta/columnar) before general LZ when data is structured.

Name a codec for hot vs cold paths and mention checksums plus max decompressed size.

When it belongs

Cross-region replication, log shipping, or large JSON APIs.

SSTable / Parquet / Kafka storage footprint discussions.

p99 regressions after enabling gzip on the request path.

How it fails

Compressing ciphertext or JPEG with no gain and extra CPU.

Zip-bomb / unbounded decompress from untrusted clients.

Dictionary version skew breaking consumers.

Recompress loops at edge and origin.

Trade-offs to weigh

Ratio versus compress/decompress CPU.

Batch size versus end-to-end latency.

Interop (gzip) versus efficiency (zstd).

Page compression versus whole-file archives.

Common misunderstandings

Quoting generic ratios without measuring your payload.

Enabling maximum compression level on the online path.

Forgetting Vary / encoding keys in caches.

Assuming decompress is free because compress ran offline.

Wrap-up

Compression is a placement problem: pick the layer, shape the bytes, choose a codec for the hottest cost, and verify integrity.

Exercises

Break-even. 500 MB/s NIC, compress 300 MB/s at 3:1. Is compression worth it for a 900 MB/s raw producer?
Small messages. 100-byte metrics at 100k/s. Compare per-message zstd vs 5k-message batches.
Table design. A column is 90% null, else low-cardinality country codes. Which encodings do you stack?

Primary sources

Key takeaway

Compress what is redundant, where bytes are expensive, with a codec that fits the latency budget. Shape structured data first; use Zstd/LZ4 as general tools; never trust decompressed size from the network without limits and checksums.