mesos-reviews mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Meng Zhu <m...@mesosphere.io>
Subject Re: Review Request 70497: Optimize the random sorter with random sampling.
Date Wed, 01 May 2019 01:36:50 GMT

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

(Updated April 30, 2019, 6:36 p.m.)


Review request for mesos, Andrei Sekretenko and Benjamin Mahler.


Changes
-------

Rebased and updated benchmark result.


Bugs: MESOS-9725
    https://issues.apache.org/jira/browse/MESOS-9725


Repository: mesos


Description
-------

This patch optimizes the random sorter by avoiding
clients shuffling. The sorter now does random sampling
as the caller asks for the next client.

The random sampling works in two steps. Clients with the same
relative weights are grouped together. In the first phase, we
randomly pick a group of clients. This requires the generation
of a weighted random number. In the second phase, a client within
the group is picked. Since all clients in the group have the same
weight, this can be done in constant time. This two step approach
minimizes the cost of generating weighted random number which
could be expensive given the size of the weights.


Diffs (updated)
-----

  src/master/allocator/sorter/random/sorter.hpp 55e22d7705f163fe47d5aa47416ee0714c5a87c0 
  src/master/allocator/sorter/random/sorter.cpp 813f5b55d38dd9fa822de53ee944c3f72251a69d 


Diff: https://reviews.apache.org/r/70497/diff/2/

Changes: https://reviews.apache.org/r/70497/diff/1-2/


Testing (updated)
-------

make check

Benchmarking: ran `QuotaParam/BENCHMARK_HierarchicalAllocator_WithQuotaParam.LargeAndSmallQuota/5`
with optimized build

Before:

Added 3000 agents in 101.884509ms
Added 3000 frameworks in 19.711779311secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks, with random sorter
Made 3856 allocations in 16.283607645secs
Made 0 allocation in 16.31197771secs

After r/70419, r/70576 and r/70497 :

Added 3000 agents in 87.147084ms
Added 3000 frameworks in 19.246494668secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks, with random sorter
Made 3872 allocations in 12.230518989secs
Made 0 allocation in 12.012211914secs


Thanks,

Meng Zhu


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