You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@mesos.apache.org by Meng Zhu <mz...@mesosphere.io> on 2019/04/08 22:30:40 UTC
Review Request 70429: Avoided hierarchical shuffling in the random
sorter.
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/70429/
-----------------------------------------------------------
Review request for mesos and Benjamin Mahler.
Bugs: MESOS-9452
https://issues.apache.org/jira/browse/MESOS-9452
Repository: mesos
Description
-------
Due to the presence of hierarchical weights, the random
sorter currently shuffles nodes level-by-level.
This patch avoids this by first calculating the relative
weights of each active leaf node and shuffle all of them
only once. This should improve the performance for
hierarchical roles while incurs a small overhead in the
case of flat roles. In addition, this paves the way for
random sampling where shuffling can be avoided altogether.
Diffs
-----
src/master/allocator/sorter/random/sorter.cpp bbe130dbf3b158ea14f9572bc5d14200fcd85127
Diff: https://reviews.apache.org/r/70429/diff/1/
Testing
-------
make check
Tests for hierarchical roles in subsequent patches
Benchmarking:
Optimized build with QuotaParam/BENCHMARK_HierarchicalAllocator_WithQuotaParam.LargeAndSmallQuota/2
## Before:
Added 3000 agents in 85.844373ms
Added 3000 frameworks in 19.713969615secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks
Made 3500 allocations in 13.690538305secs
Made 0 allocation in 9.76855825secs
## After:
Added 3000 agents in 93.482508ms
Added 3000 frameworks in 19.193235872secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks
Made 3500 allocations in 13.530734654secs
Made 0 allocation in 10.338803223secs
Thanks,
Meng Zhu
Re: Review Request 70429: Fixed a bug in the random sorter.
Posted by Benjamin Mahler <bm...@apache.org>.
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/70429/#review214890
-----------------------------------------------------------
Fix it, then Ship it!
src/master/allocator/sorter/random/sorter.hpp
Lines 135 (patched)
<https://reviews.apache.org/r/70429/#comment301172>
It's a little odd in this patch to have it as a struct, perhaps just add to the description (or a TODO here) the intent given the next patch of adding the dirty bit needs to store it as a member?
src/master/allocator/sorter/random/sorter.cpp
Line 485 (original), 484 (patched)
<https://reviews.apache.org/r/70429/#comment301171>
I think we may have to std::move here, not sure if the copy will be elided
src/master/allocator/sorter/random/sorter.cpp
Lines 581-582 (patched)
<https://reviews.apache.org/r/70429/#comment301173>
Just FYI these vectors will always grow in capacity, even without the reserve calls here, seems ok for now but maybe we should write a note about it or something
src/master/allocator/sorter/random/sorter.cpp
Lines 584-590 (patched)
<https://reviews.apache.org/r/70429/#comment301174>
I think we could boil this down to just the formula?
```
weight(node)
rWeight(node) = rWeight(parent) * ------------------------------------------
weight(node) + SUM(weight(active siblings))
```
src/master/allocator/sorter/random/sorter.cpp
Lines 596 (patched)
<https://reviews.apache.org/r/70429/#comment301177>
How about s/totalWeights/siblingWeights/?
We could either note that the siblingWeights includes the node itself, or do these adjustments:
```
double relativeWeight = parentRelativeWeight *
(sorter->getWeight(node) / (sorter->getWeight(node) + siblingWeights));
```
```
calculateRelativeWeights(child, totalWeights_ - sorter->getWeight(child), relativeWeight);
```
```
calculateRelativeWeights(sorter->root, 0.0, 1.0);
```
The version with adjustments seems to be easier to understand based on the formula above without much additional complexity?
src/master/allocator/sorter/random/sorter.cpp
Lines 597 (patched)
<https://reviews.apache.org/r/70429/#comment301176>
!activeInternals.contains(node)
(will work once we use hashset)
Also, all these checks make me think we should have a lambda?
```
auto isActive = [&](Node* node) {
return node->kind == Node::ACTIVE_LEAF || activeInternals.contains(child);
};
```
Then just call it below?
src/master/allocator/sorter/random/sorter.cpp
Lines 615-616 (patched)
<https://reviews.apache.org/r/70429/#comment301180>
This would read a bit easier as isActive(child), see the suggestion above
src/master/allocator/sorter/random/sorter.cpp
Lines 616 (patched)
<https://reviews.apache.org/r/70429/#comment301178>
activeInternals.contains(child)
src/master/allocator/sorter/random/sorter.cpp
Lines 623 (patched)
<https://reviews.apache.org/r/70429/#comment301179>
activeInternals.contains(child)
- Benjamin Mahler
On April 24, 2019, 10:34 p.m., Meng Zhu wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/70429/
> -----------------------------------------------------------
>
> (Updated April 24, 2019, 10:34 p.m.)
>
>
> Review request for mesos and Benjamin Mahler.
>
>
> Bugs: MESOS-9733
> https://issues.apache.org/jira/browse/MESOS-9733
>
>
> Repository: mesos
>
>
> Description
> -------
>
> Currently, in the presence of hierarchical roles, the
> random sorter shuffles roles level by level and then pick
> the active leave nodes using DFS. This could generate
> non-uniform random result since active leaves in a subtree
> are always picked together.
>
> This patch fixes the issue by first calculating the relative
> weights of each active leaf node and shuffle all of them
> only once.
>
>
> Diffs
> -----
>
> src/master/allocator/sorter/random/sorter.hpp 125ce84761e4c930370912151700ddda35d7b6c1
> src/master/allocator/sorter/random/sorter.cpp bbe130dbf3b158ea14f9572bc5d14200fcd85127
> src/tests/sorter_tests.cpp 91bfde01b579a9892215593ab8d8b2d096788278
>
>
> Diff: https://reviews.apache.org/r/70429/diff/4/
>
>
> Testing
> -------
>
> make check
> Tests for hierarchical roles in subsequent patches
>
> Benchmarking:
> Optimized build with QuotaParam/BENCHMARK_HierarchicalAllocator_WithQuotaParam.LargeAndSmallQuota/2
>
> ## Before:
> Added 3000 agents in 85.844373ms
> Added 3000 frameworks in 19.713969615secs
> Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks
> Made 3500 allocations in 13.690538305secs
> Made 0 allocation in 9.76855825secs
>
> ## After:
> Added 3000 agents in 93.482508ms
> Added 3000 frameworks in 19.193235872secs
> Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks
> Made 3500 allocations in 13.530734654secs
> Made 0 allocation in 10.338803223secs
>
>
> Thanks,
>
> Meng Zhu
>
>
Re: Review Request 70429: Fixed a bug in the random sorter.
Posted by Meng Zhu <mz...@mesosphere.io>.
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/70429/
-----------------------------------------------------------
(Updated April 24, 2019, 3:34 p.m.)
Review request for mesos and Benjamin Mahler.
Changes
-------
Refactored the patch.
Bugs: MESOS-9733
https://issues.apache.org/jira/browse/MESOS-9733
Repository: mesos
Description
-------
Currently, in the presence of hierarchical roles, the
random sorter shuffles roles level by level and then pick
the active leave nodes using DFS. This could generate
non-uniform random result since active leaves in a subtree
are always picked together.
This patch fixes the issue by first calculating the relative
weights of each active leaf node and shuffle all of them
only once.
Diffs (updated)
-----
src/master/allocator/sorter/random/sorter.hpp 125ce84761e4c930370912151700ddda35d7b6c1
src/master/allocator/sorter/random/sorter.cpp bbe130dbf3b158ea14f9572bc5d14200fcd85127
src/tests/sorter_tests.cpp 91bfde01b579a9892215593ab8d8b2d096788278
Diff: https://reviews.apache.org/r/70429/diff/4/
Changes: https://reviews.apache.org/r/70429/diff/3-4/
Testing
-------
make check
Tests for hierarchical roles in subsequent patches
Benchmarking:
Optimized build with QuotaParam/BENCHMARK_HierarchicalAllocator_WithQuotaParam.LargeAndSmallQuota/2
## Before:
Added 3000 agents in 85.844373ms
Added 3000 frameworks in 19.713969615secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks
Made 3500 allocations in 13.690538305secs
Made 0 allocation in 9.76855825secs
## After:
Added 3000 agents in 93.482508ms
Added 3000 frameworks in 19.193235872secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks
Made 3500 allocations in 13.530734654secs
Made 0 allocation in 10.338803223secs
Thanks,
Meng Zhu
Re: Review Request 70429: Fixed a bug in the random sorter.
Posted by Meng Zhu <mz...@mesosphere.io>.
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/70429/
-----------------------------------------------------------
(Updated April 17, 2019, 11:29 a.m.)
Review request for mesos and Benjamin Mahler.
Changes
-------
Rephrased the summary and description as a bug fix. Also, fixed the broken test.
Summary (updated)
-----------------
Fixed a bug in the random sorter.
Bugs: MESOS-9733
https://issues.apache.org/jira/browse/MESOS-9733
Repository: mesos
Description (updated)
-------
Currently, in the presence of hierarchical roles, the
random sorter shuffles roles level by level and then pick
the active leave nodes using DFS. This could generate
non-uniform random result since active leaves in a subtree
are always picked together.
This patch fixes the issue by first calculating the relative
weights of each active leaf node and shuffle all of them
only once.
Diffs (updated)
-----
src/master/allocator/sorter/random/sorter.cpp bbe130dbf3b158ea14f9572bc5d14200fcd85127
src/tests/sorter_tests.cpp 91bfde01b579a9892215593ab8d8b2d096788278
Diff: https://reviews.apache.org/r/70429/diff/3/
Changes: https://reviews.apache.org/r/70429/diff/2-3/
Testing
-------
make check
Tests for hierarchical roles in subsequent patches
Benchmarking:
Optimized build with QuotaParam/BENCHMARK_HierarchicalAllocator_WithQuotaParam.LargeAndSmallQuota/2
## Before:
Added 3000 agents in 85.844373ms
Added 3000 frameworks in 19.713969615secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks
Made 3500 allocations in 13.690538305secs
Made 0 allocation in 9.76855825secs
## After:
Added 3000 agents in 93.482508ms
Added 3000 frameworks in 19.193235872secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks
Made 3500 allocations in 13.530734654secs
Made 0 allocation in 10.338803223secs
Thanks,
Meng Zhu