SERVER-16802 SERVER-28981 Balancer consider shards and collections in random order

7 files changed, 77 insertions, 17 deletions

diff --git a/src/mongo/db/s/balancer/balancer.cpp b/src/mongo/db/s/balancer/balancer.cpp
index fcabe61f658..be50d5c8f60 100644
--- a/src/mongo/db/s/balancer/balancer.cpp
+++ b/src/mongo/db/s/balancer/balancer.cpp
@@ -151,9 +151,10 @@ void warnOnMultiVersion(const vector<ClusterStatistics::ShardStatistics>& cluste
 
 Balancer::Balancer(ServiceContext* serviceContext)
     : _balancedLastTime(0),
-      _clusterStats(stdx::make_unique<ClusterStatisticsImpl>()),
+      _random(std::random_device{}()),
+      _clusterStats(stdx::make_unique<ClusterStatisticsImpl>(_random)),
       _chunkSelectionPolicy(
-          stdx::make_unique<BalancerChunkSelectionPolicyImpl>(_clusterStats.get())),
+          stdx::make_unique<BalancerChunkSelectionPolicyImpl>(_clusterStats.get(), _random)),
       _migrationManager(serviceContext) {}
 
 Balancer::~Balancer() {
diff --git a/src/mongo/db/s/balancer/balancer.h b/src/mongo/db/s/balancer/balancer.h
index 4288dfc018b..3afd190820a 100644
--- a/src/mongo/db/s/balancer/balancer.h
+++ b/src/mongo/db/s/balancer/balancer.h
@@ -30,6 +30,7 @@
 
 #include "mongo/base/disallow_copying.h"
 #include "mongo/db/s/balancer/balancer_chunk_selection_policy.h"
+#include "mongo/db/s/balancer/balancer_random.h"
 #include "mongo/db/s/balancer/migration_manager.h"
 #include "mongo/stdx/condition_variable.h"
 #include "mongo/stdx/mutex.h"
@@ -237,11 +238,15 @@ private:
     // Number of moved chunks in last round
     int _balancedLastTime;
 
-    // Source for cluster statistics
+    // Source of randomness when metadata needs to be randomized.
+    BalancerRandomSource _random;
+
+    // Source for cluster statistics. Depends on the source of randomness above so it should be
+    // created after it and destroyed before it.
     std::unique_ptr<ClusterStatistics> _clusterStats;
 
-    // Balancer policy. Depends on the cluster statistics instance above so it should be created
-    // after it and destroyed before it.
+    // Balancer policy. Depends on the cluster statistics instance and source of randomness above so
+    // it should be created after them and destroyed before them.
     std::unique_ptr<BalancerChunkSelectionPolicy> _chunkSelectionPolicy;
 
     // Migration manager used to schedule and manage migrations
diff --git a/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.cpp b/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.cpp
index 499c7605924..8d5fe0d809f 100644
--- a/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.cpp
+++ b/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.cpp
@@ -32,6 +32,7 @@
 
 #include "mongo/db/s/balancer/balancer_chunk_selection_policy_impl.h"
 
+#include <algorithm>
 #include <vector>
 
 #include "mongo/base/status_with.h"
@@ -172,8 +173,9 @@ private:
 
 }  // namespace
 
-BalancerChunkSelectionPolicyImpl::BalancerChunkSelectionPolicyImpl(ClusterStatistics* clusterStats)
-    : _clusterStats(clusterStats) {}
+BalancerChunkSelectionPolicyImpl::BalancerChunkSelectionPolicyImpl(ClusterStatistics* clusterStats,
+                                                                   BalancerRandomSource& random)
+    : _clusterStats(clusterStats), _random(random) {}
 
 BalancerChunkSelectionPolicyImpl::~BalancerChunkSelectionPolicyImpl() = default;
 
@@ -186,13 +188,12 @@ StatusWith<SplitInfoVector> BalancerChunkSelectionPolicyImpl::selectChunksToSpli
 
     const auto shardStats = std::move(shardStatsStatus.getValue());
 
-    const auto swCollections =
-        Grid::get(opCtx)->catalogClient()->getCollections(opCtx, nullptr, nullptr);
+    auto swCollections = Grid::get(opCtx)->catalogClient()->getCollections(opCtx, nullptr, nullptr);
     if (!swCollections.isOK()) {
         return swCollections.getStatus();
     }
 
-    const auto& collections = swCollections.getValue();
+    auto& collections = swCollections.getValue();
 
     if (collections.empty()) {
         return SplitInfoVector{};
@@ -200,6 +201,8 @@ StatusWith<SplitInfoVector> BalancerChunkSelectionPolicyImpl::selectChunksToSpli
 
     SplitInfoVector splitCandidates;
 
+    std::shuffle(collections.begin(), collections.end(), _random);
+
     for (const auto& coll : collections) {
         if (coll.getDropped()) {
             continue;
@@ -239,13 +242,12 @@ StatusWith<MigrateInfoVector> BalancerChunkSelectionPolicyImpl::selectChunksToMo
     }
 
 
-    const auto swCollections =
-        Grid::get(opCtx)->catalogClient()->getCollections(opCtx, nullptr, nullptr);
+    auto swCollections = Grid::get(opCtx)->catalogClient()->getCollections(opCtx, nullptr, nullptr);
     if (!swCollections.isOK()) {
         return swCollections.getStatus();
     }
 
-    const auto& collections = swCollections.getValue();
+    auto& collections = swCollections.getValue();
 
     if (collections.empty()) {
         return MigrateInfoVector{};
@@ -254,6 +256,8 @@ StatusWith<MigrateInfoVector> BalancerChunkSelectionPolicyImpl::selectChunksToMo
     MigrateInfoVector candidateChunks;
     std::set<ShardId> usedShards;
 
+    std::shuffle(collections.begin(), collections.end(), _random);
+
     for (const auto& coll : collections) {
         if (coll.getDropped()) {
             continue;
diff --git a/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.h b/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.h
index 927437ce3c4..8837bdf6d8a 100644
--- a/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.h
+++ b/src/mongo/db/s/balancer/balancer_chunk_selection_policy_impl.h
@@ -29,6 +29,7 @@
 #pragma once
 
 #include "mongo/db/s/balancer/balancer_chunk_selection_policy.h"
+#include "mongo/db/s/balancer/balancer_random.h"
 
 namespace mongo {
 
@@ -36,7 +37,7 @@ class ClusterStatistics;
 
 class BalancerChunkSelectionPolicyImpl final : public BalancerChunkSelectionPolicy {
 public:
-    BalancerChunkSelectionPolicyImpl(ClusterStatistics* clusterStats);
+    BalancerChunkSelectionPolicyImpl(ClusterStatistics* clusterStats, BalancerRandomSource& random);
     ~BalancerChunkSelectionPolicyImpl();
 
     StatusWith<SplitInfoVector> selectChunksToSplit(OperationContext* opCtx) override;
@@ -75,6 +76,9 @@ private:
     // Source for obtaining cluster statistics. Not owned and must not be destroyed before the
     // policy object is destroyed.
     ClusterStatistics* const _clusterStats;
+
+    // Source of randomness when metadata needs to be randomized.
+    BalancerRandomSource& _random;
 };
 
 }  // namespace mongo
diff --git a/src/mongo/db/s/balancer/balancer_random.h b/src/mongo/db/s/balancer/balancer_random.h
new file mode 100644
index 00000000000..d03ba2f49c2
--- /dev/null
+++ b/src/mongo/db/s/balancer/balancer_random.h
@@ -0,0 +1,37 @@
+/**
+ *    Copyright (C) 2018 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects
+ *    for all of the code used other than as permitted herein. If you modify
+ *    file(s) with this exception, you may extend this exception to your
+ *    version of the file(s), but you are not obligated to do so. If you do not
+ *    wish to do so, delete this exception statement from your version. If you
+ *    delete this exception statement from all source files in the program,
+ *    then also delete it in the license file.
+ */
+
+#pragma once
+
+#include <random>
+
+namespace mongo {
+
+using BalancerRandomSource = std::minstd_rand;
+
+}  // namespace mongo
diff --git a/src/mongo/db/s/balancer/cluster_statistics_impl.cpp b/src/mongo/db/s/balancer/cluster_statistics_impl.cpp
index c23b6b41e32..86db3c4dba3 100644
--- a/src/mongo/db/s/balancer/cluster_statistics_impl.cpp
+++ b/src/mongo/db/s/balancer/cluster_statistics_impl.cpp
@@ -32,6 +32,8 @@
 
 #include "mongo/db/s/balancer/cluster_statistics_impl.h"
 
+#include <algorithm>
+
 #include "mongo/base/status_with.h"
 #include "mongo/bson/util/bson_extract.h"
 #include "mongo/client/read_preference.h"
@@ -91,7 +93,7 @@ StatusWith<std::string> retrieveShardMongoDVersion(OperationContext* opCtx, Shar
 
 using ShardStatistics = ClusterStatistics::ShardStatistics;
 
-ClusterStatisticsImpl::ClusterStatisticsImpl() = default;
+ClusterStatisticsImpl::ClusterStatisticsImpl(BalancerRandomSource& random) : _random(random) {}
 
 ClusterStatisticsImpl::~ClusterStatisticsImpl() = default;
 
@@ -107,7 +109,9 @@ StatusWith<std::vector<ShardStatistics>> ClusterStatisticsImpl::getStats(Operati
         return shardsStatus.getStatus();
     }
 
-    const auto& shards = shardsStatus.getValue().value;
+    auto& shards = shardsStatus.getValue().value;
+
+    std::shuffle(shards.begin(), shards.end(), _random);
 
     std::vector<ShardStatistics> stats;
 
diff --git a/src/mongo/db/s/balancer/cluster_statistics_impl.h b/src/mongo/db/s/balancer/cluster_statistics_impl.h
index 6d5524a5b1a..db73144428b 100644
--- a/src/mongo/db/s/balancer/cluster_statistics_impl.h
+++ b/src/mongo/db/s/balancer/cluster_statistics_impl.h
@@ -28,6 +28,7 @@
 
 #pragma once
 
+#include "mongo/db/s/balancer/balancer_random.h"
 #include "mongo/db/s/balancer/cluster_statistics.h"
 
 namespace mongo {
@@ -39,10 +40,14 @@ namespace mongo {
  */
 class ClusterStatisticsImpl final : public ClusterStatistics {
 public:
-    ClusterStatisticsImpl();
+    ClusterStatisticsImpl(BalancerRandomSource& random);
     ~ClusterStatisticsImpl();
 
     StatusWith<std::vector<ShardStatistics>> getStats(OperationContext* opCtx) override;
+
+private:
+    // Source of randomness when metadata needs to be randomized.
+    BalancerRandomSource& _random;
 };
 
 }  // namespace mongo