Skip to content
hashkey.bond

Archivestorage

LSM Trees: Writes First, Reads Later

Buffer writes in memory, flush sorted files, and pay for it at read and compaction time.

Published
Reading time
1 min read

A log-structured merge tree turns random writes into sequential ones: writes go to a memtable and a write-ahead log, the memtable flushes to an immutable sorted SSTable, and background compaction merges SSTables.

The read path

  1. Check the memtable.
  2. Check immutable memtables.
  3. Probe SSTables newest to oldest, using bloom filters to skip files that cannot contain the key.
  4. Merge versions and apply tombstones.

Reads are the expensive part, which is why bloom filters, block indexes, and compaction levels exist.

The write path cost

A single logical write can be rewritten many times as it moves down levels. That is write amplification, and it is the main tuning problem.

Where LSM wins

Write-heavy workloads, SSD-friendly sequential I/O, and large datasets where point reads can be served from cache. RocksDB, LevelDB, Cassandra, and ScyllaDB are all in this family.

Takeaway: LSM trades read and compaction work for fast writes. If your workload is read-dominant with small working sets, a B-tree may simply be cheaper.