HLDintermediatePremium

NoSQL Internals HLD: The LSM Tree That Makes Writes Cheap

How a write-optimized NoSQL store works inside: the LSM tree (memtable, write-ahead log, immutable SSTables), the read path with bloom filters, compaction and tombstones, and LSM versus B-tree.

By fiveyearsdevJune 14, 20268 min read

"How does a NoSQL database work inside?" Half the articles on this site reach for Cassandra or RocksDB whenever the load is write-heavy — and this is why. Under the hood they don't use the B-tree a relational database does; they use a log-structured merge-tree (LSM), which turns every write into a cheap append plus a sequential flush instead of a random in-place page update. That single choice is what lets them swallow a firehose of writes — and the price it pays (reads must check several files) is bought back by compaction. Three pieces carry it: an in-memory memtable (plus a write-ahead log …

What’s inside

Let's start nowhere near a computer

Where this exact shape shows up

Step 1 — Functional requirements (sentences first)

Step 2 — Non-functional requirements

Step 3 — The write path: memtable, WAL, flush

Step 4 — The read path

Step 5 — Compaction and tombstones

Step 6 — Trade-offs (each one keeping an NFR)

The complete implementation

Step 7 — From one node to a cluster

Step 8 — Scaling the design, one bottleneck at a time

Step 9 — When a piece fails: designing for failure

The interview corner

Where to go from here

Read this one free

HLD