cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From tylerho...@apache.org
Subject git commit: Fix AssertionError in RangeTombstoneList diff
Date Thu, 02 Oct 2014 16:59:27 GMT
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 <ud1937@gmail.com>
Authored: Thu Oct 2 11:56:42 2014 -0500
Committer: Tyler Hobbs <tyler@datastax.com>
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);


Mime
View raw message