[MESOS-9733] Random sorter generates non-uniform result for hierarchical roles.

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.8.0, 1.9.0
• Component/s: allocation
• Labels: mesosphere resource-management
• Sprint: Resource Mgmt: RI-13 Sp 44, Resource Mgmt: RI13 Sp 45
• Story Points: 3
• Assignee: Meng Zhu
• Reporter: Meng Zhu
• Created: 17/Apr/19 18:16
• Updated: 25/Apr/19 21:50
• Resolved: 25/Apr/19 21:40

Description

In the presence of hierarchical roles, the random sorter shuffles roles level by level and then pick the active leave nodes using DFS:

https://github.com/apache/mesos/blob/7e7cd8de1121589225049ea33df0624b2a1bd754/src/master/allocator/sorter/random/sorter.cpp#L513-L529

This makes the result less random because subtrees are always picked together. For example, random sorting result such as `[a/., c/d, a/b, …]` is impossible.

Issue Links

• is related to: MESOS-9724 Flatten the weighted shuffling in the random sorter.