mesos-reviews mailing list archives

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

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

Review request for mesos and Benjamin Mahler.


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
-----

  src/master/allocator/sorter/random/sorter.hpp 125ce84761e4c930370912151700ddda35d7b6c1 
  src/master/allocator/sorter/random/sorter.cpp bbe130dbf3b158ea14f9572bc5d14200fcd85127 


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


Testing
-------

**Before**:
Added 300 agents in 6.693069ms
Added 300 frameworks in 267.422912ms
Benchmark setup: 300 agents, 300 roles, 300 frameworks, with random sorter
Made 385 allocations in 1.108127379secs
Made 0 allocation in 170.055364ms

Added 3000 agents in 84.494658ms
Added 3000 frameworks in 20.057451571secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks, with random sorter
Made 3839 allocations in 16.367034017secs
Made 0 allocation in 16.471896231secs

**After**:
Added 300 agents in 10.15362ms
Added 300 frameworks in 278.300712ms
Benchmark setup: 300 agents, 300 roles, 300 frameworks, with random sorter
Made 396 allocations in 150.710728ms
Made 0 allocation in 123.912096ms

Added 3000 agents in 84.852909ms
Added 3000 frameworks in 20.260891845secs
Benchmark setup: 3000 agents, 3000 roles, 3000 frameworks, with random sorter
Made 3872 allocations in 12.754014262secs
Made 0 allocation in 12.07944231secs


Thanks,

Meng Zhu


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