Storage engines
Discord stores every message ever sent on the platform. In 2017 they moved those messages from MongoDB to Cassandra, and in 2023 they wrote about moving again, to ScyllaDB, at trillions of messages. Both destinations share one design decision underneath, the same one inside RocksDB, which in turn sits under CockroachDB, TiDB and many others: they never change data in place on disk. They only ever append.
Every database has a storage engine: the part that decides how rows are laid out on disk and how they are found again. Almost all of them belong to one of two families, the B-tree and the LSM-tree. Knowing which one a database uses tells you, before you benchmark anything, whether it will love or hate your workload.
Why might a database that never updates data in place on disk accept writes faster than one that does? What would you expect it to be worse at?
The B-tree family: update in place#
Postgres, MySQL's InnoDB, SQLite, Oracle, SQL Server, and MongoDB's default WiredTiger engine all keep data in B-trees: fixed size pages arranged in a shallow, sorted tree, the structure from the indexes chapter.
A write finds the page that holds the row and changes that page. The change is first recorded in the write ahead log for safety, and the page itself is written back to disk later. Reads are excellent: a few page lookups and you are there. Writes are fine, but every write eventually rewrites a whole 8 or 16 KB page somewhere on disk to change a few bytes, and those pages are scattered, so heavy write traffic means lots of small random writes.
The LSM-tree family: only append#
An LSM-tree (log structured merge tree) refuses to modify anything on disk. Step through a write.
So the answer to the question at the top: writes are fast because they are only appends to a log and a memory buffer, and disk writes happen in big sequential batches. The price shows up on reads and in the background.
Reading from an LSM-tree#
The newest value of a key could be in the memtable or in any SSTable, so a read checks them in order, newest first.
Three kinds of amplification#
Storage engine trade-offs are usually described with three words.
Write amplification: how many bytes the engine writes to disk for each byte of data you wrote. B-trees rewrite whole pages. LSM-trees rewrite data again during each round of compaction.
Read amplification: how many places a read must look. Low for a B-tree, a few pages. Higher for an LSM-tree, a few files, kept down by bloom filters and compaction.
Space amplification: how much extra disk the engine needs. B-trees leave half empty pages after splits. LSM-trees hold old versions until compaction removes them.
No engine wins all three, and that is the whole point of having two families.
| Choice | What you gain | What you pay | Pick it when |
|---|---|---|---|
| B-tree | Fast, predictable reads and range scans, and mature transactional behaviour. | Random page writes under heavy write load, and fragmentation over time. | General purpose OLTP: orders, users, payments. Read heavy or balanced workloads. |
| LSM-tree | Very high write throughput with sequential disk writes, and good compression. | Reads may check several files, and compaction uses background disk and CPU that can cause latency spikes. | Write heavy data: messages, events, metrics, time series, logs. |
In an LSM-tree, deleting a row writes a marker called a tombstone. Until compaction removes them, reads have to step over every tombstone in their path. Using Cassandra as a queue, where rows are inserted and deleted constantly, is a famous way to end up with reads that crawl through millions of tombstones. If your workload deletes heavily, model it before you choose.
Checkpoint#
1. Why do LSM-trees accept writes so quickly?
2. What does a bloom filter do in an LSM read?
3. Reads on a Cassandra table that is used as a job queue get slower every week. What is the likely cause?
- B-tree: update pages in place. Postgres, MySQL InnoDB, SQLite, MongoDB WiredTiger.
- LSM-tree: append, flush, compact. RocksDB, Cassandra, ScyllaDB, LevelDB.
- B-trees favour reads, LSM-trees favour writes. Bloom filters keep LSM reads affordable.
- Deletes in an LSM are tombstones. Heavy deletes hurt reads.
Storage engines mostly come in two families. B-trees, used by Postgres, MySQL InnoDB and MongoDB's WiredTiger, keep sorted pages and update them in place, which makes reads and range scans fast and predictable but turns heavy writes into scattered page rewrites. LSM-trees, used by RocksDB, Cassandra and ScyllaDB, append writes to a log and a memtable, flush full memtables as immutable sorted files, and merge them with background compaction. That makes writes very fast and sequential, while reads may check several files, kept cheap by bloom filters, and compaction costs background I/O. The trade is described as write, read and space amplification. I would choose B-tree engines for transactional, read heavy data and LSM engines for write heavy data like messages and events, watching out for tombstones from heavy deletes.