[MESOS-9725] Perform incremental sorting in the random sorter.

• Type: Improvement
• Status: Accepted
• Priority: Major
• Resolution: Unresolved
• Labels: performance resource-management
• Epic Link: Sorter::sort Performance
• Sprint: Resource Mgmt: RI-13 Sp 44
• Story Points: 3
• Assignee: Meng Zhu
• Reporter: Meng Zhu
• Created: 10/Apr/19 17:49
• Updated: 08/May/19 16:16

Description

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.

However, since the number of distinct weights is usually much smaller comparing to the size of clients, we can minimize the sample cost by picking a client in two steps:

Step1: randomly pick a group of clients that has the same weight by generating a weighted random number.

Step2: Once a vector of clients is chosen, randomly sample a specific client within the group. Since all the clients in the chosen vector have the same weight, we do not need to consider any weights.

Since the size of distinct weights is usually much smaller comparing to the size of clients, this way, we minimize the cost of generating weighted random numbers which are linear with the size of weights.