[mesos] 03/03: Avoided dirtying the DRF sorter when an allocation is performed.

[bm...@apache.org]

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

commit 86653356d763fee79e9467cf7b07bebb449e8aff
Author: Benjamin Mahler <bm...@apache.org>
AuthorDate: Fri Sep 21 12:26:19 2018 -0700

    Avoided dirtying the DRF sorter when an allocation is performed.
    
    This improves performance by ensuring that the DRF sorter can remain
    sorted throughout an allocation cycle. Without this change, we spend
    the majority of time re-sorting throughout an allocation cycle, when
    there are large numbers of clients (roles / frameworks).
    
    Before with --enable-optimize:
    
    *HierarchicalAllocator_BENCHMARK_Test.DeclineOffers/21
    Added 1000 frameworks in 28.69ms
    Added 10000 agents in 3.96secs
    round 0 allocate() took 3.18secs to make 10000 offers ...
    round 1 allocate() took 3.40secs to make 10000 offers ...
    round 2 allocate() took 3.31secs to make 10000 offers ...
    
    After with --enable-optimize:
    
    *HierarchicalAllocator_BENCHMARK_Test.DeclineOffers/21
    Added 1000 frameworks in 40.38ms
    Added 10000 agents in 1.61secs
    round 0 allocate() took 1.06secs to make 10000 offers ...
    round 1 allocate() took 1.06secs to make 10000 offers ...
    round 2 allocate() took 1.06secs to make 10000 offers ...
    
    Review: https://reviews.apache.org/r/68808
---
 src/master/allocator/sorter/drf/sorter.cpp | 47 +++++++++++++++++++++++++++---
 1 file changed, 43 insertions(+), 4 deletions(-)

diff --git a/src/master/allocator/sorter/drf/sorter.cpp b/src/master/allocator/sorter/drf/sorter.cpp
index b04d684..a648fac 100644
--- a/src/master/allocator/sorter/drf/sorter.cpp
+++ b/src/master/allocator/sorter/drf/sorter.cpp
@@ -16,6 +16,7 @@
 
 #include "master/allocator/sorter/drf/sorter.hpp"
 
+#include <iterator>
 #include <set>
 #include <string>
 #include <vector>
@@ -340,16 +341,51 @@ void DRFSorter::allocated(
 {
   Node* current = CHECK_NOTNULL(find(clientPath));
 
+  // Walk up the tree adjusting allocations. If the tree is
+  // sorted, we keep it sorted (see below).
+  //
   // NOTE: We don't currently update the `allocation` for the root
   // node. This is debatable, but the current implementation doesn't
   // require looking at the allocation of the root node.
   while (current != root) {
     current->allocation.add(slaveId, resources);
+
+    // Note that inactive leaves are not sorted, and are always
+    // stored in `children` after the active leaves and internal
+    // nodes. See the comment on `Node::children`.
+    if (!dirty && current->kind != Node::INACTIVE_LEAF) {
+      current->share = calculateShare(current);
+
+      vector<Node*>& children = current->parent->children;
+
+      // Locate the node position in the parent's children
+      // and shift it into its sorted position.
+      //
+      // TODO(bmahler): Consider storing the node's position
+      // in the parent's children to avoid scanning.
+      auto position = std::find(children.begin(), children.end(), current);
+      CHECK(position != children.end());
+
+      // Shift left until done (if needed).
+      while (position != children.begin() &&
+             DRFSorter::Node::compareDRF(current, *std::prev(position))) {
+        std::swap(*position, *std::prev(position));
+        --position;
+      }
+
+      // Or, shift right until done (if needed). Note that when
+      // shifting right, we need to stop once we reach the
+      // inactive leaves (see `Node::children`).
+      while (std::next(position) != children.end() &&
+             (*std::next(position))->kind != Node::INACTIVE_LEAF &&
+             DRFSorter::Node::compareDRF(*std::next(position), current)) {
+        std::swap(*position, *std::next(position));
+        ++position;
+      }
+    }
+
     current = CHECK_NOTNULL(current->parent);
   }
-
-  // TODO(neilc): Avoid dirtying the tree in some circumstances.
-  dirty = true;
 }
 
 
@@ -393,7 +429,10 @@ void DRFSorter::unallocated(
     current = CHECK_NOTNULL(current->parent);
   }
 
-  // TODO(neilc): Avoid dirtying the tree in some circumstances.
+  // TODO(bmahler): Similar to `allocated()`, avoid dirtying the
+  // tree here in favor of adjusting the node positions. This
+  // hasn't been critical to do since we don't allocate upon
+  // resource recovery in the allocator.
   dirty = true;
 }