Meng Zhu created MESOS-9725:
-------------------------------
Summary: Avoid full nodes shuffling in the random sorter by random
sampling.
Key: MESOS-9725
URL: https://issues.apache.org/jira/browse/MESOS-9725
Project: Mesos
Issue Type: Improvement
Reporter: Meng Zhu
Assignee: Meng Zhu
By doing random sampling every time as the caller asks for the next client (See
MESOS-9722) we could avoid the cost of full shuffling and only pay as we go.
While the hope is to do each random sampling with O(1) cost, the presence of
weights complicates the matter. We will need to pay O(log(n)) for every sample
even with fancy data structures like segment tree or binary index trees (naive
ones will result in O(n) since we need to look at every node's weights). And
the current full node shuffling is already optimal (nlog(n)) if all nodes are
picked.
That being said, it is straight forward to do random sampling with O(1) when
weights are uniform. We could keep the current full node shuffling for
customized weights but use random sampling for the uniform weights.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
