[mesos] branch master updated: Added a test of hierarchical sorting for the random sorter.

[bmahler]

This is an automated email from the ASF dual-hosted git repository.

bmahler pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/mesos.git


The following commit(s) were added to refs/heads/master by this push:
     new a03db7d  Added a test of hierarchical sorting for the random sorter.
a03db7d is described below

commit a03db7d684f343656aa229771f30c4990a2839c1
Author: Benjamin Mahler <bmah...@apache.org>
AuthorDate: Tue Apr 9 17:08:02 2019 -0400

    Added a test of hierarchical sorting for the random sorter.
    
    Review: https://reviews.apache.org/r/70438
---
 src/tests/sorter_tests.cpp | 76 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 76 insertions(+)

diff --git a/src/tests/sorter_tests.cpp b/src/tests/sorter_tests.cpp
index 9d52a80..91bfde0 100644
--- a/src/tests/sorter_tests.cpp
+++ b/src/tests/sorter_tests.cpp
@@ -16,6 +16,7 @@
 
 #include <iostream>
 #include <string>
+#include <utility>
 #include <vector>
 
 #include <gmock/gmock.h>
@@ -37,6 +38,7 @@ using mesos::internal::master::allocator::RandomSorter;
 
 using std::cout;
 using std::endl;
+using std::pair;
 using std::string;
 using std::vector;
 
@@ -94,6 +96,80 @@ TEST(WeightedShuffleTest, ProbabilityDistribution)
 }
 
 
+// Test the behavior of the random sorter by ensuring that the
+// probability distribution after a number of runs is within
+// a particular error bound.
+TEST(RandomSorterTest, HierarchicalProbabilityDistribution)
+{
+  RandomSorter sorter;
+
+  // We test the following role (weight) tree:
+  // |                 /\                   |
+  // |               /    \                 |
+  // |            /          \              |
+  // |      (1) a              c (2)        |
+  // |         / \            / \           |
+  // |    (1) .   b (2)  (1) d   e (2)      |
+
+  // Store the leaf position for each client, so that we
+  // can compute tables below.
+  hashmap<string, int> clients = {
+      {"a", 0},
+      {"a/b", 1},
+      {"c/d", 2},
+      {"c/e", 3}
+  };
+
+  vector<pair<string, double>> weights = {
+      {"a", 1.0}, {"a/b", 2.0},
+      {"c", 2.0}, {"c/d", 1.0}, {"c/e", 2.0}
+  };
+
+  foreachkey (const string& client, clients) {
+    sorter.add(client);
+    sorter.activate(client);
+  }
+
+  for (const pair<string, double> weight : weights) {
+    sorter.updateWeight(weight.first, weight.second);
+  }
+
+  // Count of how many times client i returned as the jth client
+  // in the sort result.
+  size_t totalRuns = 10000u;
+  size_t counts[4][4] = {};
+
+  for (size_t run = 0; run < totalRuns; ++run) {
+    vector<string> candidates = sorter.sort();
+    for (size_t i = 0; i < candidates.size(); ++i) {
+      ++counts[clients.at(candidates.at(i))][i];
+    }
+  }
+
+  // This table was generated by running a weighted shuffle algorithm
+  // for a large number of iterations.
+  double expectedProbabilities[4][4] = {
+    {0.11, 0.22, 0.22, 0.44},
+    {0.22, 0.11, 0.44, 0.22},
+    {0.22, 0.44, 0.11, 0.22},
+    {0.44, 0.22, 0.22, 0.11},
+  };
+
+  double actualProbabilities[4][4];
+
+  for (int i = 0; i < 4; ++i) {
+    for (int j = 0; j < 4; ++j) {
+      actualProbabilities[i][j] = counts[i][j] / (1.0 * totalRuns);
+
+      // Assert that the actual probabilities differ less than
+      // an absolute 5%.
+      EXPECT_NEAR(expectedProbabilities[i][j], actualProbabilities[i][j], 0.05)
+       << "position [" << i << "][" << j << "]";
+    }
+  }
+}
+
+
 template <typename T>
 class CommonSorterTest : public ::testing::Test {};