kudu-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ale...@apache.org
Subject kudu git commit: [rebalancing] Add a randomized rebalancing algorithm test
Date Thu, 07 Jun 2018 07:06:21 GMT
Repository: kudu
Updated Branches:
  refs/heads/master 044c210de -> a0a61bd70


[rebalancing] Add a randomized rebalancing algorithm test

This adds a randomized test of the rebalancing algorithm. Instead of
checking the specific sequence of moves is correct it expects the
algorithm to balance the cluster within a certain number of moves, set
generously high.

I ran the randomized test about 10000 times over several runs using
dist_test.py, and saw no failures.

Change-Id: Id870d1290cf6681fa8bee79d8799f879b7dc8712
Reviewed-on: http://gerrit.cloudera.org:8080/10453
Reviewed-by: Alexey Serbin <aserbin@cloudera.com>
Tested-by: Kudu Jenkins


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

Branch: refs/heads/master
Commit: a0a61bd70f68ab303c1f87d3b5c113414d4144be
Parents: 044c210
Author: Will Berkeley <wdberkeley@apache.org>
Authored: Fri May 18 13:37:07 2018 -0700
Committer: Alexey Serbin <aserbin@cloudera.com>
Committed: Thu Jun 7 07:05:27 2018 +0000

----------------------------------------------------------------------
 src/kudu/tools/rebalance_algo-test.cc | 92 +++++++++++++++++++++++++++++-
 src/kudu/tools/rebalance_algo.h       |  4 ++
 2 files changed, 94 insertions(+), 2 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/kudu/blob/a0a61bd7/src/kudu/tools/rebalance_algo-test.cc
----------------------------------------------------------------------
diff --git a/src/kudu/tools/rebalance_algo-test.cc b/src/kudu/tools/rebalance_algo-test.cc
index 3da13e1..a074387 100644
--- a/src/kudu/tools/rebalance_algo-test.cc
+++ b/src/kudu/tools/rebalance_algo-test.cc
@@ -17,7 +17,6 @@
 
 #include "kudu/tools/rebalance_algo.h"
 
-#include <algorithm>
 #include <cstddef>
 #include <iostream>
 #include <iterator>
@@ -28,13 +27,16 @@
 #include <utility>
 #include <vector>
 
+#include <boost/optional/optional.hpp>
 #include <glog/logging.h>
 #include <gtest/gtest.h>
 
 #include "kudu/gutil/macros.h"
 #include "kudu/gutil/strings/substitute.h"
+#include "kudu/util/random.h"
 #include "kudu/util/status.h"
 #include "kudu/util/test_macros.h"
+#include "kudu/util/test_util.h"
 
 namespace kudu {
 namespace tools {
@@ -50,9 +52,10 @@ struct TestClusterConfig;
     } \
   } while (false)
 
+using std::endl;
 using std::ostream;
+using std::ostringstream;
 using std::set;
-using std::sort;
 using std::string;
 using std::vector;
 using strings::Substitute;
@@ -156,6 +159,35 @@ void VerifyRebalancingMoves(const TestClusterConfig& cfg) {
   EXPECT_EQ(cfg.expected_moves, moves);
 }
 
+// Is 'cbi' balanced according to the two-dimensional greedy algorithm?
+bool IsBalanced(const ClusterBalanceInfo& cbi) {
+  if (cbi.table_info_by_skew.empty()) {
+    return true;
+  }
+  auto max_table_skew = cbi.table_info_by_skew.rbegin()->first;
+  auto cluster_skew = cbi.servers_by_total_replica_count.rbegin()->first -
+                      cbi.servers_by_total_replica_count.begin()->first;
+  return (max_table_skew <= 1) && (cluster_skew <= 1);
+}
+
+string TestClusterConfigToDebugString(const TestClusterConfig& cfg) {
+  ostringstream oss;
+  oss << Substitute("TestClusterConfig: $0 tservers, $0 tables",
+                    cfg.table_replicas.size(), cfg.tserver_uuids.size()) << endl;
+  for (const auto& t : cfg.table_replicas) {
+    oss << Substitute("table $0: [", t.table_id);
+    for (auto i = 0; i < t.num_replicas_by_server.size(); i++) {
+      if (i > 0) {
+        oss << ", ";
+      }
+      oss << Substitute("ts $0: $1",
+                        cfg.tserver_uuids[i], t.num_replicas_by_server[i]);
+    }
+    oss << "]" << endl;
+  }
+  return oss.str();
+}
+
 // Test the behavior of the algorithm when no input information is given.
 TEST(RebalanceAlgoUnitTest, EmptyClusterBalanceInfo) {
   TwoDimensionalGreedyAlgo algo;
@@ -625,5 +657,61 @@ TEST(RebalanceAlgoUnitTest, ManyMoves) {
   EXPECT_EQ(ref_moves, moves);
 }
 
+TEST(RebalanceAlgoUnitTest, RandomizedTest) {
+  const auto num_iters = AllowSlowTests() ? 1000 : 100;
+  Random r(SeedRandom());
+  const auto max_tservers = 10;
+  const auto max_tables = 10;
+  const auto max_replicas_per_table_and_tserver = 25;
+  for (auto i = 0; i < num_iters; i++) {
+    // Generate a random cluster config.
+    const auto num_tservers = 1 + r.Uniform(max_tservers);
+    const auto num_tables = 1 + r.Uniform(max_tables);
+    vector<string> tserver_uuids;
+    tserver_uuids.reserve(num_tservers);
+    for (auto i = 0; i < num_tservers; i++) {
+      tserver_uuids.push_back(Substitute("$0", i));
+    }
+    vector<TablePerServerReplicas> table_replicas;
+    table_replicas.reserve(num_tables);
+    for (auto i = 0; i < num_tables; i++) {
+      vector<size_t> num_replicas_per_server;
+      num_replicas_per_server.reserve(num_tservers);
+      for (auto j = 0; j < num_tservers; j++) {
+        num_replicas_per_server.push_back(
+            r.Uniform(1 + max_replicas_per_table_and_tserver));
+      }
+      table_replicas.push_back(TablePerServerReplicas{
+          Substitute("$0", i),
+          std::move(num_replicas_per_server),
+      });
+    }
+    TestClusterConfig cfg{
+      std::move(tserver_uuids),
+      std::move(table_replicas),
+      {}  // This tests checks achievement of balance, not the path to it.
+    };
+
+    // Make sure the rebalancing algorithm can balance the config.
+    {
+      SCOPED_TRACE(TestClusterConfigToDebugString(cfg));
+      ClusterBalanceInfo cbi;
+      ClusterConfigToClusterBalanceInfo(cfg, &cbi);
+      TwoDimensionalGreedyAlgo algo;
+      boost::optional<TableReplicaMove> move;
+      // Set a generous upper bound on the number of moves allowed before we
+      // conclude the algorithm is not converging.
+      // We shouldn't need to do more moves than there are replicas.
+      int num_moves_ub = num_tservers * num_tables * max_replicas_per_table_and_tserver;
+      int num_moves = 0;
+      while (!IsBalanced(cbi)) {
+        ASSERT_OK(algo.GetNextMove(cbi, &move));
+        ASSERT_OK(TwoDimensionalGreedyAlgo::ApplyMove(*move, &cbi));
+        ASSERT_GE(num_moves_ub, ++num_moves) << "Too many moves! The algorithm is likely
stuck";
+      }
+    }
+  }
+}
+
 } // namespace tools
 } // namespace kudu

http://git-wip-us.apache.org/repos/asf/kudu/blob/a0a61bd7/src/kudu/tools/rebalance_algo.h
----------------------------------------------------------------------
diff --git a/src/kudu/tools/rebalance_algo.h b/src/kudu/tools/rebalance_algo.h
index c3543fd..a6faac6 100644
--- a/src/kudu/tools/rebalance_algo.h
+++ b/src/kudu/tools/rebalance_algo.h
@@ -22,6 +22,8 @@
 #include <string>
 #include <vector>
 
+#include <gtest/gtest_prod.h>
+
 #include "kudu/util/status.h"
 
 namespace boost {
@@ -170,6 +172,8 @@ class TwoDimensionalGreedyAlgo : public RebalancingAlgo {
   const EqualSkewOption equal_skew_opt_;
   std::random_device random_device_;
   std::mt19937 generator_;
+
+  FRIEND_TEST(RebalanceAlgoUnitTest, RandomizedTest);
 };
 
 } // namespace tools


Mime
View raw message