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.
L0, L1, L3, L4. After a update is flushed from memtable to L0,
L0, L1are compacted into
L2, L3are compacted into
L01, L23are compacted into
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.