mesos-reviews mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Neil Conway <neil.con...@gmail.com>
Subject Re: Review Request 57254: Added support for hierarchical roles to DRFSorter.
Date Fri, 21 Apr 2017 04:32:02 GMT

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/57254/
-----------------------------------------------------------

(Updated April 21, 2017, 4:32 a.m.)


Review request for mesos, Benjamin Bannier, Benjamin Mahler, and Michael Park.


Changes
-------

Tweak comment wording.


Repository: mesos


Description
-------

This commit replaces the sorter's flat list of clients with a tree; the
tree represents the hierarchical relationship between sorter clients.
Each node in the tree contains a vector of pointers to child nodes. The
tree might contain nodes that do not correspond directly to sorter
clients. For example, adding clients "a/b" and "c/d" results in the
following tree:

root
 -> a
   -> b
 -> c
   -> d

The `sort` member function still only returns one result for each active
client in the sorter. This is implemented by ensuring that each sorter
client is associated with a leaf node in the tree (i.e., internal nodes
are not returned by `sort`). Note that it is possible for a leaf node to
be transformed into an internal node by a subsequent insertion; to
handle this case, we "implicitly" create an extra child node, which
maintains the invariant that each client is associated with a leaf
node. For example, if the client "a/b/x" is added to the tree above, the
result is:

root
 -> a
   -> b
     -> .
     -> x
 -> c
   -> d

The "." leaf node holds the allocation that has been made to the "a/b"
client itself; the "a/b" node holds the sum of all the allocations that
have been made to the subtree rooted at "a/b", which also includes
"a/b/x". The "." node is called a "virtual leaf node".

This commit also introduces a new approach to sorting: rather than
keeping a `std::set` of sorter clients, we now keep a tree of
`std::vector`, which is sorted explicitly via `std::sort` when
necessary. The previous implementation tried to optimize the sorting
process by updating the sort order incrementally when a single sorter
client was updated; this commit removes that optimization, and instead
re-sorts the entire tree whenever a change is made that might alter the
sort order. Re-introducing a version of this optimization would make
sense in the future (MESOS-7390), but benchmarking suggests that this
commit results in a net improvement in sorter performance for
non-hierarchical clients, anyway. The performance improvement is likely
due to the introduction of a secondary hashmap that allows the leaf node
associated with a client name to be found efficiently; the previous
implementation required a linear scan of a `std::set`.


Diffs (updated)
-----

  src/master/allocator/sorter/drf/metrics.cpp 15aab32db5ca1a7a14080e9bbb7c65283be3ec20 
  src/master/allocator/sorter/drf/sorter.hpp 76329220e1115c1de7810fb69b943c78c078be59 
  src/master/allocator/sorter/drf/sorter.cpp ed54680cecb637931fc344fbcf8fd3b14cc24295 
  src/master/allocator/sorter/sorter.hpp b3029fcf7342406955760da53f1ae736769f308c 
  src/tests/hierarchical_allocator_tests.cpp 33e7b455f8664858eb4f03727b076a10c80cd6e0 
  src/tests/master_allocator_tests.cpp 119e318f8a01d50e8dae5c30cf5fa6a017c3c625 
  src/tests/sorter_tests.cpp 43bd85798aef0c89751b725ebf35308a5e9e997a 


Diff: https://reviews.apache.org/r/57254/diff/24/

Changes: https://reviews.apache.org/r/57254/diff/23-24/


Testing
-------


Thanks,

Neil Conway


Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message