tigerquoll opened a new pull request, #1122:
URL: https://github.com/apache/yunikorn-core/pull/1122
Part of YUNIKORN-3350, which splits one change into three independent levers.
**Depends on YUNIKORN-3351** (hoist the per-ask backoff getter). GitHub
requires a pull request's base
to be a branch in this repository, so until 3351 merges this PR's diff
necessarily contains its commit
as well. **The commits belonging to this change are the last two**; the
first, "Hoist the per-ask
backoff getter out of tryAllocate", is 3351 and is a four-line change. I
will rebase once 3351 lands.
The third lever, YUNIKORN-3353 (keep only pending asks in sortedRequests),
is deliberately held back
until these two are settled — it carries an ordering change that deserves to
be reviewed on its own.
## What
`Application.updateAskMaxPriority` iterates the whole `sa.requests` map to
recompute the highest
priority among asks that are not yet allocated. It is called from
`allocateAsk` on every allocation
whose priority is at or above the current maximum, and again from
`removeAsksInternal` on ask removal.
Each call is O(number of asks), so scheduling N asks costs O(N^2), and the
cost grows as an
application gets larger.
It cannot stop early, because pending and allocated asks share one map — it
has to test
`IsAllocated()` on every entry, and that takes a read lock each time. In a
CPU profile of master the
function is **55% of `Application.tryAllocate`**, split 56% map iteration,
22% `IsAllocated`, 15%
`GetPriority`.
Replace it with a per-priority histogram of pending asks (`pendingPriorities
map[int32]int`),
maintained incrementally as asks enter and leave the pending set, so
`askMaxPriority` is available in
O(1). `updateAskMaxPriority` is deleted.
This PR touches `application.go` only. It changes no ordering semantics
anywhere.
## Design notes
A map of counts rather than a set, because many asks share a priority and
the structure has to know
when a priority band actually empties. Every operation is O(1) except one:
when the current top bucket
empties, the new maximum is recomputed by scanning the map keys, which is
O(distinct priority values
in use) — a handful in practice, not O(number of asks).
`setAskMaxPriority` propagates to the queue only when the value actually
changes, so this also issues
strictly fewer `UpdateApplicationPriority` calls than the rescan it replaces.
The non-O(1) path is worth quantifying, since it is the obvious question.
`askMaxPriority` is read by
all four application sort policies (`considerPriority` decides whether
priority is the primary or
secondary key, not whether it is consulted), so reads sit on the scheduling
loop and scale with
applications per queue. Recomputation happens only when the *top* band
empties. Measured on
BenchmarkScheduling, 5000 nodes, 10000 asks, with both applications in one
queue so the sort
comparator actually runs:
```
GetAskMaxPriority = 10,000 inc = 10,000 dec = 10,000
recomputations = 2 map keys scanned across both = 0
```
Two recomputations, one per application, when its last pending ask is
allocated — a 5,000:1 ratio of
reads to recomputations. Under an adversarial mix (the property fuzzer, 11
distinct priorities, heavy
add/allocate/deallocate churn) it rises to 10.5% of decrements, still
averaging only 2.0 map keys
each. Even the pathological shape — a high-priority ask interleaved with
lower ones so the top band
drains on every allocation — is O(asks x distinct priorities), against the
O(asks^2) it replaces.
One guard comes with it. `deallocateAsk` returns an ask to the histogram
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`. The rescan derived the maximum by scanning
`sa.requests`, so an ask absent from
it never influenced the converged result; the guard preserves that.
## Measured effect
`BenchmarkScheduling`, allocate phase, 10000 pods, alternating A/B, 3
samples, medians. Linux 6.8
aarch64, 6 CPUs, GOMAXPROCS=6. Cumulative figures — the stack up to and
including this PR, against
master:
| Configuration | master (c/s) | this PR (c/s) | cumulative | this PR alone |
|---|---:|---:|---:|---:|
| 500 nodes | 5,481 | 16,832 | 3.07x | 2.49x |
| 1000 nodes | 5,517 | 16,351 | 2.96x | 2.49x |
| 2000 nodes | 5,396 | 16,419 | 3.04x | 2.49x |
| 5000 nodes | 5,353 | 16,333 | 3.05x | 2.44x |
"This PR alone" is the ratio against the previous PR in the stack. Spread up
to 7%.
Scope: mock resource manager, no real bind, so this is core scheduling
headroom rather than a
real-cluster pods/second figure. The workload is 2 applications x 5,000
asks; the cost removed is
per-application and quadratic in that application's ask count, so this shape
is favourable — note
master's throughput is flat across node counts, which is the per-app rescan
dominating everything
else. A cluster of many small applications sees a proportionally smaller
absolute gain.
## Behaviour
Unchanged. The golden decision-trace tests added in YUNIKORN-3338 reproduce
byte-for-byte, goldens not
regenerated. They pin the ordered sequence of decisions the resource manager
observes through
`UpdateAllocation`, so reproducing them is the claim.
One edge worth stating precisely: `cleanupAsks` now also resets the
histogram and `askMaxPriority`.
That happens only on entering a terminal state (Completed/Failed), where the
application is no longer
schedulable, so it changes no scheduling decision — but it does mean a
terminal application no longer
retains a stale `askMaxPriority`.
A property fuzzer (`application_property_test.go`) drives an Application
through long randomized
interleavings of the real entry points — `AddAllocationAsk` including the
replace-an-existing-ask
branch, `AllocateAsk`, `DeallocateAsk`, `RemoveAllocationAsk`,
`RecoverAllocationAsk`,
`AddAllocation`, `RollbackAllocation`, and FSM-driven cleanup — and after
every single step
re-derives the expected histogram and `askMaxPriority` from an independent
reference model. Coverage
high-water marks are asserted so an operation that becomes a silent no-op
fails rather than passing
trivially.
## Concurrency
No new lock acquisition and no new ordering. `setAskMaxPriority` takes the
queue lock under the
application lock exactly as the rescan it replaces did, and does so less
often. All histogram
mutation happens under the application write lock; the helpers are unlocked
internals whose callers
all hold it. Verified green under `-race`, and under go-deadlock with
lock-order detection armed
(`DEADLOCK_DETECTION_ENABLED=true DEADLOCK_DISABLE_LOCK_ORDER=false`).
## Scope and rollback
No configuration, REST, scheduler-interface, or metrics changes. No new
public API. No persisted or
serialized state — `pendingPriorities` is core-internal and never 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.
Generated by Author with assistance from Claude Code.
--
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]
