Dale Richardson created YUNIKORN-3350:
-----------------------------------------
Summary: Fix quadratic performance of ask scans in the application
allocation cycle
Key: YUNIKORN-3350
URL: https://issues.apache.org/jira/browse/YUNIKORN-3350
Project: Apache YuniKorn
Issue Type: Improvement
Components: core - scheduler
Reporter: Dale Richardson
Only 9% of the scheduler's allocation path is spent deciding where a pod should
go. The other 91% is per-allocation work that scales with the number of asks
the application already has, so the cost over N asks is quadratic and
throughput degrades as an application grows.
h3. Where the time goes
CPU profile of BenchmarkScheduling, 5000 nodes / 10000 pods, Linux, allocate
phase:
{noformat}
ClusterContext.schedule 1.87s (the allocate phase)
Application.tryAllocate 1.77s 95% of the phase
updateAskMaxPriority 0.98s 55% of tryAllocate
Queue.GetMaxAppUnschedAskBackoff 0.32s 18%
Allocation.IsAllocated (loop skip) 0.31s 18%
actual node fitting 0.16s 9%
{noformat}
h3. Scan 1: recomputing the max ask priority (55% of tryAllocate)
{{updateAskMaxPriority}} iterates the whole {{sa.requests}} map to recompute
the highest priority among asks that are not yet allocated:
{code:go}
func (sa *Application) updateAskMaxPriority() {
value := configs.MinPriority
for _, v := range sa.requests {
if v.IsAllocated() {
continue
}
value = max(value, v.GetPriority())
}
sa.askMaxPriority = value
sa.queue.UpdateApplicationPriority(sa.ApplicationID, value)
}
{code}
It is called from {{allocateAsk}} on every allocation whose priority is >= the
current maximum, and again from {{removeAsksInternal}} on ask removal. Each
call is O(number of asks), and it cannot stop early because pending and
satisfied asks share one map.
Internally the cost is 56% map iteration, 22% {{Allocation.IsAllocated}} and
15% {{{}Allocation.GetPriority{}}}. {{IsAllocated}} takes a read lock per ask,
so the rescan also pays one lock acquisition per entry.
h3. Scan 2: walking allocated asks in the allocation loop (18% of tryAllocate)
{{sortedRequests}} holds every ask the application has, allocated or not, so
the allocation loop steps over the satisfied ones to reach the schedulable ones:
{code:go}
for _, request := range sa.sortedRequests {
backoffThreshold := sa.queue.GetMaxAppUnschedAskBackoff()
...
if request.IsAllocated() {
continue
}
{code}
As allocations accumulate, each scheduling cycle walks an ever growing prefix
of already allocated asks before reaching the first ask that can still be
scheduled.
h3. Per-iteration getter (18% of tryAllocate)
Visible in the same snippet: {{GetMaxAppUnschedAskBackoff}} is called inside
the loop, so a value that is constant for the cycle is re-fetched under lock
once per ask walked. Its cost is a direct multiplier on scan 2.
h2. Proposed changes
# Maintain a per-priority histogram of pending asks so {{askMaxPriority}} is
available in O(1), updated incrementally as asks become pending or allocated,
instead of rescanning.
# Keep {{sortedRequests}} pending-only, maintained by remove-on-allocate and
insert-on-deallocate, so the allocation loop no longer walks allocated asks.
# Hoist the per-iteration getter out of the allocation loop.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
