mesos-reviews mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Michael Park <mp...@apache.org>
Subject Re: Review Request 57254: Added support for hierarchical roles to DRFSorter.
Date Sat, 22 Apr 2017 00:52:48 GMT


> On April 20, 2017, 2: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...
> 
> Neil Conway wrote:
>     Per discussion, I revised the existing loop to remove the `found` variable.

```
Node* node = nullptr;
foreach (Node* child, current->chlidren) {
  if (child->name == element) {
    node = child;
    break;
  }
}

if (node != nullptr) {
  continue;
}

...
```


- Michael


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


On April 20, 2017, 9:32 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, 9:32 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/24/
> 
> 
> Testing
> -------
> 
> 
> Thanks,
> 
> Neil Conway
> 
>


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