Repository: cassandra Updated Branches: refs/heads/cassandra-3.0 cd5d03d2b -> eb01654b9
Backport CASSANDRA-8013 to 2.0 Fix AssertionError in RangeTombstone.diff() Patch by Carl Yeksigian; reviewed by Tyler Hobbs for CASSANDRA-10144 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/517058fe Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/517058fe Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/517058fe Branch: refs/heads/cassandra-3.0 Commit: 517058febbdf6c1faa4902f1b9b93d2b0c25c4b1 Parents: 500c035 Author: Carl Yeksigian <c...@apache.org> Authored: Tue Sep 1 13:43:22 2015 -0400 Committer: Tyler Hobbs <tylerlho...@gmail.com> Committed: Thu Sep 3 14:59:07 2015 -0500 ---------------------------------------------------------------------- CHANGES.txt | 1 + .../apache/cassandra/db/RangeTombstoneList.java | 32 ++-- .../cassandra/db/RangeTombstoneListTest.java | 178 ++++++++++++++++++- 3 files changed, 193 insertions(+), 18 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/517058fe/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 905445e..0e4ade3 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -1,4 +1,5 @@ 2.0.17 + * Backport CASSANDRA-8013 to 2.0 (CASSANDRA-10144) * Make getFullyExpiredSSTables less expensive (CASSANDRA-9882) * Add tool to find why expired sstables are not getting dropped (CASSANDRA-10015) * Remove erroneous pending HH tasks from tpstats/jmx (CASSANDRA-9129) http://git-wip-us.apache.org/repos/asf/cassandra/blob/517058fe/src/java/org/apache/cassandra/db/RangeTombstoneList.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/RangeTombstoneList.java b/src/java/org/apache/cassandra/db/RangeTombstoneList.java index 165718e..cfdd54e 100644 --- a/src/java/org/apache/cassandra/db/RangeTombstoneList.java +++ b/src/java/org/apache/cassandra/db/RangeTombstoneList.java @@ -343,29 +343,37 @@ public class RangeTombstoneList implements Iterable<RangeTombstone> if (isEmpty()) return superset; - assert size <= superset.size; - RangeTombstoneList diff = null; int j = 0; // index to iterate through our own list for (int i = 0; i < superset.size; i++) { - boolean sameStart = j < size && starts[j].equals(superset.starts[i]); - // don't care about local deletion time here. for RR it doesn't makes sense - if (!sameStart + // we can assume that this list is a subset of the superset list + while (j < size && comparator.compare(starts[j], superset.starts[i]) < 0) + j++; + + if (j >= size) + { + // we're at the end of our own list, add the remainder of the superset to the diff + if (i < superset.size) + { + if (diff == null) + diff = new RangeTombstoneList(comparator, superset.size - i); + + for(int k = i; k < superset.size; k++) + diff.add(superset.starts[k], superset.ends[k], superset.markedAts[k], superset.delTimes[k]); + } + return diff; + } + + // we don't care about local deletion time here, because it doesn't matter for read repair + if (!starts[j].equals(superset.starts[i]) || !ends[j].equals(superset.ends[i]) || markedAts[j] != superset.markedAts[i]) { if (diff == null) diff = new RangeTombstoneList(comparator, Math.min(8, superset.size - i)); diff.add(superset.starts[i], superset.ends[i], superset.markedAts[i], superset.delTimes[i]); - - if (sameStart) - j++; - } - else - { - j++; } } http://git-wip-us.apache.org/repos/asf/cassandra/blob/517058fe/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java ---------------------------------------------------------------------- diff --git a/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java b/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java index 2a7c90f..d4bc463 100644 --- a/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java +++ b/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java @@ -32,6 +32,177 @@ public class RangeTombstoneListTest private static final Comparator<ByteBuffer> cmp = IntegerType.instance; @Test + public void testDiff() + { + RangeTombstoneList superset; + RangeTombstoneList subset; + RangeTombstoneList diff; + Iterator<RangeTombstone> iter; + + // no difference + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + superset.add(rt(1, 10, 10)); + superset.add(rt(20, 30, 10)); + superset.add(rt(40, 50, 10)); + subset.add(rt(1, 10, 10)); + subset.add(rt(20, 30, 10)); + subset.add(rt(40, 50, 10)); + assertNull( subset.diff(superset)); + + // all items in subset are contained by the first range in the superset + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + subset.add(rt(1, 2, 3)); + subset.add(rt(3, 4, 4)); + subset.add(rt(5, 6, 5)); + superset.add(rt(1, 10, 10)); + superset.add(rt(20, 30, 10)); + superset.add(rt(40, 50, 10)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(1, 10, 10), iter.next()); + assertRT(rt(20, 30, 10), iter.next()); + assertRT(rt(40, 50, 10), iter.next()); + assertFalse(iter.hasNext()); + + // multiple subset RTs are contained by superset RTs + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + subset.add(rt(1, 2, 1)); + subset.add(rt(3, 4, 2)); + subset.add(rt(5, 6, 3)); + superset.add(rt(1, 5, 2)); + superset.add(rt(5, 6, 3)); + superset.add(rt(6, 10, 2)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(1, 5, 2), iter.next()); + assertRT(rt(6, 10, 2), iter.next()); + assertFalse(iter.hasNext()); + + // the superset has one RT that covers the entire subset + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + superset.add(rt(1, 50, 10)); + subset.add(rt(1, 10, 10)); + subset.add(rt(20, 30, 10)); + subset.add(rt(40, 50, 10)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(1, 50, 10), iter.next()); + assertFalse(iter.hasNext()); + + // the superset has one RT that covers the remainder of the subset + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + superset.add(rt(1, 10, 10)); + superset.add(rt(20, 50, 10)); + subset.add(rt(1, 10, 10)); + subset.add(rt(20, 30, 10)); + subset.add(rt(40, 50, 10)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(20, 50, 10), iter.next()); + assertFalse(iter.hasNext()); + + // only the timestamp differs on one RT + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + superset.add(rt(1, 10, 10)); + superset.add(rt(20, 30, 20)); + superset.add(rt(40, 50, 10)); + subset.add(rt(1, 10, 10)); + subset.add(rt(20, 30, 10)); + subset.add(rt(40, 50, 10)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(20, 30, 20), iter.next()); + assertFalse(iter.hasNext()); + + // superset has a large range on an RT at the start + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + superset.add(rt(1, 10, 10)); + superset.add(rt(20, 30, 10)); + superset.add(rt(40, 50, 10)); + subset.add(rt(1, 2, 3)); + subset.add(rt(20, 30, 10)); + subset.add(rt(40, 50, 10)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(1, 10, 10), iter.next()); + assertFalse(iter.hasNext()); + + // superset has a larger range on an RT in the middle + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + superset.add(rt(1, 10, 10)); + superset.add(rt(20, 30, 10)); + superset.add(rt(40, 50, 10)); + subset.add(rt(1, 10, 10)); + subset.add(rt(20, 25, 10)); + subset.add(rt(40, 50, 10)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(20, 30, 10), iter.next()); + assertFalse(iter.hasNext()); + + // superset has a larger range on an RT at the end + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + superset.add(rt(1, 10, 10)); + superset.add(rt(20, 30, 10)); + superset.add(rt(40, 55, 10)); + subset.add(rt(1, 10, 10)); + subset.add(rt(20, 30, 10)); + subset.add(rt(40, 50, 10)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(40, 55, 10), iter.next()); + assertFalse(iter.hasNext()); + + // superset has one additional RT in the middle + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + superset.add(rt(1, 10, 10)); + superset.add(rt(20, 30, 10)); + superset.add(rt(40, 50, 10)); + subset.add(rt(1, 10, 10)); + subset.add(rt(40, 50, 10)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(20, 30, 10), iter.next()); + assertFalse(iter.hasNext()); + + // superset has one additional RT at the start + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + superset.add(rt(1, 10, 10)); + superset.add(rt(20, 30, 10)); + superset.add(rt(40, 50, 10)); + subset.add(rt(20, 30, 10)); + subset.add(rt(40, 50, 10)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(1, 10, 10), iter.next()); + assertFalse(iter.hasNext()); + + // superset has one additional RT at the end + superset = new RangeTombstoneList(cmp, 10); + subset = new RangeTombstoneList(cmp, 10); + superset.add(rt(1, 10, 10)); + superset.add(rt(20, 30, 10)); + superset.add(rt(40, 50, 10)); + subset.add(rt(1, 10, 10)); + subset.add(rt(20, 30, 10)); + diff = subset.diff(superset); + iter = diff.iterator(); + assertRT(rt(40, 50, 10), iter.next()); + assertFalse(iter.hasNext()); + } + + @Test public void sortedAdditionTest() { sortedAdditionTest(0); @@ -193,12 +364,6 @@ public class RangeTombstoneListTest @Test public void addAllTest() { - //addAllTest(false); - addAllTest(true); - } - - private void addAllTest(boolean doMerge) - { RangeTombstoneList l1 = new RangeTombstoneList(cmp, 0); l1.add(rt(0, 4, 5)); l1.add(rt(6, 10, 2)); @@ -364,6 +529,7 @@ public class RangeTombstoneListTest { System.out.println("Error merging:"); System.out.println(" l1: " + toString(l1Initial)); + System.out.println(" l2: " + toString(l2)); System.out.println("Seed was: " + seed); throw e; }