Step 2 of 14 · 1 min

The problem every storage engine solves

A database has to keep data on disk, find it again quickly, and survive crashes. Lesson 1.2 gave the key fact about disks: writing or reading data in sequence is far faster than jumping around. Lesson 1.4 showed one answer: keep data in pages, keep a sorted index in a B-tree, and write changes to a log first.

That design updates data in place. There's another family that never updates anything in place. It only ever appends, and tidies up later. These two families, B-trees and LSM-trees, are behind nearly every database you'll use.

Step 3 of 14 · 2 min

B-trees: update in place

You met B-trees in lesson 1.4: sorted pages arranged in a tree, a few levels deep. Here's what happens when a new notification is inserted into Chirp's table:

1. Write the change to the write-ahead log (lesson 1.4), so it survives a crash. This is a sequential append, and cheap.
2. Put the row into a table page with room in it, in memory.
3. Update the index. The index on (user_id, created_at) is sorted by user, so the new entry belongs on whichever leaf page holds that user's entries. Each of the 2,500 notifications a second goes to a different user, so each one touches a different page, in a different place in the index.
4. Eventually, write the changed pages to disk. Postgres collects changes in memory and writes pages out in the background, but each changed page is still a full 8 KB page write, even if only 40 bytes changed.

That last point is the heart of it. Adding a 100-byte row can mean writing an 8 KB index page, plus the 8 KB table page, plus the log. Postgres adds one more cost: after each checkpoint (a regular point at which it makes sure all changes are on disk), the first change to any page writes that whole page into the log too, to protect against a crash mid-write. With changes scattered across millions of index pages, almost every change is the first one to its page since the last checkpoint.

The ratio between how much a database writes to disk and how much data you actually gave it is called write amplification. For Chirp's notifications, it was large: roughly tens of times more bytes written than inserted.

Pages also fill up

When an index page is full and a new entry belongs in it, the page splits into two half-full pages. Over time, an index that gets inserts in random order ends up with many partly empty pages, so it takes more space and fewer entries fit in memory.

And deletes aren't free

In Postgres specifically, deleting a row doesn't remove it immediately. The row is marked as dead, because other transactions might still need to see it (that's how Postgres lets readers and writers work without blocking each other). A background process called vacuum later finds dead rows and makes their space reusable. Deleting 40 million notifications meant 40 million dead rows, and vacuum having to visit every page they were on, plus every index page that pointed to them.

That's the nightly hour of maximum disk activity.

B-trees are excellent at many things: reads are predictable (a few page reads for any lookup), range queries are efficient, and updating a row in place is natural. Insert-heavy workloads that touch random pages, followed by huge deletes, are their weak spot.

Step 4 of 14 · 3 min

LSM-trees: append, then tidy up

The other family is the log-structured merge-tree, or LSM-tree. It's used by RocksDB, LevelDB, Cassandra, ScyllaDB, HBase and many others. The idea: never modify data on disk. Collect writes in memory, write them out in big sorted chunks, and merge chunks in the background.

Here's the path a write takes:

1. Append to a log on disk (Cassandra calls it the commit log), for crash safety. Sequential, cheap.
2. Insert into the memtable, an in-memory structure that keeps entries sorted by key. Fast, because it's all in memory.
3. When the memtable reaches a certain size (tens of megabytes, say), write it to disk as a new file, in sorted order, in one sequential write. These files are called SSTables (sorted string tables). Once written, an SSTable is never changed.
4. Start a fresh memtable, and carry on.

Every disk write here is a big sequential write of a whole file. Nothing jumps around the disk updating pages. That's why LSM-trees handle very high write rates so well.

Reading

The cost moves to reads. A key's latest value might be in the memtable, or in any SSTable, and newer ones take priority. So to read a key, the engine checks the memtable first, then SSTables from newest to oldest, until it finds the key.

That could mean checking lots of files. Two things keep it fast:

• Each SSTable has a small index saying roughly where in the file each range of keys is, so checking one file takes about one disk read, not a scan.
• Each SSTable has a Bloom filter, which can say "this key is definitely not in this file" without reading the file at all. More on these below.

Compaction

If SSTables only ever accumulated, reads would get slower forever and disk space would fill with old versions of the same keys. So a background process called compaction regularly takes several SSTables, merges them (like merging sorted lists, which is a sequential operation), keeps only the newest value for each key, and writes out new, bigger SSTables. The old files are deleted.

This is the "merge" in log-structured merge-tree. It's also where an LSM-tree's own write amplification comes from: the same data gets rewritten every time it's compacted into a larger file.

There are two main styles:

• Size-tiered compaction: when there are several SSTables of similar size, merge them into one bigger one. Rewrites data fewer times, so it's gentler on writes, but at any moment a key might be in several files, so reads check more of them, and old versions take up space until they're merged.
• Leveled compaction: SSTables are organized into levels, each about ten times bigger than the one above, and within a level, files don't overlap. A read checks at most one file per level. Data gets rewritten more often as it moves down the levels, so it costs more writes, but reads are more predictable and less space is wasted.

Deletes are writes too

Since SSTables are never changed, an LSM-tree can't delete a row by removing it. Instead it writes a tombstone: a marker saying "this key was deleted." Reads that find the tombstone know to ignore older values. Only when compaction merges the tombstone with every older copy of the key can both be dropped.

This has a trap that catches many teams. Imagine notifications stored in Cassandra with a 30-day TTL (expiry). After 30 days, each one becomes a tombstone. A user who gets lots of notifications has a partition full of tombstones, and reading their inbox means skipping over thousands of them before finding live rows. Cassandra also deliberately keeps tombstones for a while (by default, ten days) so that replicas which missed the delete don't bring the data back. Reads over tombstone-heavy partitions get slow, and Cassandra logs warnings about exactly this.

The fix is to design so expired data can be dropped in whole files rather than one tombstone at a time. For time-ordered data with a TTL, there's a compaction style designed for this (time-window compaction), which groups data by time so that whole old SSTables can simply be deleted when everything in them has expired. Notice that this is the same idea Chirp eventually used in Postgres.

Step 5 of 14 · 1 min

Bloom filters

Bloom filters deserve a closer look, because they turn up all over system design (in databases, caches, CDNs, and spam filters).

A Bloom filter answers one question about a set: "might this item be in it?" It can answer "definitely not," or "possibly yes." It can't list the items, and it's sometimes wrong in one direction only: it can say "possibly yes" for an item that isn't there (a false positive), but it never says "definitely not" for an item that is.

It's simply an array of bits, all starting at 0, plus a few hash functions:

• To add a key, run it through each hash function. Each gives a position in the array. Set those bits to 1.
• To check a key, compute the same positions. If any of them is 0, the key was never added: definitely not. If all are 1, it was probably added, though those bits might have been set by other keys.

The useful part is how little space it takes. With about 10 bits per key and seven hash functions, the false-positive rate is about 1%. A filter for an SSTable with ten million keys is roughly 12 MB, small enough to keep in memory, and it lets 99% of "is this key in this file?" checks skip the disk entirely.

For an LSM-tree, that's the difference between a read checking ten SSTables on disk and a read checking the one that actually has the key.

Step 6 of 14 · 1 min

Three kinds of amplification

Every storage engine trades off three costs:

• Write amplification: bytes written to disk, divided by bytes of data you wrote. Higher means more disk wear and less write capacity.
• Read amplification: how many disk reads one lookup needs.
• Space amplification: disk space used, divided by the size of the live data. Higher means you're storing old versions, dead rows or half-empty pages.

You can't make all three low at once. Researchers have even given this a name (the RUM conjecture, for Read, Update, Memory). Each design is a choice about which to favour:

The table is a guide, not a ranking. A B-tree with sequential inserts (keys that always increase, like a timestamp-ordered ID) has much lower write amplification than one with random inserts, because new entries always go to the last page. An LSM-tree with a badly tuned compaction can fall behind and see reads slow to a crawl. The shape of your workload matters more than the engine's reputation.

Step 7 of 14 · 1 min

Which databases use which

• B-trees: PostgreSQL, MySQL (InnoDB), SQL Server, Oracle, SQLite, and most traditional relational databases.
• LSM-trees: RocksDB and LevelDB (embedded engines used inside many other systems), Cassandra, ScyllaDB, HBase, and Bigtable. Some databases let you choose: MySQL can run on RocksDB through MyRocks, and many distributed SQL databases use an LSM engine under a SQL interface.

So "SQL or NoSQL" (lesson 3.1) and "B-tree or LSM" are separate choices. The data model is about what questions you can ask. The storage engine is about how the bytes are laid out on disk.

Step 8 of 14 · 1 min

From the real world: Discord's next problem was reads

Five years after the design in lesson 3.1, Discord stored trillions of messages on 177 Cassandra nodes, and its message database had become, in its engineers' words, a high-toil system. Their 2023 write-up is a good tour of how an LSM-tree database behaves under real pressure.

The trouble came from hot partitions. When a big community pinged everyone in a channel, thousands of clients loaded the same channel at the same moment. All those reads hit the few nodes that held that partition. Several things then fed each other:

• Reads on an LSM-tree may have to check several SSTables (lesson 3.2's read amplification), and a busy node falls behind on compaction, so there are even more SSTables to check, making reads slower still.
• Cassandra runs on the JVM, and its garbage-collection pauses stalled nodes for noticeable periods.
• Reads at quorum wait for the slowest of the replicas they ask, so one struggling node slowed queries across the cluster.

Discord's fix had two parts, and the order matters. First, they put data services (written in Rust) between the API and the database. Requests for the same channel are routed to the same data-service instance, which coalesces them: if a thousand clients ask for the same messages at once, the service sends one query and shares the answer. Then they migrated to ScyllaDB, a Cassandra-compatible database written in C++, with no garbage collector and one shard per CPU core.

They reported going from 177 nodes to 72, p99 read latency falling from 40–125 ms to about 15 ms, and inserts steadying around 5 ms. Request coalescing is the part that's easy to overlook. A database swap made each read cheaper, but not sending the same read a thousand times made the hot partition stop being hot.

Step 9 of 14 · 1 min

Going deeper: write stalls, or when the LSM-tree says "slow down"

LSM-trees make writes cheap by deferring work: write to memory, flush to a new file, merge files later. Lesson 3.2 described compaction as tidying up. Under heavy writes, it's more like debt, and the engine has rules for when the debt gets too large.

Take RocksDB, which sits underneath many databases (CockroachDB's early versions, TiKV, MyRocks, Kafka Streams state stores). Each memtable flush adds a file to level 0. Files in level 0 can overlap, so every read must check all of them. Compaction merges level 0 down into level 1. If writes arrive faster than compaction can merge, level-0 files pile up and reads get slower with each one.

RocksDB protects itself with thresholds. With its defaults, when level 0 reaches 20 files it starts deliberately delaying writes (a slowdown), and at 36 files it stops accepting writes until compaction catches up (a stop). There are similar limits on the number of unflushed memtables and on the total bytes waiting to be compacted. These are called write stalls. To an application, they look like a database whose write latency jumps from 1 ms to seconds, for no visible reason.

What to watch and do:

• Monitor compaction debt: pending compaction bytes, level-0 file count, and stall counters. They warn you hours before users notice.
• Give compaction real resources: disk throughput and background threads. A disk that's fast enough for your writes isn't fast enough for your writes plus compaction rewriting them several times (write amplification).
• Don't just raise the limits. Stalls are back-pressure; removing them trades a slow write today for unbounded read amplification and a bigger stall later.
• Smooth out bulk loads. A backfill that writes as fast as it can will hit stalls; one that's rate-limited won't.

Step 10 of 14 · 1 min

What Chirp did

The obvious move would have been to move notifications to Cassandra. Lesson 3.1 had set a threshold for that, and Chirp wasn't near it. So the team asked a different question: could the Postgres table be shaped so that it stopped fighting the storage engine?

Two problems had caused most of the pain: random index inserts and bulk deletes. Both had fixes.

Split the table by time. Postgres supports declarative partitioning: one logical table, stored as several physical tables, each holding a range of rows:

CREATE TABLE notifications (
    user_id     bigint NOT NULL,
    created_at  timestamptz NOT NULL,
    kind        text NOT NULL,
    actor_id    bigint,
    post_id     bigint,
    read        boolean NOT NULL DEFAULT false
) PARTITION BY RANGE (created_at);

CREATE TABLE notifications_2026_w47 PARTITION OF notifications
    FOR VALUES FROM ('2026-11-16') TO ('2026-11-23');

Each week gets its own partition, with its own small index. Queries for "my newest 50" still work, and mostly touch only the newest partition or two, whose indexes are small enough to stay in memory. Because the index being written to is small and hot, the pages being changed are mostly already in memory, and far fewer distinct pages are dirtied between checkpoints.

Drop old data instead of deleting it. Removing a week of notifications no longer means 40 million DELETEs, dead rows and vacuum. It's this:

DROP TABLE notifications_2026_w42;

which removes the files and takes milliseconds. This is exactly the trick from the LSM section: when data expires by time, organize storage by time, so expired data disappears in whole files.

Batch the inserts. Notifications are now written by a background worker in batches of a few hundred rows per transaction (Part 4 covers background workers), instead of one transaction per like. Fewer commits means fewer log flushes (lesson 1.4's import exercise again).

The result: disk writes for notifications dropped by about 80%, the nightly cleanup disappeared, and replication lag stopped spiking. And Chirp has a clear picture of when to move to an LSM-based store: when sustained notification writes reach tens of thousands a second, more than one Postgres server's disk can absorb.

Step 11 of 14 · 1 min

In the simulation

Stage 2's notifications feature puts this lesson into numbers. If your Stage 0 database was a B-tree store, watch disk write volume and replica lag once notifications launch, and try partitioning by time. If it was an LSM store like Cassandra, writes are easy, but watch read latency on heavy users' inboxes as tombstones build up, and try a time-window compaction setting.

Open the simulation →

Step 12 of 14 · 1 min

If you're here for an interview

Interviewers occasionally ask about storage engines directly, especially for roles close to databases. More often, it comes up inside a design: "this table gets 50,000 writes a second, what would you store it in?" Strong answers:

• Explain the write path in one sentence each: B-trees update pages in place; LSM-trees append to memory, flush sorted files, and merge them in the background.
• Name the trade-off: LSM favours writes, B-trees favour predictable reads, and both have write amplification for different reasons.
• Mention Bloom filters when explaining how LSM reads stay fast.
• Mention deletes: tombstones in LSM-trees, dead rows and vacuum in Postgres, and time-partitioning as the fix for time-expiring data.

Step 13 of 14 · 2 min

Try these yourself

Step 14 of 14 · 1 min

Further reading

• Martin Kleppmann, Designing Data-Intensive Applications, Chapter 3, "Storage and Retrieval." The clearest walkthrough of B-trees and LSM-trees side by side.
• Patrick O'Neil et al., "The Log-Structured Merge-Tree (LSM-Tree)," Acta Informatica, 1996. The original paper.
• The RocksDB wiki, especially the pages on compaction and on Bloom filters.
• PostgreSQL documentation on table partitioning, and on routine vacuuming.
• Burton H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors," Communications of the ACM, 1970.
• Bo Ingram, "How Discord Stores Trillions of Messages," Discord blog, 2023.
• RocksDB wiki, "Write Stalls," for the level-0 slowdown and stop triggers and the related settings.