Storage · 12 min

LSM tree

Follow one write through Cassandra- or RocksDB-style storage: append it to a log, sort it in memory, write whole files, and clean up old copies later.

Sakura opens your food app and changes her favourite dish from ramen to tempura. Your server sends one tiny write to the database: key user:sakura, value tempura.

Now picture a million of those every second, from every user. Most databases would struggle. Databases like Cassandra and RocksDB take them easily, because they never edit anything already on disk. This article follows Sakura’s one write from start to finish to show how.

Why editing in place is slow

The usual way to store a table, used by PostgreSQL and MySQL, keeps each key in one fixed spot on disk. Disks read and write in pages, chunks of 8 KB in PostgreSQL and 16 KB in MySQL. To change “ramen” to “tempura”, the database finds Sakura’s page, reads it, changes a few bytes and writes the whole page back.

Every user’s page sits somewhere different, so each write lands at a random place on the disk. A spinning disk has to move its head for each one, about 5–10 ms, which caps it at roughly 100–200 random writes a second.

The same disk can write 100 MB a second if it just keeps writing straight ahead. That is a million 100-byte records a second. SSDs have no head, but they too handle long sequential writes far better than many small scattered ones.

So the idea is: never jump around. Only ever add to the end. A log-structured merge tree (LSM tree) is a way of storing data built entirely on that rule. The “merge” in the name is the clean-up you’ll meet at the end.

Step 1: append to the log

Four earlier writes have already made this journey: Sakura picked ramen (#1), Haruto sushi (#2), Yui udon (#3) and Hina soba (#4). They now sit in a file on disk called table #1. You’ll see how they got there in a moment.

Sakura’s change gets the next free number and is added to the end of a file:

#5  user:sakura = tempura

Adding to the end is the fast, straight-ahead kind of write. Once it lands, the database can tell your server “saved”. If the power goes out a second later, the log still holds write #5. On restart, the database reads the log back and recovers every write that hadn’t reached a data file yet.

Step 2: a sorted list in memory

The log keeps the write safe, but it is useless for finding things: to find Sakura you would read it from the start. So the same write is also put in a second place.

Sakura’s write goes into the memtable between its alphabetical neighbours. A few more writes follow it. Ren picks onigiri (#6), Haruto deletes his account (#7) and Aoi picks mochi (#8). Now the memtable holds 4 entries and is full:

Each key appears once. If Sakura changed her mind again before the memtable filled, the new value would simply replace tempura here; only the log would keep both.

Notice Haruto’s line. His old value, sushi, is already in table #1 on disk, and files are never edited. So the database can’t remove it. It writes a new entry that says “deleted” instead.

Step 3: the memtable becomes a file

When the memtable is full, the database writes all of it to disk in one go, already sorted. This is called a flush. Then it empties the memtable and clears the log, because the data is now safely in the file.

Sakura’s write is now in table #2. Table #1, flushed earlier from writes #1–#4, still says sakura = ramen. Both versions are on disk at once, and that is fine. Write #9, Kaito picking takoyaki, arrives next and starts a fresh memtable. (The demo labels freshly flushed files L0.)

Count what the disk did: 4 small appends to the log, then 1 big sequential write of 4 entries. There were no random jumps.

Step 4: someone reads Sakura’s favourite

A friend opens Sakura’s profile. The database needs user:sakura, but it could be in three places: the memtable, table #2 or table #1. It checks them newest first and stops at the first match:

1. The memtable: not there. It only holds Kaito’s write #9.
2. Table #2: there. Because the file is sorted, the search jumps to the middle and narrows down instead of reading every line: haruto, then ren, then sakura. Answer: tempura.
3. Table #1 is never opened. Its “ramen” is older, so it would lose anyway.

That is why the numbering matters. The newest place to hold a key always wins.

The cost is on the read side: a key that was never written would have to be checked in every file. Two cheap checks avoid most of that. Each file knows its first and last key, so a key outside that range is skipped. Each file also keeps a Bloom filter (it has its own article), a tiny summary of its keys kept in memory. It can say “definitely not in this file” without opening it. Now and then it wrongly says “maybe”, which costs one wasted file read.

Hours later: compaction cleans up

Left alone, files pile up. Every read has more places to check, and the disk fills with dead values like “ramen”. So every so often the database runs a clean-up in the background.

Because every file is already sorted, the merge is one pass, like merging two sorted piles of cards. For our two files:

• In: 8 entries from table #2 and table #1.
• sakura = ramen (#1) is dropped; tempura (#5) is newer.
• haruto = sushi (#2) is dropped; the tombstone (#7) is newer.
• The tombstone itself is dropped too. Nothing older is left for it to hide.
• Out: one file with 5 entries: aoi, hina, ren, sakura = tempura, yui.

Sakura’s write has reached its final home. Her old “ramen” is gone for good, and only now is Haruto’s data truly deleted.

What Sakura’s write really cost

Nothing was ever overwritten in place, but plenty was written more than once. Count every entry the demo put on disk for its first 9 writes.

That ratio is called write amplification: how many times the disk writes each piece of data. Before compaction it was 17 ÷ 9 ≈ 1.9; after, 2.4. In a big database it is much higher, because data gets compacted again and again.

RocksDB, for example, sorts its files into levels, each 10 times bigger than the one above. Picture level 1 as 10 files and level 2 as 100 files. Inside a level, each file covers its own slice of the alphabet (aoi–bob, bob–cat, …), so a key can be in only one file per level.

When level 1 gets too big, one of its files is pushed down. Its slice of the alphabet is 10 times wider than a level-2 file’s, so it overlaps about 10 level-2 files. All 11 are merged and rewritten. So every level a piece of data moves down costs it about 10 rewrites; with 3 levels, about 10 × 3 = 30. That sounds bad, but all 30 are fast sequential writes, which still beats one random write per update.

Reads pay too, in files opened per read. In the demo a read could need 2 files before compaction and 1 after. With levels it is at most one file per level, and Bloom filters skip most of those: given about 10 bits of memory per key, one wrongly says “maybe” about 1% of the time.

When to reach for one

An LSM tree trades extra background work for writes that never wait on a random disk jump. It fits workloads with far more writes than reads, or where new data keeps arriving: chat messages, logs, metrics, sensor data, event streams.

Cassandra, ScyllaDB, HBase, Bigtable, RocksDB and LevelDB are all built this way.

Watch for two things in production. Compaction uses disk and CPU, so if writes outrun it, files pile up and reads slow down. And deletes free no space until compaction runs. A query that reads many keys in a row, like the last 100 messages in a chat, has to walk past every tombstone in that stretch.

If your data is read far more than it is written, the page-editing engines in PostgreSQL and MySQL are usually the simpler choice.