You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by al...@apache.org on 2019/08/02 13:18:46 UTC
[cassandra] 05/09: Some MT.difference() optimisations / more
Marcus's feedback
This is an automated email from the ASF dual-hosted git repository.
aleksey pushed a commit to branch 15202-4.0
in repository https://gitbox.apache.org/repos/asf/cassandra.git
commit 3f5bb3ba9d732cb04c5b49cc08d9d64ac549bf73
Author: Aleksey Yeshchenko <al...@apache.org>
AuthorDate: Mon Jul 29 17:01:22 2019 +0100
Some MT.difference() optimisations / more Marcus's feedback
---
.../org/apache/cassandra/utils/MerkleTree.java | 36 +++++++++++++---------
1 file changed, 21 insertions(+), 15 deletions(-)
diff --git a/src/java/org/apache/cassandra/utils/MerkleTree.java b/src/java/org/apache/cassandra/utils/MerkleTree.java
index bdeaa3f..68be2d1 100644
--- a/src/java/org/apache/cassandra/utils/MerkleTree.java
+++ b/src/java/org/apache/cassandra/utils/MerkleTree.java
@@ -72,11 +72,11 @@ public class MerkleTree
{
private static final Logger logger = LoggerFactory.getLogger(MerkleTree.class);
- private static final int HASH_SIZE = 32; // SHA-256 = 32 bytes.
+ private static final int HASH_SIZE = 32; // 2xMM3_128 = 32 bytes.
private static final byte[] EMPTY_HASH = new byte[HASH_SIZE];
/*
- * Thread-local byte array, large enough to host SHA256 bytes or MM3/Random partitoners' tokens
+ * Thread-local byte array, large enough to host 32B of digest or MM3/Random partitoners' tokens
*/
private static final ThreadLocal<byte[]> byteArray = ThreadLocal.withInitial(() -> new byte[HASH_SIZE]);
@@ -201,11 +201,15 @@ public class MerkleTree
if (!ltree.fullRange.equals(rtree.fullRange))
throw new IllegalArgumentException("Difference only make sense on tree covering the same range (but " + ltree.fullRange + " != " + rtree.fullRange + ')');
+ // ensure on-heap trees' inner node hashes have been computed
+ ltree.fillInnerHashes();
+ rtree.fillInnerHashes();
+
List<TreeRange> diff = new ArrayList<>();
TreeRange active = new TreeRange(ltree.fullRange.left, ltree.fullRange.right, 0);
- Node lnode = ltree.find(active);
- Node rnode = rtree.find(active);
+ Node lnode = ltree.root;
+ Node rnode = rtree.root;
if (lnode.hashesDiffer(rnode))
{
@@ -366,11 +370,12 @@ public class MerkleTree
assert current instanceof Inner;
Inner inner = (Inner) current;
- Range<Token> leftRange = new Range<>(activeRange.left, inner.token());
- Range<Token> rightRange = new Range<>(inner.token(), activeRange.right);
-
if (find.contains(activeRange)) // this node is fully contained in the range
- return inner.compute();
+ return inner.fillInnerHashes();
+
+ Token midpoint = inner.token();
+ Range<Token> leftRange = new Range<>(activeRange.left, midpoint);
+ Range<Token> rightRange = new Range<>(midpoint, activeRange.right);
// else: one of our children contains the range
@@ -757,6 +762,7 @@ public class MerkleTree
private MerkleTree moveOffHeap() throws IOException
{
assert root instanceof OnHeapNode;
+ root.fillInnerHashes(); // ensure on-heap trees' inner node hashes have been computed
ByteBuffer buffer = allocate(Ints.checkedCast(size), partitioner);
int pointer = ((OnHeapNode) root).serializeOffHeap(buffer, partitioner);
OffHeapNode newRoot = fromPointer(pointer, buffer, partitioner);
@@ -790,7 +796,7 @@ public class MerkleTree
boolean hashesDiffer(Node other);
- default Node compute()
+ default Node fillInnerHashes()
{
return this;
}
@@ -1265,12 +1271,12 @@ public class MerkleTree
}
@Override
- public Node compute()
+ public Node fillInnerHashes()
{
if (!computed) // hash and size haven't been calculated; compute children then compute this
{
- left.compute();
- right.compute();
+ left.fillInnerHashes();
+ right.fillInnerHashes();
if (!left.hasEmptyHash() && !right.hasEmptyHash())
hash = xor(left.hash(), right.hash());
@@ -1503,7 +1509,7 @@ public class MerkleTree
OnHeapLeaf left = new OnHeapLeaf(hashLeft);
OnHeapLeaf right = new OnHeapLeaf(hashRigth);
Inner inner = new OnHeapInner(partitioner.getMinimumToken(), left, right);
- inner.compute();
+ inner.fillInnerHashes();
// Some partioners have variable token sizes, try to estimate as close as we can by using the same
// heap estimate as the memtables use.
@@ -1635,8 +1641,8 @@ public class MerkleTree
}
@VisibleForTesting
- void compute()
+ void fillInnerHashes()
{
- root.compute();
+ root.fillInnerHashes();
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@cassandra.apache.org
For additional commands, e-mail: commits-help@cassandra.apache.org