DRR Algorithm

Control plane term: the control plane and GET /api/v1/fairshare/live expose share_score (served_tokens / weight). Lower score means more behind fair share and admitted next. This page explains the DRR lineage; day-to-day operations use Fairshare Engine terminology.

obleth's admission scheduler adapts Deficit Round Robin (DRR) to concurrent, token-measured requests instead of packet queues. The observable metric is share_score, not a per-tenant deficit counter.

Classic DRR

In the original DRR algorithm, each queue has a deficit counter. In each round, a queue can send up to quantum + deficit bytes. If it sends less, the remainder carries into the next round. Larger quanta produce proportionally more bandwidth while preserving starvation freedom.

obleth's adaptation

obleth applies the same fairness principle to admission. "Sending" means holding a concurrency permit for the duration of a request.

For each active tenant, obleth tracks served_tokens, the estimated token cost of admitted requests. The admission score is:

share_score = served_tokens / weight

When a concurrency slot opens, it goes to the queued tenant with the lowest share_score. A tenant with weight=500 gets roughly ten times the opportunity of one with weight=50 because its score grows ten times more slowly per token.

Hierarchical scheduling

With OBLETH_FAIRSHARE_ALGORITHM=hierarchical, obleth first partitions global concurrency among fairshare groups:

slots_for_group = floor(group_weight / sum(group_weights) * max_in_flight)

Fractional remainders are distributed largest-first so the total equals max_in_flight, and every active group gets at least one slot when max_in_flight is at least the number of active groups.

Each group's pool is then apportioned across that group's active tenants with the same largest-remainder split, weighted by tenant weight — so a boosted tenant keeps a larger slice inside a crowded group, and equal weights collapse to an even split. When a group is apportioned fewer slots than it has active tenants, the min-one guarantee does not apply and some tenants are capped at zero for that round.

Caps are ceilings on contended demand, not reservations: if no queued tenant is inside its group and tenant caps while the global pool still has a free slot, the scheduler lends the slot to a queued candidate rather than idling. Borrowed slots return as those requests finish.

Worked example

max_in_flight = 8
groups: prod (weight=500), dev (weight=50)
total_weight = 550

prod: floor(8 * 500 / 550) = floor(7.27) = 7
dev:  floor(8 *  50 / 550) = floor(0.72) = 0 -> bumped to 1
sum  = 8

The min-one guarantee means every active group eventually gets capacity.

Starvation freedom

Every tenant with a non-zero weight eventually gets admitted. The served counter grows for every tenant that gets slots. A low-weight tenant whose score is lowest will be selected once higher-weight tenants have received enough service to bring their scores above it.

Idle tenants are not in the queue, so they cannot bank unused credit. When they re-enter, they start from the current virtual-time baseline.

Scheduler loop

1. A request sends Ctl::Admit { req, respond, enqueued } to the scheduler channel.
2. If in_flight < max_in_flight, the permit is granted immediately.
3. Otherwise, the request is appended to the tenant's queue.
4. When an in-flight request completes, its permit sends Ctl::Release.
5. The scheduler picks the next tenant. Under weighted that is simply the queued tenant with the lowest served / weight. Under hierarchical it first narrows to the group with the lowest group served / group weight among eligible candidates, then picks the lowest served / weight tenant inside it.
6. The slot is granted with Admission::Queued, and served[tenant] += cost is updated.

All of this runs on a single async task, so admission order is deterministic and avoids lock races.

Observing it

obench seeds tenants across several fairshare groups so a run produces genuine cross-tenant contention, then drives load against them. It does not assert fairshare ratios — it prints a link to the control plane's Fairshare view, where you watch share_score, slot_cap, and borrowed move under load.

cargo build --release --manifest-path obench/Cargo.toml
./obench/target/release/obench --target demo --profile heavy --all

See Benchmark Suite (obench) for the full walkthrough.