Leveled compaction assigns each SSTable a level. A partition will only exist in one SSTable per level.
Animation 1: Here’s our first SSTable flushed to disk. It has five partitions, each identified by their token key.
Animation 2: Since this is a newly flushed SSTable, level-tiered compaction considers this SSTable to be in level zero. Generally any table residing in level zero immediately compacts to lower levels. Since there are no other SSTables to compact with, this table remains in L0 for the time being.
Animation 3: Here’s a second flushed SSTable. Leveled compaction will now compact the two L0 SSTables together.
Animation 4: Leveled compaction always compacts down to the level immediately below the current one. In this case, that’s level 1 (L1).
Animation 5: As with all compaction, we combine partitions together from the two source SSTables into a new SSTable. In these illustrations, we are assuming no updates/deletes, hence our new partitions sizes will be the sum of the two source partitions.
Animation 6: Here we combine the two 12 token key partitions into a single partition in a new SSTable.
Animation 7: Leveled compaction maintains a max SSTable size. This is tunable. The default value is 160MB.
Animation 8: We continue adding source partitions to the new SSTable until the new SSTable meets or exceeds the max SSTable size.
Animation 9: We maxed our size, so we create a new SSTable.
Animation 10: Partition 52 is rather large and takes up the whole of our new SSTable.
Animation 11: So we make a new SSTable.
Animation 12: Combine 74
Animation 13: And also 88
Animation 14: We delete the old L0 SSTables.
Animation 15: Each level has a max size. In practice, this is 10x the size of the previous level, L0 considered 160MB. (However, the size of L0 depends on the size of the SSTables flushed to it, which is determined by factors that cause the MemTable to flush to disk.)
Animation 16: In our example and to save screen real-estate, we will use a multiplier of two instead of ten, but the algorithm still works the same.
Animation 17: You can see that L1 is too large, so leveled compaction further compacts SSTables from L1 to L2.
Animation 18: Since there are no existing tables in L2, compacting L1 to L2 is simply a matter of moving an existing L1 SSTable to L2. Leveled compaction tries to consider the SSTables in turn when selecting which SSTable to compact to a lower level.
Animation 19: L1 is still too large.
Animation 20: So we compact another SSTable down to L2.
Animation 21: (Cleaning up the visuals.)
Animation 22: L2 has a max size.
Animation 23: L2’s max size is twice the size of L1. (Remember, the real multiplier is ten, not two however.)
Animation 24: So now our levels are in a consistent state. Leveled compaction is complete.
Animation 25: A new SSTable flushes to disk into L0. Leveled compaction will immediately compact this new SSTable with the SSTables in L1.
Critical: The way leveled compaction chooses which SSTables to compact together is simply a matter of overlapping token keys. For example, this new SSTable covers token ranges 8 to 88 inclusive. The single SSTable in L1 covers the token range 74 to 88 inclusive. Since these two ranges overlap, leveled compaction will combine these two SSTables together.
Animation 26: So let’s compact these two SSTables together.
Animation 27: Partitions 8, 28, and 52 don’t have any pairs in the SSTable on the right, so they compact as is.
Animation 28: We hit the max SSTable size, so time to write a new one.
Animation 29: 74 is the lowest key between the two SSTables, so leveled compaction writes it next.
Animation 30: Finally the two 88 partitions from both SSTables combine to make a new partition.
Animation 31: Oh no, L1 is too big again. We must continue compacting down.
Important: Can you determine which SSTables will compact next?
Answer: Since both SSTables are new to the compaction party in L1, leveled compaction picks the first to compact down. Leveled compaction then determines which SSTables in L2 overlap with this SSTable. This SSTable has a token range of 8 to 52 inclusive. This range overlaps the first two SSTables in L2, each having a token range of 12 to 28 inclusive and 52 to 52 inclusive respectively.
Animation 32: Let’s compact!
Animation 33: We first compact 8 since it’s the lowest token between all three tables.
Animation 34: Then 12
Animation 35: Then 28. Notice there are two SSTables containing a partition of token 28. If all three SSTables contained 28, we would combine all three instead.
Animation 36: That new SSTable is full.
Animation 37: We combine the two 52 partitions into one huge partition. Again, they take up the entire SSTable.
Animation 38: We are now in a consistent state where all levels are not too large.
Animation 39: And the process continues as Cassandra flushes SSTables to L0.