LSM-Tree Storage Engine — Write and Read Paths

LSM-Tree Storage Engine — Write and Read Paths A data-flow diagram generated by Archify. 01 / Write Requests 02 / Reads & Memtable 03 / Sorted Segments 04 / Background Merge Write · put(key, value) · 01 / Write Requests · append Write put(key, value) append Write-Ahead Log · append-only, checksummed · 01 / Write Requests · durability Write-Ahead Log append-only, checksummed durability Memtable · sorted in-memory map · 02 / Reads & Memtable · a few MB Memtable sorted in-memory map a few MB Point Read · get(key), newest first · 02 / Reads & Memtable · cascade Point Read get(key), newest first cascade SSTable Segments · sorted, immutable files · 03 / Sorted Segments · newest to oldest SSTable Segments sorted, immutable files newest to oldest Bloom Filter · one bitmap per segment · 03 / Sorted Segments · false positives ok Bloom Filter one bitmap per segment false positives ok Compaction · mergesort-style merge · 04 / Background Merge · background thread Compaction mergesort-style merge background thread update ordered map hot path append + fsync durability replay after crash recovery flush sorted SSTable immutable segment merge segments, keep newest value tombstones dropped 1. check memtable lookup order 2. key in this segment? probabilistic 3. seek sparse index + block confirmed only Legend primary data async batch data store data flow