Patterns

35 items

System Design Pattern

Storagelsm-treewrite-optimizedcompactionmemtablesstableadvanced

LSM Trees Pattern

Write-optimized storage with log-structured merge trees

Used in: RocksDB, Cassandra, HBase|25 min read

Summary

Log-Structured Merge Trees (LSM Trees) are write-optimized data structures used by databases like Cassandra, RocksDB, LevelDB, and HBase. Writes go to an in-memory buffer (memtable), which is periodically flushed to immutable sorted files (SSTables) on disk. Background compaction merges SSTables to maintain read performance. LSM trees achieve 10-100x better write throughput than B-trees by converting random writes to sequential I/O. The trade-off is read amplification (checking multiple levels) and write amplification (data written multiple times during compaction).

Key Takeaways

Writes Are Always Fast

Writes go to memory (memtable) first. No disk seek required. Periodically flush to disk as sequential write. This is why LSM is write-optimized.

Immutable SSTables

Once written, SSTable files never change. Simplifies concurrency (no locks needed for reads). Enables efficient caching. Updates/deletes create new entries, not modifications.

Compaction is Essential

Without compaction, reads must check all SSTables. Compaction merges SSTables, removes obsolete entries, maintains sorted order. Different strategies: leveled, tiered, FIFO.

LSM Tree Architecture

Write Path: 1. Write to WAL (durability) 2. Insert into memtable (sorted structure, e.g., red-black tree) 3. When memtable full, flush to SSTable 4. Background compaction merges SSTables

Read Path: 1. Check memtable 2. Check each level's SSTables (newest first) 3. Use bloom filters to skip SSTables 4. Binary search within SSTable

Summary

Key Takeaways

Writes Are Always Fast

Writes go to memory (memtable) first. No disk seek required. Periodically flush to disk as sequential write. This is why LSM is write-optimized.

Immutable SSTables

Once written, SSTable files never change. Simplifies concurrency (no locks needed for reads). Enables efficient caching. Updates/deletes create new entries, not modifications.

Compaction is Essential

Without compaction, reads must check all SSTables. Compaction merges SSTables, removes obsolete entries, maintains sorted order. Different strategies: leveled, tiered, FIFO.

Read Amplification

Point lookup may check memtable + multiple SSTables. Bloom filters help skip SSTables. Still slower than B-tree point lookups. Range scans can be efficient.

Write Amplification

Data written to memtable, then SSTable, then compacted multiple times. Total writes = 10-30x logical writes. Trade-off for write throughput.

Space Amplification

Obsolete entries exist until compacted. Multiple versions of same key in different levels. Need more space than logical data size.

Pattern Details

LSM Tree Architecture

Write Path: 1. Write to WAL (durability) 2. Insert into memtable (sorted structure, e.g., red-black tree) 3. When memtable full, flush to SSTable 4. Background compaction merges SSTables

Read Path: 1. Check memtable 2. Check each level's SSTables (newest first) 3. Use bloom filters to skip SSTables 4. Binary search within SSTable

Trade-offs

Aspect	Advantage	Disadvantage

Patterns

Horizontal Scaling Pattern

Retry with Backoff Pattern

Replication Pattern

Caching Strategies Pattern

Persistent Connections Pattern

Load Balancing Pattern

Fan-out Pattern

Fan-in Pattern

Circuit Breaker Pattern

Eventual Consistency Pattern

Queue-based Load Leveling Pattern

Bloom Filters Pattern

Time-Series Storage Pattern

Bulkhead Pattern

Batch Processing Pattern

Write-Ahead Log Pattern

API Gateway Pattern

Backend for Frontend Pattern

Sidecar Pattern

Idempotency Pattern

Rate Limiting Pattern

Backpressure Pattern

Pub/Sub Pattern

Strong Consistency Pattern

Conflict Resolution Pattern

Leader Election Pattern

Consensus Protocols Pattern

CQRS Pattern