[
https://issues.apache.org/jira/browse/YUNIKORN-3084?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17955641#comment-17955641
]
Peter Bacsko commented on YUNIKORN-3084:
----------------------------------------
Good catch, unfortunately this is really a bug.
I can think of two solutions right now:
1) Don't use binary search when removing, just iterate over the slice and check
allocation ID
2) Use an unique, monotonically increasing ID for each allocation object
internally and use that counter when removing
The thing is, we might even get rid of the whole binary search stuff
completely, even for addition. It only achieves noticable speedup when adding
an application with very high number of pods and even in this case, the
priority/creation time have to show considerable fluctuation to make it
worthwile. I think in most situations, pods belonging to the same app will have
the same priority and almost the same second-based "creationTime". In 99.9% of
the case, we'll end up appending to the end of the slice, ie. the fast path
code:
{noformat}
func (s *sortedRequests) insert(ask *Allocation) {
size := len(*s)
if size > 0 && ask.LessThan((*s)[size-1]) {
// fast path, insert at the end (most likely)
s.insertAt(size, ask) <--- this is performed in always every
case
return
}
{noformat}
Pods are most likely arriving with the same priority and the same/increasing
"creationTime". There's simply no need to use binary search in either case, it
just makes things complicated. We can confirm this theory by using the
performance unit test {{BenchmarkSchedulingThroughPut()}} located inside
{{yunikorn-k8shim/pkg/shim/scheduler_perf_test.go}}.
When I added this code 2 years ago, I wasn't thinking this through properly,
but thinking about it now, getting rid of {{sort.Search()}} is probably the
most sensible approach.
> Fix Inconsistency in Allocation Removal from sortedRequests
> -----------------------------------------------------------
>
> Key: YUNIKORN-3084
> URL: https://issues.apache.org/jira/browse/YUNIKORN-3084
> Project: Apache YuniKorn
> Issue Type: Bug
> Components: core - scheduler
> Affects Versions: 1.6.0, 1.6.1, 1.6.2, 1.6.3
> Reporter: Mit Desai
> Assignee: Mit Desai
> Priority: Major
>
> There is an issue in the _remove_ method of _sortedRequests_ in the scheduler
> that causes allocations to be inconsistently removed. This can lead to a
> situation where an allocation is removed from the application's allocations
> map but remains in the sortedRequests list, consuming scheduler cycles for
> non-existant pods. This also leads to a state where not all allocations get
> removed and Application stays in the UI in a _New_ state even though it has
> already been removed from the cluster.
> The current implementation of the _remove_ method in _sortedRequests_ uses a
> binary search approach with the _LessThan_ comparison function to find
> allocations to remove. However, this approach is flawed because:
> 1. The binary search is looking for an allocation based on priority and
> creation time, not by its unique allocation key
> 2. When multiple allocations have the same priority and creation time, the
> binary search may find the wrong allocation
> 3. This causes inconsistent behavior where allocations are not properly
> removed from the _sortedRequests_ list
> The binary search in the _remove_ method is using the _LessThan_ comparison
> function, which compares allocations based on priority and creation time, not
> by allocation key. When multiple allocations have the same priority and
> creation time, the binary search may find a different allocation than the one
> we want to remove.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
