-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/57254/
-----------------------------------------------------------
(Updated April 18, 2017, 4:58 a.m.)
Review request for mesos, Benjamin Bannier, Benjamin Mahler, and Michael Park.
Changes
-------
Address reviews.
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. 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 has 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".
This commit also introduces a new approach to sorting: rather than
keeping an `std::set` of sorter clients, we now keep a tree of
`std::vector`, which is sorted explicitly via `std::sort`. 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 the sort order is changed.
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 anyway. The sorter perf
improvement is likely due to the introduction of a secondary hashmap
that allows the leaf node associated with a tree path to be find
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/19/
Changes: https://reviews.apache.org/r/57254/diff/18-19/
Testing
-------
Thanks,
Neil Conway
