bookkeeper-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From iv...@apache.org
Subject bookkeeper git commit: BOOKKEEPER-799: Distribution schedule coverage sets don't take gaps in response lists into account when writequorum > ackquorum (ivank)
Date Fri, 05 Dec 2014 16:51:40 GMT
Repository: bookkeeper
Updated Branches:
  refs/heads/master 78d6e49d4 -> 5de01f700


BOOKKEEPER-799: Distribution schedule coverage sets don't take gaps in response lists into
account when writequorum > ackquorum (ivank)


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

Branch: refs/heads/master
Commit: 5de01f700ede31f186f5d8d97afac382f1e45327
Parents: 78d6e49
Author: Ivan Kelly <ivank@apache.org>
Authored: Fri Dec 5 17:51:16 2014 +0100
Committer: Ivan Kelly <ivank@apache.org>
Committed: Fri Dec 5 17:51:16 2014 +0100

----------------------------------------------------------------------
 CHANGES.txt                                     |  2 +
 .../client/RoundRobinDistributionSchedule.java  | 34 ++++---
 .../RoundRobinDistributionScheduleTest.java     | 99 +++++++++++++++++---
 3 files changed, 102 insertions(+), 33 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/bookkeeper/blob/5de01f70/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index 4dc93ea..e3f5a87 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -16,6 +16,8 @@ Trunk (unreleased changes)
 
       BOOKKEEPER-815: Ledger fence state is lost when the ledger file is evicted (Charles
Xie via ivank)
 
+      BOOKKEEPER-799: Distribution schedule coverage sets don't take gaps in response lists
into account when writequorum > ackquorum (ivank)
+
     IMPROVEMENTS:
 
       BOOKKEEPER-800: Expose whether a ledger is closed or not (ivank)

http://git-wip-us.apache.org/repos/asf/bookkeeper/blob/5de01f70/bookkeeper-server/src/main/java/org/apache/bookkeeper/client/RoundRobinDistributionSchedule.java
----------------------------------------------------------------------
diff --git a/bookkeeper-server/src/main/java/org/apache/bookkeeper/client/RoundRobinDistributionSchedule.java
b/bookkeeper-server/src/main/java/org/apache/bookkeeper/client/RoundRobinDistributionSchedule.java
index b34ff75..82f300b 100644
--- a/bookkeeper-server/src/main/java/org/apache/bookkeeper/client/RoundRobinDistributionSchedule.java
+++ b/bookkeeper-server/src/main/java/org/apache/bookkeeper/client/RoundRobinDistributionSchedule.java
@@ -67,33 +67,31 @@ class RoundRobinDistributionSchedule implements DistributionSchedule {
     }
 
     private class RRQuorumCoverageSet implements QuorumCoverageSet {
-        // covered[i] is true if the quorum starting at bookie index i has been
-        // covered by a recovery reply
-        private boolean[] covered = null;
-        private int numQuorumsUncovered;
+        private final boolean[] covered = new boolean[ensembleSize];
 
         private RRQuorumCoverageSet() {
-            covered = new boolean[ensembleSize];
-            numQuorumsUncovered = ensembleSize;
+            for (int i = 0; i < covered.length; i++) {
+                covered[i] = false;
+            }
         }
 
         public synchronized boolean addBookieAndCheckCovered(int bookieIndexHeardFrom) {
-            if (numQuorumsUncovered == 0) {
-                return true;
-            }
+            covered[bookieIndexHeardFrom] = true;
 
-            for (int i = 0; i < ackQuorumSize; i++) {
-                int quorumStartIndex = MathUtils.signSafeMod(bookieIndexHeardFrom - i, ensembleSize);
-                if (!covered[quorumStartIndex]) {
-                    covered[quorumStartIndex] = true;
-                    numQuorumsUncovered--;
-
-                    if (numQuorumsUncovered == 0) {
-                        return true;
+            // now check if there are any write quorums, with |ackQuorum| nodes available
+            for (int i = 0; i < ensembleSize; i++) {
+                int nodesNotCovered = 0;
+                for (int j = 0; j < writeQuorumSize; j++) {
+                    int nodeIndex = (i + j) % ensembleSize;
+                    if (!covered[nodeIndex]) {
+                        nodesNotCovered++;
                     }
                 }
+                if (nodesNotCovered >= ackQuorumSize) {
+                    return false;
+                }
             }
-            return false;
+            return true;
         }
     }
 

http://git-wip-us.apache.org/repos/asf/bookkeeper/blob/5de01f70/bookkeeper-server/src/test/java/org/apache/bookkeeper/client/RoundRobinDistributionScheduleTest.java
----------------------------------------------------------------------
diff --git a/bookkeeper-server/src/test/java/org/apache/bookkeeper/client/RoundRobinDistributionScheduleTest.java
b/bookkeeper-server/src/test/java/org/apache/bookkeeper/client/RoundRobinDistributionScheduleTest.java
index ce9aab9..12e3c17 100644
--- a/bookkeeper-server/src/test/java/org/apache/bookkeeper/client/RoundRobinDistributionScheduleTest.java
+++ b/bookkeeper-server/src/test/java/org/apache/bookkeeper/client/RoundRobinDistributionScheduleTest.java
@@ -22,6 +22,10 @@
 package org.apache.bookkeeper.client;
 
 import java.util.List;
+import java.util.Set;
+import java.util.HashSet;
+import com.google.common.collect.Sets;
+
 import org.junit.Test;
 import static org.junit.Assert.*;
 
@@ -43,21 +47,86 @@ public class RoundRobinDistributionScheduleTest {
         assertFalse("Shouldn't ack yet", ackSet.addBookieAndCheck(wSet.get(0)));
         assertTrue("Should ack after 2 unique", ackSet.addBookieAndCheck(wSet.get(2)));
         assertTrue("Should still be acking", ackSet.addBookieAndCheck(wSet.get(1)));
+    }
+
+    /**
+     * Test that coverage sets only respond as covered when it has
+     * heard from enough bookies that no ack quorum can exist without these bookies.
+     */
+    @Test(timeout=60000)
+    public void testCoverageSets() {
+        int errors = 0;
+        for (int e = 6; e > 0; e--) {
+            for (int w = e; w > 0; w--) {
+                for (int a = w; a > 0; a--) {
+                    errors += testCoverageForConfiguration(e, w, a);
+                }
+            }
+        }
+        assertEquals("Should be no errors", 0, errors);
+    }
+
+    /**
+     * Build a boolean array of which nodes have not responded
+     * and thus are available to build a quorum.
+     */
+    boolean[] buildAvailable(int ensemble, Set<Integer> responses) {
+        boolean[] available = new boolean[ensemble];
+        for (int i = 0; i < ensemble; i++) {
+            if (responses.contains(i)) {
+                available[i] = false;
+            } else {
+                available[i] = true;
+            }
+        }
+        return available;
+    }
+
+    /**
+     * Check whether it is possible for a write to reach
+     * a quorum with a given set of nodes available
+     */
+    boolean canGetAckQuorum(int ensemble, int writeQuorum, int ackQuorum, boolean[] available)
{
+        for (int i = 0; i < ensemble; i++) {
+            int count = 0;
+            for (int j = 0; j < writeQuorum; j++) {
+                if (available[(i+j)%ensemble]) {
+                    count++;
+                }
+            }
+            if (count >= ackQuorum) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private int testCoverageForConfiguration(int ensemble, int writeQuorum, int ackQuorum)
{
+        RoundRobinDistributionSchedule schedule = new RoundRobinDistributionSchedule(
+                writeQuorum, ackQuorum, ensemble);
+        Set<Integer> indexes = new HashSet<Integer>();
+        for (int i = 0; i < ensemble; i++) {
+            indexes.add(i);
+        }
+        Set<Set<Integer>> subsets = Sets.powerSet(indexes);
+
+        int errors = 0;
+        for (Set<Integer> subset : subsets) {
+            DistributionSchedule.QuorumCoverageSet covSet = schedule.getCoverageSet();
+            boolean covSetSays = false;
+            for (Integer i : subset) {
+                covSetSays = covSet.addBookieAndCheckCovered(i);
+            }
 
-        DistributionSchedule.QuorumCoverageSet covSet = schedule.getCoverageSet();
-        assertFalse("Shouldn't cover yet", covSet.addBookieAndCheckCovered(0));
-        assertFalse("Shouldn't cover yet", covSet.addBookieAndCheckCovered(2));
-        assertTrue("Should cover now", covSet.addBookieAndCheckCovered(3));
-
-        covSet = schedule.getCoverageSet();
-        assertFalse("Shouldn't cover yet", covSet.addBookieAndCheckCovered(0));
-        assertFalse("Shouldn't cover yet", covSet.addBookieAndCheckCovered(1));
-        assertFalse("Shouldn't cover yet", covSet.addBookieAndCheckCovered(2));
-        assertTrue("Should cover now", covSet.addBookieAndCheckCovered(3));
-
-        covSet = schedule.getCoverageSet();
-        assertFalse("Shouldn't cover yet", covSet.addBookieAndCheckCovered(4));
-        assertFalse("Shouldn't cover yet", covSet.addBookieAndCheckCovered(0));
-        assertTrue("Should cover now", covSet.addBookieAndCheckCovered(2));
+            boolean[] nodesAvailable = buildAvailable(ensemble, subset);
+            boolean canGetAck = canGetAckQuorum(ensemble, writeQuorum, ackQuorum, nodesAvailable);
+            if (canGetAck == covSetSays) {
+                LOG.error("e{}:w{}:a{} available {}    canGetAck {} covSetSays {}",
+                          new Object[] { ensemble, writeQuorum, ackQuorum,
+                                         nodesAvailable, canGetAck, covSetSays });
+                errors++;
+            }
+        }
+        return errors;
     }
 }


Mime
View raw message