----------------------------------------------------------- This is an automatically generated e-mail. To reply, visit: https://reviews.apache.org/r/57254/#review172425 -----------------------------------------------------------
Overall, it's looking good! I think there are a few places where `Node*` should be marked `const Node*`. One of the things that I would like to see if the cleaning up of some the terminology being used. For example, I think the use of `name` is used for both `clientPath` as well as the last part of the "full path". `logicalPath` seems exactly `clientPath`, so it seems that we could consolidate that as well. I decided to drop the efforts to pull out `Node::createVirtualNode()` because it ended up needing separate cases anyway. (for creating one off of an internal node vs a leaf node.) src/master/allocator/sorter/drf/sorter.hpp Lines 57 (patched) <https://reviews.apache.org/r/57254/#comment245579> It seems that we should update these `name`s to be `clientPath`s? src/master/allocator/sorter/drf/sorter.hpp Lines 112 (patched) <https://reviews.apache.org/r/57254/#comment245555> Let's also remove this debugging utility. src/master/allocator/sorter/drf/sorter.hpp Line 44 (original), 198-201 (patched) <https://reviews.apache.org/r/57254/#comment245580> ``` Node(const std::string& _name, Node* _parent) : name(_name), share(0), active(false), parent(_parent) { ``` src/master/allocator/sorter/drf/sorter.hpp Lines 246 (patched) <https://reviews.apache.org/r/57254/#comment245554> Can we refer to this as `clientPath`? src/master/allocator/sorter/drf/sorter.hpp Lines 248-249 (patched) <https://reviews.apache.org/r/57254/#comment245572> `return CHECK_NOTNULL(parent)->path;` src/master/allocator/sorter/drf/sorter.hpp Line 263 (original), 380 (patched) <https://reviews.apache.org/r/57254/#comment245556> `s/DRFComparator/compare/`? We typically name the parameters `left` and `right` src/master/allocator/sorter/drf/sorter.cpp Lines 46-56 (original), 47-77 (patched) <https://reviews.apache.org/r/57254/#comment245543> We generally don't have functions like this. Let's get rid of them please. src/master/allocator/sorter/drf/sorter.cpp Line 74 (original), 108-116 (patched) <https://reviews.apache.org/r/57254/#comment245581> There are `nameElements` and `element` here rather than `elements/element` or `nameElements/nameElement`. I think we also used `components/component` in `quotaHandler`. Maybe it'd be better to stick with that naming scheme? src/master/allocator/sorter/drf/sorter.cpp Lines 117-125 (patched) <https://reviews.apache.org/r/57254/#comment245544> I think this would be cleaner to say: ```cpp auto iter = std::find_if( current->children.begin(), current->children.end(), [&](const Node* child) { return child->name == element; }); if (iter != current->children.end()) { current = *iter; continue; } /* ... */ ``` src/master/allocator/sorter/drf/sorter.cpp Lines 128 (patched) <https://reviews.apache.org/r/57254/#comment245573> I think the "// We didn't find `element`, so add a new child to `current`.` is better placed after the "leaf -> internal" if block, where we actually add the new child. src/master/allocator/sorter/drf/sorter.cpp Lines 75-77 (original), 143-172 (patched) <https://reviews.apache.org/r/57254/#comment245576> Kind of seems like it'd be simpler to just modify `current`. ``` parent->removeChild(current); // Create a node under `parent`. This internal node will become the new parent. Node* internal = new Node(current->name, parent); parent->addChild(internal); internal->allocation = current->allocation; CHECK_EQ(path, internal->path); // Update `current` to become the virtual leaf node. current->name = "."; current->parent = internal; internal->addChild(current); current->path = strings::join("/", parent->path, current->name); current = internal; ``` src/master/allocator/sorter/drf/sorter.cpp Line 155 (original), 328 (patched) <https://reviews.apache.org/r/57254/#comment245577> ``` for (Node* current = CHECK_NOTNULL(find(name)); current != root; current = CHECK_NOTNULL(current->parent)) ``` Other similar situations below. - Michael Park On April 19, 2017, 5:10 p.m., Neil Conway wrote: > > ----------------------------------------------------------- > This is an automatically generated e-mail. To reply, visit: > https://reviews.apache.org/r/57254/ > ----------------------------------------------------------- > > (Updated April 19, 2017, 5:10 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; 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 > ----- > > 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/20/ > > > Testing > ------- > > > Thanks, > > Neil Conway > >
