Log-Structured Storage and Compaction
Writing sequentially to a log and merging sorted runs in the background turns random writes into sequential ones. Reads then have to consult several runs, so the design trades read amplification and background work against write throughput.
What a learner can do afterwards
- Trace a key through a memory table, a flushed run and a compaction
- Say which of write, read and space amplification each compaction policy favours
- Explain why a read may have to touch several runs, and what a membership filter saves
1 · Read
Every write lands first in a memory table, which later flushes to disk as one sorted run. Each key may then own several copies across runs, and the newest copy wins. A background job called compaction merges runs into bigger sorted runs and drops the shadowed copies.
Key k is written twice. The older value rests in a flushed run while the newer value sits in the memory table. A read checks newest first and stops at the fresh copy. After the next compaction, only one copy of k remains.
Two policies split the trade. Tiered merging keeps several runs per level and merges rarely: writes stay cheap, but reads check more runs and old copies linger, so read and space amplification grow. Leveled merging keeps about one run per level and merges often: reads stay short and space stays tight, but data is rewritten more, so write amplification grows.
A read may have to touch several runs, so each run carries a small membership filter. A filter that says no lets the read skip that run entirely. The price is a little memory plus rare false positives that cost one wasted look.
Sequential writes plus background merges trade read and space costs against write speed.
2 · Watch
Take it off screen
Where it sits
Learn first
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.