[YUNIKORN-807] Improve performance of node sorting

• Type: New Feature
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 0.12.1
• Component/s: core - scheduler
• Labels: pull-request-available
• Target Version: 0.12.1
• Assignee: Craig Condit
• Reporter: Craig Condit
• Created: 19/Aug/21 15:02
• Updated: 21/Jan/22 21:48
• Resolved: 30/Aug/21 21:08

Description

YuniKorn currently sorts all nodes on demand whenever scheduling of a container occurs. This causes significant performance degradation as the number of nodes increases.

If we replace the on-demand sorting with a B-Tree sorted proactively, we can improve performance considerably.

This is a similar approach to YUNIKORN-21, but without the associated behavioral changes.

I've attached a design document with the details of the approach and the performance improvement gained.

Issue Links

• is related to: YUNIKORN-831 node sorting should check other resources of nodes instead of comparing node id directly
• is related to: YUNIKORN-847 Use resource weighting for node sorting
• relates to: YUNIKORN-21 Optimize node sorting algorithms
• relates to: YUNIKORN-780 Refactor node sorting policies into separate implementations
• links to: GitHub Pull Request #307