Uploaded image for project: 'Cassandra'
  1. Cassandra
  2. CASSANDRA-3854

Lower levels should have higher priority in LeveledCompactionStrategy

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Resolved
    • Low
    • Resolution: Duplicate
    • None
    • None

    Description

      In LeveledCompactionStrategy, there is a comment explaining why compactions prioritize the top levels:

      So instead, we force compacting higher levels first. This may not minimize the number of reads done as quickly in the short term, but it minimizes the i/o needed to compact optimially which gives us a long term win.

      The argument is that compacting the lower levels first causes data to be re-compacted more frequently.

      But the result of compacting the top levels first is that each compaction pass does less total work, because the number of overlapping files in a particular level is limited to the number of files that can be generated by a single compaction pass.

      Consider the overload example from that comment:

      L0: 988 [ideal: 4]
      L1: 117 [ideal: 10]
      L2: 12 [ideal: 100]

      Assuming that there are initially no overlapping files in L2 or L1, the current implementation will:

      1. Compact 32 files from L0 into L1 (which will cause 32 L0 files and 117 L1 files to be compacted together)
      2. Possibly compact L1 and L2 in order to remove overlapping files due to the L0 compaction
      3. Repeat
        The problem with this strategy is that only every 3rd compaction will be working to drain L0. Additionally, each compaction that occurs in L1 and L2 will be doing the minimum possible work that can trigger a compaction (the equivalent of SizeTieredStrategy triggering the min threshold).

      If we agree that the goal is to ensure that L0 is drained (since a proliferation of tiny overlapping files means worst case read behavior), then a better strategy would be to start from the lower levels, and to change compaction of L0 to not include L1. With this strategy, the steps would be:

      1. Compact 32 files from L0 (causing them to be partitioned and placed in L1)
      2. Repeat
      3. Compact ?? files from LN into LN+1 (existing strategy)
      4. Repeat
        With this approach, L0 is quickly partitioned, considerably shortening the time during which 988 files need to be checked. Additionally, because each level is completely drained before moving to the next, compactions occurring within a level are triggering the equivalent of SizeTieredStrategy's max threshold (aka, always hitting a cap of 32 involved files.)

      Attachments

        Issue Links

          Activity

            People

              Unassigned Unassigned
              stuhood Stu Hood
              Votes:
              0 Vote for this issue
              Watchers:
              7 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: