The Log-Structured Merge-Tree (LSM-Tree)
Buy cheap writes with expensive reads on purpose, and settle the trade with a cost model rather than a benchmark.
Read the original ↗Every write-optimised store of the last twenty years cites this paper, and almost none of them implement what is in it. Read it anyway: the thing it gets right is not the data structure, it is the arithmetic underneath the data structure, and that half is still the best argument for the design anyone has written.
Included with a plan
This discussion is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.
Related on chalk
The same idea as a board, lab, video or lesson.
- BoardStorage Enginesthe memtable, the SSTables and the compaction, as they were eventually built
- BoardB-Tree on Diskthe update-in-place structure whose doubled I/O cost this paper opens by complaining about
- BoardWAL & Recoverythe log the paper's recovery scheme free-rides on rather than writing its own
- BoardThe Append-Only Filethe idea at its smallest - only ever append, and pay for it at read time
- BoardThe Memory Hierarchythe seek-against-sequential gap the paper's whole cost model is denominated in
- BoardThe Message Store Sagaan LSM store at trillions of rows, and the compaction backlog the paper's model cannot show
- BoardThe Right Book for the Jobwhere a write-tuned engine wins, and the queries it hands back to you
- LabLSM vs B-treethe exact trade with a dial on it, and the read share where the bill flips
- LabThe write-ahead logcheckpoint frequency against replay time - the recovery half of the design, run
- LabThe memory hierarchy31x between a scan and a pointer chase, which is why a merge beats a seek
- VideoChoosing a datastore: the workload picks the bookan LSM and a B-tree cut in half side by side, with the workload choosing
- LessonStorage EnginesUses the board Storage Engines
- LessonBuild Your Own LSM TreeUses the board Storage Engines
- LessonLSM 01-02: The Memtable and the LogUses the board Storage Engines
- LessonB-Tree on DiskUses the board B-Tree on Disk
- LessonWhich shortcut to buildUses the board B-Tree on Disk
- LessonBuild three ways to joinUses the board B-Tree on Disk
- LessonWAL & RecoveryUses the board WAL & Recovery
- LessonThe engine in productionUses the board WAL & Recovery
- LessonDatabase 01: The Append-Only FileUses the board The Append-Only File
- LessonThe Memory Hierarchy (cache, locality, the memory wall)Uses the board The Memory Hierarchy
- LessonLSM 06-07: Compaction and LevelsUses the board The Message Store Saga
- LessonDiscord - the case studyUses the board The Message Store Saga
- LessonLSM Capstone: EverythingUses the board The Right Book for the Job
- LessonThe Right Book for the Job (databases, deeply)Uses the board The Right Book for the Job
- LessonThe last vada (inventory contention and locking)Uses the board The Right Book for the Job
Further reading
Read the original for the full argument and its evidence.
- The paper (PDF) ↗Acta Informatica, 1996. Sections 1 and 3 are the argument - the disk-arm economics and Theorem 3.1. Read section 2's rolling merge knowing in advance that nothing shipped it.
- LSM-based Storage Techniques: A Survey ↗Later work: the map of everything that happened between this paper and RocksDB - the compaction strategies, the filters, and the three amplifications written down as numbers you can trade against each other.
- RocksDB compaction ↗Later work: what levelled and universal compaction actually do, in the engine most people mean when they say LSM.