Parallel Compression

Parallel Compression and Decompression is the high-throughput implementation of data compression algorithms (LZ4, Zstandard, Snappy, gzip) that exploits multi-core CPUs, SIMD instructions, or GPU parallelism to compress and decompress data at rates matching modern NVMe SSDs and memory bandwidths — enabling storage, networking, and database systems to use compression as a transparent performance enhancement rather than a throughput bottleneck. Modern multi-threaded compression at 5–20 GB/s enables compression to be applied in the critical path of data pipelines.

Why Parallel Compression Matters

• Single-threaded gzip: ~100–150 MB/s → bottleneck for fast SSDs (7 GB/s) or memory bandwidth (50+ GB/s).
• Uncompressed data: 2–10× more storage I/O → limits effective SSD throughput.
• Solution: Parallel compression at memory bandwidth speeds → compress data faster than storage can write → transparent benefit.
• Target: ≥ 5 GB/s compression throughput on an 8-core server → matches NVMe SSD write speed.

LZ4 — Speed-First Compression

• Lempel-Ziv algorithm variant optimized for speed over ratio.
• Decompression: ~4–5 GB/s (single thread), ~50+ GB/s (multi-thread).
• Compression: ~700 MB/s (single thread), ~8 GB/s (multi-thread with frame splitting).
• Ratio: 2–3× for typical datasets (lower than gzip 5–8× but much faster).
• Use: Real-time streaming pipelines, database page compression (InnoDB, ZFS), Kafka message compression.

Zstandard (Zstd) — Balance of Speed and Ratio

• Facebook-developed compressor (open source since 2016).
• Levels 1–22: Level 1 (speed) ≈ LZ4, Level 19 (ratio) ≈ gzip-9.
• Decompression: Always fast regardless of compression level (~2–3 GB/s per thread).
• Parallel: `zstd --threads=8` → splits input into independent frames → parallel compression.
• Dictionary: Pre-shared dictionary → much better ratio for small records (JSON, logs) → used by Facebook for RPC compression.

Parallel Strategies

1. Frame Splitting
- Divide input into independent chunks (frames) → compress each in parallel → concatenate output.
- LZ4 frame format, Zstd frame format support this natively.
- Decompression: Each frame independently decompressible → parallel decompress → concatenate.
- Trade-off: Cross-frame references impossible → slightly worse ratio at block boundaries.

2. SIMD Acceleration (Within-Thread)
- AVX2/AVX-512: Process 32–64 bytes per instruction → vectorized hash computation for LZ match finding.
- ISA-l (Intel Storage Acceleration Library): Optimized gzip with SIMD → 4× single-core gzip speedup.
- zlib-ng: Drop-in zlib replacement with SIMD optimization → 2–4× faster than reference zlib.

3. GPU Compression

• NVIDIA nvcomp library: GPU-accelerated LZ4, Snappy, Zstd, Deflate.
• nvcomp LZ4: ~200 GB/s throughput (batch mode, A100) → 40× faster than CPU.
• Use cases: Checkpoint compression for LLM training, database column decompression for GPU analytics.
• Pipeline: NVMe → PCIe → GPU memory → GPU decompresses → compute on decompressed data.

Compression in Storage Systems

Columnar Database Compression

• Run-length encoding (RLE): Sequences of same value → (value, count) → excellent for sorted data.
• Dictionary encoding: Map unique values to integer codes → compress codes → effective for low-cardinality columns.
• Bit packing: Store integers in minimum bits → 1000 values 0–255 → 8 bits each → 8 KB vs 32 KB int32.
• Delta encoding: Store differences between consecutive values → small deltas → better compression.
• These columnar encodings are SIMD-friendly and 10–100× faster than general-purpose LZ compression.

Parallel compression is the throughput multiplier that makes storage and networking economics viable at data-center scale — by compressing data at memory bandwidth speeds using multi-core CPUs or GPU acceleration, modern compression turns the CPU's idle cycles into effective storage capacity savings of 2–5×, network bandwidth savings of 2–4×, and often query speed improvements (less I/O), making it one of the highest-ROI optimizations in any large-scale data system.