Cassandra
  1. Cassandra
  2. CASSANDRA-4234

Add tombstone-removal compaction to LCS

    Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Minor Minor
    • Resolution: Fixed
    • Fix Version/s: 1.2.0 beta 1
    • Component/s: None
    • Labels:

      Description

      CASSANDRA-3442 will recompact sstables with high levels of expired tombstones, but only under SCS.

      1. 4234.txt
        16 kB
        Yuki Morishita
      2. 4234.txt
        15 kB
        Yuki Morishita

        Activity

        Hide
        Yuki Morishita added a comment -

        Attaching patch to enable tombstone removal on leveled compaction with unit test. (or see https://github.com/yukim/cassandra/commits/4234)
        Logic is basically the same as size-tiered. We don't want to promote level of compacted sstable after tombstone removal compaction(otherwise may cause AIOOB exception), so I added new compaction OperationType.TOMBSTONE_COMPACTION to prevent promotion.

        Show
        Yuki Morishita added a comment - Attaching patch to enable tombstone removal on leveled compaction with unit test. (or see https://github.com/yukim/cassandra/commits/4234 ) Logic is basically the same as size-tiered. We don't want to promote level of compacted sstable after tombstone removal compaction(otherwise may cause AIOOB exception), so I added new compaction OperationType.TOMBSTONE_COMPACTION to prevent promotion.
        Hide
        Jonathan Ellis added a comment -

        How expensive is findDroppableSSTable when you have 50K sstables?

        If it needs to be optimized, one possibility might be to create a new IntervalTree method (intersects?) that returns true if any sstable in the tree overlaps the given range. This would allow us to (1) short circuit the search as soon as the first overlap is found and (2) avoid the rest of the allocation done by union + difference in getOverlappingSSTables. Would need some logic to avoid self-matching though...

        Nit: would prefer to inline loop sources unless they're exceptionally complex, e.g.

        +            List<SSTableReader> candidates = manifest.getLevel(i);
        +            for (SSTableReader sstable : candidates)
        

        becomes simply

        +            for (SSTableReader sstable : manifest.getLevel(i))
        
        Show
        Jonathan Ellis added a comment - How expensive is findDroppableSSTable when you have 50K sstables? If it needs to be optimized, one possibility might be to create a new IntervalTree method ( intersects ?) that returns true if any sstable in the tree overlaps the given range. This would allow us to (1) short circuit the search as soon as the first overlap is found and (2) avoid the rest of the allocation done by union + difference in getOverlappingSSTables. Would need some logic to avoid self-matching though... Nit: would prefer to inline loop sources unless they're exceptionally complex, e.g. + List<SSTableReader> candidates = manifest.getLevel(i); + for (SSTableReader sstable : candidates) becomes simply + for (SSTableReader sstable : manifest.getLevel(i))
        Hide
        Yuki Morishita added a comment -

        (Attaching modified and rebased patch)

        So, after running some benchmark, I concluded that getOverlappingSSTables is not going to be a bottleneck. After all it's O(log n) operation.

        But the problem rises if you iterate on 50K (or large number of) sstables. So I modified the patch to first sort sstables by droppable ratio in descent order, and skip iteration if it finds the ratio below threshold. I think this feature combined with the nature of LCS (fewer overlap among sstables) prevent a lot of calculation in findDroppableSSTable.

        Show
        Yuki Morishita added a comment - (Attaching modified and rebased patch) So, after running some benchmark, I concluded that getOverlappingSSTables is not going to be a bottleneck. After all it's O(log n) operation. But the problem rises if you iterate on 50K (or large number of) sstables. So I modified the patch to first sort sstables by droppable ratio in descent order, and skip iteration if it finds the ratio below threshold. I think this feature combined with the nature of LCS (fewer overlap among sstables) prevent a lot of calculation in findDroppableSSTable.
        Hide
        Jonathan Ellis added a comment -

        I think we need a synchronized method in LeveledManifest to return a copy of generations[i]. Otherwise {{new ArrayList<SSTableReader>(manifest.getLevel) }}can race and error out.

        Nit: would rename canDropTombstone to something like worthDroppingTombstones

        Show
        Jonathan Ellis added a comment - I think we need a synchronized method in LeveledManifest to return a copy of generations [i] . Otherwise {{new ArrayList<SSTableReader>(manifest.getLevel ) }}can race and error out. Nit: would rename canDropTombstone to something like worthDroppingTombstones
        Hide
        Yuki Morishita added a comment -

        Attaching patch with above two points corrected.

        Show
        Yuki Morishita added a comment - Attaching patch with above two points corrected.
        Hide
        Jonathan Ellis added a comment -

        LGTM, +1

        Show
        Jonathan Ellis added a comment - LGTM, +1
        Hide
        Yuki Morishita added a comment -

        Committed, thanks!

        Show
        Yuki Morishita added a comment - Committed, thanks!
        Hide
        Hudson added a comment -

        Integrated in Cassandra #1699 (See https://builds.apache.org/job/Cassandra/1699/)
        Track tombstone for LCS; patch by yukim reviewed by jbellis for CASSANDRA-4234 (Revision 0091af932c6ef65a0a5917f123fe24398b79c079)

        Result = ABORTED
        yukim :
        Files :

        • src/java/org/apache/cassandra/db/compaction/SizeTieredCompactionStrategy.java
        • src/java/org/apache/cassandra/db/compaction/OperationType.java
        • src/java/org/apache/cassandra/db/compaction/LeveledCompactionStrategy.java
        • CHANGES.txt
        • test/unit/org/apache/cassandra/db/compaction/CompactionsTest.java
        • src/java/org/apache/cassandra/db/compaction/LeveledManifest.java
        • src/java/org/apache/cassandra/db/compaction/AbstractCompactionStrategy.java
        Show
        Hudson added a comment - Integrated in Cassandra #1699 (See https://builds.apache.org/job/Cassandra/1699/ ) Track tombstone for LCS; patch by yukim reviewed by jbellis for CASSANDRA-4234 (Revision 0091af932c6ef65a0a5917f123fe24398b79c079) Result = ABORTED yukim : Files : src/java/org/apache/cassandra/db/compaction/SizeTieredCompactionStrategy.java src/java/org/apache/cassandra/db/compaction/OperationType.java src/java/org/apache/cassandra/db/compaction/LeveledCompactionStrategy.java CHANGES.txt test/unit/org/apache/cassandra/db/compaction/CompactionsTest.java src/java/org/apache/cassandra/db/compaction/LeveledManifest.java src/java/org/apache/cassandra/db/compaction/AbstractCompactionStrategy.java

          People

          • Assignee:
            Yuki Morishita
            Reporter:
            Jonathan Ellis
            Reviewer:
            Jonathan Ellis
          • Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development