hesela.devFragmented LSM tree
A fragmented LSM tree organizes overlapping sorted tables within disjoint guard key ranges to reduce repeated compaction writes.
Layout: PebblesDB introduced FLSM at SOSP 2017. A guard identifies a key interval, not a single table; tables within it may overlap. Compaction partitions output for destination guards instead of repeatedly merging it into their existing tables. [1]
Boundary: the last level still rewrites data, and the penultimate level can also rewrite locally. FLSM is not a zero-compaction design. [1]
Queries: table-level Bloom filters can reject point membership, but a negative for key q does not exclude a successor greater than q. PebblesDB uses additional seek optimizations, including compaction and parallel search, with their own write and CPU costs. The project documentation distinguishes these controls. [2]
Relations
- related
- Log-structured merge-tree, Sorted string table, Bloom filter, LSM compaction, Read amplification, Write amplification
Limitations
- Historical performance results depend on workload, compaction state and hardware; they are not a ranking of current database releases. [1]
Citations
- Raju et al. PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees. SOSP 2017, sections 3-5. DOI: 10.1145/3132747.3132765.
- PebblesDB authors: read and seek optimizations, tuning and post-paper changes
Further reading
Sources & caveats
- Source-based synthesis, not a PebblesDB execution or reproduction of its benchmarks.
- Hesela's separate successor example uses constructed integer keys and exact membership, not an implemented Bloom filter.