Every 4 seconds, every active Tiffin rider's phone sends a location ping. At dinner time that's 150,000 riders, so about 37,500 writes a second, nearly all of them inserts into a giant, ever-growing history table. Reads are rare: support agents replaying a delivery route, or the ETA model training overnight.
A B-tree, from the last lesson, handles this badly. Each insert rewrites a whole page, inserts land all over the tree if the key isn't time-ordered, and the WAL doubles the writing. The disk spends its time on random writes.
The log-structured merge tree (LSM tree) flips the trade-off. It never updates anything in place. Writes go into memory and are flushed to disk as large, sorted, immutable files. Background work merges those files later. Writes become almost entirely sequential, and that's much faster on both spinning disks and SSDs.
The parts
| Part | Where | What it is |
|---|---|---|
| WAL | disk | Append-only log of every write, for crash recovery (the last-but-one lesson) |
| Memtable | memory | A sorted structure (often a skip list) holding recent writes |
| SSTable | disk | Sorted String Table: an immutable file of key-value pairs sorted by key, with an index and a Bloom filter |
| Compaction | background | Merges SSTables, keeping only the newest version of each key |
An LSM tree buffers writes in a sorted in-memory table, flushes it to disk as an immutable sorted file when it fills, and merges those files in the background. Writes are sequential and cheap. Reads may have to check several files.