You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mesos.apache.org by bm...@apache.org on 2018/07/02 06:23:51 UTC
[1/7] mesos git commit: Added a test for weighted shuffling.
Repository: mesos
Updated Branches:
refs/heads/1.4.x 1c03262a9 -> d29d9f309
Added a test for weighted shuffling.
Review: https://reviews.apache.org/r/67370/
Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/c546bbf7
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/c546bbf7
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/c546bbf7
Branch: refs/heads/1.4.x
Commit: c546bbf7b06278b15efa4a33648dfbed858e3167
Parents: d3fe380
Author: Benjamin Mahler <bm...@apache.org>
Authored: Sat Jun 2 21:25:58 2018 -0400
Committer: Benjamin Mahler <bm...@apache.org>
Committed: Fri Jun 29 16:34:26 2018 -0700
----------------------------------------------------------------------
src/tests/sorter_tests.cpp | 51 +++++++++++++++++++++++++++++++++++++++++
1 file changed, 51 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/mesos/blob/c546bbf7/src/tests/sorter_tests.cpp
----------------------------------------------------------------------
diff --git a/src/tests/sorter_tests.cpp b/src/tests/sorter_tests.cpp
index 6ca724d..8e14573 100644
--- a/src/tests/sorter_tests.cpp
+++ b/src/tests/sorter_tests.cpp
@@ -26,6 +26,8 @@
#include "master/allocator/sorter/drf/sorter.hpp"
+#include "master/allocator/sorter/random/utils.hpp"
+
#include "tests/mesos.hpp"
#include "tests/resources_utils.hpp"
@@ -40,6 +42,55 @@ namespace mesos {
namespace internal {
namespace tests {
+// Test the behavior of weighted shuffle by ensuring that the
+// probability distribution after a number of runs is within
+// a particular error bound.
+TEST(WeightedShuffleTest, ProbabilityDistribution)
+{
+ std::mt19937 generator(0); // Pass a consistent seed.
+
+ // Count of how many times item i was shuffled into position j.
+ size_t totalRuns = 1000u;
+ size_t counts[5][5] = {};
+
+ for (size_t run = 0; run < totalRuns; ++run) {
+ // Items: [ 0, ..., 4]
+ // Weights: [1.0, ..., 5.0]
+ vector<size_t> items = {0, 1, 2, 3, 4};
+ vector<double> weights = {1.0, 2.0, 3.0, 4.0, 5.0};
+
+ mesos::internal::master::allocator::weightedShuffle(
+ items.begin(), items.end(), weights, generator);
+
+ for (size_t i = 0; i < items.size(); ++i) {
+ // Count the item landing in position i.
+ ++counts[items[i]][i];
+ }
+ }
+
+ // This table was generated by running a weighted shuffle algorithm
+ // for a large number of iterations.
+ double expectedProbabilities[5][5] = {
+ { 0.07, 0.08, 0.12, 0.20, 0.54 },
+ { 0.13, 0.16, 0.20, 0.28, 0.23 },
+ { 0.20, 0.22, 0.24, 0.22, 0.12 },
+ { 0.27, 0.26, 0.23, 0.17, 0.07 },
+ { 0.33, 0.28, 0.21, 0.13, 0.04 },
+ };
+
+ double actualProbabilities[5][5];
+
+ for (int i = 0; i < 5; ++i) {
+ for (int j = 0; j < 5; ++j) {
+ actualProbabilities[i][j] = counts[i][j] / (1.0 * totalRuns);
+
+ // Assert that the actual probabilities differ less than
+ // an absolute 5%.
+ ASSERT_NEAR(expectedProbabilities[i][j], actualProbabilities[i][j], 0.05);
+ }
+ }
+}
+
TEST(SorterTest, DRFSorter)
{
[6/7] mesos git commit: Added MESOS-8936 to the 1.4.2 CHANGELOG.
Posted by bm...@apache.org.
Added MESOS-8936 to the 1.4.2 CHANGELOG.
Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/d29d9f30
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/d29d9f30
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/d29d9f30
Branch: refs/heads/1.4.x
Commit: d29d9f309686867393b9f7c9d7da1ef4ca6c56f5
Parents: 1addca3
Author: Benjamin Mahler <bm...@apache.org>
Authored: Fri Jun 29 16:38:19 2018 -0700
Committer: Benjamin Mahler <bm...@apache.org>
Committed: Sun Jul 1 15:03:41 2018 -0700
----------------------------------------------------------------------
CHANGELOG | 1 +
1 file changed, 1 insertion(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/mesos/blob/d29d9f30/CHANGELOG
----------------------------------------------------------------------
diff --git a/CHANGELOG b/CHANGELOG
index 6585f99..1d38f2c 100644
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -34,6 +34,7 @@ Release Notes - Mesos - Version 1.4.2 (WIP)
* [MESOS-8881] - Enable epoll backend in libevent integration.
* [MESOS-8885] - Disable libevent debug mode.
* [MESOS-8904] - Master crash when removing quota.
+ * [MESOS-8936] - Implement a Random Sorter for offer allocations.
* [MESOS-8942] - Master streaming API does not send (health) check updates for tasks.
* [MESOS-8945] - Master check failure due to CHECK_SOME(providerId).
* [MESOS-8947] - Improve the container preparing logging in IOSwitchboard and volume/secret isolator.
[2/7] mesos git commit: Introduced a weighted shuffle algorithm
implementation.
Posted by bm...@apache.org.
Introduced a weighted shuffle algorithm implementation.
This will be used by the random sorter in order to support weights.
Review: https://reviews.apache.org/r/67369/
Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/d3fe3804
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/d3fe3804
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/d3fe3804
Branch: refs/heads/1.4.x
Commit: d3fe3804f1474343182e2109125701a5f6e60c62
Parents: 1c03262
Author: Benjamin Mahler <bm...@apache.org>
Authored: Sat Jun 2 21:23:08 2018 -0400
Committer: Benjamin Mahler <bm...@apache.org>
Committed: Fri Jun 29 16:34:26 2018 -0700
----------------------------------------------------------------------
src/Makefile.am | 1 +
src/master/allocator/sorter/random/utils.hpp | 92 +++++++++++++++++++++++
2 files changed, 93 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/mesos/blob/d3fe3804/src/Makefile.am
----------------------------------------------------------------------
diff --git a/src/Makefile.am b/src/Makefile.am
index 68fff14..e05e39b 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -1097,6 +1097,7 @@ libmesos_no_3rdparty_la_SOURCES += \
master/allocator/sorter/sorter.hpp \
master/allocator/sorter/drf/metrics.hpp \
master/allocator/sorter/drf/sorter.hpp \
+ master/allocator/sorter/random/utils.hpp \
master/contender/standalone.hpp \
master/contender/zookeeper.hpp \
master/detector/standalone.hpp \
http://git-wip-us.apache.org/repos/asf/mesos/blob/d3fe3804/src/master/allocator/sorter/random/utils.hpp
----------------------------------------------------------------------
diff --git a/src/master/allocator/sorter/random/utils.hpp b/src/master/allocator/sorter/random/utils.hpp
new file mode 100644
index 0000000..1329359
--- /dev/null
+++ b/src/master/allocator/sorter/random/utils.hpp
@@ -0,0 +1,92 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef __MASTER_ALLOCATOR_SORTER_RANDOM_UTILS_HPP__
+#define __MASTER_ALLOCATOR_SORTER_RANDOM_UTILS_HPP__
+
+#include <algorithm>
+#include <cmath>
+#include <numeric>
+#include <random>
+#include <vector>
+
+#include <stout/check.hpp>
+
+namespace mesos {
+namespace internal {
+namespace master {
+namespace allocator {
+
+// A weighted variant of std::shuffle. Items with higher weight
+// have a higher chance of being towards the front of the list,
+// equivalent to weighted random sampling without replacement.
+// Code adapted from the following paper:
+//
+// http://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf
+// Found from: https://softwareengineering.stackexchange.com/a/344274
+//
+// This has O(n log n) runtime complexity.
+template <class RandomAccessIterator, class URBG>
+void weightedShuffle(
+ RandomAccessIterator begin,
+ RandomAccessIterator end,
+ const std::vector<double>& weights,
+ URBG&& urbg)
+{
+ CHECK_EQ(end - begin, (int) weights.size());
+
+ std::vector<double> keys(weights.size());
+
+ for (size_t i = 0; i < weights.size(); ++i) {
+ CHECK_GT(weights[i], 0.0);
+
+ // Make the key negative so that we don't have to reverse sort.
+ double random = std::uniform_real_distribution<>(0.0, 1.0)(urbg);
+ keys[i] = 0.0 - std::pow(random, (1.0 / weights[i]));
+ }
+
+ // Sort from smallest to largest keys. We store the sort permutation
+ // so that we can apply it to `items`.
+ std::vector<size_t> permutation(keys.size());
+ std::iota(permutation.begin(), permutation.end(), 0);
+
+ std::sort(permutation.begin(), permutation.end(),
+ [&](size_t i, size_t j){ return keys[i] < keys[j]; });
+
+ // Now apply the permutation to `items`.
+ //
+ // TODO(bmahler): Consider avoiding the copy of entries in `items`
+ // via an in-place application of the permutation:
+ // https://blog.merovius.de/2014/08/12/applying-permutation-in-constant.html
+ std::vector<typename std::iterator_traits<RandomAccessIterator>::value_type>
+ shuffled(end - begin);
+
+ std::transform(
+ permutation.begin(),
+ permutation.end(),
+ shuffled.begin(),
+ [&](size_t i){ return begin[i]; });
+
+ // Move the shuffled copy back into the `items`.
+ std::move(shuffled.begin(), shuffled.end(), begin);
+}
+
+} // namespace allocator {
+} // namespace master {
+} // namespace internal {
+} // namespace mesos {
+
+#endif // __MASTER_ALLOCATOR_SORTER_RANDOM_UTILS_HPP__
[4/7] mesos git commit: Added typedefs for using the allocator with
random sorters.
Posted by bm...@apache.org.
Added typedefs for using the allocator with random sorters.
Review: https://reviews.apache.org/r/67373/
Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/1aa69d04
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/1aa69d04
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/1aa69d04
Branch: refs/heads/1.4.x
Commit: 1aa69d04ac569ac06f57ac83ab2bac383ebed6b0
Parents: 528c883
Author: Benjamin Mahler <bm...@apache.org>
Authored: Mon Jun 4 15:17:19 2018 -0400
Committer: Benjamin Mahler <bm...@apache.org>
Committed: Sun Jul 1 15:03:41 2018 -0700
----------------------------------------------------------------------
src/master/allocator/mesos/hierarchical.hpp | 7 +++++++
1 file changed, 7 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/mesos/blob/1aa69d04/src/master/allocator/mesos/hierarchical.hpp
----------------------------------------------------------------------
diff --git a/src/master/allocator/mesos/hierarchical.hpp b/src/master/allocator/mesos/hierarchical.hpp
index 3f15b2c..6db912d 100644
--- a/src/master/allocator/mesos/hierarchical.hpp
+++ b/src/master/allocator/mesos/hierarchical.hpp
@@ -38,6 +38,7 @@
#include "master/allocator/mesos/metrics.hpp"
#include "master/allocator/sorter/drf/sorter.hpp"
+#include "master/allocator/sorter/random/sorter.hpp"
#include "master/constants.hpp"
@@ -60,6 +61,12 @@ HierarchicalDRFAllocatorProcess;
typedef MesosAllocator<HierarchicalDRFAllocatorProcess>
HierarchicalDRFAllocator;
+typedef HierarchicalAllocatorProcess<RandomSorter, RandomSorter, RandomSorter>
+HierarchicalRandomAllocatorProcess;
+
+typedef MesosAllocator<HierarchicalRandomAllocatorProcess>
+HierarchicalRandomAllocator;
+
namespace internal {
[5/7] mesos git commit: Updated flags to support choosing the random
sorter.
Posted by bm...@apache.org.
Updated flags to support choosing the random sorter.
This deprecates `--user_sorter` in favor of `--role_sorter`.
This patch also modifies the `--allocator` default to exclude "DRF"
from the value, while still ensuring the previous default works.
For now, both sorter flags must be set to `drf` or `random`.
Review: https://reviews.apache.org/r/67374/
Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/1addca38
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/1addca38
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/1addca38
Branch: refs/heads/1.4.x
Commit: 1addca384b0382361bcf960ac4c2c2732d4589cd
Parents: 1aa69d0
Author: Benjamin Mahler <bm...@apache.org>
Authored: Mon Jun 4 15:17:39 2018 -0400
Committer: Benjamin Mahler <bm...@apache.org>
Committed: Sun Jul 1 15:03:41 2018 -0700
----------------------------------------------------------------------
include/mesos/allocator/allocator.hpp | 8 +++++++-
src/master/allocator/allocator.cpp | 24 +++++++++++++++++++++---
src/master/constants.hpp | 4 ++--
src/master/flags.cpp | 12 +++++++-----
src/master/flags.hpp | 2 +-
src/master/main.cpp | 12 +++++++-----
6 files changed, 45 insertions(+), 17 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/mesos/blob/1addca38/include/mesos/allocator/allocator.hpp
----------------------------------------------------------------------
diff --git a/include/mesos/allocator/allocator.hpp b/include/mesos/allocator/allocator.hpp
index 537658b..8bbd7fb 100644
--- a/include/mesos/allocator/allocator.hpp
+++ b/include/mesos/allocator/allocator.hpp
@@ -60,9 +60,15 @@ public:
* allocator instance from a module using the given name. If `Try`
* does not report an error, the wrapped `Allocator*` is not null.
*
+ * TODO(bmahler): Figure out how to pass parameters without
+ * burning in the built-in module arguments.
+ *
* @param name Name of the allocator.
*/
- static Try<Allocator*> create(const std::string& name);
+ static Try<Allocator*> create(
+ const std::string& name,
+ const std::string& roleSorter,
+ const std::string& frameworkSorter);
Allocator() {}
http://git-wip-us.apache.org/repos/asf/mesos/blob/1addca38/src/master/allocator/allocator.cpp
----------------------------------------------------------------------
diff --git a/src/master/allocator/allocator.cpp b/src/master/allocator/allocator.cpp
index e3dd737..4357436 100644
--- a/src/master/allocator/allocator.cpp
+++ b/src/master/allocator/allocator.cpp
@@ -27,18 +27,36 @@
using std::string;
using mesos::internal::master::allocator::HierarchicalDRFAllocator;
+using mesos::internal::master::allocator::HierarchicalRandomAllocator;
namespace mesos {
namespace allocator {
-Try<Allocator*> Allocator::create(const string& name)
+Try<Allocator*> Allocator::create(
+ const string& name,
+ const string& roleSorter,
+ const string& frameworkSorter)
{
// Create an instance of the default allocator. If other than the
// default allocator is requested, search for it in loaded modules.
+ //
// NOTE: We do not need an extra not-null check, because both
// ModuleManager and built-in allocator factory do that already.
- if (name == mesos::internal::master::DEFAULT_ALLOCATOR) {
- return HierarchicalDRFAllocator::create();
+ //
+ // We also look for "HierarchicalDRF" since that was the
+ // previous value for `DEFAULT_ALLOCATOR`.
+ if (name == "HierarchicalDRF" ||
+ name == mesos::internal::master::DEFAULT_ALLOCATOR) {
+ if (roleSorter == "drf" && frameworkSorter == "drf") {
+ return HierarchicalDRFAllocator::create();
+ }
+
+ if (roleSorter == "random" && frameworkSorter == "random") {
+ return HierarchicalRandomAllocator::create();
+ }
+
+ return Error("Unsupported combination of 'role_sorter'"
+ " and 'framework_sorter': must be equal (for now)");
}
return modules::ModuleManager::create<Allocator>(name);
http://git-wip-us.apache.org/repos/asf/mesos/blob/1addca38/src/master/constants.hpp
----------------------------------------------------------------------
diff --git a/src/master/constants.hpp b/src/master/constants.hpp
index 725680b..c35ed45 100644
--- a/src/master/constants.hpp
+++ b/src/master/constants.hpp
@@ -125,8 +125,8 @@ constexpr Duration ZOOKEEPER_SESSION_TIMEOUT = Seconds(10);
// Name of the default, CRAM-MD5 authenticator.
constexpr char DEFAULT_AUTHENTICATOR[] = "crammd5";
-// Name of the default, HierarchicalDRF authenticator.
-constexpr char DEFAULT_ALLOCATOR[] = "HierarchicalDRF";
+// Name of the default hierarchical allocator.
+constexpr char DEFAULT_ALLOCATOR[] = "hierarchical";
// The default interval between allocations.
constexpr Duration DEFAULT_ALLOCATION_INTERVAL = Seconds(1);
http://git-wip-us.apache.org/repos/asf/mesos/blob/1addca38/src/master/flags.cpp
----------------------------------------------------------------------
diff --git a/src/master/flags.cpp b/src/master/flags.cpp
index fa6d274..ffd9d7e 100644
--- a/src/master/flags.cpp
+++ b/src/master/flags.cpp
@@ -176,15 +176,17 @@ mesos::internal::master::Flags::Flags()
"machines are accepted. Path can be of the form\n"
"`file:///path/to/file` or `/path/to/file`.\n");
- add(&Flags::user_sorter,
- "user_sorter",
- "Policy to use for allocating resources between users. May be one of:\n"
- " dominant_resource_fairness (drf)",
+ add(&Flags::role_sorter,
+ "role_sorter",
+ flags::DeprecatedName("user_sorter"),
+ "Policy to use for allocating resources between roles when\n"
+ "allocating up to quota guarantees as well as when allocating\n"
+ "up to quota limits. May be one of: [drf, random]",
"drf");
add(&Flags::framework_sorter,
"framework_sorter",
- "Policy to use for allocating resources between a given user's\n"
+ "Policy to use for allocating resources between a given role's\n"
"frameworks. Options are the same as for `--user_sorter`.",
"drf");
http://git-wip-us.apache.org/repos/asf/mesos/blob/1addca38/src/master/flags.hpp
----------------------------------------------------------------------
diff --git a/src/master/flags.hpp b/src/master/flags.hpp
index edda71a..8b1944c 100644
--- a/src/master/flags.hpp
+++ b/src/master/flags.hpp
@@ -60,7 +60,7 @@ public:
Option<std::string> agent_removal_rate_limit;
std::string webui_dir;
Option<Path> whitelist;
- std::string user_sorter;
+ std::string role_sorter;
std::string framework_sorter;
Duration allocation_interval;
Option<std::string> cluster;
http://git-wip-us.apache.org/repos/asf/mesos/blob/1addca38/src/master/main.cpp
----------------------------------------------------------------------
diff --git a/src/master/main.cpp b/src/master/main.cpp
index 1a78a55..b701870 100644
--- a/src/master/main.cpp
+++ b/src/master/main.cpp
@@ -327,17 +327,19 @@ int main(int argc, char** argv)
}
// Create an instance of allocator.
- const string allocatorName = flags.allocator;
- Try<Allocator*> allocator = Allocator::create(allocatorName);
+ Try<Allocator*> allocator = Allocator::create(
+ flags.allocator,
+ flags.role_sorter,
+ flags.framework_sorter);
if (allocator.isError()) {
EXIT(EXIT_FAILURE)
- << "Failed to create '" << allocatorName
- << "' allocator: " << allocator.error();
+ << "Failed to create allocator '" << flags.allocator << "'"
+ << ": " << allocator.error();
}
CHECK_NOTNULL(allocator.get());
- LOG(INFO) << "Using '" << allocatorName << "' allocator";
+ LOG(INFO) << "Using '" << flags.allocator << "' allocator";
Storage* storage = nullptr;
#ifndef __WINDOWS__
[7/7] mesos git commit: Updated sorter tests to run against multiple
sorters where possible.
Posted by bm...@apache.org.
Updated sorter tests to run against multiple sorters where possible.
Several of the sorter tests, including the benchmarks, were agnostic
to the sorter implementation. These have been updated to run for both
`DRFSorter` and `RandomSorter`. The remainder have been updated to
be called DRFSorter tests.
Review: https://reviews.apache.org/r/67372/
Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/528c8832
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/528c8832
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/528c8832
Branch: refs/heads/1.4.x
Commit: 528c88320d994a48b5a8fa3db4659651037a8211
Parents: e000555
Author: Benjamin Mahler <bm...@apache.org>
Authored: Mon Jun 4 15:04:05 2018 -0400
Committer: Benjamin Mahler <bm...@apache.org>
Committed: Sun Jul 1 15:03:41 2018 -0700
----------------------------------------------------------------------
src/tests/sorter_tests.cpp | 582 ++++++++++++++++++++--------------------
1 file changed, 293 insertions(+), 289 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/mesos/blob/528c8832/src/tests/sorter_tests.cpp
----------------------------------------------------------------------
diff --git a/src/tests/sorter_tests.cpp b/src/tests/sorter_tests.cpp
index 8e14573..6d048ec 100644
--- a/src/tests/sorter_tests.cpp
+++ b/src/tests/sorter_tests.cpp
@@ -26,12 +26,14 @@
#include "master/allocator/sorter/drf/sorter.hpp"
+#include "master/allocator/sorter/random/sorter.hpp"
#include "master/allocator/sorter/random/utils.hpp"
#include "tests/mesos.hpp"
#include "tests/resources_utils.hpp"
using mesos::internal::master::allocator::DRFSorter;
+using mesos::internal::master::allocator::RandomSorter;
using std::cout;
using std::endl;
@@ -92,7 +94,15 @@ TEST(WeightedShuffleTest, ProbabilityDistribution)
}
-TEST(SorterTest, DRFSorter)
+template <typename T>
+class CommonSorterTest : public ::testing::Test {};
+
+// Some tests are testing logic common to any sorter implementation.
+typedef ::testing::Types<DRFSorter, RandomSorter> SorterTypes;
+TYPED_TEST_CASE(CommonSorterTest, SorterTypes);
+
+
+TEST(DRFSorterTest, DRF)
{
DRFSorter sorter;
@@ -185,7 +195,7 @@ TEST(SorterTest, DRFSorter)
}
-TEST(SorterTest, WDRFSorter)
+TEST(DRFSorterTest, WDRF)
{
DRFSorter sorter;
@@ -245,7 +255,7 @@ TEST(SorterTest, WDRFSorter)
}
-TEST(SorterTest, WDRFSorterUpdateWeight)
+TEST(DRFSorterTest, UpdateWeight)
{
DRFSorter sorter;
@@ -277,7 +287,7 @@ TEST(SorterTest, WDRFSorterUpdateWeight)
// Check that the sorter uses the total number of allocations made to
// a client as a tiebreaker when the two clients have the same share.
-TEST(SorterTest, CountAllocations)
+TEST(DRFSorterTest, AllocationCountTieBreak)
{
DRFSorter sorter;
@@ -360,7 +370,7 @@ TEST(SorterTest, CountAllocations)
// sequence of operations happens as in the `DRFSorter` test, but all
// client names are nested into disjoint branches of the tree. In this
// case, the hierarchy should not change allocation behavior.
-TEST(SorterTest, ShallowHierarchy)
+TEST(DRFSorterTest, ShallowHierarchy)
{
DRFSorter sorter;
@@ -455,7 +465,7 @@ TEST(SorterTest, ShallowHierarchy)
// Analogous to `ShallowHierarchy` except the client names are nested
// more deeply and different client names are at different depths in
// the tree.
-TEST(SorterTest, DeepHierarchy)
+TEST(DRFSorterTest, DeepHierarchy)
{
DRFSorter sorter;
@@ -551,7 +561,7 @@ TEST(SorterTest, DeepHierarchy)
}
-TEST(SorterTest, HierarchicalAllocation)
+TEST(DRFSorterTest, HierarchicalAllocation)
{
DRFSorter sorter;
@@ -658,7 +668,7 @@ TEST(SorterTest, HierarchicalAllocation)
// This test checks that the sorted list of clients returned by the
// sorter iterates over the client tree in the correct order.
-TEST(SorterTest, HierarchicalIterationOrder)
+TEST(DRFSorterTest, HierarchicalIterationOrder)
{
DRFSorter sorter;
@@ -706,7 +716,7 @@ TEST(SorterTest, HierarchicalIterationOrder)
// This test checks what happens when a new sorter client is added as
// a child of what was previously a leaf node.
-TEST(SorterTest, AddChildToLeaf)
+TEST(DRFSorterTest, AddChildToLeaf)
{
DRFSorter sorter;
@@ -777,7 +787,7 @@ TEST(SorterTest, AddChildToLeaf)
// This test checks what happens when a new sorter client is added as
// a child of what was previously an internal node.
-TEST(SorterTest, AddChildToInternal)
+TEST(DRFSorterTest, AddChildToInternal)
{
DRFSorter sorter;
@@ -820,7 +830,7 @@ TEST(SorterTest, AddChildToInternal)
// This test checks what happens when a new sorter client is added as
// a child of what was previously an inactive leaf node.
-TEST(SorterTest, AddChildToInactiveLeaf)
+TEST(DRFSorterTest, AddChildToInactiveLeaf)
{
DRFSorter sorter;
@@ -855,7 +865,7 @@ TEST(SorterTest, AddChildToInactiveLeaf)
// This test checks what happens when a sorter client is removed,
// which allows a leaf node to be collapsed into its parent node. This
// is basically the inverse situation to `AddChildToLeaf`.
-TEST(SorterTest, RemoveLeafCollapseParent)
+TEST(DRFSorterTest, RemoveLeafCollapseParent)
{
DRFSorter sorter;
@@ -890,7 +900,7 @@ TEST(SorterTest, RemoveLeafCollapseParent)
// This test checks what happens when a sorter client is removed and a
// leaf node can be collapsed into its parent node, we correctly
// propagate the `inactive` flag from leaf -> parent.
-TEST(SorterTest, RemoveLeafCollapseParentInactive)
+TEST(DRFSorterTest, RemoveLeafCollapseParentInactive)
{
DRFSorter sorter;
@@ -926,7 +936,7 @@ TEST(SorterTest, RemoveLeafCollapseParentInactive)
// This test checks that setting a weight on an internal node works
// correctly.
-TEST(SorterTest, ChangeWeightOnSubtree)
+TEST(DRFSorterTest, ChangeWeightOnSubtree)
{
DRFSorter sorter;
@@ -979,7 +989,7 @@ TEST(SorterTest, ChangeWeightOnSubtree)
// Some resources are split across multiple resource objects (e.g.
// persistent volumes). This test ensures that the shares for these
// are accounted correctly.
-TEST(SorterTest, SplitResourceShares)
+TEST(DRFSorterTest, SplitResourceShares)
{
DRFSorter sorter;
@@ -1014,9 +1024,9 @@ TEST(SorterTest, SplitResourceShares)
}
-TEST(SorterTest, UpdateAllocation)
+TYPED_TEST(CommonSorterTest, UpdateAllocation)
{
- DRFSorter sorter;
+ TypeParam sorter;
SlaveID slaveId;
slaveId.set_value("agentId");
@@ -1051,9 +1061,9 @@ TEST(SorterTest, UpdateAllocation)
}
-TEST(SorterTest, UpdateAllocationNestedClient)
+TYPED_TEST(CommonSorterTest, UpdateAllocationNestedClient)
{
- DRFSorter sorter;
+ TypeParam sorter;
SlaveID slaveId;
slaveId.set_value("agentId");
@@ -1090,9 +1100,9 @@ TEST(SorterTest, UpdateAllocationNestedClient)
// This test checks that the sorter correctly reports allocation
// information about inactive clients.
-TEST(SorterTest, AllocationForInactiveClient)
+TYPED_TEST(CommonSorterTest, AllocationForInactiveClient)
{
- DRFSorter sorter;
+ TypeParam sorter;
SlaveID slaveId;
slaveId.set_value("agentId");
@@ -1130,9 +1140,9 @@ TEST(SorterTest, AllocationForInactiveClient)
// we need to keep track of the SlaveIDs of the resources. This
// tests that no resources vanish in the process of aggregation
// by inspecting the result of 'allocation'.
-TEST(SorterTest, MultipleSlaves)
+TYPED_TEST(CommonSorterTest, MultipleSlaves)
{
- DRFSorter sorter;
+ TypeParam sorter;
SlaveID slaveA;
slaveA.set_value("agentA");
@@ -1163,9 +1173,9 @@ TEST(SorterTest, MultipleSlaves)
// keep track of the SlaveIDs of the resources. This tests that no
// resources vanish in the process of aggregation by performing update
// allocations from unreserved to reserved resources.
-TEST(SorterTest, MultipleSlavesUpdateAllocation)
+TYPED_TEST(CommonSorterTest, MultipleSlavesUpdateAllocation)
{
- DRFSorter sorter;
+ TypeParam sorter;
SlaveID slaveA;
slaveA.set_value("agentA");
@@ -1206,7 +1216,7 @@ TEST(SorterTest, MultipleSlavesUpdateAllocation)
// This test verifies that when the total pool of resources is updated
// the sorting order of clients reflects the new total.
-TEST(SorterTest, UpdateTotal)
+TEST(DRFSorterTest, UpdateTotal)
{
DRFSorter sorter;
@@ -1243,7 +1253,7 @@ TEST(SorterTest, UpdateTotal)
// Similar to the above 'UpdateTotal' test, but tests the scenario
// when there are multiple slaves.
-TEST(SorterTest, MultipleSlavesUpdateTotal)
+TEST(DRFSorterTest, MultipleSlavesUpdateTotal)
{
DRFSorter sorter;
@@ -1284,7 +1294,7 @@ TEST(SorterTest, MultipleSlavesUpdateTotal)
// This test verifies that revocable resources are properly accounted
// for in the DRF sorter.
-TEST(SorterTest, RevocableResources)
+TEST(DRFSorterTest, RevocableResources)
{
DRFSorter sorter;
@@ -1325,7 +1335,7 @@ TEST(SorterTest, RevocableResources)
// This test verifies that shared resources are properly accounted for in
// the DRF sorter.
-TEST(SorterTest, SharedResources)
+TEST(DRFSorterTest, SharedResources)
{
DRFSorter sorter;
@@ -1419,7 +1429,7 @@ TEST(SorterTest, SharedResources)
// This test verifies that shared resources can make clients
// indistinguishable with its high likelihood of becoming the
// dominant resource.
-TEST(SorterTest, SameDominantSharedResourcesAcrossClients)
+TEST(DRFSorterTest, SameDominantSharedResourcesAcrossClients)
{
DRFSorter sorter;
@@ -1468,7 +1478,7 @@ TEST(SorterTest, SameDominantSharedResourcesAcrossClients)
// This test verifies that allocating the same shared resource to the
// same client does not alter its fair share.
-TEST(SorterTest, SameSharedResourcesSameClient)
+TEST(DRFSorterTest, SameSharedResourcesSameClient)
{
DRFSorter sorter;
@@ -1513,7 +1523,7 @@ TEST(SorterTest, SameSharedResourcesSameClient)
// This test verifies that shared resources are unallocated when all
// the copies are unallocated.
-TEST(SorterTest, SharedResourcesUnallocated)
+TEST(DRFSorterTest, SharedResourcesUnallocated)
{
DRFSorter sorter;
@@ -1566,9 +1576,9 @@ TEST(SorterTest, SharedResourcesUnallocated)
// This test verifies that shared resources are removed from the sorter
// only when all instances of the the same shared resource are removed.
-TEST(SorterTest, RemoveSharedResources)
+TYPED_TEST(CommonSorterTest, RemoveSharedResources)
{
- DRFSorter sorter;
+ TypeParam sorter;
SlaveID slaveId;
slaveId.set_value("agentId");
@@ -1601,331 +1611,325 @@ TEST(SorterTest, RemoveSharedResources)
}
-class Sorter_BENCHMARK_Test
- : public ::testing::Test,
- public ::testing::WithParamInterface<std::tuple<size_t, size_t>> {};
-
-
-// The sorter benchmark tests are parameterized by
-// the number of clients and agents.
-INSTANTIATE_TEST_CASE_P(
- AgentAndClientCount,
- Sorter_BENCHMARK_Test,
- ::testing::Combine(
- ::testing::Values(1000U, 5000U, 10000U, 20000U, 30000U, 50000U),
- ::testing::Values(1U, 50U, 100U, 200U, 500U, 1000U))
- );
-
-
// This benchmark simulates sorting a number of clients that have
// different amount of allocations.
-TEST_P(Sorter_BENCHMARK_Test, FullSort)
+//
+// NOTE: There is not a way to write a test that is *both* type and
+// value parameterized, so the benchmark is typed and iterates over
+// the values specific to what it benchmarks.
+TYPED_TEST(CommonSorterTest, BENCHMARK_FullSort)
{
- size_t agentCount = std::get<0>(GetParam());
- size_t clientCount = std::get<1>(GetParam());
-
- cout << "Using " << agentCount << " agents and "
- << clientCount << " clients" << endl;
+ size_t agentCounts[] = {1000U, 5000U, 10000U, 20000U, 30000U, 50000U};
+ size_t clientCounts[] = {1U, 50U, 100U, 200U, 500U, 1000U};
- vector<SlaveID> agents;
- agents.reserve(agentCount);
+ foreach (size_t agentCount, agentCounts) {
+ foreach (size_t clientCount, clientCounts) {
+ cout << "Using " << agentCount << " agents and "
+ << clientCount << " clients" << endl;
- vector<string> clients;
- clients.reserve(clientCount);
+ vector<SlaveID> agents;
+ agents.reserve(agentCount);
- DRFSorter sorter;
- Stopwatch watch;
+ vector<string> clients;
+ clients.reserve(clientCount);
- watch.start();
- {
- for (size_t i = 0; i < clientCount; i++) {
- const string clientId = stringify(i);
+ TypeParam sorter;
+ Stopwatch watch;
- clients.push_back(clientId);
+ watch.start();
+ {
+ for (size_t i = 0; i < clientCount; i++) {
+ const string clientId = stringify(i);
- sorter.add(clientId);
- }
- }
- watch.stop();
+ clients.push_back(clientId);
- cout << "Added " << clientCount << " clients in "
- << watch.elapsed() << endl;
+ sorter.add(clientId);
+ }
+ }
+ watch.stop();
- Resources agentResources = Resources::parse(
- "cpus:24;mem:4096;disk:4096;ports:[31000-32000]").get();
+ cout << "Added " << clientCount << " clients in "
+ << watch.elapsed() << endl;
- watch.start();
- {
- for (size_t i = 0; i < agentCount; i++) {
- SlaveID slaveId;
- slaveId.set_value("agent" + stringify(i));
+ Resources agentResources = Resources::parse(
+ "cpus:24;mem:4096;disk:4096;ports:[31000-32000]").get();
- agents.push_back(slaveId);
+ watch.start();
+ {
+ for (size_t i = 0; i < agentCount; i++) {
+ SlaveID slaveId;
+ slaveId.set_value("agent" + stringify(i));
- sorter.add(slaveId, agentResources);
- }
- }
- watch.stop();
+ agents.push_back(slaveId);
- cout << "Added " << agentCount << " agents in "
- << watch.elapsed() << endl;
+ sorter.add(slaveId, agentResources);
+ }
+ }
+ watch.stop();
- Resources allocated = Resources::parse(
- "cpus:16;mem:2014;disk:1024").get();
+ cout << "Added " << agentCount << " agents in "
+ << watch.elapsed() << endl;
- // TODO(gyliu513): Parameterize the number of range for the fragment.
- Try<::mesos::Value::Ranges> ranges = fragment(createRange(31000, 32000), 100);
- ASSERT_SOME(ranges);
- ASSERT_EQ(100, ranges->range_size());
+ Resources allocated = Resources::parse(
+ "cpus:16;mem:2014;disk:1024").get();
- allocated += createPorts(ranges.get());
+ // TODO(gyliu513): Parameterize the number of range for the fragment.
+ Try<::mesos::Value::Ranges> ranges =
+ fragment(createRange(31000, 32000), 100);
+ ASSERT_SOME(ranges);
+ ASSERT_EQ(100, ranges->range_size());
- watch.start();
- {
- // Allocate resources on all agents, round-robin through the clients.
- size_t clientIndex = 0;
- foreach (const SlaveID& slaveId, agents) {
- const string& client = clients[clientIndex++ % clients.size()];
- sorter.allocated(client, slaveId, allocated);
- }
- }
- watch.stop();
+ allocated += createPorts(ranges.get());
- cout << "Added allocations for " << agentCount << " agents in "
- << watch.elapsed() << endl;
+ watch.start();
+ {
+ // Allocate resources on all agents, round-robin through the clients.
+ size_t clientIndex = 0;
+ foreach (const SlaveID& slaveId, agents) {
+ const string& client = clients[clientIndex++ % clients.size()];
+ sorter.allocated(client, slaveId, allocated);
+ }
+ }
+ watch.stop();
- watch.start();
- {
- sorter.sort();
- }
- watch.stop();
+ cout << "Added allocations for " << agentCount << " agents in "
+ << watch.elapsed() << endl;
- cout << "Full sort of " << clientCount << " clients took "
- << watch.elapsed() << endl;
+ watch.start();
+ {
+ sorter.sort();
+ }
+ watch.stop();
- watch.start();
- {
- sorter.sort();
- }
- watch.stop();
+ cout << "Full sort of " << clientCount << " clients took "
+ << watch.elapsed() << endl;
- cout << "No-op sort of " << clientCount << " clients took "
- << watch.elapsed() << endl;
+ watch.start();
+ {
+ sorter.sort();
+ }
+ watch.stop();
+
+ cout << "No-op sort of " << clientCount << " clients took "
+ << watch.elapsed() << endl;
+
+ watch.start();
+ {
+ // Unallocate resources on all agents, round-robin through the clients.
+ size_t clientIndex = 0;
+ foreach (const SlaveID& slaveId, agents) {
+ const string& client = clients[clientIndex++ % clients.size()];
+ sorter.unallocated(client, slaveId, allocated);
+ }
+ }
+ watch.stop();
- watch.start();
- {
- // Unallocate resources on all agents, round-robin through the clients.
- size_t clientIndex = 0;
- foreach (const SlaveID& slaveId, agents) {
- const string& client = clients[clientIndex++ % clients.size()];
- sorter.unallocated(client, slaveId, allocated);
- }
- }
- watch.stop();
+ cout << "Removed allocations for " << agentCount << " agents in "
+ << watch.elapsed() << endl;
- cout << "Removed allocations for " << agentCount << " agents in "
- << watch.elapsed() << endl;
+ watch.start();
+ {
+ foreach (const SlaveID& slaveId, agents) {
+ sorter.remove(slaveId, agentResources);
+ }
+ }
+ watch.stop();
- watch.start();
- {
- foreach (const SlaveID& slaveId, agents) {
- sorter.remove(slaveId, agentResources);
- }
- }
- watch.stop();
+ cout << "Removed " << agentCount << " agents in "
+ << watch.elapsed() << endl;
- cout << "Removed " << agentCount << " agents in "
- << watch.elapsed() << endl;
+ watch.start();
+ {
+ foreach (const string& clientId, clients) {
+ sorter.remove(clientId);
+ }
+ }
+ watch.stop();
- watch.start();
- {
- foreach (const string& clientId, clients) {
- sorter.remove(clientId);
+ cout << "Removed " << clientCount << " clients in "
+ << watch.elapsed() << endl;
}
}
- watch.stop();
-
- cout << "Removed " << clientCount << " clients in "
- << watch.elapsed() << endl;
}
-class HierarchicalSorter_BENCHMARK_Test
- : public ::testing::Test,
- public ::testing::WithParamInterface<
- std::tuple<size_t, std::tuple<size_t, size_t>>> {};
-
-
-INSTANTIATE_TEST_CASE_P(
- AgentAndClientCount,
- HierarchicalSorter_BENCHMARK_Test,
- ::testing::Combine(
- ::testing::Values(1000U, 5000U, 10000U, 20000U, 30000U, 50000U),
- ::testing::Values(
- // ~1000 clients with different heights and branching factors.
- std::tuple<size_t, size_t>{3U, 32U}, // 1056 clients.
- std::tuple<size_t, size_t>{7U, 3U}, // 1092 clients.
- std::tuple<size_t, size_t>{10U, 2U})) // 1022 clients.
- );
-
-
// This benchmark simulates sorting a hierarchy of clients that have
// different amount of allocations. The shape of the hierarchy is
// determined by two parameters: height (depth of the hierarchy
// including the root node) and branching factor (number of children
// of each internal node).
-TEST_P(HierarchicalSorter_BENCHMARK_Test, FullSort)
+//
+// NOTE: There is not a way to write a test that is *both* type and
+// value parameterized, so the benchmark is typed and iterates over
+// the values specific to what it benchmarks.
+TYPED_TEST(CommonSorterTest, BENCHMARK_HierarchyFullSort)
{
- const size_t agentCount = std::get<0>(GetParam());
- const std::tuple<size_t, size_t> tuple = std::get<1>(GetParam());
- const size_t treeHeight = std::get<0>(tuple);
- const size_t branchingFactor = std::get<1>(tuple);
-
- vector<SlaveID> agents;
- agents.reserve(agentCount);
-
- // Compute total number of clients in a tree of given depth and
- // breadth, including root node.
- std::function<size_t (size_t)> totalClients =
- [&totalClients, branchingFactor](size_t depth) -> size_t {
- if (depth == 0 || depth == 1) {
- return depth;
- }
+ typedef std::pair<size_t, size_t> HeightAndBranchingFactor;
- return 1 + branchingFactor * totalClients(depth - 1);
- };
+ const size_t agentCounts[] = {1000U, 5000U, 10000U, 20000U, 30000U, 50000U};
- const size_t clientCount = totalClients(treeHeight) - 1;
-
- vector<string> clients;
- clients.reserve(clientCount);
+ // ~1000 clients with different heights and branching factors.
+ const HeightAndBranchingFactor heightAndBranchingFactors[] = {
+ {3U, 32U}, // Short and wide: 1056 clients.
+ {7U, 3U}, // Medium height and width: 1092 clients.
+ {10U, 2U}, // Tall and thin: 1022 clients.
+ };
- DRFSorter sorter;
- Stopwatch watch;
+ foreach (size_t agentCount, agentCounts) {
+ foreach (HeightAndBranchingFactor pair, heightAndBranchingFactors) {
+ const size_t treeHeight = std::get<0>(pair);
+ const size_t branchingFactor = std::get<1>(pair);
- watch.start();
- {
- // Build a tree of given depth and branching factor in depth-first fashion.
- std::function<void (string, size_t)> buildTree =
- [&buildTree, &sorter, &clients, branchingFactor](
- string path, size_t depth) {
- if (depth == 0) {
- return;
- }
+ vector<SlaveID> agents;
+ agents.reserve(agentCount);
- for (size_t i = 0; i < branchingFactor; i++) {
- buildTree(path + stringify(i) + "/", depth - 1);
+ // Compute total number of clients in a tree of given depth and
+ // breadth, including root node.
+ std::function<size_t (size_t)> totalClients =
+ [&totalClients, branchingFactor](size_t depth) -> size_t {
+ if (depth == 0 || depth == 1) {
+ return depth;
}
- const string client = strings::remove(path, "/", strings::SUFFIX);
- if (!client.empty()) {
- sorter.add(client);
- clients.push_back(client);
- }
+ return 1 + branchingFactor * totalClients(depth - 1);
};
- buildTree("", treeHeight);
- }
- watch.stop();
-
- cout << "Added " << clientCount << " clients in "
- << watch.elapsed() << endl;
+ const size_t clientCount = totalClients(treeHeight) - 1;
+
+ vector<string> clients;
+ clients.reserve(clientCount);
+
+ TypeParam sorter;
+ Stopwatch watch;
+
+ watch.start();
+ {
+ // Build a tree of given depth and branching factor
+ // in depth-first fashion.
+ std::function<void (string, size_t)> buildTree =
+ [&buildTree, &sorter, &clients, branchingFactor](
+ string path, size_t depth) {
+ if (depth == 0) {
+ return;
+ }
+
+ for (size_t i = 0; i < branchingFactor; i++) {
+ buildTree(path + stringify(i) + "/", depth - 1);
+ }
+
+ const string client = strings::remove(path, "/", strings::SUFFIX);
+ if (!client.empty()) {
+ sorter.add(client);
+ clients.push_back(client);
+ }
+ };
+
+ buildTree("", treeHeight);
+ }
+ watch.stop();
- Resources agentResources = Resources::parse(
- "cpus:24;mem:4096;disk:4096;ports:[31000-32000]").get();
+ cout << "Added " << clientCount << " clients in "
+ << watch.elapsed() << endl;
- watch.start();
- {
- for (size_t i = 0; i < agentCount; i++) {
- SlaveID slaveId;
- slaveId.set_value("agent" + stringify(i));
+ Resources agentResources = Resources::parse(
+ "cpus:24;mem:4096;disk:4096;ports:[31000-32000]").get();
- agents.push_back(slaveId);
+ watch.start();
+ {
+ for (size_t i = 0; i < agentCount; i++) {
+ SlaveID slaveId;
+ slaveId.set_value("agent" + stringify(i));
- sorter.add(slaveId, agentResources);
- }
- }
- watch.stop();
+ agents.push_back(slaveId);
- cout << "Added " << agentCount << " agents in "
- << watch.elapsed() << endl;
+ sorter.add(slaveId, agentResources);
+ }
+ }
+ watch.stop();
- Resources allocated = Resources::parse("cpus:16;mem:2014;disk:1024").get();
+ cout << "Added " << agentCount << " agents in "
+ << watch.elapsed() << endl;
- // TODO(gyliu513): Parameterize the number of range for the fragment.
- Try<::mesos::Value::Ranges> ranges = fragment(createRange(31000, 32000), 100);
- ASSERT_SOME(ranges);
- ASSERT_EQ(100, ranges->range_size());
+ Resources allocated =
+ Resources::parse("cpus:16;mem:2014;disk:1024").get();
- allocated += createPorts(ranges.get());
+ // TODO(gyliu513): Parameterize the number of range for the fragment.
+ Try<::mesos::Value::Ranges> ranges =
+ fragment(createRange(31000, 32000), 100);
+ ASSERT_SOME(ranges);
+ ASSERT_EQ(100, ranges->range_size());
- watch.start();
- {
- // Allocate resources on all agents, round-robin through the clients.
- size_t clientIndex = 0;
- foreach (const SlaveID& slaveId, agents) {
- const string& client = clients[clientIndex++ % clients.size()];
- sorter.allocated(client, slaveId, allocated);
- }
- }
- watch.stop();
+ allocated += createPorts(ranges.get());
- cout << "Added allocations for " << agentCount << " agents in "
- << watch.elapsed() << endl;
+ watch.start();
+ {
+ // Allocate resources on all agents, round-robin through the clients.
+ size_t clientIndex = 0;
+ foreach (const SlaveID& slaveId, agents) {
+ const string& client = clients[clientIndex++ % clients.size()];
+ sorter.allocated(client, slaveId, allocated);
+ }
+ }
+ watch.stop();
- watch.start();
- {
- sorter.sort();
- }
- watch.stop();
+ cout << "Added allocations for " << agentCount << " agents in "
+ << watch.elapsed() << endl;
- cout << "Full sort of " << clientCount << " clients took "
- << watch.elapsed() << endl;
+ watch.start();
+ {
+ sorter.sort();
+ }
+ watch.stop();
- watch.start();
- {
- sorter.sort();
- }
- watch.stop();
+ cout << "Full sort of " << clientCount << " clients took "
+ << watch.elapsed() << endl;
- cout << "No-op sort of " << clientCount << " clients took "
- << watch.elapsed() << endl;
+ watch.start();
+ {
+ sorter.sort();
+ }
+ watch.stop();
+
+ cout << "No-op sort of " << clientCount << " clients took "
+ << watch.elapsed() << endl;
+
+ watch.start();
+ {
+ // Unallocate resources on all agents, round-robin through the clients.
+ size_t clientIndex = 0;
+ foreach (const SlaveID& slaveId, agents) {
+ const string& client = clients[clientIndex++ % clients.size()];
+ sorter.unallocated(client, slaveId, allocated);
+ }
+ }
+ watch.stop();
- watch.start();
- {
- // Unallocate resources on all agents, round-robin through the clients.
- size_t clientIndex = 0;
- foreach (const SlaveID& slaveId, agents) {
- const string& client = clients[clientIndex++ % clients.size()];
- sorter.unallocated(client, slaveId, allocated);
- }
- }
- watch.stop();
+ cout << "Removed allocations for " << agentCount << " agents in "
+ << watch.elapsed() << endl;
- cout << "Removed allocations for " << agentCount << " agents in "
- << watch.elapsed() << endl;
+ watch.start();
+ {
+ foreach (const SlaveID& slaveId, agents) {
+ sorter.remove(slaveId, agentResources);
+ }
+ }
+ watch.stop();
- watch.start();
- {
- foreach (const SlaveID& slaveId, agents) {
- sorter.remove(slaveId, agentResources);
- }
- }
- watch.stop();
+ cout << "Removed " << agentCount << " agents in "
+ << watch.elapsed() << endl;
- cout << "Removed " << agentCount << " agents in "
- << watch.elapsed() << endl;
+ watch.start();
+ {
+ foreach (const string& clientId, clients) {
+ sorter.remove(clientId);
+ }
+ }
+ watch.stop();
- watch.start();
- {
- foreach (const string& clientId, clients) {
- sorter.remove(clientId);
+ cout << "Removed " << clientCount << " clients in "
+ << watch.elapsed() << endl;
}
}
- watch.stop();
-
- cout << "Removed " << clientCount << " clients in "
- << watch.elapsed() << endl;
}
} // namespace tests {
[3/7] mesos git commit: Introduced a random sorter as an alternative
to the DRF sorter.
Posted by bm...@apache.org.
Introduced a random sorter as an alternative to the DRF sorter.
This sorter returns a weighted random shuffling of its clients
upon each `sort()` request.
This implementation is a copy of the `DRFSorter` with share
calculation logic (including the `dirty` bit) removed and an
adjusted `sort()` implementation. Work needs to be done to
reduce the amount of duplicated logic needed across sorter
implementations, but it is left unaddressed here.
Review: https://reviews.apache.org/r/67371/
Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/e0005550
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/e0005550
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/e0005550
Branch: refs/heads/1.4.x
Commit: e0005550968185ebef9c555b549545501cee2a10
Parents: c546bbf
Author: Benjamin Mahler <bm...@apache.org>
Authored: Sat Jun 2 21:27:10 2018 -0400
Committer: Benjamin Mahler <bm...@apache.org>
Committed: Sun Jul 1 15:03:39 2018 -0700
----------------------------------------------------------------------
src/CMakeLists.txt | 1 +
src/Makefile.am | 2 +
src/master/allocator/sorter/random/sorter.cpp | 570 +++++++++++++++++++++
src/master/allocator/sorter/random/sorter.hpp | 424 +++++++++++++++
4 files changed, 997 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/mesos/blob/e0005550/src/CMakeLists.txt
----------------------------------------------------------------------
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 98ccaf4..9ea4791 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -372,6 +372,7 @@ set(MASTER_SRC
master/allocator/mesos/metrics.cpp
master/allocator/sorter/drf/metrics.cpp
master/allocator/sorter/drf/sorter.cpp
+ master/allocator/sorter/random/sorter.cpp
master/contender/contender.cpp
master/contender/standalone.cpp
master/contender/zookeeper.cpp
http://git-wip-us.apache.org/repos/asf/mesos/blob/e0005550/src/Makefile.am
----------------------------------------------------------------------
diff --git a/src/Makefile.am b/src/Makefile.am
index e05e39b..8f7c4ac 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -956,6 +956,7 @@ libmesos_no_3rdparty_la_SOURCES += \
master/allocator/mesos/metrics.cpp \
master/allocator/sorter/drf/metrics.cpp \
master/allocator/sorter/drf/sorter.cpp \
+ master/allocator/sorter/random/sorter.cpp \
master/contender/contender.cpp \
master/contender/standalone.cpp \
master/contender/zookeeper.cpp \
@@ -1097,6 +1098,7 @@ libmesos_no_3rdparty_la_SOURCES += \
master/allocator/sorter/sorter.hpp \
master/allocator/sorter/drf/metrics.hpp \
master/allocator/sorter/drf/sorter.hpp \
+ master/allocator/sorter/random/sorter.hpp \
master/allocator/sorter/random/utils.hpp \
master/contender/standalone.hpp \
master/contender/zookeeper.hpp \
http://git-wip-us.apache.org/repos/asf/mesos/blob/e0005550/src/master/allocator/sorter/random/sorter.cpp
----------------------------------------------------------------------
diff --git a/src/master/allocator/sorter/random/sorter.cpp b/src/master/allocator/sorter/random/sorter.cpp
new file mode 100644
index 0000000..bcc14d6
--- /dev/null
+++ b/src/master/allocator/sorter/random/sorter.cpp
@@ -0,0 +1,570 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "master/allocator/sorter/random/sorter.hpp"
+#include "master/allocator/sorter/random/utils.hpp"
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include <mesos/mesos.hpp>
+#include <mesos/resources.hpp>
+#include <mesos/values.hpp>
+
+#include <process/pid.hpp>
+
+#include <stout/check.hpp>
+#include <stout/foreach.hpp>
+#include <stout/hashmap.hpp>
+#include <stout/option.hpp>
+#include <stout/strings.hpp>
+
+using std::set;
+using std::string;
+using std::vector;
+
+using process::UPID;
+
+namespace mesos {
+namespace internal {
+namespace master {
+namespace allocator {
+
+
+RandomSorter::RandomSorter()
+ : root(new Node("", Node::INTERNAL, nullptr)) {}
+
+
+RandomSorter::RandomSorter(
+ const UPID& allocator,
+ const string& metricsPrefix)
+ : root(new Node("", Node::INTERNAL, nullptr)) {}
+
+
+RandomSorter::~RandomSorter()
+{
+ delete root;
+}
+
+
+void RandomSorter::initialize(
+ const Option<set<string>>& _fairnessExcludeResourceNames) {}
+
+
+void RandomSorter::add(const string& clientPath)
+{
+ vector<string> pathElements = strings::tokenize(clientPath, "/");
+ CHECK(!pathElements.empty());
+
+ Node* current = root;
+ Node* lastCreatedNode = nullptr;
+
+ // Traverse the tree to add new nodes for each element of the path,
+ // if that node doesn't already exist (similar to `mkdir -p`).
+ foreach (const string& element, pathElements) {
+ Node* node = nullptr;
+
+ foreach (Node* child, current->children) {
+ if (child->name == element) {
+ node = child;
+ break;
+ }
+ }
+
+ if (node != nullptr) {
+ current = node;
+ continue;
+ }
+
+ // We didn't find `element`, so add a new child to `current`.
+ //
+ // If adding this child would result in turning `current` from a
+ // leaf node into an internal node, we need to create an
+ // additional child node: `current` must have been associated with
+ // a client and clients must always be associated with leaf nodes.
+ if (current->isLeaf()) {
+ Node* parent = CHECK_NOTNULL(current->parent);
+
+ parent->removeChild(current);
+
+ // Create a node under `parent`. This internal node will take
+ // the place of `current` in the tree.
+ Node* internal = new Node(current->name, Node::INTERNAL, parent);
+ parent->addChild(internal);
+ internal->allocation = current->allocation;
+
+ CHECK_EQ(current->path, internal->path);
+
+ // Update `current` to become a virtual leaf node and a child of
+ // `internal`.
+ current->name = ".";
+ current->parent = internal;
+ current->path = strings::join("/", parent->path, current->name);
+
+ internal->addChild(current);
+
+ CHECK_EQ(internal->path, current->clientPath());
+
+ current = internal;
+ }
+
+ // Now actually add a new child to `current`.
+ Node* newChild = new Node(element, Node::INTERNAL, current);
+ current->addChild(newChild);
+
+ current = newChild;
+ lastCreatedNode = newChild;
+ }
+
+ CHECK(current->kind == Node::INTERNAL);
+
+ // `current` is the node associated with the last element of the
+ // path. If we didn't add `current` to the tree above, create a leaf
+ // node now. For example, if the tree contains "a/b" and we add a
+ // new client "a", we want to create a new leaf node "a/." here.
+ if (current != lastCreatedNode) {
+ Node* newChild = new Node(".", Node::INACTIVE_LEAF, current);
+ current->addChild(newChild);
+ current = newChild;
+ } else {
+ // If we created `current` in the loop above, it was marked an
+ // `INTERNAL` node. It should actually be an inactive leaf node.
+ current->kind = Node::INACTIVE_LEAF;
+
+ // `current` has changed from an internal node to an inactive
+ // leaf, so remove and re-add it to its parent. This moves it to
+ // the end of the parent's list of children.
+ CHECK_NOTNULL(current->parent);
+
+ current->parent->removeChild(current);
+ current->parent->addChild(current);
+ }
+
+ // `current` is the newly created node associated with the last
+ // element of the path. `current` should be an inactive leaf node.
+ CHECK(current->children.empty());
+ CHECK(current->kind == Node::INACTIVE_LEAF);
+
+ // Add a new entry to the lookup table. The full path of the newly
+ // added client should not already exist in `clients`.
+ CHECK_EQ(clientPath, current->clientPath());
+ CHECK(!clients.contains(clientPath));
+
+ clients[clientPath] = current;
+}
+
+
+void RandomSorter::remove(const string& clientPath)
+{
+ Node* current = CHECK_NOTNULL(find(clientPath));
+
+ // Save a copy of the leaf node's allocated resources, because we
+ // destroy the leaf node below.
+ const hashmap<SlaveID, Resources> leafAllocation =
+ current->allocation.resources;
+
+ // Remove the lookup table entry for the client.
+ CHECK(clients.contains(clientPath));
+ clients.erase(clientPath);
+
+ // To remove a client from the tree, we have to do two things:
+ //
+ // (1) Update the tree structure to reflect the removal of the
+ // client. This means removing the client's leaf node, then
+ // walking back up the tree to remove any internal nodes that
+ // are now unnecessary.
+ //
+ // (2) Update allocations of ancestor nodes to reflect the removal
+ // of the client.
+ //
+ // We do both things at once: find the leaf node, remove it, and
+ // walk up the tree, updating ancestor allocations and removing
+ // ancestors when possible.
+ while (current != root) {
+ Node* parent = CHECK_NOTNULL(current->parent);
+
+ // Update `parent` to reflect the fact that the resources in the
+ // leaf node are no longer allocated to the subtree rooted at
+ // `parent`. We skip `root`, because we never update the
+ // allocation made to the root node.
+ if (parent != root) {
+ foreachpair (const SlaveID& slaveId,
+ const Resources& resources,
+ leafAllocation) {
+ parent->allocation.subtract(slaveId, resources);
+ }
+ }
+
+ if (current->children.empty()) {
+ parent->removeChild(current);
+ delete current;
+ } else if (current->children.size() == 1) {
+ // If `current` has only one child that was created to
+ // accommodate inserting `clientPath` (see `RandomSorter::add()`),
+ // we can remove the child node and turn `current` back into a
+ // leaf node.
+ Node* child = *(current->children.begin());
+
+ if (child->name == ".") {
+ CHECK(child->isLeaf());
+ CHECK(clients.contains(current->path));
+ CHECK_EQ(child, clients.at(current->path));
+
+ current->kind = child->kind;
+ current->removeChild(child);
+
+ // `current` has changed kind (from `INTERNAL` to a leaf,
+ // which might be active or inactive). Hence we might need to
+ // change its position in the `children` list.
+ if (current->kind == Node::INTERNAL) {
+ CHECK_NOTNULL(current->parent);
+
+ current->parent->removeChild(current);
+ current->parent->addChild(current);
+ }
+
+ clients[current->path] = current;
+
+ delete child;
+ }
+ }
+
+ current = parent;
+ }
+}
+
+
+void RandomSorter::activate(const string& clientPath)
+{
+ Node* client = CHECK_NOTNULL(find(clientPath));
+
+ if (client->kind == Node::INACTIVE_LEAF) {
+ client->kind = Node::ACTIVE_LEAF;
+
+ // `client` has been activated, so move it to the beginning of its
+ // parent's list of children.
+ CHECK_NOTNULL(client->parent);
+
+ client->parent->removeChild(client);
+ client->parent->addChild(client);
+ }
+}
+
+
+void RandomSorter::deactivate(const string& clientPath)
+{
+ Node* client = CHECK_NOTNULL(find(clientPath));
+
+ if (client->kind == Node::ACTIVE_LEAF) {
+ client->kind = Node::INACTIVE_LEAF;
+
+ // `client` has been deactivated, so move it to the end of its
+ // parent's list of children.
+ CHECK_NOTNULL(client->parent);
+
+ client->parent->removeChild(client);
+ client->parent->addChild(client);
+ }
+}
+
+
+void RandomSorter::updateWeight(const string& path, double weight)
+{
+ weights[path] = weight;
+}
+
+
+void RandomSorter::allocated(
+ const string& clientPath,
+ const SlaveID& slaveId,
+ const Resources& resources)
+{
+ Node* current = CHECK_NOTNULL(find(clientPath));
+
+ // NOTE: We don't currently update the `allocation` for the root
+ // node. This is debatable, but the current implementation doesn't
+ // require looking at the allocation of the root node.
+ while (current != root) {
+ current->allocation.add(slaveId, resources);
+ current = CHECK_NOTNULL(current->parent);
+ }
+}
+
+
+void RandomSorter::update(
+ const string& clientPath,
+ const SlaveID& slaveId,
+ const Resources& oldAllocation,
+ const Resources& newAllocation)
+{
+ // TODO(bmahler): Check invariants between old and new allocations.
+ // Namely, the roles and quantities of resources should be the same!
+
+ Node* current = CHECK_NOTNULL(find(clientPath));
+
+ // NOTE: We don't currently update the `allocation` for the root
+ // node. This is debatable, but the current implementation doesn't
+ // require looking at the allocation of the root node.
+ while (current != root) {
+ current->allocation.update(slaveId, oldAllocation, newAllocation);
+ current = CHECK_NOTNULL(current->parent);
+ }
+}
+
+
+void RandomSorter::unallocated(
+ const string& clientPath,
+ const SlaveID& slaveId,
+ const Resources& resources)
+{
+ Node* current = CHECK_NOTNULL(find(clientPath));
+
+ // NOTE: We don't currently update the `allocation` for the root
+ // node. This is debatable, but the current implementation doesn't
+ // require looking at the allocation of the root node.
+ while (current != root) {
+ current->allocation.subtract(slaveId, resources);
+ current = CHECK_NOTNULL(current->parent);
+ }
+}
+
+
+const hashmap<SlaveID, Resources>& RandomSorter::allocation(
+ const string& clientPath) const
+{
+ const Node* client = CHECK_NOTNULL(find(clientPath));
+ return client->allocation.resources;
+}
+
+
+const Resources& RandomSorter::allocationScalarQuantities(
+ const string& clientPath) const
+{
+ const Node* client = CHECK_NOTNULL(find(clientPath));
+ return client->allocation.scalarQuantities;
+}
+
+
+hashmap<string, Resources> RandomSorter::allocation(
+ const SlaveID& slaveId) const
+{
+ hashmap<string, Resources> result;
+
+ // We want to find the allocation that has been made to each client
+ // on a particular `slaveId`. Rather than traversing the tree
+ // looking for leaf nodes (clients), we can instead just iterate
+ // over the `clients` hashmap.
+ //
+ // TODO(jmlvanre): We can index the allocation by slaveId to make
+ // this faster. It is a tradeoff between speed vs. memory. For now
+ // we use existing data structures.
+ foreachvalue (const Node* client, clients) {
+ if (client->allocation.resources.contains(slaveId)) {
+ // It is safe to use `at()` here because we've just checked the
+ // existence of the key. This avoids unnecessary copies.
+ string path = client->clientPath();
+ CHECK(!result.contains(path));
+ result.emplace(path, client->allocation.resources.at(slaveId));
+ }
+ }
+
+ return result;
+}
+
+
+Resources RandomSorter::allocation(
+ const string& clientPath,
+ const SlaveID& slaveId) const
+{
+ const Node* client = CHECK_NOTNULL(find(clientPath));
+
+ if (client->allocation.resources.contains(slaveId)) {
+ return client->allocation.resources.at(slaveId);
+ }
+
+ return Resources();
+}
+
+
+const Resources& RandomSorter::totalScalarQuantities() const
+{
+ return total_.scalarQuantities;
+}
+
+
+void RandomSorter::add(const SlaveID& slaveId, const Resources& resources)
+{
+ if (!resources.empty()) {
+ // Add shared resources to the total quantities when the same
+ // resources don't already exist in the total.
+ const Resources newShared = resources.shared()
+ .filter([this, slaveId](const Resource& resource) {
+ return !total_.resources[slaveId].contains(resource);
+ });
+
+ total_.resources[slaveId] += resources;
+
+ const Resources scalarQuantities =
+ (resources.nonShared() + newShared).createStrippedScalarQuantity();
+
+ total_.scalarQuantities += scalarQuantities;
+
+ foreach (const Resource& resource, scalarQuantities) {
+ total_.totals[resource.name()] += resource.scalar();
+ }
+ }
+}
+
+
+void RandomSorter::remove(const SlaveID& slaveId, const Resources& resources)
+{
+ if (!resources.empty()) {
+ CHECK(total_.resources.contains(slaveId));
+ CHECK(total_.resources[slaveId].contains(resources))
+ << total_.resources[slaveId] << " does not contain " << resources;
+
+ total_.resources[slaveId] -= resources;
+
+ // Remove shared resources from the total quantities when there
+ // are no instances of same resources left in the total.
+ const Resources absentShared = resources.shared()
+ .filter([this, slaveId](const Resource& resource) {
+ return !total_.resources[slaveId].contains(resource);
+ });
+
+ const Resources scalarQuantities =
+ (resources.nonShared() + absentShared).createStrippedScalarQuantity();
+
+ foreach (const Resource& resource, scalarQuantities) {
+ total_.totals[resource.name()] -= resource.scalar();
+ }
+
+ CHECK(total_.scalarQuantities.contains(scalarQuantities));
+ total_.scalarQuantities -= scalarQuantities;
+
+ if (total_.resources[slaveId].empty()) {
+ total_.resources.erase(slaveId);
+ }
+ }
+}
+
+
+vector<string> RandomSorter::sort()
+{
+ std::function<void (Node*)> shuffleTree = [this, &shuffleTree](Node* node) {
+ // Inactive leaves are always stored at the end of the
+ // `children` vector; this means that we should only shuffle
+ // the prefix of the vector before the first inactive leaf.
+ auto inactiveBegin = std::find_if(
+ node->children.begin(),
+ node->children.end(),
+ [](Node* n) { return n->kind == Node::INACTIVE_LEAF; });
+
+ vector<double> weights(inactiveBegin - node->children.begin());
+
+ for (int i = 0; i < inactiveBegin - node->children.begin(); ++i) {
+ weights[i] = findWeight(node->children[i]);
+ }
+
+ weightedShuffle(node->children.begin(), inactiveBegin, weights, generator);
+
+ foreach (Node* child, node->children) {
+ if (child->kind == Node::INTERNAL) {
+ shuffleTree(child);
+ } else if (child->kind == Node::INACTIVE_LEAF) {
+ break;
+ }
+ }
+ };
+
+ shuffleTree(root);
+
+ // Return all active leaves in the tree via pre-order traversal.
+ // The children of each node are already shuffled, with
+ // inactive leaves stored after active leaves and internal nodes.
+ vector<string> result;
+ result.reserve(clients.size());
+
+ std::function<void (const Node*)> listClients =
+ [&listClients, &result](const Node* node) {
+ foreach (const Node* child, node->children) {
+ switch (child->kind) {
+ case Node::ACTIVE_LEAF:
+ result.push_back(child->clientPath());
+ break;
+
+ case Node::INACTIVE_LEAF:
+ // As soon as we see the first inactive leaf, we can stop
+ // iterating over the current node's list of children.
+ return;
+
+ case Node::INTERNAL:
+ listClients(child);
+ break;
+ }
+ }
+ };
+
+ listClients(root);
+
+ return result;
+}
+
+
+bool RandomSorter::contains(const string& clientPath) const
+{
+ return find(clientPath) != nullptr;
+}
+
+
+int RandomSorter::count() const
+{
+ return clients.size();
+}
+
+
+double RandomSorter::findWeight(const Node* node) const
+{
+ Option<double> weight = weights.get(node->path);
+
+ if (weight.isNone()) {
+ return 1.0;
+ }
+
+ return weight.get();
+}
+
+
+RandomSorter::Node* RandomSorter::find(const string& clientPath) const
+{
+ Option<Node*> client_ = clients.get(clientPath);
+
+ if (client_.isNone()) {
+ return nullptr;
+ }
+
+ Node* client = client_.get();
+
+ CHECK(client->isLeaf());
+
+ return client;
+}
+
+} // namespace allocator {
+} // namespace master {
+} // namespace internal {
+} // namespace mesos {
http://git-wip-us.apache.org/repos/asf/mesos/blob/e0005550/src/master/allocator/sorter/random/sorter.hpp
----------------------------------------------------------------------
diff --git a/src/master/allocator/sorter/random/sorter.hpp b/src/master/allocator/sorter/random/sorter.hpp
new file mode 100644
index 0000000..2c4f9b1
--- /dev/null
+++ b/src/master/allocator/sorter/random/sorter.hpp
@@ -0,0 +1,424 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef __MASTER_ALLOCATOR_SORTER_RANDOM_SORTER_HPP__
+#define __MASTER_ALLOCATOR_SORTER_RANDOM_SORTER_HPP__
+
+#include <algorithm>
+#include <random>
+#include <set>
+#include <string>
+#include <vector>
+
+#include <mesos/mesos.hpp>
+#include <mesos/resources.hpp>
+#include <mesos/values.hpp>
+
+#include <stout/check.hpp>
+#include <stout/hashmap.hpp>
+#include <stout/option.hpp>
+
+#include "master/allocator/sorter/sorter.hpp"
+
+
+namespace mesos {
+namespace internal {
+namespace master {
+namespace allocator {
+
+class RandomSorter : public Sorter
+{
+public:
+ RandomSorter();
+
+ explicit RandomSorter(
+ const process::UPID& allocator,
+ const std::string& metricsPrefix);
+
+ virtual ~RandomSorter();
+
+ virtual void initialize(
+ const Option<std::set<std::string>>& fairnessExcludeResourceNames);
+
+ virtual void add(const std::string& clientPath);
+
+ virtual void remove(const std::string& clientPath);
+
+ virtual void activate(const std::string& clientPath);
+
+ virtual void deactivate(const std::string& clientPath);
+
+ virtual void updateWeight(const std::string& path, double weight);
+
+ virtual void allocated(
+ const std::string& clientPath,
+ const SlaveID& slaveId,
+ const Resources& resources);
+
+ virtual void update(
+ const std::string& clientPath,
+ const SlaveID& slaveId,
+ const Resources& oldAllocation,
+ const Resources& newAllocation);
+
+ virtual void unallocated(
+ const std::string& clientPath,
+ const SlaveID& slaveId,
+ const Resources& resources);
+
+ virtual const hashmap<SlaveID, Resources>& allocation(
+ const std::string& clientPath) const;
+
+ virtual const Resources& allocationScalarQuantities(
+ const std::string& clientPath) const;
+
+ virtual hashmap<std::string, Resources> allocation(
+ const SlaveID& slaveId) const;
+
+ virtual Resources allocation(
+ const std::string& clientPath,
+ const SlaveID& slaveId) const;
+
+ virtual const Resources& totalScalarQuantities() const;
+
+ virtual void add(const SlaveID& slaveId, const Resources& resources);
+
+ virtual void remove(const SlaveID& slaveId, const Resources& resources);
+
+ // This will perform a weighted random shuffle on each call.
+ //
+ // TODO(bmahler): Unlike the DRF sorter, the allocator ideally would
+ // not call `sort()` for every agent, but rather loop through a single
+ // weighted shuffle before re-shuffling..
+ virtual std::vector<std::string> sort();
+
+ virtual bool contains(const std::string& clientPath) const;
+
+ virtual int count() const;
+
+private:
+ // A node in the sorter's tree.
+ struct Node;
+
+ // Returns the weight associated with the node. If no weight has
+ // been configured for the node's path, the default weight (1.0) is
+ // returned.
+ double findWeight(const Node* node) const;
+
+ // Returns the client associated with the given path. Returns
+ // nullptr if the path is not found or if the path identifies an
+ // internal node in the tree (not a client).
+ Node* find(const std::string& clientPath) const;
+
+ // Used for random number generation.
+ std::mt19937 generator;
+
+ // The root node in the sorter tree.
+ Node* root;
+
+ // To speed lookups, we keep a map from client paths to the leaf
+ // node associated with that client. There is an entry in this map
+ // for every leaf node in the client tree (except for the root when
+ // the tree is empty). Paths in this map do NOT contain the trailing
+ // "." label we use for leaf nodes.
+ hashmap<std::string, Node*> clients;
+
+ // Weights associated with role paths. Setting the weight for a path
+ // influences the sampling probability of all nodes in the subtree
+ // rooted at that path. This hashmap might include weights for paths
+ // that are not currently in the sorter tree.
+ hashmap<std::string, double> weights;
+
+ // Total resources.
+ struct Total
+ {
+ // We need to keep track of the resources (and not just scalar
+ // quantities) to account for multiple copies of the same shared
+ // resources. We need to ensure that we do not update the scalar
+ // quantities for shared resources when the change is only in the
+ // number of copies in the sorter.
+ hashmap<SlaveID, Resources> resources;
+
+ // NOTE: Scalars can be safely aggregated across slaves. We keep
+ // that to speed up the calculation of shares. See MESOS-2891 for
+ // the reasons why we want to do that.
+ //
+ // NOTE: We omit information about dynamic reservations and
+ // persistent volumes here to enable resources to be aggregated
+ // across slaves more effectively. See MESOS-4833 for more
+ // information.
+ //
+ // Sharedness info is also stripped out when resource identities
+ // are omitted because sharedness inherently refers to the
+ // identities of resources and not quantities.
+ Resources scalarQuantities;
+
+ // We also store a map version of `scalarQuantities`, mapping
+ // the `Resource::name` to aggregated scalar. This improves the
+ // performance of calculating shares. See MESOS-4694.
+ //
+ // TODO(bmahler): Ideally we do not store `scalarQuantities`
+ // redundantly here, investigate performance improvements to
+ // `Resources` to make this unnecessary.
+ hashmap<std::string, Value::Scalar> totals;
+ } total_;
+};
+
+
+// Represents a node in the sorter's tree. The structure of the tree
+// reflects the hierarchical relationships between the clients of the
+// sorter. Some (but not all) nodes correspond to sorter clients; some
+// nodes only exist to represent the structure of the sorter
+// tree. Clients are always associated with leaf nodes.
+//
+// For example, if there are two sorter clients "a/b" and "c/d", the
+// tree will contain five nodes: the root node, internal nodes for "a"
+// and "c", and leaf nodes for the clients "a/b" and "c/d".
+struct RandomSorter::Node
+{
+ // Indicates whether a node is an active leaf node, an inactive leaf
+ // node, or an internal node. Sorter clients always correspond to
+ // leaf nodes, and only leaf nodes can be activated or deactivated.
+ // The root node is always an "internal" node.
+ enum Kind
+ {
+ ACTIVE_LEAF,
+ INACTIVE_LEAF,
+ INTERNAL
+ };
+
+ Node(const std::string& _name, Kind _kind, Node* _parent)
+ : name(_name), kind(_kind), parent(_parent)
+ {
+ // Compute the node's path. Three cases:
+ //
+ // (1) If the root node, use the empty string
+ // (2) If a child of the root node, use the child's name
+ // (3) Otherwise, use the parent's name, "/", and the child's name.
+ if (parent == nullptr) {
+ path = "";
+ } else if (parent->parent == nullptr) {
+ path = name;
+ } else {
+ path = strings::join("/", parent->path, name);
+ }
+ }
+
+ ~Node()
+ {
+ foreach (Node* child, children) {
+ delete child;
+ }
+ }
+
+ // The label of the edge from this node's parent to the
+ // node. "Implicit" leaf nodes are always named ".".
+ //
+ // TODO(neilc): Consider naming implicit leaf nodes in a clearer
+ // way, e.g., by making `name` an Option?
+ std::string name;
+
+ // Complete path from root to node. This includes the trailing "."
+ // label for virtual leaf nodes.
+ std::string path;
+
+ Kind kind;
+
+ Node* parent;
+
+ // Pointers to the child nodes. `children` is only non-empty if
+ // `kind` is INTERNAL_NODE.
+ //
+ // All inactive leaves are stored at the end of the vector; that
+ // is, each `children` vector consists of zero or more active leaves
+ // and internal nodes, followed by zero or more inactive leaves. This
+ // means that code that only wants to iterate over active children
+ // can stop when the first inactive leaf is observed.
+ std::vector<Node*> children;
+
+ // If this node represents a sorter client, this returns the path of
+ // that client. Unlike the `path` field, this does NOT include the
+ // trailing "." label for virtual leaf nodes.
+ //
+ // For example, if the sorter contains two clients "a" and "a/b",
+ // the tree will contain four nodes: the root node, "a", "a/."
+ // (virtual leaf), and "a/b". The `clientPath()` of "a/." is "a",
+ // because that is the name of the client associated with that
+ // virtual leaf node.
+ std::string clientPath() const
+ {
+ if (name == ".") {
+ CHECK(kind == ACTIVE_LEAF || kind == INACTIVE_LEAF);
+ return CHECK_NOTNULL(parent)->path;
+ }
+
+ return path;
+ }
+
+ bool isLeaf() const
+ {
+ if (kind == ACTIVE_LEAF || kind == INACTIVE_LEAF) {
+ CHECK(children.empty());
+ return true;
+ }
+
+ return false;
+ }
+
+ void removeChild(const Node* child)
+ {
+ // Sanity check: ensure we are removing an extant node.
+ auto it = std::find(children.begin(), children.end(), child);
+ CHECK(it != children.end());
+
+ children.erase(it);
+ }
+
+ void addChild(Node* child)
+ {
+ // Sanity check: don't allow duplicates to be inserted.
+ auto it = std::find(children.begin(), children.end(), child);
+ CHECK(it == children.end());
+
+ // If we're inserting an inactive leaf, place it at the end of the
+ // `children` vector; otherwise, place it at the beginning. This
+ // maintains ordering invariant above.
+ if (child->kind == INACTIVE_LEAF) {
+ children.push_back(child);
+ } else {
+ children.insert(children.begin(), child);
+ }
+ }
+
+ // Allocation for a node.
+ struct Allocation
+ {
+ Allocation() {}
+
+ void add(const SlaveID& slaveId, const Resources& toAdd)
+ {
+ // Add shared resources to the allocated quantities when the same
+ // resources don't already exist in the allocation.
+ const Resources sharedToAdd = toAdd.shared()
+ .filter([this, slaveId](const Resource& resource) {
+ return !resources[slaveId].contains(resource);
+ });
+
+ const Resources quantitiesToAdd =
+ (toAdd.nonShared() + sharedToAdd).createStrippedScalarQuantity();
+
+ resources[slaveId] += toAdd;
+ scalarQuantities += quantitiesToAdd;
+
+ foreach (const Resource& resource, quantitiesToAdd) {
+ totals[resource.name()] += resource.scalar();
+ }
+ }
+
+ void subtract(const SlaveID& slaveId, const Resources& toRemove)
+ {
+ CHECK(resources.contains(slaveId));
+ CHECK(resources.at(slaveId).contains(toRemove))
+ << "Resources " << resources.at(slaveId) << " at agent " << slaveId
+ << " does not contain " << toRemove;
+
+ resources[slaveId] -= toRemove;
+
+ // Remove shared resources from the allocated quantities when there
+ // are no instances of same resources left in the allocation.
+ const Resources sharedToRemove = toRemove.shared()
+ .filter([this, slaveId](const Resource& resource) {
+ return !resources[slaveId].contains(resource);
+ });
+
+ const Resources quantitiesToRemove =
+ (toRemove.nonShared() + sharedToRemove).createStrippedScalarQuantity();
+
+ foreach (const Resource& resource, quantitiesToRemove) {
+ totals[resource.name()] -= resource.scalar();
+ }
+
+ CHECK(scalarQuantities.contains(quantitiesToRemove))
+ << scalarQuantities << " does not contain " << quantitiesToRemove;
+
+ scalarQuantities -= quantitiesToRemove;
+
+ if (resources[slaveId].empty()) {
+ resources.erase(slaveId);
+ }
+ }
+
+ void update(
+ const SlaveID& slaveId,
+ const Resources& oldAllocation,
+ const Resources& newAllocation)
+ {
+ const Resources oldAllocationQuantity =
+ oldAllocation.createStrippedScalarQuantity();
+ const Resources newAllocationQuantity =
+ newAllocation.createStrippedScalarQuantity();
+
+ CHECK(resources.contains(slaveId));
+ CHECK(resources[slaveId].contains(oldAllocation))
+ << "Resources " << resources[slaveId] << " at agent " << slaveId
+ << " does not contain " << oldAllocation;
+
+ CHECK(scalarQuantities.contains(oldAllocationQuantity))
+ << scalarQuantities << " does not contain " << oldAllocationQuantity;
+
+ resources[slaveId] -= oldAllocation;
+ resources[slaveId] += newAllocation;
+
+ scalarQuantities -= oldAllocationQuantity;
+ scalarQuantities += newAllocationQuantity;
+
+ foreach (const Resource& resource, oldAllocationQuantity) {
+ totals[resource.name()] -= resource.scalar();
+ }
+
+ foreach (const Resource& resource, newAllocationQuantity) {
+ totals[resource.name()] += resource.scalar();
+ }
+ }
+
+ // We maintain multiple copies of each shared resource allocated
+ // to a client, where the number of copies represents the number
+ // of times this shared resource has been allocated to (and has
+ // not been recovered from) a specific client.
+ hashmap<SlaveID, Resources> resources;
+
+ // Similarly, we aggregate scalars across slaves and omit information
+ // about dynamic reservations, persistent volumes and sharedness of
+ // the corresponding resource. See notes above.
+ Resources scalarQuantities;
+
+ // We also store a map version of `scalarQuantities`, mapping
+ // the `Resource::name` to aggregated scalar. This improves the
+ // performance of calculating shares. See MESOS-4694.
+ //
+ // TODO(bmahler): Ideally we do not store `scalarQuantities`
+ // redundantly here, investigate performance improvements to
+ // `Resources` to make this unnecessary.
+ hashmap<std::string, Value::Scalar> totals;
+ } allocation;
+};
+
+} // namespace allocator {
+} // namespace master {
+} // namespace internal {
+} // namespace mesos {
+
+#endif // __MASTER_ALLOCATOR_SORTER_RANDOM_SORTER_HPP__