Add least_load Proxy Instance selection strategy and document strategy options

[zhy1658858023]

Background

Resource metrics are currently mainly used for observability. They are reported through Proxy-local Instance state, queue snapshots, and pool_resource, but they are not yet used for Proxy-side Instance routing decisions.

The next step is to introduce a first resource-aware Instance selection strategy on the Proxy data plane. This issue should add a least_load strategy that can run side by side with the existing round_robin strategy.

Current code already has a Proxy-side strategy interface and factory:

proxy/strategy/base.py
proxy/strategy/round_robin.py
proxy/strategy/factory.py

proxy/proxy.py reads PROXY_INSTANCE_STRATEGY, defaulting to round_robin, and builds the data-plane strategy through build_instance_strategy(...).

Goal

Add a new Proxy-side Instance selection strategy:

least_load

The strategy should select the alive Instance with the lowest observed load, using safe runtime fields that already exist in Proxy memory.

It must coexist with round_robin and be selectable through the same configuration mechanism.

Branch hygiene

Follow doc/codex_workflow.md if present.

Start from latest origin/main and use a fresh branch for this issue. Do not continue from previous Codex branches or include previous unmerged PR changes.

Suggested branch name:

codex/issue-115-least-load-instance-strategy

Scope

Expected files may include:

proxy/strategy/least_load.py
proxy/strategy/factory.py
proxy/strategy/__init__.py
proxy/README.md
README.md
test/demo_proxy.py

Only modify files that are necessary for adding the strategy and documenting/selecting it.

Strategy behavior

Selection candidates

The strategy input should remain the same as the existing strategy contract:

select(instances: List[InstanceLike], hint: Optional[Any] = None) -> InstanceLike

It should assume instances is already the current live list from InstancePool.list(include_dead=False).

If instances is empty, preserve the existing behavior style and raise RuntimeError("no instances").

Load score

Implement a deterministic load score for each Instance.

Preferred scoring order:

1. Use InstanceInfo.load.inflight when available.
2. Use InstanceInfo.load.qps_1m as a secondary signal when available.
3. Use queue-depth hint if a caller passes a safe hint containing per-instance queue depths.
4. If no load data is available for an Instance, treat it as unknown and avoid making misleading assumptions.

A practical initial score can be:

score = known_inflight_or_default + small_qps_weight * known_qps + queue_depth_weight * known_queue_depth

But keep the first implementation simple and explain the exact score in comments/doc.

Unknown metrics semantics

Do not treat unknown load as a real zero.

Recommended behavior:

• If at least one candidate has known load data, prefer candidates with known load data and compare by score.
• If all candidates have unknown load data, fall back to round-robin behavior to avoid always picking the first Instance.
• For ties, use round-robin tie-breaking among equally scored candidates.

This keeps least_load stable before all load metrics are fully wired.

Queue pressure integration

This issue should be the first step only.

Use current Proxy-side fields where safe. Do not require Scheduler-level pool_resource to drive per-Instance routing yet, because pool_resource is a coarse pool-level summary.

If queue-depth data is not available at the per-Instance strategy call site, keep queue integration optional and leave a clear TODO. Do not add invasive data-plane rewiring just to pass queue details.

Acceptable minimal implementation:

• least_load uses InstanceInfo.load.inflight / qps_1m when present.
• unknown load falls back to round-robin.
• queue-depth hints are supported only if naturally available without changing request flow.

Factory and aliases

Update proxy/strategy/factory.py so the following names work:

least_load
least-load
ll

Existing aliases for round_robin must continue to work:

round_robin
round-robin
rr

Do not change the default strategy. Default should remain round_robin.

Runtime configuration

The strategy must remain selectable via the existing Proxy configuration path:

PROXY_INSTANCE_STRATEGY=least_load

or demo CLI if test/demo_proxy.py exposes --strategy.

Example expected commands:

python3 test/demo_proxy.py \
  --host 127.0.0.1 \
  --port 8001 \
  --strategy least_load \
  --injection-strategy iws

and/or:

PROXY_INSTANCE_STRATEGY=least_load python3 test/demo_proxy.py

Keep round_robin examples working.

Documentation requirements

Update README documentation to show the new strategy option.

Also add a dedicated subsection for supported Proxy Instance selection strategies.

Suggested structure:

## Proxy Instance selection strategies

CacheRoute currently supports the following Proxy-side Instance selection strategies:

| Strategy | Alias | Description | Status |
| --- | --- | --- | --- |
| `round_robin` | `rr`, `round-robin` | Rotates across alive Instances in order. | Default |
| `least_load` | `ll`, `least-load` | Chooses the alive Instance with the lowest known Proxy-side load score; falls back to round-robin when load is unknown. | Experimental |

Planned strategies:

- `kv_aware`: choose Instances based on KVCache locality / reuse potential.

The README should also show how to select the strategy from CLI/env.

Non-goals

Do not implement yet:

• Scheduler resource-aware routing
• Scheduler Proxy selection based on pool_resource
• KV-aware Instance routing
• KDN-aware routing
• KVCache locality scoring
• changes to IWS injection logic
• changes to request forwarding semantics
• changes to Resource Agent sampling
• changes to pool_resource schema unless strictly needed for documentation

This issue is only about adding one Proxy-side Instance strategy and documenting the strategy options.

Suggested implementation notes

A clean implementation could be:

1. Add proxy/strategy/least_load.py.
2. Implement LeastLoadStrategy(BaseInstanceStrategy).
3. Internally keep a RoundRobinStrategy instance for fallback and tie-breaking.
4. In select(...), compute scores only from fields actually present on each InstanceInfo object.
5. Use fallback round-robin if all candidates have unknown load.
6. Update build_instance_strategy(...) aliases.
7. Update README / proxy README / demo help text as needed.

Pseudo-behavior:

known = []
unknown = []
for instance in instances:
    score = compute_score(instance)
    if score is None:
        unknown.append(instance)
    else:
        known.append((score, instance))

if known:
    min_score = min(score for score, _ in known)
    ties = [it for score, it in known if score == min_score]
    return round_robin_tie_breaker.select(ties)

return round_robin_fallback.select(instances)

compute_score() should return None when all relevant load fields are unavailable, not 0.

Validation plan

Compile check

PYTHONDONTWRITEBYTECODE=1 python3 -m py_compile \
  proxy/strategy/base.py \
  proxy/strategy/round_robin.py \
  proxy/strategy/factory.py \
  proxy/strategy/least_load.py \
  proxy/proxy.py \
  test/demo_proxy.py

Factory smoke test

python3 - <<'PY'
from proxy.strategy.factory import build_instance_strategy

for name in ["round_robin", "round-robin", "rr", "least_load", "least-load", "ll"]:
    s = build_instance_strategy(name)
    print(name, "->", s.name)
PY

Expected:

round_robin -> round_robin
round-robin -> round_robin
rr -> round_robin
least_load -> least_load
least-load -> least_load
ll -> least_load

Strategy behavior smoke test

Create small fake instances with load.inflight and verify:

• lower inflight wins
• ties do not always select the same first item
• all-unknown load falls back to round-robin
• empty list raises RuntimeError("no instances")

Runtime smoke test

Start Proxy with round robin:

python3 test/demo_proxy.py --strategy round_robin

Start Proxy with least load:

python3 test/demo_proxy.py --strategy least_load

Both should start successfully and log the selected instance strategy.

Acceptance criteria

• round_robin remains the default and continues to work.
• least_load can be selected through PROXY_INSTANCE_STRATEGY=least_load and demo CLI --strategy least_load if available.
• least_load does not treat unknown metrics as real zero.
• least_load falls back to round-robin when all load metrics are unknown.
• Tie-breaking among equal least-load candidates is fair enough and does not always pick the first item.
• README has a dedicated Proxy Instance selection strategies subsection.
• README documents round_robin, least_load, aliases, and planned kv_aware.
• No Scheduler routing, KDN, KVCache, IWS, Resource Agent, or request forwarding behavior is changed.