You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by jb...@apache.org on 2014/04/03 23:00:54 UTC
[2/3] git commit: Fix BTree.clear for large updates patch by Benedict
Elliott Smith; reviewed by jbellis for CASSANDRA-6943
Fix BTree.clear for large updates
patch by Benedict Elliott Smith; reviewed by jbellis for CASSANDRA-6943
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/e6e596d1
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/e6e596d1
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/e6e596d1
Branch: refs/heads/trunk
Commit: e6e596d1a86272b70d759aad18f561e84e2854be
Parents: 38db6e4
Author: Jonathan Ellis <jb...@apache.org>
Authored: Thu Apr 3 14:55:07 2014 -0500
Committer: Jonathan Ellis <jb...@apache.org>
Committed: Thu Apr 3 15:56:25 2014 -0500
----------------------------------------------------------------------
CHANGES.txt | 1 +
.../org/apache/cassandra/utils/btree/BTree.java | 4 +-
.../cassandra/utils/btree/NodeBuilder.java | 24 +++++---
.../apache/cassandra/utils/LongBTreeTest.java | 60 ++++++++++++++++---
.../org/apache/cassandra/utils/BTreeTest.java | 61 +++++++++++++++++++-
5 files changed, 132 insertions(+), 18 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/cassandra/blob/e6e596d1/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index ceeb0c1..11dd6bd 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -1,4 +1,5 @@
2.1.0-beta2
+ * Fix BTree.clear for large updates (CASSANDRA-6943)
* Fail write instead of logging a warning when unable to append to CL
(CASSANDRA-6764)
* Eliminate possibility of CL segment appearing twice in active list
http://git-wip-us.apache.org/repos/asf/cassandra/blob/e6e596d1/src/java/org/apache/cassandra/utils/btree/BTree.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/BTree.java b/src/java/org/apache/cassandra/utils/btree/BTree.java
index 5ca5006..0e8f156 100644
--- a/src/java/org/apache/cassandra/utils/btree/BTree.java
+++ b/src/java/org/apache/cassandra/utils/btree/BTree.java
@@ -26,6 +26,8 @@ import java.util.Queue;
import org.apache.cassandra.utils.ObjectSizes;
+import static org.apache.cassandra.utils.btree.UpdateFunction.NoOp;
+
public class BTree
{
/**
@@ -141,7 +143,7 @@ public class BTree
*/
public static <V> Object[] update(Object[] btree, Comparator<V> comparator, Collection<V> updateWith, boolean updateWithIsSorted)
{
- return update(btree, comparator, updateWith, updateWithIsSorted, UpdateFunction.NoOp.<V>instance());
+ return update(btree, comparator, updateWith, updateWithIsSorted, NoOp.<V>instance());
}
public static <V> Object[] update(Object[] btree,
http://git-wip-us.apache.org/repos/asf/cassandra/blob/e6e596d1/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java b/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java
index 7039380..5a9b149 100644
--- a/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java
+++ b/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java
@@ -69,17 +69,25 @@ final class NodeBuilder
void clear()
{
NodeBuilder current = this;
- while (current != null)
+ while (current != null && current.upperBound != null)
{
- if (current.upperBound != null)
- {
- current.reset(null, null, null, null);
- Arrays.fill(current.buildKeys, 0, current.maxBuildKeyPosition, null);
- Arrays.fill(current.buildChildren, 0, current.maxBuildKeyPosition + 1, null);
- current.maxBuildKeyPosition = 0;
- }
+ current.clearSelf();
current = current.child;
}
+ current = parent;
+ while (current != null && current.upperBound != null)
+ {
+ current.clearSelf();
+ current = current.parent;
+ }
+ }
+
+ void clearSelf()
+ {
+ reset(null, null, null, null);
+ Arrays.fill(buildKeys, 0, maxBuildKeyPosition, null);
+ Arrays.fill(buildChildren, 0, maxBuildKeyPosition + 1, null);
+ maxBuildKeyPosition = 0;
}
// reset counters/setup to copy from provided node
http://git-wip-us.apache.org/repos/asf/cassandra/blob/e6e596d1/test/long/org/apache/cassandra/utils/LongBTreeTest.java
----------------------------------------------------------------------
diff --git a/test/long/org/apache/cassandra/utils/LongBTreeTest.java b/test/long/org/apache/cassandra/utils/LongBTreeTest.java
index 514d166..76ff2bf 100644
--- a/test/long/org/apache/cassandra/utils/LongBTreeTest.java
+++ b/test/long/org/apache/cassandra/utils/LongBTreeTest.java
@@ -25,6 +25,8 @@ import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
+import javax.annotation.Nullable;
+
import com.google.common.util.concurrent.Futures;
import com.google.common.util.concurrent.ListenableFuture;
import com.google.common.util.concurrent.ListenableFutureTask;
@@ -38,6 +40,7 @@ import com.yammer.metrics.stats.Snapshot;
import org.apache.cassandra.concurrent.NamedThreadFactory;
import org.apache.cassandra.utils.btree.BTree;
import org.apache.cassandra.utils.btree.BTreeSet;
+import org.apache.cassandra.utils.btree.UpdateFunction;
// TODO : should probably lower fan-factor for tests to make them more intensive
public class LongBTreeTest
@@ -47,6 +50,7 @@ public class LongBTreeTest
private static final Timer TREE_TIMER = Metrics.newTimer(BTree.class, "TREE", TimeUnit.NANOSECONDS, TimeUnit.NANOSECONDS);
private static final ExecutorService MODIFY = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors(), new NamedThreadFactory("MODIFY"));
private static final ExecutorService COMPARE = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors(), new NamedThreadFactory("COMPARE"));
+ private static final RandomAbort<Integer> SPORADIC_ABORT = new RandomAbort<>(new Random(), 0.0001f);
static
{
@@ -94,7 +98,7 @@ public class LongBTreeTest
@Test
public void testLargeBatchesLargeRange() throws ExecutionException, InterruptedException
{
- testInsertions(10000000, 5000, 3, 100, true);
+ testInsertions(100000000, 5000, 3, 100, true);
}
@Test
@@ -178,16 +182,21 @@ public class LongBTreeTest
canon.putAll(buffer);
ctxt.stop();
ctxt = BTREE_TIMER.time();
- btree = BTree.update(btree, ICMP, buffer.keySet(), true, null);
+ Object[] next = null;
+ while (next == null)
+ next = BTree.update(btree, ICMP, buffer.keySet(), true, SPORADIC_ABORT);
+ btree = next;
ctxt.stop();
+ if (!BTree.isWellFormed(btree, ICMP))
+ {
+ System.out.println("ERROR: Not well formed");
+ throw new AssertionError("Not well formed!");
+ }
if (quickEquality)
testEqual("", BTree.<Integer>slice(btree, true), canon.keySet().iterator());
else
r.addAll(testAllSlices("RND", btree, new TreeSet<>(canon.keySet())));
-
- if (!BTree.isWellFormed(btree))
- System.out.println("ERROR: Not well formed");
}
return r;
}
@@ -207,7 +216,10 @@ public class LongBTreeTest
String id = String.format("[0..%d)", canon.size());
System.out.println("Testing " + id);
Futures.allAsList(testAllSlices(id, cur, canon)).get();
- cur = BTree.update(cur, ICMP, Arrays.asList(i), true, null);
+ Object[] next = null;
+ while (next == null)
+ next = BTree.update(cur, ICMP, Arrays.asList(i), true, SPORADIC_ABORT);
+ cur = next;
canon.add(i);
}
}
@@ -277,7 +289,7 @@ public class LongBTreeTest
}
}
- private static <V> boolean testEqual(String id, Iterator<V> btree, Iterator<V> canon)
+ private static <V> void testEqual(String id, Iterator<V> btree, Iterator<V> canon)
{
boolean equal = true;
while (btree.hasNext() && canon.hasNext())
@@ -300,7 +312,8 @@ public class LongBTreeTest
System.out.println(String.format("%s: Expected %d, Got Nil", id, canon.next()));
equal = false;
}
- return equal;
+ if (!equal)
+ throw new AssertionError("Not equal");
}
// should only be called on sets that range from 0->N or N->0
@@ -354,4 +367,35 @@ public class LongBTreeTest
};
}
+ private static final class RandomAbort<V> implements UpdateFunction<V>
+ {
+ final Random rnd;
+ final float chance;
+ private RandomAbort(Random rnd, float chance)
+ {
+ this.rnd = rnd;
+ this.chance = chance;
+ }
+
+ public V apply(V replacing, V update)
+ {
+ return update;
+ }
+
+ public boolean abortEarly()
+ {
+ return rnd.nextFloat() < chance;
+ }
+
+ public void allocated(long heapSize)
+ {
+
+ }
+
+ public V apply(V v)
+ {
+ return v;
+ }
+ }
+
}
http://git-wip-us.apache.org/repos/asf/cassandra/blob/e6e596d1/test/unit/org/apache/cassandra/utils/BTreeTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/utils/BTreeTest.java b/test/unit/org/apache/cassandra/utils/BTreeTest.java
index b4a960b..a6d4528 100644
--- a/test/unit/org/apache/cassandra/utils/BTreeTest.java
+++ b/test/unit/org/apache/cassandra/utils/BTreeTest.java
@@ -25,6 +25,7 @@ import java.util.concurrent.ThreadLocalRandom;
import org.junit.Test;
+import junit.framework.Assert;
import org.apache.cassandra.utils.btree.BTree;
import org.apache.cassandra.utils.btree.BTreeSet;
import org.apache.cassandra.utils.btree.UpdateFunction;
@@ -119,7 +120,65 @@ public class BTreeTest
assert vs.size() == count;
int i = 0;
for (Integer j : vs)
- assert j == ints[i++];
+ Assert.assertEquals(j, ints[i++]);
}
+ @Test
+ public void testClearOnAbort()
+ {
+ final Comparator<String> cmp = new Comparator<String>()
+ {
+ public int compare(String o1, String o2)
+ {
+ return o1.compareTo(o2);
+ }
+ };
+
+ Object[] btree = BTree.build(ranges(range(0, 8)), cmp, true, UpdateFunction.NoOp.<String>instance());
+ BTree.update(btree, cmp, ranges(range(0, 94)), false, new AbortAfterX(90));
+ btree = BTree.update(btree, cmp, ranges(range(0, 94)), false, UpdateFunction.NoOp.<String>instance());
+ Assert.assertTrue(BTree.isWellFormed(btree, cmp));
+ }
+
+ private static final class AbortAfterX implements UpdateFunction<String>
+ {
+ int counter;
+ final int abortAfter;
+ private AbortAfterX(int abortAfter)
+ {
+ this.abortAfter = abortAfter;
+ }
+ public String apply(String replacing, String update)
+ {
+ return update;
+ }
+ public boolean abortEarly()
+ {
+ return counter++ > abortAfter;
+ }
+ public void allocated(long heapSize)
+ {
+ }
+ public String apply(String v)
+ {
+ return v;
+ }
+ }
+
+ private static int[] range(int lb, int ub)
+ {
+ return new int[] { lb, ub };
+ }
+
+ private static List<String> ranges(int[] ... ranges)
+ {
+
+ List<String> r = new ArrayList<>();
+ for (int[] range : ranges)
+ {
+ for (int i = range[0] ; i < range[1] ; i+=1)
+ r.add(Integer.toString(i));
+ }
+ return r;
+ }
}