RocksDB

22 July 2018

Levelled Compaction vs Universal Compaction

The former only happens between two adjacent sorted runs. The latter happens between more than 1 adjacent sorted runs. Universal-Compaction#conceptual-basis gives a high-level description about this.

  • Why exponentially closer?
    Consider L0, L1, L3, L4. After a update is flushed from memtable to L0,

  • L0, L1 are compacted into L01
  • L2, L3 are compacted into L23

  • L01, L23 are compacted into L0123

  • Why?

    In leveled compaction, however, an update is compacted more as a part of the larger sorted run where a smaller sorted run is merged into, than as a part of the smaller sorted run. As a result, in most of the times an update is compacted, it is not moved to a larger sorted run, so it doesn’t make much progress towards the final largest run.

The reason is how we pick SST files? After we pick more than one SST file in the small level, we need to pick all the overlapping SST files in the large level.

References