SSTABLE - Immutable Disk Storage

Complete Answer:

An SSTable (Sorted String Table) is Cassandra's immutable on-disk storage format - a collection of sorted files that permanently store data flushed from memtables.

What is SSTable:

• Collection of files: Data.db, Index.db, Filter.db, Summary.db, Statistics.db, CompressionInfo.db
• Sorted: By partition key → clustering key for efficient lookups
• Immutable: Written once, never modified
• Compressed: Typically 3-5x compression with LZ4
• Part of LSM tree: Memtable (L0) → SSTables (L1+)
• Created by: Memtable flush when reaches threshold

Why Immutability:

1. Lock-free reads:

• Multiple readers can access simultaneously
• File never changes so no coordination needed
• Unlimited read parallelism
• Predictable performance - no lock contention

2. Crash safety:

• SSTables are atomic - either complete or don't exist
• Can't corrupt existing SSTables during crash
• Simple recovery - just delete incomplete files
• No complex recovery logic needed
• Real example: Netflix zero SSTable corruption in 5 years

3. Easy replication:

• Just copy files to other nodes
• Can copy while reads continue (no locking)
• Streaming for new nodes is simple
• Repair = replace damaged files

4. Compaction-friendly:

• Background merge creates new SSTable
• Old SSTables keep serving reads
• Atomic swap to new, delete old
• Zero downtime during compaction

Trade-offs:

• Cost: Updates create new versions (space amplification)
• Deletes create tombstones (more data temporarily)
• Requires compaction to reclaim space
• Benefit: Worth it! Disk cheap, corruption expensive

Key Insight: Immutability trades some disk space for massive simplicity and reliability. No locks, no corruption, simple replication. Modern databases (Cassandra, RocksDB, BigTable) all use this pattern because the benefits far outweigh the costs!

Complete Answer:

Bloom filters are probabilistic data structures that quickly test whether a partition key exists in an SSTable - saving billions of unnecessary disk reads!

How Bloom Filters Work:

Data structure:

• Bit array (millions of bits set to 0 or 1)
• Multiple hash functions (typically 3-5)
• Each key hashes to multiple bit positions

Insert operation:

• Hash partition key with 3-5 different hash functions
• Each hash produces a bit position
• Set all those bit positions to 1
• Example: key "user123" → bits 45, 892, 3421 set to 1

Test operation:

• Hash the query key with same hash functions
• Check if ALL corresponding bits are 1
• All 1s: "Maybe present" (might be false positive)
• Any 0: "Definitely NOT present" (100% accurate!)

False Positive Rate:

• Default: 1% false positive rate
• Meaning: 1% chance says "maybe" when key not actually there
• True negative: 100% accurate (if it says no, definitely no!)
• Configurable: 0.01% - 10% via bloom_filter_fp_chance

Why Critical for Performance:

The problem without bloom filters:

• Reading key "user999" that doesn't exist
• Must check Index.db for ALL 20 SSTables
• 20 SSTables × 10ms disk read = 200ms wasted!
• Most queries access keys not in most SSTables

With bloom filters:

• Check bloom filter in memory (~1ms)
• Says "definitely not here" for 99% of SSTables
• Skip 19 out of 20 SSTables
• 200ms → 1ms (200x faster!)

Real Impact - Spotify Example:

• 10 billion SSTable reads per day
• Average 20 SSTables checked per read
• = 200 billion potential disk reads
• Bloom filters: 99% efficiency
• 200B → 2B actual reads (198 billion saved!)
• 10ms per saved read = 22,916 days of I/O saved daily

Memory Cost:

• Formula: ~10 bytes per key for 1% FP rate
• 100 million keys = 1GB bloom filter
• Must fit in memory (always loaded)
• Trade-off: Small memory cost for massive I/O savings

Tuning:

• Lower FP (0.1%): Larger filter, fewer false positives
• Use for read-heavy workloads
• Higher FP (10%): Smaller filter, more false positives
• Use for write-heavy workloads where reads are rare

Key Insight: Bloom filters are the unsung heroes of Cassandra performance. For minimal memory cost (~1% of data size), they eliminate 99% of wasted disk I/O. This is THE optimization that makes SSTable-based databases viable at scale!

Complete Answer:

Cassandra has three main compaction strategies, each optimized for different workload patterns.

1. STCS (Size-Tiered Compaction Strategy)

How it works:

• Groups SSTables into "tiers" by similar size
• When 4+ SSTables in same tier → merge them
• Creates larger SSTable at next tier
• Tiers: 10MB, 100MB, 1GB, 10GB, etc.
• Simple and write-optimized

Characteristics:

• Read amplification: 5-20 SSTables per read
• Write amplification: 5-10x (moderate rewriting)
• Space amplification: 2x (old + new versions)
• Compaction frequency: Less frequent (efficient)

When to use STCS:

• Write-heavy workloads: Inserts >> reads
• Time-series data (logs, events, metrics)
• IoT sensor data
• Append-only patterns
• Example: Epic Games telemetry (100M events/hour)
• Default: Good starting point for most workloads

2. LCS (Leveled Compaction Strategy)

How it works:

• Organizes SSTables into levels (L0, L1, L2...)
• Each level 10x larger than previous
• L1+: Non-overlapping key ranges
• Promotes SSTables through levels
• Constant compaction happening

Characteristics:

• Read amplification: 1-2 SSTables per read (optimal!)
• Write amplification: 10-30x (lots of rewriting)
• Space amplification: 1.1x (very efficient)
• Compaction frequency: Continuous (high I/O)

When to use LCS:

• Read-heavy workloads: Reads >> writes
• User profiles, session data
• Applications where read latency is critical
• Disk space constrained (90% less waste than STCS)
• Example: Discord messages (1 trillion+ messages)
• Warning: Don't use for write-heavy (death spiral!)

3. TWCS (Time-Window Compaction Strategy)

How it works:

• Groups SSTables by time window (hour, day, week)
• Each window becomes one SSTable
• Old windows expired by deleting entire SSTable
• Designed specifically for time-series + TTL

Characteristics:

• Read amplification: 1-3 SSTables per time range
• Write amplification: 2-5x (minimal)
• Space amplification: 1.5x
• TTL expiration: Instant (delete file!)

When to use TWCS:

• Time-series with TTL: Must have expiration!
• Metrics, monitoring data
• Application logs
• Event streams
• Queries typically by time range
• Example: Uber trip history (90 day TTL)
• Requirement: Don't use without TTL!

Decision Framework:

Choose STCS if:

• Write:Read ratio > 10:1
• Append-only or mostly inserts
• Reads are batch/analytics (latency OK)
• Uncertain (good default)

Choose LCS if:

• Write:Read ratio < 1:10
• Read latency is critical
• Lots of updates/deletes
• Disk space constrained

Choose TWCS if:

• Time-series data
• Has TTL expiration
• Queries by time range
• Recent data accessed most

Key Insight: There's no universal best strategy! STCS favors writes, LCS favors reads, TWCS favors time-series. Choose based on your workload pattern. When in doubt, start with STCS and switch to LCS only if read latency becomes a problem!