Handle overload and fair scheduling: observe and experiment

Use the offline walkthrough to compare an accepted dispatch, admission rejection, and a started call with uncertain termination. The static lifecycle remains readable without scripting.

Sequence diagram. The durable job store and quota guard are separate local transactions in the exercise. A crash between reservation and execution can conservatively retain a slot; reconciliation is required. They are not advertised as one distributed transaction.

Under sustained equal-cost arrivals λ=10 jobs/s and capacity μ=6 jobs/s, unbounded backlog grows at λ−μ=4 jobs/s. Starting empty, a 12-job waiting buffer fills in roughly three seconds in the fluid approximation. Finite queues then force rejection or upstream waiting. A finite burst that ends can drain; do not apply this sustained-growth claim to every burst scenario.

In a stable regime, Little’s law relates average in-system count to throughput and mean time: L=λW. At an admitted 4 jobs/s and 1.5 seconds mean time in system, L≈6 jobs. It does not prove tail latency, fairness, or stability when offered arrivals exceed departures indefinitely. The intuition is how many items remain present while each spends time in the system; it is not a capacity generator.

If six jobs/s are possible under a request quota, 12 simultaneous calls each taking two seconds also provide only six jobs/s in an idealised occupancy model. A 10,000-token/s quota with 2,000 expected tokens/job further caps average token-feasible throughput near five jobs/s. Variable lengths, burst windows, and reservation rules can reduce it. Check request rate, token rate, concurrency, and remaining deadline independently.

A rough global waiting-time estimate at queue length Q is Q/μ under the assumed homogeneous service. A tenant with a 25% share of six jobs/s has nominal 1.5 jobs/s while all are backlogged; its own queue of six jobs represents roughly four seconds before additional service-time variation. This is a planning estimate, not a hard WRR latency bound, especially if non-preemptive long calls occupy slots.

Retries at multiple layers multiply rather than merely add. If three nested layers each make three attempts per parent attempt, one original can induce up to 3³=27 downstream attempts. Bound the total attempt budget and preserve stable keys. Backoff spreads timing; it does not make repeated side effects safe.

Open the fair-scheduling experiment. It varies policy, Tenant A burst (0–60 jobs), provider slots (1–6 one-second jobs), unsafe retry copies (0–2), and a common deadline (1–10 seconds). B and C each offer six jobs. All arrive at time zero in A-then-B-then-C insertion order. FIFO preserves that fixed arrival order. Priority serves B before C before A.

This is a simplified provider-call class, not a replacement for T18.3’s illustrative 20-second document preparation and 90-second durable-job deadline. Mixed production classes need separate cost/deadline analysis before mapping them to service shares.

Each tenant may queue at most 12 jobs. Excess is rejected before queueing. Every admitted job has the same one-second cost and common absolute deadline; a dispatch at second t completes at t+1. No work starts after expiry. Queues are sampled after each second’s service and deadline sweep over a ten-second horizon. The weights are fixed at 2:1:1, and empty tenant turns are skipped.

Default inputs are A=30, B=6, C=6, three slots, no retry copies, four-second deadline. Admitted work is 12+6+6=24. The service window permits at most 3×4=12 completions. Queue history for defaults is 21,18,15,0,0,0,0,0,0,0; the remaining 12 expire at time four. A scheduling policy changes allocation, not that bound.

“Unsafe retry copies” deliberately represents clients creating new operation identities, multiplying A’s offered work before admission. Correct same-key retries are deduplicated by the actual guard and must not become those copies. The simulator does not model real variable token cost, random arrival/service times, provider cancellation, dynamic weights, or a distributed scheduler. Its queue and deadline counts are exact only under its stated conventions.

Run this stage's Python lab in your terminal to see each idea in the stage hold. It needs Python 3.10 or later and nothing else: the standard library and SQLite only.

From the root of your local clone of the repository, run:

python3 10_AI_System_Design/stages/05-overload-fairness/labs/test_overload.py -v

-v prints one line per test, and each test name states one behaviour. Read a test, change one value in the lab code, predict which test fails, and run it again.

admission.py uses real SQLite transactions for shared fixture reservations, request/token buckets, per-tenant request buckets, and concurrency. scheduler.py independently computes finite-burst queues and service shares. Tests race concurrent reservation callers, separate request and token limits, refill logical buckets, reject conflicting/replayed keys, retain unknown slots, reject expired work, isolate a noisy tenant, compare four policies, exercise deadlines/empty queues/retry amplification, and integrate a grant with T18.3’s actual durable worker store.

Fixture defaults allow a two-request burst with one request credit/second refill, a 2,000-token burst with 1,000 token credits/second refill, and two simultaneous calls. These are local demonstration configurations, not vendor quotas. All gate instances sharing the store must use the same authoritative configuration and a consistent monotonic clock. Completed reservations release slots but do not refund consumed rate/token credits; unknown states deliberately have no automatic expiry/reconciliation method.

For build depth practice, make a call expire after reservation but before provider start. Explain which durable evidence would safely release its slot. Then inject loss after external start and show why that same release rule is unsafe. Do not “fix” saturation by deleting reservations. For design depth fairness, compare normalised shares with weights and explain why equal request counts do not prove equal compute allocation for mixed lengths.

A rejected client creates a new operation key and immediately retries twice. Is it helping recover service for the original request?

• At 10 arrivals and 6 completions a second, a 12-job buffer fills in about three seconds. Little's law, L=λW, relates average count, throughput and time in a stable system but proves nothing about tail latency, fairness or sustained overload.
• Rate, tokens and concurrency each cap throughput on their own. A 10,000-token/s quota at 2,000 tokens a job allows only about five jobs a second, and 12 slots of two-second calls give six.
• Three nested layers each making three attempts can turn one request into 3³=27 downstream attempts. Bound the total attempt budget and keep stable operation keys.
• In the noisy-tenant lab, three slots and a four-second deadline allow at most 12 completions under any policy. FIFO gives A all 12, WRR gives 6/3/3, and only adding slots raises the total.