kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ale...@apache.org
Subject [2/2] kudu git commit: [rebalancer] location-aware rebalancer (part 8/n)
Date Thu, 01 Nov 2018 03:33:43 GMT
[rebalancer] location-aware rebalancer (part 8/n)

Updated FindBestReplicaToReplace() to handle common and edge cases
of even replication factors.  Added corresponding unit tests as well.

Change-Id: I8f8831d254b2ca0d9a12e0ffbc336a59c3c5c8de
Reviewed-on: http://gerrit.cloudera.org:8080/11761
Tested-by: Kudu Jenkins
Reviewed-by: Will Berkeley <wdberkeley@gmail.com>


Project: http://git-wip-us.apache.org/repos/asf/kudu/repo
Commit: http://git-wip-us.apache.org/repos/asf/kudu/commit/4ec2598a
Tree: http://git-wip-us.apache.org/repos/asf/kudu/tree/4ec2598a
Diff: http://git-wip-us.apache.org/repos/asf/kudu/diff/4ec2598a

Branch: refs/heads/master
Commit: 4ec2598a355bbbd1c00c4bdc03d37bafe04d0d5f
Parents: 81bba24
Author: Alexey Serbin <aserbin@cloudera.com>
Authored: Tue Oct 23 17:50:10 2018 -0700
Committer: Alexey Serbin <aserbin@cloudera.com>
Committed: Thu Nov 1 03:32:50 2018 +0000

----------------------------------------------------------------------
 src/kudu/tools/placement_policy_util-test.cc | 194 ++++++++++++++++++++++
 src/kudu/tools/placement_policy_util.cc      |  31 +++-
 2 files changed, 222 insertions(+), 3 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/4ec2598a/src/kudu/tools/placement_policy_util-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tools/placement_policy_util-test.cc b/src/kudu/tools/placement_policy_util-test.cc
index 68266f3..7d48cbe 100644
--- a/src/kudu/tools/placement_policy_util-test.cc
+++ b/src/kudu/tools/placement_policy_util-test.cc
@@ -470,6 +470,24 @@ TEST_F(ClusterLocationTest, NoCandidateMovesToFixPolicyViolations) {
       { { "t0", "L0" }, },
       {},
     },
+    {
+      // One RF=6 tablet with replica placement violating the placement policy.
+      {
+        { "T0", 6, { "t0", } },
+      },
+      {
+        { "L0", { "A", "B", "C", } },
+        { "L1", { "D", "E", } },
+        { "L2", { "F", } },
+      },
+      {
+        { "A", { "t0", } }, { "B", { "t0", } }, { "C", { "t0", } },
+        { "D", { "t0", } }, { "E", { "t0", } },
+        { "F", { "t0", } },
+      },
+      { { "t0", "L0" }, },
+      {}
+    },
   };
   for (auto idx = 0; idx < configs.size(); ++idx) {
     SCOPED_TRACE(Substitute("test config index: $0", idx));
@@ -490,5 +508,181 @@ TEST_F(ClusterLocationTest, NoCandidateMovesToFixPolicyViolations) {
   }
 }
 
+TEST_F(ClusterLocationTest, PlacementPolicyViolationsEvenRFEdgeCases) {
+  const vector<TestClusterConfig> configs = {
+    {
+      // One location, RF=2 and RF=4.
+      {
+        { "T0", 2, { "t0", } },
+        { "T1", 4, { "t1", } },
+      },
+      {
+        { "L0", { "A", "B", "C", "D", "E", } },
+      },
+      {
+        { "A", { "t0", "t1", } },
+        { "B", { "t0", "t1", } },
+        { "C", { "t1", } },
+        { "D", { "t1", } },
+      },
+      { { "t0", "L0" }, { "t1", "L0" }, },
+      {}
+    },
+    {
+      // Two locations, RF=2.
+      {
+        { "T0", 2, { "t0", "t1", } },
+      },
+      {
+        { "L0", { "A", "B", } },
+        { "L1", { "D", "E", } },
+      },
+      {
+        { "A", { "t0", } }, { "B", { "t0", } },
+        { "D", { "t1", } }, { "E", { "t1", } },
+      },
+      { { "t0", "L0" }, { "t1", "L1" }, },
+      {}
+    },
+    {
+      // Two locations, RF=2 and RF=4.
+      {
+        { "T0", 2, { "t0", } },
+        { "T1", 4, { "t1", } },
+      },
+      {
+        { "L0", { "A", "B", "C", } },
+        { "L1", { "D", "E", "F", } },
+      },
+      {
+        { "A", { "t0", "t1", } }, { "B", { "t0", "t1", } },
+        { "D", { "t1", } }, { "E", { "t1", } },
+      },
+      { { "t0", "L0" }, { "t1", "L1" }, },
+      {}
+    },
+    {
+      // Two locations, two tablets, RF=2.
+      {
+        { "T0", 2, { "t0", "t1", } },
+      },
+      {
+        { "L0", { "A", "B", } },
+        { "L1", { "C", "D", } },
+      },
+      {
+        { "A", { "t0", } }, { "B", { "t0", } },
+        { "C", { "t1", } }, { "D", { "t1", } },
+      },
+      { { "t0", "L0" }, { "t1", "L1" }, },
+      {}
+    },
+    {
+      // Three locations, RF=4.
+      {
+        { "T0", 4, { "t0", } },
+      },
+      {
+        { "L0", { "A", "B", } },
+        { "L1", { "D", "E", } },
+        { "L2", { "F", "G", } },
+      },
+      {
+        { "A", { "t0", } }, { "B", { "t0", } },
+        { "D", { "t0", } },
+        { "F", { "t0", } },
+      },
+      { { "t0", "L0" }, },
+      {}
+    },
+  };
+  NO_FATALS(RunTest(configs));
+}
+
+TEST_F(ClusterLocationTest, PlacementPolicyViolationsEvenRF) {
+  const vector<TestClusterConfig> configs = {
+    {
+      // Three locations, RF=6.
+      {
+        { "T0", 6, { "t0", } },
+      },
+      {
+        { "L0", { "A", "B", "C", } },
+        { "L1", { "D", "E", "F", } },
+        { "L2", { "G", "H", } },
+      },
+      {
+        { "A", { "t0", } }, { "B", { "t0", } }, { "C", { "t0", } },
+        { "D", { "t0", } }, { "F", { "t0", } },
+        { "H", { "t0", } },
+      },
+      { { "t0", "L0" }, },
+      { { "t0", "B" }, }
+    },
+    {
+      // Three locations, RF=8.
+      {
+        { "T0", 8, { "t0", } },
+      },
+      {
+        { "L0", { "A", "B", "C", } },
+        { "L1", { "D", "E", "F", "G", } },
+        { "L2", { "H", "J", } },
+      },
+      {
+        { "A", { "t0", } }, { "B", { "t0", } }, { "C", { "t0", } },
+        { "D", { "t0", } }, { "E", { "t0", } }, { "F", { "t0", } },
+        { "G", { "t0", } },
+        { "H", { "t0", } },
+      },
+      { { "t0", "L1" }, },
+      { { "t0", "D" }, }
+    },
+  };
+  NO_FATALS(RunTest(configs));
+}
+
+TEST_F(ClusterLocationTest, PlacementPolicyViolationsNoneEvenRF) {
+  const vector<TestClusterConfig> configs = {
+    {
+      // Three locations, RF=6.
+      {
+        { "T0", 6, { "t0", } },
+      },
+      {
+        { "L0", { "A", "B", "C", } },
+        { "L1", { "D", "E", "F", } },
+        { "L2", { "G", "H", } },
+      },
+      {
+        { "A", { "t0", } }, { "B", { "t0", } },
+        { "D", { "t0", } }, { "E", { "t0", } },
+        { "G", { "t0", } }, { "H", { "t0", } },
+      },
+      {},
+      {}
+    },
+    {
+      // Three locations, RF=8.
+      {
+        { "T0", 8, { "t0", } },
+      },
+      {
+        { "L0", { "A", "B", "C", } },
+        { "L1", { "D", "E", "F", } },
+        { "L2", { "G", "H", } },
+      },
+      {
+        { "A", { "t0", } }, { "B", { "t0", } }, { "C", { "t0", } },
+        { "D", { "t0", } }, { "E", { "t0", } }, { "F", { "t0", } },
+        { "G", { "t0", } }, { "H", { "t0", } },
+      },
+      {},
+      {}
+    },
+  };
+  NO_FATALS(RunTest(configs));
+}
+
 } // namespace tools
 } // namespace kudu

http://git-wip-us.apache.org/repos/asf/kudu/blob/4ec2598a/src/kudu/tools/placement_policy_util.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tools/placement_policy_util.cc b/src/kudu/tools/placement_policy_util.cc
index d6494eb..be1b502 100644
--- a/src/kudu/tools/placement_policy_util.cc
+++ b/src/kudu/tools/placement_policy_util.cc
@@ -68,17 +68,42 @@ Status FindBestReplicaToReplace(
   }
 
   const auto& tablet_id = info.tablet_id;
+  const auto location_num = ts_id_by_location.size();
 
   // If a total number of locations is 2, it's impossible to make its replica
   // distribution conform with the placement policy constraints.
   const auto& table_id = FindOrDie(tablets_info.tablet_to_table_id, tablet_id);
   const auto& table_info = FindOrDie(tablets_info.tables_info, table_id);
-  if (ts_id_by_location.size() == 2 && table_info.replication_factor % 2 == 1) {
+
+  // There are a few edge cases which are most likely to occur, so let's have
+  // a special error message for those. In these cases there are too few
+  // locations relative to the replication factor, so it's impossible to find
+  // any replica movements to satisfy the placement policy constraints.
+  //
+  // One interesting case placing replicas of a tablet with RF=4 in a cluster
+  // with 3 locations. In that case, it's impossible to place the replicas to
+  // satisfy the placement policy's constraints, since any possible replicas
+  // placement does not allow to have the majority of the replicas online
+  // if any single location becomes unavailable. Below is the all the possible
+  // replica distributions for that case (modulo permutations of locations):
+  // if the first location becomes unavailable, the majority of the replicas
+  // is lost and the tablet becomes unavailable.
+  //
+  //   4 + 0 + 0
+  //   3 + 1 + 0
+  //   2 + 1 + 1
+  //
+  // Note that with 3 locations and higher replication factors (5, 6, etc.),
+  // there is always a way to place tablet replicas to conform with the
+  // restriction mentioned above.
+  if (location_num == 2 ||
+      (location_num == 3 && table_info.replication_factor == 4)) {
     return Status::ConfigurationError(Substitute(
         "tablet $0 (table name '$1'): replica distribution cannot conform "
         "with the placement policy constraints since its replication "
-        "factor is odd ($2) and there are two locations in the cluster",
-        tablet_id, table_info.name, table_info.replication_factor));
+        "factor is $2 and there are $3 locations in the cluster",
+        tablet_id, table_info.name,
+        table_info.replication_factor, location_num));
   }
 
   const auto& location = info.majority_location;


Mime
View raw message