Rate Limiting and Fair Scheduling
Rate limiting controls how much work a caller consumes over time; fair scheduling decides which eligible work runs next.
Rate Limiting and Fair Scheduling
Rate limiting controls how much work a caller consumes over time; fair scheduling decides which eligible work runs next. A token bucket stores capacity B and refills at rate r. It permits a burst up to B while limiting sustained rate to r. Fixed windows are simple but allow boundary bursts; sliding logs are precise but costly; sliding counters approximate. Distributed enforcement needs atomic state updates and a defined failure mode.
Mechanism and worked example
A bucket with capacity 10 and refill 2 tokens/s permits ten immediate requests, then sustains about two requests/s. For multi-tenant APIs, apply global safety cap, tenant quota and route-specific limits. Expensive endpoints may consume weighted tokens.
| Algorithm | Strength | Limitation |
|---|---|---|
| Token bucket | Burst plus sustained rate | Atomic refill/consume required |
| Leaky bucket | Smooth output rate | Can add queueing latency |
| Fixed window | Low state | Boundary bursts |
| Sliding log/counter | More precise rolling window | More storage or approximation |
Failure modes and operations
Non-atomic read/modify/write overspends under concurrency. Clock skew distorts refill. A single key can become hot. A limiter outage can fail open and invite abuse or fail closed and deny legitimate traffic. Rate limiting alone does not cap expensive concurrent work.
Trade-offs and design boundary
Token buckets permit bursts; strict smoothing costs coordination. Local limiters are fast but multiply capacity across instances. Centralized limiters coordinate better but add latency. Weighted cost is more accurate than one token per request.
Interview transfer exercise
Design tenant fairness when a tenant sends few but expensive queries. Combine request-rate budgets with database concurrency and query-cost limits.
Read the diagram
Request arrives with tenant identity → Atomic bucket admits or rejects → Eligible work enters bounded tenant queue → Fair scheduler selects within tenant budget
Design tenant fairness when a tenant sends few but expensive queries. Combine request-rate budgets with database concurrency and query-cost limits.
Your design draft
Clarify assumptions, explain your approach, and test the difficult cases. Save your draft, then compare it with the study notes.
Self-review checklist
Self-guided practice. Automated AI feedback and code execution are not connected.