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 03:27:11 GMT


> On April 20, 2017, 9:35 a.m., Michael Park wrote:
> > src/master/allocator/sorter/drf/sorter.hpp
> > Line 263 (original), 380 (patched)
> > <https://reviews.apache.org/r/57254/diff/19/?file=1693589#file1693589line482>
> >
> >     `s/DRFComparator/compare/`?
> >     
> >     We typically name the parameters `left` and `right`
> 
> Neil Conway wrote:
>     Personally I like `DRFComparator` more: it makes it clear that the function is comparing
the two nodes according to DRF.
>     
>     I renamed the parameters.
> 
> Michael Park wrote:
>     `compareDRF`? I guess I was more-so saying that it's no longer an object.

Done.


> On April 20, 2017, 9:35 a.m., Michael Park wrote:
> > src/master/allocator/sorter/drf/sorter.cpp
> > Lines 117-125 (patched)
> > <https://reviews.apache.org/r/57254/diff/19/?file=1693590#file1693590line118>
> >
> >     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;
> >     }
> >     
> >     /* ... */
> >     ```
> 
> Neil Conway wrote:
>     Happy to discuss further, but this seems more difficult to read, personally. I feel
like we usually use an explicit `foreach` loop in similar situations elsewhere...

Per discussion, I revised the existing loop to remove the `found` variable.


> On April 20, 2017, 9:35 a.m., Michael Park wrote:
> > src/master/allocator/sorter/drf/sorter.cpp
> > Lines 75-77 (original), 143-172 (patched)
> > <https://reviews.apache.org/r/57254/diff/19/?file=1693590#file1693590line144>
> >
> >     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;
> >     ```
> 
> Neil Conway wrote:
>     Happy to discuss further, but personally I prefer the current coding because it seems
safer to avoid mutating an existing tree node "in place". e.g., if there were other pointers
to `current` that should _not_ be updated to point to the virtual leaf node, they will now
be dangling pointers (i.e., clearly wrong) rather than now silently pointing at the virtual
leaf node.

Per discussion, I changed this to use the approach suggested above.


- Neil


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


On April 20, 2017, 8:40 p.m., Neil Conway wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/57254/
> -----------------------------------------------------------
> 
> (Updated April 20, 2017, 8:40 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 (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
> -----
> 
>   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/22/
> 
> 
> Testing
> -------
> 
> 
> Thanks,
> 
> Neil Conway
> 
>


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