[PR #27] [CLOSED] feat(scheduler): add projected least-loaded placement strategy #126

New issue

Closed

opened 2026-10-29 14:19:58 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-29 14:19:58 +00:00

Owner

📋 Pull Request Information

Original PR: https://github.com/kvcache-ai/AgentENV/pull/27
Author: @catyans
Created: 7/28/2026
Status: ❌ Closed

Base: main ← Head: feat/least-loaded-scheduler

📝 Commits (10+)

46403a4 feat(scheduler): add projected least-loaded strategy
13a53a0 fix(scheduler): require capacity for requested resources
f288cd4 fix(scheduler): reserve projected placements
0679b78 docs(scheduler): explain placement reservations
148a982 fix(scheduler): reconcile reserved resources from allocation
5d0addf refactor(scheduler): scope least-loaded reservations
a493491 fix(scheduler): reconcile on heartbeat generations
121d728 fix(scheduler): bound conservative reservation cleanup
85ad4eb fix(scheduler): reconcile failed placements
82b9a3c fix(scheduler): reconcile resource dimensions independently

📊 Changes

14 files changed (+1354 additions, -11 deletions)

View changed files

📝 deploy/docker/config/default.json (+1 -0)
📝 services/README.md (+34 -2)
📝 services/config/local.json (+1 -0)
📝 services/scheduler/cmd/main.go (+4 -1)
➕ services/scheduler/internal/least_loaded.go (+433 -0)
➕ services/scheduler/internal/least_loaded_test.go (+713 -0)
📝 services/scheduler/internal/metrics.go (+2 -0)
📝 services/scheduler/internal/node_registry.go (+16 -3)
📝 services/scheduler/internal/node_registry_test.go (+32 -0)
📝 services/scheduler/internal/service.go (+4 -2)
📝 services/scheduler/internal/strategy.go (+24 -2)
📝 services/scheduler/internal/types.go (+2 -1)
📝 services/shared/config/config.go (+23 -0)
📝 services/shared/config/config_test.go (+65 -0)

📄 Description

Summary

add a built-in least_loaded scheduler strategy;
rank nodes by projected CPU/memory allocation pressure using heartbeat snapshots and cold-sandbox resource hints;
use starting, running, and paused sandbox counts as tie-breakers;
round-robin equally loaded candidates to avoid request concentration between heartbeats;
reserve projected placements atomically so concurrent requests observe in-flight selections;
order heartbeats with a scheduler-local generation, reconcile successful creates and running resource allocations independently, and provide a configurable conservative expiry for unconfirmed placements;
reserve only requests carrying a sandbox-creation hint;
expose the strategy through scheduler config and Prometheus labels;
document fallback behavior for nodes without usable heartbeat capacity.

Motivation

The scheduler already passes RichNode heartbeat snapshots and structured
ScheduleRequestHint values to every strategy, but the current built-in
strategies (round_robin and random) do not use either signal. On
heterogeneous clusters, round-robin assigns the same number of sandboxes to
small and large nodes and can create severe normalized load skew.

This PR provides a general load-aware fallback that can also be reused by the
cache-locality work proposed in #15.

Selection model

For each eligible node:

cpu_pressure = (allocated_cpu + paused_allocated_cpu + requested_cpu) / cpu_capacity
memory_pressure = (allocated_memory + paused_allocated_memory + requested_memory) / memory_capacity
pressure = max(cpu_pressure, memory_pressure)

The request projection is available for /sandboxes-cold; other request types
use the current allocation snapshot.

Candidates are ordered by:

usable observed capacity before unknown capacity;
lower projected pressure;
fewer starting sandboxes;
fewer running sandboxes;
fewer paused sandboxes.

Equal candidates are selected round-robin. For requests carrying a
sandbox-creation hint, selection and reservation happen under one strategy
mutex. Subsequent requests include pending CPU, memory, and sandbox-count
reservations in their projected load. Ordinary read/list routing does not
reserve capacity. Creation candidates whose active+paused allocation plus the
request and pending reservations exceeds advertised capacity are excluded; if
all candidates are full, scheduling returns no nodes. Partial capacity
snapshots retain sandbox counts for fallback ranking. Newer heartbeats are
detected with a scheduler-local receipt
generation rather than the node wall clock. The monotonic create_successes
counter reconciles projected sandbox count independently from compatible
running CPU/memory allocation deltas, so a sandbox entering starting does not
release its reservation early. Resource deltas apply only to reservations that
predate that heartbeat and already own a create-success acknowledgement;
acknowledgements are never transferred between differently sized reservations.
CPU and memory acknowledgement are tracked independently, so eventually
consistent fields can reconcile across heartbeats without carrying generic
credit into later reservations. Unmatched delta is discarded instead of
leaking into later selections. Aggregate create_fails changes do not release
reservations because they cannot identify which request failed; without a
correlated outcome, reservations remain conservative until a compatible
allocation update or TTL. Reconciliation is linear in pending reservations.
Requests with no observed outcome use the configurable
scheduler.placement_reservation_ttl, which defaults to 10 minutes so
operators can cover their maximum queueing, creation, and heartbeat
acknowledgement delay.

When a cold-sandbox request omits CPU or memory, the node applies its locally
configured default. That default is not currently reported in NodeSnapshot,
so the scheduler reserves the sandbox count but cannot project the omitted
resource dimension. Template-based NewSandbox requests likewise lack resolved
CPU/memory hints; they are conservatively rejected when either known node
dimension is already full.

An explicit request-level reservation lifecycle, including confirm/cancel,
shared replica ownership, and template-resource resolution, is proposed in
#90.

Cluster validation

Validated on three 192-logical-CPU Intel Xeon Platinum 8575C nodes:

On lingjun-099, the final reservation-aware implementation selects among 1000
candidates in approximately 54.3 µs/op with 145–146 B/op, 0 allocs/op. The original
round-robin baseline is 7.926 ns/op.

In a replay with 16/64/192-CPU nodes and 300 requests of 2 CPU / 4 GiB:

peak allocation pressure: round_robin=12.5000 least_loaded=2.2188

The maximum normalized pressure decreased by 82.25%.

Verification

go test ./...
go test -race ./scheduler/internal
go vet ./...
git diff --check

Scope

This PR intentionally does not:

add cache inventory or locality scoring;
change the existing hard resource filters;
introduce configurable scoring weights;
add the cross-service reservation-token lifecycle proposed in #90.

Those can be discussed separately under #15 and #90.

_{🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.}

## 📋 Pull Request Information **Original PR:** https://github.com/kvcache-ai/AgentENV/pull/27 **Author:** [@catyans](https://github.com/catyans) **Created:** 7/28/2026 **Status:** ❌ Closed **Base:** `main` ← **Head:** `feat/least-loaded-scheduler` --- ### 📝 Commits (10+) - [`46403a4`](https://github.com/kvcache-ai/AgentENV/commit/46403a4fde1d2db3bfff1cfea820fe4710f5f617) feat(scheduler): add projected least-loaded strategy - [`13a53a0`](https://github.com/kvcache-ai/AgentENV/commit/13a53a085341538c64440c7f5115aaa82e8bec05) fix(scheduler): require capacity for requested resources - [`f288cd4`](https://github.com/kvcache-ai/AgentENV/commit/f288cd432f50f5559051046ed3e19d95e2f669c1) fix(scheduler): reserve projected placements - [`0679b78`](https://github.com/kvcache-ai/AgentENV/commit/0679b781aff8129f65b1e69d8fa6cd6851c07838) docs(scheduler): explain placement reservations - [`148a982`](https://github.com/kvcache-ai/AgentENV/commit/148a982a751b554abd04210ca0de0f6963cc37ec) fix(scheduler): reconcile reserved resources from allocation - [`5d0addf`](https://github.com/kvcache-ai/AgentENV/commit/5d0addf6a389233eab453e941a5a9339aa39cf4b) refactor(scheduler): scope least-loaded reservations - [`a493491`](https://github.com/kvcache-ai/AgentENV/commit/a493491c4c049cfae86156045577e302d3ce2c05) fix(scheduler): reconcile on heartbeat generations - [`121d728`](https://github.com/kvcache-ai/AgentENV/commit/121d728dfeea901bd41daf5b241821822e1be902) fix(scheduler): bound conservative reservation cleanup - [`85ad4eb`](https://github.com/kvcache-ai/AgentENV/commit/85ad4eb74d46fcfd23e3a34f885626d69bf43d3d) fix(scheduler): reconcile failed placements - [`82b9a3c`](https://github.com/kvcache-ai/AgentENV/commit/82b9a3cdceb395116cb7ef2c167dcf780351d615) fix(scheduler): reconcile resource dimensions independently ### 📊 Changes **14 files changed** (+1354 additions, -11 deletions) <details> <summary>View changed files</summary> 📝 `deploy/docker/config/default.json` (+1 -0) 📝 `services/README.md` (+34 -2) 📝 `services/config/local.json` (+1 -0) 📝 `services/scheduler/cmd/main.go` (+4 -1) ➕ `services/scheduler/internal/least_loaded.go` (+433 -0) ➕ `services/scheduler/internal/least_loaded_test.go` (+713 -0) 📝 `services/scheduler/internal/metrics.go` (+2 -0) 📝 `services/scheduler/internal/node_registry.go` (+16 -3) 📝 `services/scheduler/internal/node_registry_test.go` (+32 -0) 📝 `services/scheduler/internal/service.go` (+4 -2) 📝 `services/scheduler/internal/strategy.go` (+24 -2) 📝 `services/scheduler/internal/types.go` (+2 -1) 📝 `services/shared/config/config.go` (+23 -0) 📝 `services/shared/config/config_test.go` (+65 -0) </details> ### 📄 Description ## Summary - add a built-in `least_loaded` scheduler strategy; - rank nodes by projected CPU/memory allocation pressure using heartbeat snapshots and cold-sandbox resource hints; - use starting, running, and paused sandbox counts as tie-breakers; - round-robin equally loaded candidates to avoid request concentration between heartbeats; - reserve projected placements atomically so concurrent requests observe in-flight selections; - order heartbeats with a scheduler-local generation, reconcile successful creates and running resource allocations independently, and provide a configurable conservative expiry for unconfirmed placements; - reserve only requests carrying a sandbox-creation hint; - expose the strategy through scheduler config and Prometheus labels; - document fallback behavior for nodes without usable heartbeat capacity. ## Motivation The scheduler already passes `RichNode` heartbeat snapshots and structured `ScheduleRequestHint` values to every strategy, but the current built-in strategies (`round_robin` and `random`) do not use either signal. On heterogeneous clusters, round-robin assigns the same number of sandboxes to small and large nodes and can create severe normalized load skew. This PR provides a general load-aware fallback that can also be reused by the cache-locality work proposed in #15. ## Selection model For each eligible node: ```text cpu_pressure = (allocated_cpu + paused_allocated_cpu + requested_cpu) / cpu_capacity memory_pressure = (allocated_memory + paused_allocated_memory + requested_memory) / memory_capacity pressure = max(cpu_pressure, memory_pressure) ``` The request projection is available for `/sandboxes-cold`; other request types use the current allocation snapshot. Candidates are ordered by: 1. usable observed capacity before unknown capacity; 2. lower projected pressure; 3. fewer starting sandboxes; 4. fewer running sandboxes; 5. fewer paused sandboxes. Equal candidates are selected round-robin. For requests carrying a sandbox-creation hint, selection and reservation happen under one strategy mutex. Subsequent requests include pending CPU, memory, and sandbox-count reservations in their projected load. Ordinary read/list routing does not reserve capacity. Creation candidates whose active+paused allocation plus the request and pending reservations exceeds advertised capacity are excluded; if all candidates are full, scheduling returns no nodes. Partial capacity snapshots retain sandbox counts for fallback ranking. Newer heartbeats are detected with a scheduler-local receipt generation rather than the node wall clock. The monotonic `create_successes` counter reconciles projected sandbox count independently from compatible running CPU/memory allocation deltas, so a sandbox entering `starting` does not release its reservation early. Resource deltas apply only to reservations that predate that heartbeat and already own a create-success acknowledgement; acknowledgements are never transferred between differently sized reservations. CPU and memory acknowledgement are tracked independently, so eventually consistent fields can reconcile across heartbeats without carrying generic credit into later reservations. Unmatched delta is discarded instead of leaking into later selections. Aggregate `create_fails` changes do not release reservations because they cannot identify which request failed; without a correlated outcome, reservations remain conservative until a compatible allocation update or TTL. Reconciliation is linear in pending reservations. Requests with no observed outcome use the configurable `scheduler.placement_reservation_ttl`, which defaults to 10 minutes so operators can cover their maximum queueing, creation, and heartbeat acknowledgement delay. When a cold-sandbox request omits CPU or memory, the node applies its locally configured default. That default is not currently reported in `NodeSnapshot`, so the scheduler reserves the sandbox count but cannot project the omitted resource dimension. Template-based `NewSandbox` requests likewise lack resolved CPU/memory hints; they are conservatively rejected when either known node dimension is already full. An explicit request-level reservation lifecycle, including confirm/cancel, shared replica ownership, and template-resource resolution, is proposed in #90. ## Cluster validation Validated on three 192-logical-CPU Intel Xeon Platinum 8575C nodes: On lingjun-099, the final reservation-aware implementation selects among 1000 candidates in approximately `54.3 µs/op` with `145–146 B/op, 0 allocs/op`. The original round-robin baseline is `7.926 ns/op`. In a replay with 16/64/192-CPU nodes and 300 requests of 2 CPU / 4 GiB: ```text peak allocation pressure: round_robin=12.5000 least_loaded=2.2188 ``` The maximum normalized pressure decreased by 82.25%. ## Verification ```text go test ./... go test -race ./scheduler/internal go vet ./... git diff --check ``` ## Scope This PR intentionally does not: - add cache inventory or locality scoring; - change the existing hard resource filters; - introduce configurable scoring weights; - add the cross-service reservation-token lifecycle proposed in #90. Those can be discussed separately under #15 and #90. --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>

bsakaguchi

2026-10-29 14:19:58 +00:00