cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jbel...@apache.org
Subject [2/3] git commit: Fix BTree.clear for large updates patch by Benedict Elliott Smith; reviewed by jbellis for CASSANDRA-6943
Date Thu, 03 Apr 2014 21:00:54 GMT
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 <jbellis@apache.org>
Authored: Thu Apr 3 14:55:07 2014 -0500
Committer: Jonathan Ellis <jbellis@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;
+    }
 }


Mime
View raw message