Course contentsShow
← System Design
Lesson 415 of 1,91912. NoSQL: Wide-Column StoresFree lesson

Write Path and LSM Trees

How wide-column stores use log-structured merge trees for fast writes and eventual compaction.

Write Path and LSM Trees

What you'll learn: How wide-column stores achieve extremely fast writes by using a log-structured merge tree (LSM tree) architecture.

The Write Problem in Databases

Traditional databases write data directly to disk in sorted order, which is slow because it requires finding the right location and potentially shifting data around. Wide-column stores like Cassandra and HBase need to handle massive write volumes, so they use a different strategy.

How LSM Trees Work

An LSM tree separates writes from reads in time. Here's the flow:

  1. Memory write (MemTable): Writes go immediately to an in-memory structure (often a sorted tree). This is lightning-fast—microseconds.

  2. Write-ahead log (WAL): Simultaneously, the write is appended to a sequential log file on disk for durability. Sequential writes are much faster than random writes.

  3. Flush to disk (SSTable): When the in-memory structure fills up, it's flushed to disk as an immutable sorted file called an SSTable (Sorted String Table).

  4. Compaction: Over time, multiple SSTables accumulate. Background processes merge and compact them, removing duplicates and deleted entries.

The Analogy

Think of it like taking notes during a lecture. You quickly jot everything down in a notebook (MemTable + WAL) without organizing. Later, at home (compaction), you sort and consolidate those notes into a neat study guide (merged SSTable). The fast note-taking keeps you from falling behind during the lecture.

Why This Matters

This architecture trades write speed for read complexity. Writes are always fast because they're append-only. Reads may need to check multiple SSTables, but indexes and bloom filters mitigate this. The eventual compaction keeps storage efficient and improves read performance over time.

Key Takeaway: LSM trees enable wide-column stores to achieve high write throughput by writing to memory and sequential logs first, then asynchronously compacting data on disk—optimizing for write-heavy workloads.