[
https://issues.apache.org/jira/browse/YUNIKORN-3350?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Dale Richardson reassigned YUNIKORN-3350:
-----------------------------------------
Assignee: Dale Richardson
> 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
> Assignee: Dale Richardson
> Priority: Major
>
> 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]
