LSM trees and the NoSQL family
How do stores built for heavy writes work, and what are document, wide-column, key-value, graph, search and time-series stores each good at?
Why can the database not keep up with the riders?
The delivery service signs a deal with a riders’ cooperative. From Monday, 4,000 riders across Pune carry its boxes, and each rider’s phone sends its location every four seconds.
The arithmetic is short: 4,000 riders, each sending a location every 4 seconds, is 1,000 new rows a second, all day. A rider_locations table goes into the same PostgreSQL database that holds the orders, with an index on rider and time.
On Monday it works. By Thursday lunch the order page is slow again, and nothing about the orders has changed.
The location table has grown past 300 million rows. Every insert has to find the right page in each index, and most of those pages are no longer in memory, so the disk spends the lunch hour reading pages from all over the disk, only to change a few bytes in each and write them back. The orders are stuck in the same queue for the same disk.
Location rows are only ever added. Nobody edits where a rider was at 12:31. Yet the database handles each new row the way it handles an edit: in every index it finds the page where the row belongs, reads that page from wherever it sits on the disk, changes it and writes it back.
The usual advice at this point is a NoSQL database, on the grounds that stores like Cassandra are built for heavy write loads. Two questions are worth asking before taking it. What is NoSQL? And what does a store give up to take that many writes?
Pause and predict The table receives 1,000 new rows a second. Rows are only ever added, never changed, yet each insert reads index pages from scattered places on the disk. What should the database do with incoming writes instead?
In-place updates meet a stream of appends
In how a row is stored, lesson 2.1, you saw how PostgreSQL and most relational databases store data: in fixed-size pages, with B+tree indexes whose leaves are kept in key order. That design is excellent for reads. Finding one rider’s last location is three or four page reads, however large the table.
Writes pay for that read speed. A B+tree is updated in place. To insert a row the database must find the one leaf page where the key belongs, bring it into memory, change it, log the change (lesson 2.2), and later write the whole page back. With three indexes, that is three leaves per row.
While the indexes fit in memory this is cheap. Once they do not, each insert becomes several random disk reads and writes. Random I/O is the slowest thing a disk does, and on a cloud volume it is what you pay for by the operation.
A mental model
A railway sorting office solves this problem by hand.
- Log-structured merge tree (LSM tree)
- A storage structure that never updates data in place. Writes go to memory and a log; full memory is written out as a sorted, immutable file; background merges keep the number of files small.
- For example: A location for rider 1042 lands in the memtable in microseconds. Minutes later it is part of a sorted file on disk. Hours later compaction merges that file with others and drops the rider’s older locations if the store keeps only the latest.
The four moves
- Write. Append to the write-ahead log from lesson 2.2 (sequential, so fast) and insert into the memtable, a sorted in-memory structure such as a skip list. That is the whole write path.
- Flush. When the memtable is full, write it to disk in key order as an SSTable (sorted string table): one long sequential write. The file is never modified again. The log for it can then be discarded.
- Read. Look in the memtable, then in the SSTables from newest to oldest, and stop at the first copy of the key: that is the newest value. Each SSTable carries a small index and a Bloom filter, so most files that do not hold the key are skipped without a disk read.
- Compact. In the background, merge several SSTables into new ones, keeping only the newest copy of each key and dropping deleted ones. Merging sorted files is sequential work, like merging sorted decks of cards.
Pause and predict An SSTable is never modified. So how does a rider who leaves the cooperative get deleted?
The rider stream in numbers
| Quantity | Working | Result |
|---|---|---|
| Writes per second | 4,000 riders / 4 s | 1,000/s |
| Rows per day | 1,000 x 86,400 | 86.4 million |
| Raw data per day | 86.4M x 100 B | 8.64 GB |
| Raw data per year | 8.64 GB x 365 | 3.15 TB |
| Bloom filters per day of data, 10 bits a key | 86.4M x 10 / 8 | 108 MB |
| Bloom false-positive rate, 10 bits a key | (1 - e-7/10)7 | 0.82% |
A Bloom filter is a bit array with k hash functions. Adding a key sets k bits; checking a key reads the same k bits. If any is 0 the key is definitely absent. If all are 1 it is probably present. With b bits per key and k hashes the false-positive rate is about (1 − e−k/b)k, smallest when k ≈ b ln 2. Ten bits a key and seven hashes give 0.82%, which matches RocksDB’s guidance that about 10 bits a key gives about 1%.
In the Try it simulator, after 60,000 writes with Bloom filters off:
| Policy | Runs on disk | Runs read for an unknown rider | Write amplification | Space amplification |
|---|---|---|---|---|
| Size-tiered | 6 | 6 | 4.0x | 2.18x |
| Leveled | 4 | 4 | 5.58x | 1.23x |
Pause and predict Turn on 10-bit filters. Under size-tiered, how many file reads does a lookup for an unknown rider cost now?
Where should the rider locations live?
The cause of the slowdown is clear, and there are two reasonable ways to fix it.
Staying in PostgreSQL works today: daily partitions and batched inserts can absorb 1,000 rows a second, and many teams would stop there. Today’s number is not what decides it. The location data grows with every new city, it is only ever appended, it is read by one key, and it must not slow down the orders again.
If the location stream were small and not expected to grow, keeping one database would have been the better answer.
What to remember
- A B+tree updates pages in place. That is good for reads, and costly for a heavy stream of random writes once the indexes no longer fit in memory.
- An LSM tree only appends. Each write goes to a log and a memtable, a full memtable is flushed as an immutable sorted SSTable, and compaction merges SSTables later. Deletes are written as tombstones.
- Bloom filters let reads skip files that cannot hold a key; about 10 bits a key gives about 1% false positives, and there are no false negatives.
- Each compaction policy strikes a different balance of read, write and space amplification: size-tiered writes less, leveled reads and stores less.
- “NoSQL” is a set of data models, each good at some questions and bad at others; the storage engine underneath is a separate choice.
For data that is only ever appended, write it sequentially and do the sorting and merging later, in bulk.
In the real world
Real LSM engines add what the simulator leaves out: values, compression per block, many files per level with compaction chosen by key range, rate limits on compaction, and filters kept in memory or cached. Cassandra and ScyllaDB let you choose the compaction strategy per table; RocksDB exposes dozens of knobs, and its tuning guide is mostly about choosing where to sit between read, write and space amplification.
The rider stream returns twice: in metrics and monitoring (lesson 5.8), where time-series data is the whole problem, and in rider matching (lesson 6.2), where only the latest location matters.