Repository: cassandra Updated Branches: refs/heads/cassandra-2.1 1c3932086 -> f0893f544
Fix AssertionError in RangeTombstoneList diff Patch by Philo Yang and Oleg Anastasyev; reviewed by Tyler Hobbs for CASSANDRA-8013 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/f0893f54 Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/f0893f54 Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/f0893f54 Branch: refs/heads/cassandra-2.1 Commit: f0893f544ff30162f4432730634978530ec15077 Parents: 1c39320 Author: Philo Yang <[email protected]> Authored: Thu Oct 2 11:56:42 2014 -0500 Committer: Tyler Hobbs <[email protected]> Committed: Thu Oct 2 11:56:42 2014 -0500 ---------------------------------------------------------------------- CHANGES.txt | 1 + .../apache/cassandra/db/RangeTombstoneList.java | 34 ++-- .../cassandra/db/RangeTombstoneListTest.java | 171 +++++++++++++++++++ 3 files changed, 193 insertions(+), 13 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/f0893f54/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 95218cb..3c3b838 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -1,4 +1,5 @@ 2.1.1 + * Fix Assertion error on RangeTombstoneList diff (CASSANDRA-8013) * Release references to overlapping sstables during compaction (CASSANDRA-7819) * Send notification when opening compaction results early (CASSANDRA-8034) * Make native server start block until properly bound (CASSANDRA-7885) http://git-wip-us.apache.org/repos/asf/cassandra/blob/f0893f54/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 cbb4abe..c0ab42b 100644 --- a/src/java/org/apache/cassandra/db/RangeTombstoneList.java +++ b/src/java/org/apache/cassandra/db/RangeTombstoneList.java @@ -410,7 +410,7 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>, IMeasurable } }; } - + /** * Evaluates a diff between superset (known to be all merged tombstones) and this list for read repair * @@ -421,29 +421,37 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>, IMeasurable 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/f0893f54/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 798ce91..712cfa2 100644 --- a/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java +++ b/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java @@ -34,6 +34,177 @@ public class RangeTombstoneListTest private static final Random rand = new Random(); @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);
