22 July 2018

Levelled Compaction vs Universal Compaction

• 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.