LSM Capstone: Everything

The System Design board on choosing a storage engine for the job, with the log-structured one drawn as a stack of sorted books. This capstone is that engine, built. Closes the LSM series, Build Your Own LSM Tree.

Before you start. This series built a small copy of a log-structured storage engine in seven stages. By now it can: keep recent writes in a sorted memtable (LSM 01-02: The Memtable and the Log); log every write first so a crash cannot lose one; flush the memtable into an immutable sorted file with a sparse index (LSM 03-04: Table Files and the Sparse Index); skip files with a Bloom filter (LSM 05: The Bloom Filter); and merge files in levels so a lookup touches about one (LSM 06-07: Compaction and Levels). This lesson follows a write and a read through all of it and compares the result with the real library the design came from.