LSM trees: how write-heavy databases work

Insert a 100-byte row into a big table in Postgres and, in the worst case, the database ends up rewriting several 8 KB pages scattered around the disk: one for the table and one for each index the row touches. Do that thousands of times a second and most of what your disk is doing is moving pages that are 98% unchanged.

That’s the trade a B-tree makes (I drew those out in 2015, and this is more or less the sequel), and for most applications it’s the right one. But there’s a whole family of databases built on a different structure that never updates anything in place, and it’s behind most of the “handles millions of writes a second” claims you’ve heard: Bigtable, HBase, Cassandra, LevelDB, RocksDB, and the MyRocks engine Facebook built for MySQL. It’s called a log-structured merge tree, from a 1996 paper by Patrick O’Neil and colleagues, and it’s one of my favorite data structures because it’s mostly just a sorted file and a merge sort, applied with a lot of patience.

The Guardian’s write-up of moving from MongoDB to Postgres has been going around the last couple of weeks, and the discussion threads turned, as they always do, into arguments about storage engines that mostly weren’t about what the article was about (which was mostly about operations: running MongoDB on AWS themselves, its management tooling, and a couple of outages, and moving to a managed Postgres with JSONB columns). But it reminded me that I’d been meaning to write this up since we evaluated Cassandra earlier in the year, so here it is.

The write path

An LSM tree accepts a write in two steps, both of them cheap.

First, it appends the write to a log on disk, the write-ahead log, so it survives a crash. Appending is sequential, which is the one thing every kind of storage is good at.

Second, it inserts the key and value into an in-memory sorted structure called the memtable. LevelDB uses a skip list, other engines use a balanced tree, it doesn’t much matter which. That’s it. The write is done. Nothing on disk was searched or modified in place.

When the memtable gets big enough (tens of megabytes is typical), it’s frozen, a new empty one takes its place for incoming writes, and the frozen one is written out to disk in sorted order as a single immutable file. That file is an SSTable, a sorted string table, the name comes from the Bigtable paper. Once it’s written, the corresponding part of the log can be thrown away.

Updates work the same way as inserts: write the key again with the new value. Deletes write a special marker called a tombstone. Nothing old is ever touched. The old versions are still sitting in older SSTables, and it’s somebody else’s job, later, to clean them up.

The read path

The price shows up on reads. The current value for a key could be in the memtable, or in any SSTable, and the newest one wins. So a read checks the memtable first, then the SSTables from newest to oldest, and stops at the first one that has the key (or a tombstone for it, which means “deleted”).

Within an SSTable, finding a key is cheap. The file is sorted and has a small index of where each block starts, so it’s one index lookup and one block read. The problem is how many SSTables you might have to check, especially for a key that doesn’t exist at all, where you’d have to check every single one before you could say “not found”.

The fix is a bloom filter per SSTable, kept in memory. A bloom filter can tell you a key is definitely not in a file, or that it probably is, and it never gets the first one wrong, which is exactly the right way round for this. I drew one out in 2016, so just the number that matters here: with 10 bits per key and 7 hash functions you get about 1% false positives, so a lookup for a missing key skips 99% of the files without touching the disk. That’s the setting LevelDB suggests.

Range scans are worse. A scan from “g” to “j” has to merge the matching ranges from the memtable and from every SSTable that overlaps, and bloom filters can’t help with ranges. This is the main reason LSM databases tend to be pitched at workloads that are mostly point lookups by key.

Compaction

If nothing ever happened to the SSTables, you’d end up with thousands of them, reads would get slower forever, and every overwritten or deleted value would sit on disk forever. So in the background, the engine keeps picking some SSTables and compacting them: merge-sorting several files into new ones, keeping only the newest version of each key, and dropping tombstones once it’s safe to. Because all the inputs are sorted, it’s a streaming merge, sequential reads in, sequential writes out, the same merge step you’d write for merge sort in a CS class.

How you choose what to compact is where the engines differ, and it’s the main tuning knob:

• Size-tiered (Cassandra’s default): when there are several SSTables of similar size, merge them into one bigger one. Cheap on writes, since each piece of data gets rewritten relatively few times. But a key can be spread across many files of different sizes, so reads may check more of them, and a big compaction temporarily needs room for both the inputs and the output, so you can need up to twice the disk space.
• Leveled (LevelDB and RocksDB’s default, and an option in Cassandra): the scheme in the diagram. Level 0 holds fresh flushes that can overlap. From level 1 down, each level is a set of SSTables with non-overlapping key ranges, and each level is about 10 times bigger than the one above. Compaction takes one file from level N and merges it into the overlapping files in level N+1. A read needs to check at most one file per level, and space overhead is small. The cost is that every piece of data gets rewritten roughly ten times per level on its way down.

The amplification triangle

The useful way to compare all of this is by three kinds of amplification. Write amplification: how many bytes the storage actually writes per byte you wrote. Read amplification: how many places a read has to look. Space amplification: how much disk you use per byte of live data.

A B-tree has low read amplification (one path down the tree), but high write amplification for small random writes, since it rewrites a whole page to change a row. LSM with size-tiered compaction has the lowest write amplification and worse read and space amplification. Leveled LSM sits in between, with much better reads and space but write amplification that can run to 10 or 20 times or more. There’s a 2016 paper that formalized this as the RUM conjecture (read, update, memory), and the gist is that you can optimize for two of them at the cost of the third. I don’t know if it’s a theorem, but I haven’t seen a counterexample.

The reason LSM has won so much ground recently is that its writes are big and sequential. That suits spinning disks, where random writes are slow. It also suits SSDs, where large sequential writes are kinder to the flash and its own internal garbage collection, which is a whole other post.

The other cost, and the one that bit us when we tried it, is that compaction is real work happening in the background, competing with your foreground traffic for disk and CPU. If writes come in faster than compaction can keep up, the number of level-0 files grows, reads slow down, and eventually the engine deliberately stalls writes to let compaction catch up. On the latency graph that looks like hours of a flat line and then a cliff.

What we actually did

Earlier this year we looked at moving our event store (the events table from the B-trees post, on sequential keys these days), an append-mostly table that takes most of our write volume, off Postgres and onto Cassandra. On paper it was a perfect fit: write-heavy, read by key and time range, data never updated. We ran it in a staging cluster for about a month. Write throughput was great. What we weren’t ready for was the operational surface: tuning compaction, repairs, tombstone warnings from a cleanup job, a new on-call runbook for a database only two of us understood.

We stayed on Postgres, and fixed the actual problem with partitioning. The event table is now partitioned by month using the declarative partitioning that arrived in Postgres 10, so each partition’s indexes are small enough to stay in memory, and dropping old data is dropping a partition instead of a giant DELETE. Insert throughput roughly doubled, mostly because the hot indexes now fit in RAM. If we grow by another 10x I’d look at an LSM store again, and I’d look at RocksDB-based options as well as Cassandra, and I’d budget for the on-call side before the benchmarks.