[
https://issues.apache.org/jira/browse/YUNIKORN-3350?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18103448#comment-18103448
]
Manikandan R commented on YUNIKORN-3350:
----------------------------------------
#
{quote}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.{quote}
How do we read the ask from those histograms? We do retrieval in many other
places as well.
(or)
Should we simply use one single PriorityQueue/Heap based data structure backed
up by Map to store the pending asks?
As and when any new ask gets added, structure itself would place it on the
right index with adjustments ONLY if required based on the priority. If
priority is same, comparison can be done using create time. Similarly, on the
removal side, it does takes care of the rearrangement (if needed)
automatically. Cost is O(logN). We can always use ask located at zeroth index
to update app's askMaxPriority which is O(1). Existing sortedRequests uses more
or less similar structure.
[https://pkg.go.dev/github.com/jba/heap] looks promising when compared to
[https://pkg.go.dev/container/heap] as earlier is already on the way to be
adopted as replacement for later one.
[https://github.com/golang/go/issues/80590] discussions cover this.
Since there are reads from other places, above based structure can be modified
slightly to be backed up by map with a appropriate linkage to fetch the GET
requests in 0(1) time.
> 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]
