cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From s...@apache.org
Subject [2/6] cassandra git commit: Stop merkle tree recursion at leafs
Date Wed, 24 May 2017 12:53:33 GMT
Stop merkle tree recursion at leafs

patch by Stefan Podkowinski; reviewed by Blake Eggleston for CASSANDRA-13052


Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/38725802
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/38725802
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/38725802

Branch: refs/heads/cassandra-3.11
Commit: 38725802456dfcfcc2584cdfd061ac22215c2dfb
Parents: 7db6a3b
Author: Stefan Podkowinski <s.podkowinski@gmail.com>
Authored: Tue Dec 20 14:40:18 2016 +0100
Committer: Stefan Podkowinski <s.podkowinski@gmail.com>
Committed: Wed May 24 13:55:11 2017 +0200

----------------------------------------------------------------------
 CHANGES.txt                                     |  1 +
 .../cassandra/repair/messages/RepairOption.java |  4 ++
 .../org/apache/cassandra/utils/MerkleTree.java  | 42 +++++++++++++++++++-
 .../repair/messages/RepairOptionTest.java       |  2 +-
 .../apache/cassandra/utils/MerkleTreeTest.java  | 34 +++++++++++++++-
 5 files changed, 79 insertions(+), 4 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/38725802/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index 84aba99..98a1808 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -1,4 +1,5 @@
 3.0.14
+ * Fix repair process violating start/end token limits for small ranges (CASSANDRA-13052)
  * Add storage port options to sstableloader (CASSANDRA-13518)
  * Properly handle quoted index names in cqlsh DESCRIBE output (CASSANDRA-12847)
  * Avoid reading static row twice from old format sstables (CASSANDRA-13236)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/38725802/src/java/org/apache/cassandra/repair/messages/RepairOption.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/repair/messages/RepairOption.java b/src/java/org/apache/cassandra/repair/messages/RepairOption.java
index 44a1e57..9d60ad7 100644
--- a/src/java/org/apache/cassandra/repair/messages/RepairOption.java
+++ b/src/java/org/apache/cassandra/repair/messages/RepairOption.java
@@ -158,6 +158,10 @@ public class RepairOption
                 }
                 Token parsedBeginToken = partitioner.getTokenFactory().fromString(rangeStr[0].trim());
                 Token parsedEndToken = partitioner.getTokenFactory().fromString(rangeStr[1].trim());
+                if (parsedBeginToken.equals(parsedEndToken))
+                {
+                    throw new IllegalArgumentException("Start and end tokens must be different.");
+                }
                 ranges.add(new Range<>(parsedBeginToken, parsedEndToken));
             }
         }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/38725802/src/java/org/apache/cassandra/utils/MerkleTree.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/MerkleTree.java b/src/java/org/apache/cassandra/utils/MerkleTree.java
index 8a8cd9c..0d5a469 100644
--- a/src/java/org/apache/cassandra/utils/MerkleTree.java
+++ b/src/java/org/apache/cassandra/utils/MerkleTree.java
@@ -25,6 +25,9 @@ import java.util.*;
 import com.google.common.base.Preconditions;
 import com.google.common.collect.PeekingIterator;
 
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
 import org.apache.cassandra.db.TypeSizes;
 import org.apache.cassandra.dht.IPartitioner;
 import org.apache.cassandra.dht.IPartitionerDependentSerializer;
@@ -58,6 +61,8 @@ import org.apache.cassandra.net.MessagingService;
  */
 public class MerkleTree implements Serializable
 {
+    private static Logger logger = LoggerFactory.getLogger(MerkleTree.class);
+
     public static final MerkleTreeSerializer serializer = new MerkleTreeSerializer();
     private static final long serialVersionUID = 2L;
 
@@ -241,8 +246,12 @@ public class MerkleTree implements Serializable
 
         if (lhash != null && rhash != null && !Arrays.equals(lhash, rhash))
         {
+            logger.debug("Digest mismatch detected, traversing trees [{}, {}]", ltree, rtree);
             if (FULLY_INCONSISTENT == differenceHelper(ltree, rtree, diff, active))
+            {
+                logger.debug("Range {} fully inconsistent", active);
                 diff.add(active);
+            }
         }
         else if (lhash == null || rhash == null)
             diff.add(active);
@@ -262,8 +271,19 @@ public class MerkleTree implements Serializable
             return CONSISTENT;
 
         Token midpoint = ltree.partitioner().midpoint(active.left, active.right);
+        // sanity check for midpoint calculation, see CASSANDRA-13052
+        if (midpoint.equals(active.left) || midpoint.equals(active.right))
+        {
+            // Unfortunately we can't throw here to abort the validation process, as the
code is executed in it's own
+            // thread with the caller waiting for a condition to be signaled after completion
and without an option
+            // to indicate an error (2.x only).
+            logger.error("Invalid midpoint {} for [{},{}], range will be reported inconsistent",
midpoint, active.left, active.right);
+            return FULLY_INCONSISTENT;
+        }
+
         TreeDifference left = new TreeDifference(active.left, midpoint, inc(active.depth));
         TreeDifference right = new TreeDifference(midpoint, active.right, inc(active.depth));
+        logger.debug("({}) Hashing sub-ranges [{}, {}] for {} divided by midpoint {}", active.depth,
left, right, active, midpoint);
         byte[] lhash, rhash;
         Hashable lnode, rnode;
 
@@ -278,9 +298,16 @@ public class MerkleTree implements Serializable
         int ldiff = CONSISTENT;
         boolean lreso = lhash != null && rhash != null;
         if (lreso && !Arrays.equals(lhash, rhash))
-            ldiff = differenceHelper(ltree, rtree, diff, left);
+        {
+            logger.debug("({}) Inconsistent digest on left sub-range {}: [{}, {}]", active.depth,
left, lnode, rnode);
+            if (lnode instanceof Leaf) ldiff = FULLY_INCONSISTENT;
+            else ldiff = differenceHelper(ltree, rtree, diff, left);
+        }
         else if (!lreso)
+        {
+            logger.debug("({}) Left sub-range fully inconsistent {}", active.depth, right);
             ldiff = FULLY_INCONSISTENT;
+        }
 
         // see if we should recurse right
         lnode = ltree.find(right);
@@ -293,25 +320,36 @@ public class MerkleTree implements Serializable
         int rdiff = CONSISTENT;
         boolean rreso = lhash != null && rhash != null;
         if (rreso && !Arrays.equals(lhash, rhash))
-            rdiff = differenceHelper(ltree, rtree, diff, right);
+        {
+            logger.debug("({}) Inconsistent digest on right sub-range {}: [{}, {}]", active.depth,
right, lnode, rnode);
+            if (rnode instanceof Leaf) rdiff = FULLY_INCONSISTENT;
+            else rdiff = differenceHelper(ltree, rtree, diff, right);
+        }
         else if (!rreso)
+        {
+            logger.debug("({}) Right sub-range fully inconsistent {}", active.depth, right);
             rdiff = FULLY_INCONSISTENT;
+        }
 
         if (ldiff == FULLY_INCONSISTENT && rdiff == FULLY_INCONSISTENT)
         {
             // both children are fully inconsistent
+            logger.debug("({}) Fully inconsistent range [{}, {}]", active.depth, left, right);
             return FULLY_INCONSISTENT;
         }
         else if (ldiff == FULLY_INCONSISTENT)
         {
+            logger.debug("({}) Adding left sub-range to diff as fully inconsistent {}", active.depth,
left);
             diff.add(left);
             return PARTIALLY_INCONSISTENT;
         }
         else if (rdiff == FULLY_INCONSISTENT)
         {
+            logger.debug("({}) Adding right sub-range to diff as fully inconsistent {}",
active.depth, right);
             diff.add(right);
             return PARTIALLY_INCONSISTENT;
         }
+        logger.debug("({}) Range {} partially inconstent", active.depth, active);
         return PARTIALLY_INCONSISTENT;
     }
 

http://git-wip-us.apache.org/repos/asf/cassandra/blob/38725802/test/unit/org/apache/cassandra/repair/messages/RepairOptionTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/repair/messages/RepairOptionTest.java b/test/unit/org/apache/cassandra/repair/messages/RepairOptionTest.java
index 27eff56..b617e96 100644
--- a/test/unit/org/apache/cassandra/repair/messages/RepairOptionTest.java
+++ b/test/unit/org/apache/cassandra/repair/messages/RepairOptionTest.java
@@ -122,7 +122,7 @@ public class RepairOptionTest
     @Test
     public void testIncrementalRepairWithSubrangesIsNotGlobal() throws Exception
     {
-        RepairOption ro = RepairOption.parse(ImmutableMap.of(RepairOption.INCREMENTAL_KEY,
"true", RepairOption.RANGES_KEY, "42:42"),
+        RepairOption ro = RepairOption.parse(ImmutableMap.of(RepairOption.INCREMENTAL_KEY,
"true", RepairOption.RANGES_KEY, "41:42"),
                            Murmur3Partitioner.instance);
         assertFalse(ro.isGlobal());
         ro = RepairOption.parse(ImmutableMap.of(RepairOption.INCREMENTAL_KEY, "true", RepairOption.RANGES_KEY,
""),

http://git-wip-us.apache.org/repos/asf/cassandra/blob/38725802/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java b/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java
index 5924de0..c9aa09f 100644
--- a/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java
+++ b/test/unit/org/apache/cassandra/utils/MerkleTreeTest.java
@@ -21,7 +21,7 @@ package org.apache.cassandra.utils;
 import java.math.BigInteger;
 import java.util.*;
 
-import org.apache.cassandra.utils.AbstractIterator;
+import com.google.common.collect.Lists;
 
 import org.junit.Before;
 import org.junit.Test;
@@ -443,6 +443,38 @@ public class MerkleTreeTest
     }
 
     /**
+     * difference should behave as expected, even with extremely small ranges
+     */
+    @Test
+    public void differenceSmallRange()
+    {
+        Token start = new BigIntegerToken("9");
+        Token end = new BigIntegerToken("10");
+        Range<Token> range = new Range<>(start, end);
+
+        MerkleTree ltree = new MerkleTree(partitioner, range, RECOMMENDED_DEPTH, 16);
+        ltree.init();
+        MerkleTree rtree = new MerkleTree(partitioner, range, RECOMMENDED_DEPTH, 16);
+        rtree.init();
+
+        byte[] h1 = "asdf".getBytes();
+        byte[] h2 = "hjkl".getBytes();
+
+        // add dummy hashes to both trees
+        for (TreeRange tree : ltree.invalids())
+        {
+            tree.addHash(new RowHash(range.right, h1, h1.length));
+        }
+        for (TreeRange tree : rtree.invalids())
+        {
+            tree.addHash(new RowHash(range.right, h2, h2.length));
+        }
+
+        List<TreeRange> diffs = MerkleTree.difference(ltree, rtree);
+        assertEquals(Lists.newArrayList(range), diffs);
+    }
+
+    /**
      * Return the root hash of a binary tree with leaves at the given depths
      * and with the given hash val in each leaf.
      */


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org


Mime
View raw message