You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@mesos.apache.org by mz...@apache.org on 2019/04/25 21:03:17 UTC
[mesos] branch 1.8.x updated (ac6ab14 -> d2a3683)
This is an automated email from the ASF dual-hosted git repository.
mzhu pushed a change to branch 1.8.x
in repository https://gitbox.apache.org/repos/asf/mesos.git.
from ac6ab14 Ensured that task groups do not specify overlapping ranges or sets.
new 0f97e8a Simplified Sorter::add(client) implementations.
new 956f631 Added a random sorter helper to find active internal nodes.
new e6ca1a6 Fixed a bug in the random sorter.
new d2a3683 Avoided some recalculation in the random sorter.
The 4 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
src/master/allocator/sorter/drf/sorter.cpp | 131 +++++------
src/master/allocator/sorter/random/sorter.cpp | 323 +++++++++++++++-----------
src/master/allocator/sorter/random/sorter.hpp | 36 +++
3 files changed, 288 insertions(+), 202 deletions(-)
[mesos] 02/04: Added a random sorter helper to find active internal
nodes.
Posted by mz...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
mzhu pushed a commit to branch 1.8.x
in repository https://gitbox.apache.org/repos/asf/mesos.git
commit 956f631247e51a310b5180af5f032077f2059250
Author: Meng Zhu <mz...@mesosphere.io>
AuthorDate: Tue Apr 23 18:44:33 2019 -0700
Added a random sorter helper to find active internal nodes.
Active internal nodes are defined as internal nodes that have
at least one active leaf node.
Review: https://reviews.apache.org/r/70542
---
src/master/allocator/sorter/random/sorter.cpp | 39 +++++++++++++++++++++++++++
src/master/allocator/sorter/random/sorter.hpp | 5 ++++
2 files changed, 44 insertions(+)
diff --git a/src/master/allocator/sorter/random/sorter.cpp b/src/master/allocator/sorter/random/sorter.cpp
index 183a903..ad06b0b 100644
--- a/src/master/allocator/sorter/random/sorter.cpp
+++ b/src/master/allocator/sorter/random/sorter.cpp
@@ -545,6 +545,45 @@ double RandomSorter::getWeight(const Node* node) const
}
+hashset<RandomSorter::Node*> RandomSorter::activeInternalNodes() const
+{
+ // Using post-order traversal to find all the internal nodes
+ // that have at least one active leaf descendant and store
+ // them in the input `result` hashset.
+ //
+ // Returns true if the subtree at the input `node` contains any
+ // active leaf node.
+ std::function<bool(Node*, hashset<Node*>&)> searchActiveInternal =
+ [&searchActiveInternal](Node* node, hashset<Node*>& result) {
+ switch (node->kind) {
+ case Node::ACTIVE_LEAF: return true;
+
+ case Node::INACTIVE_LEAF: return false;
+
+ case Node::INTERNAL: {
+ bool active = false;
+ foreach (Node* child, node->children) {
+ if (searchActiveInternal(child, result)) {
+ active = true;
+ }
+ }
+
+ if (active) {
+ result.insert(node);
+ }
+ return active;
+ }
+ }
+ UNREACHABLE();
+ };
+
+ hashset<Node*> result;
+ searchActiveInternal(root, result);
+
+ return result;
+}
+
+
RandomSorter::Node* RandomSorter::find(const string& clientPath) const
{
Option<Node*> client_ = clients.get(clientPath);
diff --git a/src/master/allocator/sorter/random/sorter.hpp b/src/master/allocator/sorter/random/sorter.hpp
index 125ce84..0c2d645 100644
--- a/src/master/allocator/sorter/random/sorter.hpp
+++ b/src/master/allocator/sorter/random/sorter.hpp
@@ -29,6 +29,7 @@
#include <stout/check.hpp>
#include <stout/hashmap.hpp>
+#include <stout/hashset.hpp>
#include <stout/option.hpp>
#include "common/resource_quantities.hpp"
@@ -123,6 +124,10 @@ private:
// returned.
double getWeight(const Node* node) const;
+ // Get active internal nodes -- internal nodes that have at least
+ // one active leaf descendant.
+ hashset<Node*> activeInternalNodes() 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).
[mesos] 01/04: Simplified Sorter::add(client) implementations.
Posted by mz...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
mzhu pushed a commit to branch 1.8.x
in repository https://gitbox.apache.org/repos/asf/mesos.git
commit 0f97e8af2f8f3efe12634cc0a4805ddc93dd5be8
Author: Benjamin Mahler <bm...@apache.org>
AuthorDate: Wed Apr 17 17:34:35 2019 -0400
Simplified Sorter::add(client) implementations.
The existing logic is rather hard to understand and there is no
guiding explanation of the algorithm.
This re-writes the logic into an easier to understand approach,
along with a comment at the top that explains the two phase
algorithm.
Review: https://reviews.apache.org/r/70498
---
src/master/allocator/sorter/drf/sorter.cpp | 131 ++++++++++++--------------
src/master/allocator/sorter/random/sorter.cpp | 131 ++++++++++++--------------
2 files changed, 120 insertions(+), 142 deletions(-)
diff --git a/src/master/allocator/sorter/drf/sorter.cpp b/src/master/allocator/sorter/drf/sorter.cpp
index 554ac84..9367469 100644
--- a/src/master/allocator/sorter/drf/sorter.cpp
+++ b/src/master/allocator/sorter/drf/sorter.cpp
@@ -71,102 +71,91 @@ void DRFSorter::initialize(
void DRFSorter::add(const string& clientPath)
{
- vector<string> pathElements = strings::tokenize(clientPath, "/");
- CHECK(!pathElements.empty());
+ CHECK(!clients.contains(clientPath)) << clientPath;
- Node* current = root;
- Node* lastCreatedNode = nullptr;
+ // Adding a client is a two phase algorithm:
+ //
+ // root
+ // / | \ Three interesting cases:
+ // a e w Add a (i.e. phase 1(a))
+ // | / \ Add e/f, e/f/g, e/f/g/... (i.e. phase 1(b))
+ // b . z Add w/x, w/x/y, w/x/y/... (i.e. phase 1(c))
+ //
+ // Phase 1: Walk down the tree until:
+ // (a) we run out of tokens -> add "." node
+ // (b) or, we reach a leaf -> transform the leaf into internal + "."
+ // (c) or, we're at an internal node but can't find the next child
+ //
+ // Phase 2: For any remaining tokens, walk down creating children:
+ // (a) if last token of the client path -> create INACTIVE_LEAF
+ // (b) else, create INTERNAL and keep going
+
+ vector<string> tokens = strings::split(clientPath, "/");
+ auto token = tokens.begin();
// 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;
+ Node* current = root;
- foreach (Node* child, current->children) {
- if (child->name == element) {
- node = child;
- break;
- }
- }
+ // Phase 1:
+ while (true) {
+ // Case (a).
+ if (token == tokens.end()) {
+ Node* virt = new Node(".", Node::INACTIVE_LEAF, current);
- if (node != nullptr) {
- current = node;
- continue;
+ current->addChild(virt);
+ current = virt;
+
+ break;
}
- // 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.
+ // Case (b).
if (current->isLeaf()) {
- Node* parent = CHECK_NOTNULL(current->parent);
+ Node::Kind oldKind = current->kind;
- parent->removeChild(current);
+ current->parent->removeChild(current);
+ current->kind = Node::INTERNAL;
+ current->parent->addChild(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;
+ Node* virt = new Node(".", oldKind, current);
+ virt->allocation = current->allocation;
- CHECK_EQ(current->path, internal->path);
+ current->addChild(virt);
+ clients[virt->clientPath()] = virt;
- // 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);
+ break;
+ }
- internal->addChild(current);
+ Option<Node*> child = [&]() -> Option<Node*> {
+ foreach (Node* c, current->children) {
+ if (c->name == *token) return c;
+ }
+ return None();
+ }();
- CHECK_EQ(internal->path, current->clientPath());
+ // Case (c).
+ if (child.isNone()) break;
- current = internal;
- }
+ current = *child;
+ ++token;
+ }
- // Now actually add a new child to `current`.
- Node* newChild = new Node(element, Node::INTERNAL, current);
- current->addChild(newChild);
+ // Phase 2:
+ for (; token != tokens.end(); ++token) {
+ Node::Kind kind = (token == tokens.end() - 1)
+ ? Node::INACTIVE_LEAF : Node::INTERNAL;
- current = newChild;
- lastCreatedNode = newChild;
- }
+ Node* child = new Node(*token, kind, current);
- 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->addChild(child);
+ current = child;
}
- // `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));
+ CHECK(!clients.contains(clientPath)) << clientPath;
clients[clientPath] = current;
diff --git a/src/master/allocator/sorter/random/sorter.cpp b/src/master/allocator/sorter/random/sorter.cpp
index bbe130d..183a903 100644
--- a/src/master/allocator/sorter/random/sorter.cpp
+++ b/src/master/allocator/sorter/random/sorter.cpp
@@ -67,102 +67,91 @@ void RandomSorter::initialize(
void RandomSorter::add(const string& clientPath)
{
- vector<string> pathElements = strings::tokenize(clientPath, "/");
- CHECK(!pathElements.empty());
+ CHECK(!clients.contains(clientPath)) << clientPath;
- Node* current = root;
- Node* lastCreatedNode = nullptr;
+ // Adding a client is a two phase algorithm:
+ //
+ // root
+ // / | \ Three interesting cases:
+ // a e w Add a (i.e. phase 1(a))
+ // | / \ Add e/f, e/f/g, e/f/g/... (i.e. phase 1(b))
+ // b . z Add w/x, w/x/y, w/x/y/... (i.e. phase 1(c))
+ //
+ // Phase 1: Walk down the tree until:
+ // (a) we run out of tokens -> add "." node
+ // (b) or, we reach a leaf -> transform the leaf into internal + "."
+ // (c) or, we're at an internal node but can't find the next child
+ //
+ // Phase 2: For any remaining tokens, walk down creating children:
+ // (a) if last token of the client path -> create INACTIVE_LEAF
+ // (b) else, create INTERNAL and keep going
+
+ vector<string> tokens = strings::split(clientPath, "/");
+ auto token = tokens.begin();
// 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;
+ Node* current = root;
- foreach (Node* child, current->children) {
- if (child->name == element) {
- node = child;
- break;
- }
- }
+ // Phase 1:
+ while (true) {
+ // Case (a).
+ if (token == tokens.end()) {
+ Node* virt = new Node(".", Node::INACTIVE_LEAF, current);
+
+ current->addChild(virt);
+ current = virt;
- if (node != nullptr) {
- current = node;
- continue;
+ break;
}
- // 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.
+ // Case (b).
if (current->isLeaf()) {
- Node* parent = CHECK_NOTNULL(current->parent);
+ Node::Kind oldKind = current->kind;
- parent->removeChild(current);
+ current->parent->removeChild(current);
+ current->kind = Node::INTERNAL;
+ current->parent->addChild(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;
+ Node* virt = new Node(".", oldKind, current);
+ virt->allocation = current->allocation;
- CHECK_EQ(current->path, internal->path);
+ current->addChild(virt);
+ clients[virt->clientPath()] = virt;
- // 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);
+ break;
+ }
- internal->addChild(current);
+ Option<Node*> child = [&]() -> Option<Node*> {
+ foreach (Node* c, current->children) {
+ if (c->name == *token) return c;
+ }
+ return None();
+ }();
- CHECK_EQ(internal->path, current->clientPath());
+ // Case (c).
+ if (child.isNone()) break;
- current = internal;
- }
+ current = *child;
+ ++token;
+ }
- // Now actually add a new child to `current`.
- Node* newChild = new Node(element, Node::INTERNAL, current);
- current->addChild(newChild);
+ // Phase 2:
+ for (; token != tokens.end(); ++token) {
+ Node::Kind kind = (token == tokens.end() - 1)
+ ? Node::INACTIVE_LEAF : Node::INTERNAL;
- current = newChild;
- lastCreatedNode = newChild;
- }
+ Node* child = new Node(*token, kind, current);
- 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->addChild(child);
+ current = child;
}
- // `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));
+ CHECK(!clients.contains(clientPath)) << clientPath;
clients[clientPath] = current;
}
[mesos] 03/04: Fixed a bug in the random sorter.
Posted by mz...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
mzhu pushed a commit to branch 1.8.x
in repository https://gitbox.apache.org/repos/asf/mesos.git
commit e6ca1a6942e999a331cf0a3fe33d0f045272050a
Author: Meng Zhu <mz...@mesosphere.io>
AuthorDate: Wed Apr 24 10:51:06 2019 -0700
Fixed a bug in the random sorter.
Currently, in the presence of hierarchical roles, the
random sorter shuffles roles level by level and then pick
the active leave nodes using DFS. This could generate
non-uniform random result since active leaves in a subtree
are always picked together.
This patch fixes the issue by first calculating the relative
weights of each active leaf node and shuffle all of them
only once.
Review: https://reviews.apache.org/r/70429
---
src/master/allocator/sorter/random/sorter.cpp | 131 ++++++++++++++------------
src/master/allocator/sorter/random/sorter.hpp | 29 ++++++
2 files changed, 102 insertions(+), 58 deletions(-)
diff --git a/src/master/allocator/sorter/random/sorter.cpp b/src/master/allocator/sorter/random/sorter.cpp
index ad06b0b..8cf01e3 100644
--- a/src/master/allocator/sorter/random/sorter.cpp
+++ b/src/master/allocator/sorter/random/sorter.cpp
@@ -33,6 +33,7 @@
#include <stout/option.hpp>
#include <stout/strings.hpp>
+using std::pair;
using std::set;
using std::string;
using std::vector;
@@ -460,66 +461,16 @@ void RandomSorter::remove(const SlaveID& slaveId, const Resources& resources)
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] = getWeight(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;
-
- // TODO(bmahler): This over-reserves where there are inactive
- // clients, only reserve the number of active clients.
- 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;
- }
- }
- };
+ pair<vector<string>, vector<double>> clientsAndWeights =
+ SortInfo(this).getClientsAndWeights();
- listClients(root);
+ weightedShuffle(
+ clientsAndWeights.first.begin(),
+ clientsAndWeights.first.end(),
+ clientsAndWeights.second,
+ generator);
- return result;
+ return std::move(clientsAndWeights.first);
}
@@ -599,6 +550,70 @@ RandomSorter::Node* RandomSorter::find(const string& clientPath) const
return client;
}
+
+pair<vector<string>, vector<double>>
+RandomSorter::SortInfo::getClientsAndWeights()
+{
+ updateRelativeWeights();
+
+ return std::make_pair(clients, weights);
+}
+
+
+void RandomSorter::SortInfo::updateRelativeWeights()
+{
+ hashset<Node*> activeInternalNodes = sorter->activeInternalNodes();
+
+ auto isActive = [&activeInternalNodes](Node* node) {
+ return node->kind == Node::ACTIVE_LEAF ||
+ activeInternalNodes.contains(node);
+ };
+
+ clients.reserve(sorter->clients.size());
+ weights.reserve(sorter->clients.size());
+
+ // We use the following formula to compute the relative weights (Rw):
+ //
+ // weight(node)
+ // Rw(node) = Rw(parent) * -------------------------------------------
+ // weight(node) + SUM(weight(active siblings))
+ //
+ // Using pre-order traversal to calculate node's relative weight.
+ // Active leaves and their relative weights are stored in `clients`
+ // and `weights`.
+ std::function<void(Node*, double, double)> calculateRelativeWeights =
+ [&](Node* node, double siblingWeights, double parentRelativeWeight) {
+ // We only calculate relative weights for active nodes.
+ if (!isActive(node)) {
+ return;
+ }
+ double relativeWeight = parentRelativeWeight * sorter->getWeight(node) /
+ (sorter->getWeight(node) + siblingWeights);
+
+ // Store the result for active leaves.
+ if (node->kind == Node::ACTIVE_LEAF) {
+ clients.push_back(node->clientPath());
+ weights.push_back(relativeWeight);
+ }
+
+ // Calculate active children's total weights.
+ double totalWeights_ = 0.0;
+
+ foreach (Node* child, node->children) {
+ totalWeights_ += isActive(child) ? sorter->getWeight(child) : 0.0;
+ }
+
+ foreach (Node* child, node->children) {
+ if (isActive(child)) {
+ calculateRelativeWeights(
+ child, totalWeights_ - sorter->getWeight(child), relativeWeight);
+ }
+ }
+ };
+
+ calculateRelativeWeights(sorter->root, 0.0, 1.0);
+}
+
} // namespace allocator {
} // namespace master {
} // namespace internal {
diff --git a/src/master/allocator/sorter/random/sorter.hpp b/src/master/allocator/sorter/random/sorter.hpp
index 0c2d645..15bc75c 100644
--- a/src/master/allocator/sorter/random/sorter.hpp
+++ b/src/master/allocator/sorter/random/sorter.hpp
@@ -133,6 +133,35 @@ private:
// internal node in the tree (not a client).
Node* find(const std::string& clientPath) const;
+ // Sorting related info are kept in memory to avoid recalculations.
+ //
+ // TODO(mzhu): Keep this in the memory to avoid recalculations.
+ struct SortInfo
+ {
+ public:
+ SortInfo(const RandomSorter* sorter_) : sorter(sorter_) {}
+
+ // Returns a pair of vectors which are active clients and
+ // their corresponding relative weights.
+ std::pair<std::vector<std::string>, std::vector<double>>
+ getClientsAndWeights();
+
+ private:
+ void updateRelativeWeights();
+
+ std::vector<std::string> clients;
+
+ // Relative weights of the `clients` above.
+ // Relative weight denotes the weight of an active leaf node relative to
+ // other active leaf nodes given their configured weights. The number here
+ // stands for the probability of a given node being shuffled to the 1st in
+ // all the nodes in a random shuffle. Intuitively, the sum of all relative
+ // weights should be one.
+ std::vector<double> weights;
+
+ const RandomSorter* sorter;
+ };
+
// Used for random number generation.
std::mt19937 generator;
[mesos] 04/04: Avoided some recalculation in the random sorter.
Posted by mz...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
mzhu pushed a commit to branch 1.8.x
in repository https://gitbox.apache.org/repos/asf/mesos.git
commit d2a368363c6738d83c721e5c7eb5e1f2ebc9cb07
Author: Meng Zhu <mz...@mesosphere.io>
AuthorDate: Wed Apr 24 11:32:38 2019 -0700
Avoided some recalculation in the random sorter.
This patch keeps the sorting related information in the memory
and accompanies a dirty bit with it. This helps to avoid
unnecessary recalculation of this info in `sort()`.
Review: https://reviews.apache.org/r/70430
---
src/master/allocator/sorter/random/sorter.cpp | 22 ++++++++++++++++++++--
src/master/allocator/sorter/random/sorter.hpp | 10 ++++++----
2 files changed, 26 insertions(+), 6 deletions(-)
diff --git a/src/master/allocator/sorter/random/sorter.cpp b/src/master/allocator/sorter/random/sorter.cpp
index 8cf01e3..f4132bb 100644
--- a/src/master/allocator/sorter/random/sorter.cpp
+++ b/src/master/allocator/sorter/random/sorter.cpp
@@ -47,13 +47,13 @@ namespace allocator {
RandomSorter::RandomSorter()
- : root(new Node("", Node::INTERNAL, nullptr)) {}
+ : sortInfo(this), root(new Node("", Node::INTERNAL, nullptr)) {}
RandomSorter::RandomSorter(
const UPID& allocator,
const string& metricsPrefix)
- : root(new Node("", Node::INTERNAL, nullptr)) {}
+ : sortInfo(this), root(new Node("", Node::INTERNAL, nullptr)) {}
RandomSorter::~RandomSorter()
@@ -70,6 +70,8 @@ void RandomSorter::add(const string& clientPath)
{
CHECK(!clients.contains(clientPath)) << clientPath;
+ sortInfo.dirty = true;
+
// Adding a client is a two phase algorithm:
//
// root
@@ -160,6 +162,8 @@ void RandomSorter::add(const string& clientPath)
void RandomSorter::remove(const string& clientPath)
{
+ sortInfo.dirty = true;
+
Node* current = CHECK_NOTNULL(find(clientPath));
// Save a copy of the leaf node's allocated resources, because we
@@ -237,6 +241,8 @@ void RandomSorter::remove(const string& clientPath)
void RandomSorter::activate(const string& clientPath)
{
+ sortInfo.dirty = true;
+
Node* client = CHECK_NOTNULL(find(clientPath));
if (client->kind == Node::INACTIVE_LEAF) {
@@ -254,6 +260,8 @@ void RandomSorter::activate(const string& clientPath)
void RandomSorter::deactivate(const string& clientPath)
{
+ sortInfo.dirty = true;
+
Node* client = CHECK_NOTNULL(find(clientPath));
if (client->kind == Node::ACTIVE_LEAF) {
@@ -271,6 +279,8 @@ void RandomSorter::deactivate(const string& clientPath)
void RandomSorter::updateWeight(const string& path, double weight)
{
+ sortInfo.dirty = true;
+
weights[path] = weight;
// Update the weight of the corresponding internal node,
@@ -562,6 +572,10 @@ RandomSorter::SortInfo::getClientsAndWeights()
void RandomSorter::SortInfo::updateRelativeWeights()
{
+ if (!dirty) {
+ return;
+ }
+
hashset<Node*> activeInternalNodes = sorter->activeInternalNodes();
auto isActive = [&activeInternalNodes](Node* node) {
@@ -569,6 +583,8 @@ void RandomSorter::SortInfo::updateRelativeWeights()
activeInternalNodes.contains(node);
};
+ // Note, though we reserve here, the size of the vector will always
+ // grow (as we add more roles).
clients.reserve(sorter->clients.size());
weights.reserve(sorter->clients.size());
@@ -612,6 +628,8 @@ void RandomSorter::SortInfo::updateRelativeWeights()
};
calculateRelativeWeights(sorter->root, 0.0, 1.0);
+
+ dirty = false;
}
} // namespace allocator {
diff --git a/src/master/allocator/sorter/random/sorter.hpp b/src/master/allocator/sorter/random/sorter.hpp
index 15bc75c..55e22d7 100644
--- a/src/master/allocator/sorter/random/sorter.hpp
+++ b/src/master/allocator/sorter/random/sorter.hpp
@@ -134,18 +134,20 @@ private:
Node* find(const std::string& clientPath) const;
// Sorting related info are kept in memory to avoid recalculations.
- //
- // TODO(mzhu): Keep this in the memory to avoid recalculations.
struct SortInfo
{
public:
- SortInfo(const RandomSorter* sorter_) : sorter(sorter_) {}
+ SortInfo(const RandomSorter* sorter_) : dirty(true), sorter(sorter_) {}
// Returns a pair of vectors which are active clients and
// their corresponding relative weights.
std::pair<std::vector<std::string>, std::vector<double>>
getClientsAndWeights();
+ // A dirty bit indicates whether the info is up-to-date
+ // and requires recalculation.
+ bool dirty;
+
private:
void updateRelativeWeights();
@@ -160,7 +162,7 @@ private:
std::vector<double> weights;
const RandomSorter* sorter;
- };
+ } sortInfo;
// Used for random number generation.
std::mt19937 generator;