Replaced the sorter's notion of "activation" with a three-valued enum.
Conceptually, a node in the sorter tree can either be an internal node or a leaf node. Furthermore, leaf nodes can either be active or inactive (internal nodes do not have a concept of "activation"). We previously represented this situation with a single boolean, `active`. The boolean was true for active leaves, and false for inactive leaves and internal nodes. Whether a node was an internal node was determined by checking the number of children it has. This commit replaces `active` with a three-valued enum named `kind`, which can take on the values `ACTIVE_LEAF`, `INACTIVE_LEAF`, or `INTERNAL`. This enforces the idea that internal nodes do not have a notion of "activation", and more explicitly distinguishes between leaf and internal nodes. Review: https://reviews.apache.org/r/59483/ Project: http://git-wip-us.apache.org/repos/asf/mesos/repo Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/dcb0b7ce Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/dcb0b7ce Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/dcb0b7ce Branch: refs/heads/master Commit: dcb0b7ce95309be64886c7ee36413c3665cfef9b Parents: 8139ec0 Author: Neil Conway <neil.con...@gmail.com> Authored: Tue May 23 10:36:16 2017 -0700 Committer: Neil Conway <neil.con...@gmail.com> Committed: Wed May 24 14:40:28 2017 -0700 ---------------------------------------------------------------------- src/master/allocator/sorter/drf/sorter.cpp | 40 +++++++++++++++++-------- src/master/allocator/sorter/drf/sorter.hpp | 22 +++++++++----- 2 files changed, 42 insertions(+), 20 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/mesos/blob/dcb0b7ce/src/master/allocator/sorter/drf/sorter.cpp ---------------------------------------------------------------------- diff --git a/src/master/allocator/sorter/drf/sorter.cpp b/src/master/allocator/sorter/drf/sorter.cpp index 26b77f5..74da5b1 100644 --- a/src/master/allocator/sorter/drf/sorter.cpp +++ b/src/master/allocator/sorter/drf/sorter.cpp @@ -45,13 +45,13 @@ namespace allocator { DRFSorter::DRFSorter() - : root(new Node("", nullptr)) {} + : root(new Node("", Node::INTERNAL, nullptr)) {} DRFSorter::DRFSorter( const UPID& allocator, const string& metricsPrefix) - : root(new Node("", nullptr)), + : root(new Node("", Node::INTERNAL, nullptr)), metrics(Metrics(allocator, *this, metricsPrefix)) {} @@ -112,7 +112,7 @@ void DRFSorter::add(const string& clientPath) // Create a node under `parent`. This internal node will take // the place of `current` in the tree. - Node* internal = new Node(current->name, parent); + Node* internal = new Node(current->name, Node::INTERNAL, parent); parent->addChild(internal); internal->allocation = current->allocation; @@ -131,28 +131,34 @@ void DRFSorter::add(const string& clientPath) } // Now actually add a new child to `current`. - Node* newChild = new Node(element, 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(".", current); + 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` is the newly created node associated with the last // element of the path. `current` should be an inactive node with no // children. CHECK(current->children.empty()); - CHECK(!current->active); + 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`. @@ -223,10 +229,12 @@ void DRFSorter::remove(const string& clientPath) if (child->name == ".") { CHECK(child->children.empty()); + CHECK(child->kind == Node::ACTIVE_LEAF || + child->kind == Node::INACTIVE_LEAF); CHECK(clients.contains(current->path)); CHECK_EQ(child, clients.at(current->path)); - current->active = child->active; + current->kind = child->kind; current->removeChild(child); clients[current->path] = current; @@ -250,14 +258,14 @@ void DRFSorter::remove(const string& clientPath) void DRFSorter::activate(const string& clientPath) { Node* client = CHECK_NOTNULL(find(clientPath)); - client->active = true; + client->kind = Node::ACTIVE_LEAF; } void DRFSorter::deactivate(const string& clientPath) { Node* client = CHECK_NOTNULL(find(clientPath)); - client->active = false; + client->kind = Node::INACTIVE_LEAF; } @@ -491,7 +499,7 @@ vector<string> DRFSorter::sort() std::function<void (const Node*)> listClients = [&listClients, &result](const Node* node) { - if (node->active) { + if (node->kind == Node::ACTIVE_LEAF) { result.push_back(node->clientPath()); } @@ -562,13 +570,19 @@ double DRFSorter::findWeight(const Node* node) const DRFSorter::Node* DRFSorter::find(const string& clientPath) const { - Option<Node*> client = clients.get(clientPath); + Option<Node*> client_ = clients.get(clientPath); - if (client.isNone()) { + if (client_.isNone()) { return nullptr; } - return client.get(); + Node* client = client_.get(); + + CHECK(client->kind == Node::ACTIVE_LEAF || + client->kind == Node::INACTIVE_LEAF); + CHECK(client->children.empty()); + + return client; } } // namespace allocator { http://git-wip-us.apache.org/repos/asf/mesos/blob/dcb0b7ce/src/master/allocator/sorter/drf/sorter.hpp ---------------------------------------------------------------------- diff --git a/src/master/allocator/sorter/drf/sorter.hpp b/src/master/allocator/sorter/drf/sorter.hpp index fee58d6..f76d2f7 100644 --- a/src/master/allocator/sorter/drf/sorter.hpp +++ b/src/master/allocator/sorter/drf/sorter.hpp @@ -195,8 +195,19 @@ private: // and "c", and leaf nodes for the clients "a/b" and "c/d". struct DRFSorter::Node { - Node(const std::string& _name, Node* _parent) - : name(_name), share(0), active(false), parent(_parent) + // 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), share(0), kind(_kind), parent(_parent) { // Compute the node's path. Three cases: // @@ -232,11 +243,7 @@ struct DRFSorter::Node double share; - // True if this node represents an active sorter client. False if - // this node represents an inactive sorter client or an internal node. - // - // TODO(neilc): Replace this with a three-valued enum? - bool active; + Kind kind; Node* parent; std::vector<Node*> children; @@ -253,6 +260,7 @@ struct DRFSorter::Node std::string clientPath() const { if (name == ".") { + CHECK(kind == ACTIVE_LEAF || kind == INACTIVE_LEAF); return CHECK_NOTNULL(parent)->path; }