[7/7] mesos git commit: Optimized sorter performance with many inactive clients.

[ne...@apache.org]

Optimized sorter performance with many inactive clients.

Unlike in Mesos <= 1.2, the sorter now stores inactive clients in the
same data structure used to store active clients. This resulted in a
significant performance regression when the vast majority of sorter
clients are inactive: when sorting clients and producing the sorted
order, we iterate over ALL clients (active and inactive), which could be
much slower than the old active-only implementation.

This commit revises the sorter to ensure that inactive leaf nodes are
always stored at the end of their parent's list of child nodes. This
allows the sorter to stop early (at the first inactive leaf) when
iterating over a node's children, if we're only interested in applying
an operation to each active leaf or internal node. This change fixes the
observed performance regression relative to Mesos 1.2.0.

Review: https://reviews.apache.org/r/59355/


Project: http://git-wip-us.apache.org/repos/asf/mesos/repo
Commit: http://git-wip-us.apache.org/repos/asf/mesos/commit/a637df6d
Tree: http://git-wip-us.apache.org/repos/asf/mesos/tree/a637df6d
Diff: http://git-wip-us.apache.org/repos/asf/mesos/diff/a637df6d

Branch: refs/heads/master
Commit: a637df6d3807ab13ce6f426a03cb4396ffa453e6
Parents: fd58fa1
Author: Neil Conway <ne...@gmail.com>
Authored: Tue May 23 10:36:18 2017 -0700
Committer: Neil Conway <ne...@gmail.com>
Committed: Wed May 24 14:40:39 2017 -0700

----------------------------------------------------------------------
 src/master/allocator/sorter/drf/sorter.cpp | 98 +++++++++++++++++++++----
 src/master/allocator/sorter/drf/sorter.hpp | 27 ++++++-
 2 files changed, 110 insertions(+), 15 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/mesos/blob/a637df6d/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 1d8959d..ecc5586 100644
--- a/src/master/allocator/sorter/drf/sorter.cpp
+++ b/src/master/allocator/sorter/drf/sorter.cpp
@@ -147,6 +147,14 @@ void DRFSorter::add(const string& clientPath)
     // 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
@@ -229,6 +237,16 @@ void DRFSorter::remove(const string& clientPath)
         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;
@@ -250,14 +268,41 @@ void DRFSorter::remove(const string& clientPath)
 void DRFSorter::activate(const string& clientPath)
 {
   Node* client = CHECK_NOTNULL(find(clientPath));
-  client->kind = Node::ACTIVE_LEAF;
+
+  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. We mark the tree dirty, so that the
+    // client's share is updated correctly and it is sorted properly.
+    //
+    // TODO(neilc): We could instead calculate share here and insert
+    // the client into the appropriate place here, which would avoid
+    // dirtying the whole tree.
+    CHECK_NOTNULL(client->parent);
+
+    client->parent->removeChild(client);
+    client->parent->addChild(client);
+
+    dirty = true;
+  }
 }
 
 
 void DRFSorter::deactivate(const string& clientPath)
 {
   Node* client = CHECK_NOTNULL(find(clientPath));
-  client->kind = Node::INACTIVE_LEAF;
+
+  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);
+  }
 }
 
 
@@ -467,16 +512,33 @@ vector<string> DRFSorter::sort()
 {
   if (dirty) {
     std::function<void (Node*)> sortTree = [this, &sortTree](Node* node) {
-      foreach (Node* child, node->children) {
+      // Inactive leaves are always stored at the end of the
+      // `children` vector; this means that as soon as we see an
+      // inactive leaf, we can stop calculating shares, and we only
+      // need to sort the prefix of the vector before that point.
+      auto childIter = node->children.begin();
+
+      while (childIter != node->children.end()) {
+        Node* child = *childIter;
+
+        if (child->kind == Node::INACTIVE_LEAF) {
+          break;
+        }
+
         child->share = calculateShare(child);
+        ++childIter;
       }
 
       std::sort(node->children.begin(),
-                node->children.end(),
+                childIter,
                 DRFSorter::Node::compareDRF);
 
       foreach (Node* child, node->children) {
-        sortTree(child);
+        if (child->kind == Node::INTERNAL) {
+          sortTree(child);
+        } else if (child->kind == Node::INACTIVE_LEAF) {
+          break;
+        }
       }
     };
 
@@ -485,18 +547,28 @@ vector<string> DRFSorter::sort()
     dirty = false;
   }
 
-  // Return the leaf nodes in the tree. The children of each node are
-  // already sorted in DRF order.
+  // Return all active leaves in the tree via pre-order traversal.
+  // The children of each node are already sorted in DRF order, with
+  // inactive leaves sorted after active leaves and internal nodes.
   vector<string> result;
 
   std::function<void (const Node*)> listClients =
       [&listClients, &result](const Node* node) {
-    if (node->kind == Node::ACTIVE_LEAF) {
-      result.push_back(node->clientPath());
-    }
-
-    foreach (Node* child, node->children) {
-      listClients(child);
+    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;
+      }
     }
   };
 

http://git-wip-us.apache.org/repos/asf/mesos/blob/a637df6d/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 67700d5..77e52de 100644
--- a/src/master/allocator/sorter/drf/sorter.hpp
+++ b/src/master/allocator/sorter/drf/sorter.hpp
@@ -125,7 +125,7 @@ private:
   // Resources (by name) that will be excluded from fair sharing.
   Option<std::set<std::string>> fairnessExcludeResourceNames;
 
-  // If true, sort() will recalculate all shares.
+  // If true, sort() will recalculate all shares and resort the tree.
   bool dirty = false;
 
   // The root node in the sorter tree.
@@ -246,6 +246,19 @@ struct DRFSorter::Node
   Kind kind;
 
   Node* parent;
+
+  // Pointers to the child nodes. `children` is only non-empty if
+  // `kind` is INTERNAL_NODE. Two ordering invariants are maintained
+  // on the `children` vector:
+  //
+  // (1) 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.
+  //
+  // (2) If the tree is not dirty, the active leaves and internal
+  // nodes are kept sorted by DRF share.
   std::vector<Node*> children;
 
   // If this node represents a sorter client, this returns the path of
@@ -279,6 +292,7 @@ struct DRFSorter::Node
 
   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());
 
@@ -287,10 +301,19 @@ struct DRFSorter::Node
 
   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());
 
-    children.push_back(child);
+    // 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 (1) above. It is up to the caller
+    // to maintain invariant (2) -- e.g., by marking the tree dirty.
+    if (child->kind == INACTIVE_LEAF) {
+      children.push_back(child);
+    } else {
+      children.insert(children.begin(), child);
+    }
   }
 
   // Allocation for a node.