Repository: cassandra Updated Branches: refs/heads/cassandra-3.0 7db6a3b3c -> 387258024 refs/heads/cassandra-3.11 83c9ac313 -> e4cef08d0 refs/heads/trunk e1f2300a1 -> baffdeae8
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.0 Commit: 38725802456dfcfcc2584cdfd061ac22215c2dfb Parents: 7db6a3b Author: Stefan Podkowinski <[email protected]> Authored: Tue Dec 20 14:40:18 2016 +0100 Committer: Stefan Podkowinski <[email protected]> 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: [email protected] For additional commands, e-mail: [email protected]
