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

(cherry picked from commit 651b3e017ce880d9ddbebb400af621c61d8c7389)

7 files changed, 73 insertions, 11 deletions

diff --git a/src/mongo/db/s/balancer/balancer.cpp b/src/mongo/db/s/balancer/balancer.cpp
index 7e334b8b86e..d6291503cc4 100644
--- a/src/mongo/db/s/balancer/balancer.cpp
+++ b/src/mongo/db/s/balancer/balancer.cpp
@@ -153,9 +153,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 7f601a849e2..a9a8ce47e74 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"
@@ -239,11 +240,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 2f7c6feb7ec..7a551c9c1cc 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"
@@ -178,8 +179,9 @@ private:
 
 }  // namespace
 
-BalancerChunkSelectionPolicyImpl::BalancerChunkSelectionPolicyImpl(ClusterStatistics* clusterStats)
-    : _clusterStats(clusterStats) {}
+BalancerChunkSelectionPolicyImpl::BalancerChunkSelectionPolicyImpl(ClusterStatistics* clusterStats,
+                                                                   BalancerRandomSource& random)
+    : _clusterStats(clusterStats), _random(random) {}
 
 BalancerChunkSelectionPolicyImpl::~BalancerChunkSelectionPolicyImpl() = default;
 
@@ -206,6 +208,8 @@ StatusWith<SplitInfoVector> BalancerChunkSelectionPolicyImpl::selectChunksToSpli
 
     SplitInfoVector splitCandidates;
 
+    std::shuffle(collections.begin(), collections.end(), _random);
+
     for (const auto& coll : collections) {
         if (coll.getDropped()) {
             continue;
@@ -259,6 +263,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 5a1277cd5ea..9ddfc8d80ac 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* txn) override;
@@ -73,6 +74,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 3bde0866770..fcad1e04da3 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"
@@ -96,7 +98,7 @@ StatusWith<string> retrieveShardMongoDVersion(OperationContext* txn, ShardId sha
 
 using ShardStatistics = ClusterStatistics::ShardStatistics;
 
-ClusterStatisticsImpl::ClusterStatisticsImpl() = default;
+ClusterStatisticsImpl::ClusterStatisticsImpl(BalancerRandomSource& random) : _random(random) {}
 
 ClusterStatisticsImpl::~ClusterStatisticsImpl() = default;
 
@@ -112,7 +114,9 @@ StatusWith<vector<ShardStatistics>> ClusterStatisticsImpl::getStats(OperationCon
         return shardsStatus.getStatus();
     }
 
-    const vector<ShardType> shards(std::move(shardsStatus.getValue().value));
+    auto& shards = shardsStatus.getValue().value;
+
+    std::shuffle(shards.begin(), shards.end(), _random);
 
     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 d03a2f2b403..4fa19a36c90 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* txn) override;
+
+private:
+    // Source of randomness when metadata needs to be randomized.
+    BalancerRandomSource& _random;
 };
 
 }  // namespace mongo