Block Compression

Deep dive into LZ4 and Zstd compression in nori-sstable.

---

---

Overview

nori-sstable supports block-level compression using industry-standard algorithms: LZ4 (fast compression with excellent decompression speed) and Zstd (higher compression ratios with moderate speed). Compression is applied at the block level (default 4KB blocks), balancing memory usage and compression effectiveness.

{: .highlight }

NEW Feature: Compression support was added in version 0.1 with full LZ4 and Zstd integration, comprehensive testing, and production-ready performance.

Why Compress?

Storage Cost Savings: - Typical workloads: 2-3x size reduction with LZ4 - Highly compressible data: 14x+ size reduction - Zstd: 3-5x reduction for archival use cases

Performance Tradeoffs: - Write overhead: Minimal (<10% CPU increase with LZ4) - Read overhead: Mitigated by caching (decompress once, cache decompressed blocks) - Network savings: Smaller files mean faster backups and replication

---

Compression Algorithms

Compression::None (No Compression)

When to use: - Ultra-low latency requirements (<5µs reads) - Already compressed data (images, videos, encrypted data) - Very fast CPUs with slow storage (rare edge case) - Debugging or benchmarking raw SSTable performance

Configuration:

use nori_sstable::{SSTableConfig, Compression};

let config = SSTableConfig {
    compression: Compression::None,
    ..Default::default()
};

Characteristics: - Zero CPU overhead - Largest file sizes - Simplest read/write path - Best for testing and development

---

Compression::Lz4 (Recommended Default) 🌟

When to use: - Most production workloads (balanced speed and compression) - Hot data with frequent reads (combine with caching) - Real-time applications - Text data, JSON, logs, structured data

Performance: - Compression speed: ~750 MB/s - Decompression speed: ~3,900 MB/s (blazingly fast!) - Compression ratio: 2-3x typical, up to 14x for highly compressible data - CPU overhead: Minimal (<10% on writes)

Configuration:

use nori_sstable::{SSTableConfig, Compression};

let config = SSTableConfig {
    compression: Compression::Lz4,  // Recommended!
    ..Default::default()
};

Why LZ4? 1. Fast decompression: 3.9 GB/s means negligible read overhead 2. Good compression: 2-3x savings for typical key-value data 3. Widely used: Industry standard (Kafka, RocksDB, Cassandra) 4. Cache-friendly: Decompress once, cache hot blocks

{: .note }

LZ4 + Cache = Best Performance: With the LRU cache enabled (default), hot blocks are decompressed once and served from memory. This means you get the storage savings of compression with zero decompression cost on cache hits.

---

Compression::Zstd (Higher Compression)

When to use: - Cold storage or archival data - Infrequently accessed data - Storage cost is critical - Backup systems - Historical data retention

Performance: - Compression speed: ~400 MB/s (slower than LZ4) - Decompression speed: ~1,200 MB/s (still fast!) - Compression ratio: 3-5x typical, better than LZ4 - CPU overhead: Moderate (~20% on writes)

Configuration:

use nori_sstable::{SSTableConfig, Compression};

let config = SSTableConfig {
    compression: Compression::Zstd,  // For cold storage
    block_cache_mb: 0,               // Disable cache for cold data
    ..Default::default()
};

Why Zstd? 1. Best compression ratio: 3-5x savings, sometimes higher 2. Still fast: 1.2 GB/s decompression is acceptable for cold data 3. Facebook-backed: Used in production at scale 4. Configurable: Can tune compression level (nori-sstable uses level 3)

---

How Compression Works

Block-Level Compression

nori-sstable compresses individual blocks (not the entire file):

Uncompressed Block (4KB):
┌────────────────────────────────────┐
│ Entry 1 | Entry 2 | ... | Entry N  │
│ (prefix compressed, ~4096 bytes)   │
└────────────────────────────────────┘
            ↓ Compress with LZ4
┌─────────────────────────┐
│ Compressed Block (~1.5KB)│
│ (stored on disk)        │
└─────────────────────────┘

Benefits of block-level compression: - Random access: Can decompress single block without reading entire file - Memory efficient: Only decompress blocks you need - Balanced compression: 4KB blocks compress well without excessive overhead - Prefix compression + LZ4: Double compression benefit (prefix within block, LZ4 across block)

Write Path (Compression)

Builder.add(entry)
    ↓
BlockBuilder (prefix compression)
    ↓ Block fills up (4KB)
BlockBuilder.finish()
    ↓ Returns uncompressed block
compress::compress(block, Compression::Lz4)
    ↓ Compress entire block
Writer.write_block(compressed_data)
    ↓ Write to disk
File: [...compressed blocks...][index][bloom][footer]

Code snippet from builder.rs:

// Finish the block (uncompressed, with prefix compression)
let block_data = self.block_builder.finish();
let uncompressed_size = block_data.len();

// Compress the entire block
let compressed_data = compress::compress(&block_data, self.config.compression)?;
let compressed_size = compressed_data.len();

// Write compressed block to disk
let block_offset = self.writer.write_block(&compressed_data).await?;

// Track compression ratio
let ratio = uncompressed_size as f64 / compressed_size.max(1) as f64;
self.meter.histo("sstable_compression_ratio", ...).observe(ratio);

Read Path (Decompression)

Reader.get(key)
    ↓
Check bloom filter → Check cache → Find block via index
    ↓
read_block(offset, size)
    ↓
Check cache (decompressed blocks cached)
    ↓ Cache miss
Read compressed bytes from disk
    ↓
compress::decompress(bytes, footer.compression)
    ↓ Decompress entire block
Block::decode(decompressed_bytes)
    ↓ Decode entries (prefix decompression)
Cache decompressed block (for future hits)
    ↓
Return entry to user

Key insight: Decompressed blocks are cached, so hot data only pays decompression cost once!

---

Configuration Examples

Default (LZ4 with Cache)

use nori_sstable::{SSTableBuilder, SSTableConfig, Compression};

let config = SSTableConfig {
    path: "data.sst".into(),
    estimated_entries: 10_000,
    compression: Compression::Lz4,  // Fast compression
    block_cache_mb: 64,              // Cache decompressed blocks
    ..Default::default()
};

let mut builder = SSTableBuilder::new(config).await?;

Use case: Production workloads with balanced read/write performance

---

Maximum Compression (Zstd for Cold Storage)

let config = SSTableConfig {
    path: "archive.sst".into(),
    estimated_entries: 100_000,
    compression: Compression::Zstd,  // Higher compression ratio
    block_cache_mb: 0,               // Disable cache (cold data)
    ..Default::default()
};

Use case: Archival, backups, infrequently accessed data

---

No Compression (Maximum Speed)

let config = SSTableConfig {
    path: "hot.sst".into(),
    estimated_entries: 1_000,
    compression: Compression::None,  // No compression overhead
    block_cache_mb: 256,             // Large cache for speed
    ..Default::default()
};

Use case: Ultra-low latency requirements, testing, or already-compressed data

---

Compression Ratios

Real-World Test Results

From tests/compression_tests.rs:

// Test: Repetitive text data (highly compressible)
let value = "test_value_that_should_compress_well_".repeat(10);

// Result: 14.38x compression ratio!
// Uncompressed: 11,777 bytes
// Compressed:      819 bytes

Expected ratios by data type:

Data Type	LZ4 Ratio	Zstd Ratio	Notes
Repeated values	10-20x	15-30x	Highly compressible
JSON/Text	2-4x	3-6x	Structured data compresses well
Binary data	1.5-2.5x	2-4x	Moderate compression
Random data	~1x	~1x	May expand slightly
Pre-compressed	~1x	~1x	Already compressed (images, videos)

Compression vs Block Size

Larger blocks generally compress better, but increase memory usage:

Block Size	Compression Ratio	Memory per Block	Random Access
1 KB	~1.8x	Low	Excellent
4 KB	~2.5x	Balanced	Good
16 KB	~3.2x	High	Fair
64 KB	~3.8x	Very high	Poor

Recommendation: Stick with the default 4KB block size for balanced performance.

---

Performance Analysis

Write Performance

LZ4 overhead on build (10K entries): - No compression: 100K entries/sec - LZ4 compression: 95K entries/sec (~5% slower) - Zstd compression: 85K entries/sec (~15% slower)

Bottleneck: Disk I/O, not compression (SSDs write slower than LZ4 compresses)

Read Performance

Point lookup with cache: - Cache hit: ~5µs (no decompression needed) - Cache miss + decompress: ~15µs (one-time cost) - Subsequent reads: ~5µs (cached)

Impact: Negligible with caching enabled (default).

Storage Savings

Example: 1GB of JSON data - Uncompressed: 1,000 MB - LZ4 compressed: ~350 MB (2.9x savings) - Zstd compressed: ~220 MB (4.5x savings)

Cost-benefit: - LZ4: 650MB saved, <5% write overhead, <1% read overhead with cache - Zstd: 780MB saved, ~15% write overhead, ~3% read overhead with cache

---

Compression + Caching Synergy

The killer combination: LZ4 compression + LRU block cache

let config = SSTableConfig {
    compression: Compression::Lz4,  // 2-3x storage savings
    block_cache_mb: 64,              // Cache decompressed blocks
    ..Default::default()
};

What happens: 1. Write: Data is compressed before writing (save storage) 2. First read (cache miss): Decompress block once (~10µs overhead) 3. Cache: Store decompressed block in memory 4. Subsequent reads (cache hit): Serve from cache (no decompression!)

Result: Storage savings of compression + speed of uncompressed reads!

Metrics to monitor:

// Cache effectiveness
sstable_block_cache_hits     // High = good caching
sstable_block_cache_misses   // Low = good caching

// Compression effectiveness
sstable_compression_ratio    // Higher = better compression

---

Migration Guide

Changing Compression on Existing Data

Important: You cannot change compression on existing SSTable files. Compression is set at build time and stored in the footer.

To change compression: 1. Build new SSTables with desired compression setting 2. Read from old SSTables, write to new SSTables 3. Delete old SSTables once migrated

Example migration:

// Read from old uncompressed SSTable
let old_reader = Arc::new(SSTableReader::open("old.sst").await?);

// Create new compressed SSTable
let config = SSTableConfig {
    path: "new.sst".into(),
    compression: Compression::Lz4,  // Enable compression
    ..Default::default()
};
let mut builder = SSTableBuilder::new(config).await?;

// Copy all entries
let mut iter = old_reader.iter();
while let Some(entry) = iter.try_next().await? {
    builder.add(&entry).await?;
}

builder.finish().await?;

---

Best Practices

Do

• Use LZ4 by default for production workloads
• Enable caching with compression (64MB+ cache)
• Monitor compression ratios via metrics
• Use Zstd for cold storage where reads are infrequent
• Keep default 4KB blocks unless you have specific needs
• Test with your data to measure actual compression ratios

Don't

• Don't compress already-compressed data (images, videos)
• Don't use Zstd for hot, latency-sensitive workloads
• Don't disable caching with compression (loses performance benefit)
• Don't change block size unless benchmarks show improvement
• Don't expect compression on random or encrypted data

---

Troubleshooting

"Compression ratio is only 1.1x"

Possible causes: - Data is already compressed (check data type) - Data is random/encrypted (not compressible) - Very small values (compression overhead dominates)

Solution: Consider Compression::None if ratio < 1.5x

"Reads are slower with compression"

Possible causes: - Cache disabled (decompressing every read) - Cache too small (frequent evictions) - Using Zstd on hot data

Solution: - Enable cache: block_cache_mb: 64 or higher - Switch to LZ4 for hot data - Monitor sstable_block_cache_hits metric

"Write performance degraded"

Possible causes: - Using Zstd (slower compression) - Very large blocks (compression overhead)

Solution: - Use LZ4 instead of Zstd - Keep default 4KB block size - Write overhead should be <10% with LZ4

---

Implementation Details

Compression Module

Location: crates/nori-sstable/src/compress.rs

pub fn compress(data: &[u8], algo: Compression) -> Result<Vec<u8>> {
    match algo {
        Compression::None => Ok(data.to_vec()),
        Compression::Lz4 => compress_lz4(data),
        Compression::Zstd => compress_zstd(data),
    }
}

pub fn decompress(data: &[u8], algo: Compression) -> Result<Vec<u8>> {
    match algo {
        Compression::None => Ok(data.to_vec()),
        Compression::Lz4 => decompress_lz4(data),
        Compression::Zstd => decompress_zstd(data),
    }
}

Safety: Conservative decompression limits prevent decompression bombs: - LZ4: Max 256KB decompressed output - Zstd: Bounded by input size heuristics

Footer Storage

Compression type is stored in the SSTable footer:

pub struct Footer {
    // ... other fields
    pub compression: Compression,  // Enum: None, Lz4, or Zstd
    // ...
}

On open: Reader reads footer and uses compression type for all block decompression.

---

Related Documentation

• Caching Guide - Learn how caching works with compression
• Performance Benchmarks - See compression benchmark results
• API Reference - SSTableConfig compression field

---

Summary

Compression in nori-sstable: - Block-level compression (4KB blocks) - LZ4 (fast, 2-3x) and Zstd (higher, 3-5x) support - Production-ready with 108 tests passing - Works seamlessly with LRU cache (decompress once, cache decompressed) - Minimal performance overhead (<10% writes, ~0% reads with cache) - 2-14x storage savings on typical workloads

Recommended configuration:

SSTableConfig {
    compression: Compression::Lz4,  // Fast + good ratio
    block_cache_mb: 64,              // Cache decompressed blocks
    ..Default::default()
}

Result: Storage savings + fast reads = production-ready performance!