hesela.devSorted run
In an LSM-tree, a disk-resident sorted run is a logical sequence of key-ordered records stored in one immutable SST file or range-partitioned across multiple SST files.
Layout: RocksDB's nonzero leveled levels each form one run, while L0 can contain overlapping runs. Individual files being sorted does not make an arbitrary overlapping collection one globally ordered run. [1]
Counting: The documented Universal-compaction example has three one-file L0 runs, a four-file L4 run and an eight-file L5 run: five runs across fifteen files. This is a layout illustration, not a benchmark or a required configuration. [2]
Visibility: Sorted records are not necessarily only the latest values visible to a reader. LevelDB retains deletion markers to hide older values and merges tables during compaction. Ordering, visibility and reclamation are separate concerns. [3]
Relations
Limitations
- Run count is not a physical-read count: key-range selection, filters, caching and the query type affect which data must actually be read. [4, 6]
- A Bloom-negative probe can still require filter metadata. Measure key-present/key-absent mix and metadata-cache residency; the cited study's mixed-query latency is an experiment-specific result, not a consequence of run count alone. [4]
Citations
- RocksDB project. Leveled Compaction: Structure of the files.
- RocksDB project. Universal Compaction: Overview and Data Layout / Sorted Runs.
- LevelDB 1.23 implementation note: Sorted tables and Compactions.
- Sarkar et al. Constructing and Analyzing the LSM Compaction Design Space. PVLDB 14(11), 2216-2229 (2021), sections 2 and 5.1.2. DOI: 10.14778/3476249.3476274.
- RocksDB project. Tuning Guide: Amplification factors and cached versus physical reads.