This is an automated email from the ASF dual-hosted git repository. bmahler pushed a commit to branch 1.7.x in repository https://gitbox.apache.org/repos/asf/mesos.git
commit 6ef0df93fb20a9a46f7885aa89a8062bc00d5f29 Author: Benjamin Mahler <[email protected]> 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; }
