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 <[email protected]> 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; }
