LSM Trees (Database Internals)

Why batch writes into sorted files?

Most relational databases (PostgreSQL, MySQL) use B+ Trees.

• Read: Fast
• Write: A page-oriented index updates pages and may split them. Buffer pools and write-ahead logging reduce physical random I/O; performance is workload-dependent.

An LSM Tree (Log-Structured Merge Tree) batches updates into sorted files. This trades immediate in-place updates for later compaction; it is an option for write-heavy workloads, not a universal throughput guarantee.

Components

MemTable (In-Memory)

When a write comes in (PUT key=value), it is written to an in-memory structure called the MemTable.

• Structure: Usually a Red-Black Tree or SkipList.
• Why?: Keeps data sorted in RAM. Writes are fast ($O(log N)$ memory op).
• WAL: To prevent data loss if power fails, we write to a sequential Write Ahead Log on disk first.

SSTable (Sorted String Table) (On-Disk)

When the MemTable gets big (e.g., 64MB), it is flushed to disk as an SSTable.

• Immutable: Once written, an SSTable is never modified.
• Sorted: Keys are sorted, allowing binary search scanning.

Bloom Filter

Problem: If we have 100 SSTables on disk, do we search all of them for a key? A common optimization is a Bloom Filter associated with a table or key range.

• It tells us "The key is definitely NOT in this file" or "Maybe in this file".
• Avoids many absent-key reads; effectiveness depends on filter size, false positives, and the workload.

The Write Path

• Append to WAL (for durability).
• Insert into MemTable (RAM).
• Acknowledge after the configured durability requirement is satisfied. A memory-buffered WAL append is not the same as a completed disk sync.
• Background: If MemTable > Limit, flush to new SSTable.

The Read Path

• Check MemTable (Is it in RAM?).
• Check Block Cache (Is it in LRU Cache?).
• Check Bloom Filter of SSTable L0 (Most recent).
• Check Bloom Filter of SSTable L... until found

Read amplification means an operation may examine multiple files. Cache hits, filters, and compaction strategy determine whether a particular read is fast or slow.

Compaction (The Cleanup)

Over time, you have duplicates.

• SSTable: Key A = 10
• SSTable 5: Key A = 20 (Newer)

To save space and speed up reads, we run Compaction.

• Read multiple SSTables.
• Merge them into one new larger SSTable (like Merge Sort).
• Discard obsolete values and tombstones only when snapshots and replica-repair requirements make deletion safe.

Strategies

• Size-Tiered: Groups similarly sized files. Can reduce write amplification while requiring more read work; defaults depend on Cassandra version and table settings.
• Leveled: Optimized for Read throughput (LevelDB/RocksDB). More aggressive merging means fewer files to search.

B-Tree vs LSM Tree

Choosing a storage engine

RocksDB is an embedded LSM engine; Cassandra is a distributed database with additional replication and coordination behavior. An engine's data structure does not predict a whole service's throughput. Compare point reads, range scans, overwrites, retention, and durability at the same data size before selecting one.

Summary

• MemTable: Buffers writes in RAM (Sorted).
• SSTable: Immutable files on disk (Sorted).
• Bloom Filter: Optimization to avoid disk reads.
• Compaction: Background merge sort to cleanup garbage.
• Use Case: Write-heavy workloads like time-series, logs, analytics

Related Concepts

• Redis Internals — In-memory data structures
• Database Sharding — Horizontal partitioning
• CAP Theorem — Availability vs consistency trade-offs

Sources and verification

RocksDB overview describes WALs, memtables, sorted files, and compaction. A useful benchmark runs long enough to reach steady compaction, records write stalls and disk usage, and includes missing-key reads. A short load into an empty database hides much of the LSM trade-off.