----------------------------------------------------------- This is an automatically generated e-mail. To reply, visit: https://reviews.apache.org/r/57254/#review170798 -----------------------------------------------------------
src/master/allocator/sorter/drf/sorter.hpp Line 41 (original), 47 (patched) <https://reviews.apache.org/r/57254/#comment243673> Neil and I spoke about maybe calling this `Node` within `DRFSorter`. src/master/allocator/sorter/drf/sorter.cpp Lines 502-506 (patched) <https://reviews.apache.org/r/57254/#comment243678> I think the use of `std::set` is not useful, especially if we're going to be breaking its invariants like this. Specifically, modifying the `child->share` here does not get reflected according to `DRFComparator`. In the a dirty state, the `std::set` is sorted, but holds invalid shares anyway. When we actually "sort", we compute all of the shares and re-insert into `std::set`. It seems like keeping a `std::vector` which is modified and unsorted while dirty, and calling `std::sort()` when we actually want to sort it, reflects what we want to do here more clearly. __NOTE__: there are other very subtle issues with using `std::set` with a custom comparator. For example, a naive assumption of `std::set`'s invariant is that it holds unique elements in sorted order. With our custom comparator as defined, it allows multiple clients with the same name, as long as they have a different share, or allocation count. We would have to have something like this in order to enforce the unique-by-name constraint. ```cpp if (left.name == right.name) { return false; } ``` - Michael Park On March 31, 2017, 1:59 p.m., Neil Conway wrote: > > ----------------------------------------------------------- > This is an automatically generated e-mail. To reply, visit: > https://reviews.apache.org/r/57254/ > ----------------------------------------------------------- > > (Updated March 31, 2017, 1:59 p.m.) > > > Review request for mesos, Benjamin Bannier, Benjamin Mahler, and Michael Park. > > > Repository: mesos > > > Description > ------- > > This commit replaces the sorter's flat list of clients with a tree of > client names; this tree represents the hierarchical relationship between > sorter clients. Each node in the tree contains an (ordered) list 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". > > > Diffs > ----- > > 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 > e343dc37bd7136f0f6dd5dbc22a25cabe715038d > src/tests/master_allocator_tests.cpp > 9f3750215f2b72f6148d0c47cdde6a3f7dfb1b50 > src/tests/sorter_tests.cpp ec0636beb936d46a253d19322f2157abe95156b6 > > > Diff: https://reviews.apache.org/r/57254/diff/16/ > > > Testing > ------- > > > Thanks, > > Neil Conway > >
