tigerquoll opened a new pull request, #1127:
URL: https://github.com/apache/yunikorn-core/pull/1127
Part of YUNIKORN-3350, which splits one change into three independent
levers. This is the third and
last lever, the one held back from the earlier submissions because it
carries the contested
decisions: pending-only membership, where a returning ask lands, and
identity-based `remove`.
> **Stacked on #1122** (YUNIKORN-3352, the pending-priority histogram): the
first two commits here
> ARE #1122 — please review only the last three. This PR rebases down to
those three as soon as
> #1122 lands. YUNIKORN-3351 (the backoff getter hoist) is already on master
as 7dc1287.
## What
`sortedRequests` is ordered by priority, then age. Whether an ask is
allocated plays no part in that
ordering, so allocated and pending asks sit side by side in the list.
`tryAllocate` walks it from the
front, skipping the allocated ones with `if request.IsAllocated() { continue
}` — a read lock each. The
more asks an application has already had satisfied, the more there are to
skip, so each scheduling
cycle costs more than the last. In a CPU profile of master that skip is 18%
of
`Application.tryAllocate`.
Keep the slice pending-only instead: `allocateAsk` removes the ask,
`deallocateAsk` puts it back. The
container, its comparator and its insert behaviour are unchanged — only
membership changes, plus one
placement rule for the way back in (below). (`insert`'s slow path is shared
with the new `reinsert`
since the two are byte-identical, so they cannot diverge.)
## Measured effect
`BenchmarkScheduling`, allocate phase, 10000 pods, alternating A/B, 3
samples, medians. Linux 6.8
aarch64, 6 CPUs, GOMAXPROCS=6. Cumulative is the whole stack against master;
"this PR" is the ratio
against the previous PR in the stack.
| nodes | master (c/s) | this PR (c/s) | cumulative | this PR |
|---|---:|---:|---:|---:|
| 500 | 5,481 | 44,421 | 8.10x | 2.64x |
| 1000 | 5,517 | 42,452 | 7.70x | 2.60x |
| 2000 | 5,396 | 43,086 | 7.99x | 2.62x |
| 5000 | 5,353 | 40,577 | 7.58x | 2.48x |
Spread up to 7%. After the change both hot symbols are absent from the
profile entirely and node
iteration becomes the dominant term, which is the correct shape.
Scope: mock resource manager, no real bind, so this is core scheduling
headroom rather than a
real-cluster pods/second figure — on a real cluster the ceiling remains the
Kubernetes API bind rate.
The workload is 2 applications x 5,000 asks, which is favourable to a
per-application quadratic fix.
Reproduce with:
```
go test ./pkg/scheduler/tests/ -run '^$' -bench 'BenchmarkScheduling'
-benchtime=1x -v
```
## What else reads `sortedRequests`
Pending-only membership changes what every reader sees, so all were checked.
`sortedRequests` is
unexported, has no accessor, and appears in no DAO, REST handler, metric or
proto conversion. Inside
`pkg/scheduler/objects` there are exactly three readers:
| reader | effect |
|---|---|
| `tryAllocate` | the target of this change |
| `tryPlaceholderAllocate` | already skips on `IsAllocated()`, so sees the
same set |
| `getOutstandingRequests` | unchanged here, already skips on
`IsAllocated()`, so sees the same set |
No caller uses `len(sortedRequests)` as a count of an application's asks, so
its changed meaning is
not observed anywhere.
Insertion of new asks is untouched, so for a workload that only adds asks
all three readers see the
slice exactly as master builds it. The one order change is the re-insert
path (next section), and it
is visible to all three readers, including `getOutstandingRequests` — which
consumes headroom as it
walks, so which asks land in the outstanding set can differ when headroom
runs out inside a tie
group. That set feeds `UpdateContainerSchedulingState`, i.e. the pods
reported to the resource
manager as unschedulable for cluster autoscaling.
## Where a returning ask lands
Nothing on master re-inserts into `sortedRequests`: an ask that becomes
pending again (preemption
revert, placeholder-replacement revert, rollback after a failed bind) has
been sitting in its
original position all along. Pending-only membership creates the question of
where it goes back in,
and the existing machinery cannot answer it: `createTime` is whole-second
resolution end to end — the
shim sends `pod.CreationTimestamp.Unix()`, the core does `time.Unix(secs,
0)`, and Kubernetes
`creationTimestamp` is second-resolution at source — so every pod of a burst
ties on
`(priority, createTime)`, and `LessThan` reports both directions as
less-than for a tie. Plain
`insert` would place a returning ask by slice contents: behind its tie-peers
when the group sits at
the tail (the append fast path), in front of them otherwise.
So the placement is made a stated rule instead of a side effect: **a
returning ask goes to the head
of its `(priority, createTime)` tie-group** — `sortedRequests.reinsert`,
which is `insert` minus the
append fast path. The scheduler was already trying that ask ahead of its
tie-peers when it allocated
it; putting it back at the head means it is retried before the others rather
than sent to the back
of a group it had already cleared. The comparator is untouched, no
tiebreaker is added, and ties
between newly *arriving* asks keep the existing position-dependent placement
— no canonical order is
imposed where nothing needs one.
The trade-off is deliberate: an ask that keeps failing (say, a repeated bind
failure) is re-attempted
first each cycle. That costs the group one attempt per cycle, not the cycle:
when an attempt fails
`tryAllocate` walks on to the next pending ask, and the application-level
unschedulable-ask backoff
bounds the walk as it always has. If retry-first proves wrong for that path
specifically, sending the
returning ask to the back of its group instead is the same binary search
with the opposite tie
handling — a scheduling-policy decision that can be made in its own change
without touching this
structure.
## Three guards
The full rescan tolerated states that incremental membership does not:
- `AddAllocationAsk`'s replace branch drops the displaced ask from
`sortedRequests`. The unconditional
insert that follows would otherwise leave two entries for one key. The
duplicate exists on master,
masked because nothing depended on the slice holding each key once.
- `sortedRequests.remove` matches on **pointer identity** rather than
`allocationKey`. On master
`remove` has a single cold call site; this PR puts it on the allocation
path, so "first entry with
this key" is no longer good enough. Every direct call site passes a map-
or slice-resolved object,
so no outcome changes today. This is correctness by construction rather
than a fix for a live
hazard: the one path that could present a stale object —
`AddAllocationAsk` replacing an ask that
holds a reservation, whose captured `reserve.alloc`
`tryReservedAllocate`'s second loop uses
without re-resolving — is unreachable, because that function's only caller
adds an ask solely when
`GetAllocationAsk` returned nil, and both run on the single
allocation-event goroutine. Identity
matching means the invariant does not depend on that remaining true.
- `deallocateAsk` returns an ask to the pending structures only when it is
still the tracked object
for its key. `removeAsksInternal("")` wipes `sa.requests` while
`sa.allocations` survives until the
shim confirms the releases, and a release arriving in that window reaches
`RollbackAllocation`.
A dedicated commit extends this guard to the pending-resource re-add
(`sa.pending` and queue
pending), closing a leak that predates this series and exists on upstream
master: a ghost
rollback re-added resource that nothing could ever subtract again —
`sa.requests` is already
empty, so every later cleanup short-circuits — permanently blocking the
`IsZero(pending)` check
that gates the Completing transition and inflating queue pending until app
removal. The returned
delta is unchanged in the rejected case, since callers use it to unwind
node/queue *allocated*
tracking that the rolled-back allocation genuinely occupied; only the
*pending* re-add is
conditional. Pinned by `TestRollbackAllocationAskNotTracked`.
### Why not a different structure
- **Leave allocated asks in and keep skipping them.** That is master, and it
is the cost being removed.
- **Tombstone and compact periodically.** Keeps positions stable, but adds a
compaction policy and
leaves the loop walking tombstones in between.
- **A second list, or an order-maintenance structure.** Position-preserving,
so no re-insert rule
would be needed — but it trades one ordering invariant for two structures
that must agree, and
gives up the binary-search insert the slice already provides. This is the
alternative worth
revisiting if the re-insert placement proves contentious.
### `remove` is O(n) — has the quadratic just moved?
No, and this was measured. `remove` → `removeAt` → `memmove` is **~30ms** of
the post-change profile,
against the **~0.31s** of allocated-ask skipping this PR removes on the same
workload. (That 0.31s is
the share of `IsAllocated` attributed to `tryAllocate`; the rest belongs to
the rescan the previous PR
removes and is not claimed here.) Two reasons: `tryAllocate` allocates the
first ask that fits, so
`remove`'s linear search almost always terminates at or near index 0; and
moving pointers is far
cheaper per element than the scan it replaces, where each element cost a
read lock. The cost also
falls across a run as the pending list shrinks, whereas the scan it replaces
grew.
The one place a miss-scan was guaranteed is also closed:
`removeAsksInternal` now skips the slice
removal for allocated asks, which left `sortedRequests` at `allocateAsk`
time — without the skip,
every release of a satisfied allocation would scan the whole pending list to
find nothing.
### Why the histogram is kept
Once the slice is pending-only it is ordered highest priority first, so
`sortedRequests[0]` is the
pending maximum and the previous PR's histogram becomes derivable — the
equivalence holds across the
whole property fuzzer. It is kept anyway, because deriving it would make
queue-priority accounting
silently contingent on the ask sort policy, and on the pending-only
invariant this PR introduces. The
two values answer different questions.
## Hardening
`tryAllocate` iterated with a range loop while paths inside call
`allocateAsk`, which now removes from
that same slice — a range loop captures the slice header once, so a mid-loop
remove could leave the
final iteration reading the nil'd tail slot. That was safe only by
convention.
It becomes an index loop that re-reads `len()` each iteration, so a future
mutate-then-continue
degrades to skipping one ask instead of crashing. Two asserts come with it:
the pre-loop length is
checked for mid-iteration mutation, and the `IsAllocated()` skip — now dead
by the pending-only
invariant — is upgraded from a silent skip to scream-then-repair: it
`DPanic`s, drops the ghost
entry and ends the cycle. An allocated entry in the slice means the
remove-on-allocate pairing
broke, and nothing else would ever clean it up (every removal path skips
allocated asks precisely
because they cannot be in the slice), so the repair turns a permanently
re-detected entry into a
hard failure in tests and a single logged self-heal in production. Neither
assert can fire against
the current code.
`DPanic` severity differs by deployment. Core's `Development: true` is
applied only when no logger has
been preset, so it holds for core unit tests and standalone core, where a
violation is a hard failure
and green suites are positive evidence. A Kubernetes deployment presets the
logger with
`Development: false`, so the same asserts log and fall through. Loud in
test, non-fatal in production.
## Behaviour and testing
For workloads that never revert an allocation — the overwhelming majority of
scheduling activity —
ordering is byte-for-byte what master produces, because the comparator and
`insert` are untouched.
The behaviour change is confined to the revert paths, and the tests carry it:
- `TestReinsertHeadOfTieGroup` (sorted_asks_test.go) pins the `reinsert`
contract: a returning ask
heads its tie-group, whether the group sits at the tail or has
lower-priority asks behind it, and
an ask with nothing sorting after it returns to the end, not the front.
- `TestGetOutstandingRequests_PartialHeadroom` pins that outstanding-ask
selection follows slice
order; it holds before and after. The pre-existing cases at all three
levels size headroom so that
either all or none are selected, so they pass under any ordering.
- The previous PR's property fuzzer is extended to assert `sortedRequests`
membership (pending keys
exactly, no duplicates, nothing allocated) and comparator-validity of the
order against its
independent reference model, across every entry point including rollback
and replace.
- `TestAddAllocationAskReplaceExistingPendingAsk` and
`TestRollbackAllocationAskNotTracked` pin the
two guards above at the application level.
- Full `pkg/scheduler/...` green, including under `-race`.
Concurrency: no new lock acquisition and no new ordering. All slice mutation
happens under the
application write lock, where the previous PR's histogram maintenance
already lives.
## Scope and rollback
No configuration, REST, scheduler-interface or metrics changes. No new
public API. No persisted or
serialized state — nothing crosses a process or version boundary, so there
is nothing to migrate and
no mixed-version concern during a rolling upgrade. Rollback is a single
revert.
Release note: an ask whose allocation is reverted (preemption, placeholder
replacement, failed-bind
rollback) is now retried before other pending asks of equal priority and
creation time, instead of
holding its original arrival slot. Additionally, rolling back an allocation
whose ask the
application no longer tracks no longer permanently inflates application and
queue pending resource
(pre-existing leak, also present upstream).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
