System Design Patterns
Rate limiting
A noisy tenant scripts ChatGPT-style API calls, hammers a login form, or retries a failed checkout in a tight loop. Without a speed limit, one tenant or bot can starve everyone else and melt the database pool.
is that fair limit. Good design chooses an algorithm, a key (user, tenant, IP, ), and clear behavior, not silent drops.
Request journey
/
Stop volumetric abuse early.
API gateway
Per-key and per-route quotas.
App policy
User + route + method limits.
Data admission
Pools and timeouts as last gate.
Problem → naive → break
Problem: one tenant scripts ChatGPT-style API calls, a bot hammers login, or a mobile SDK retries checkout in a tight loop. Scarce capacity (DB pools, auth workers) must stay fair.
Naive move: "reject when the box is busy" with a local counter per process, or drop packets silently. Counterexample: 200 replicas each allow 100 req/s locally → 20k req/s admitted against a 2k/s product quota.
Break: local limits do not compose. Silent drops hide abuse from clients and ops. When clients retry without jitter, a brief overload becomes a synchronized retry storm (SRE cascading failure).
Correctness invariant (with error bound)
For every limit key k and window W, accepted requests satisfy accepted(k,W) ≤ limit(k,W) + ε, where ε is a declared error bound (for example instances × warm_tokens, clock-skew allowance, or regional reconciliation lag), not an accidental unbounded overshoot. Routes must document fail-open vs fail-closed when the counter store is unavailable.
What actually happens
Every protected request asks a counter: "May this key spend capacity now?" A refills steadily and allows short bursts; a softens fence-post spikes; a drains at a fixed rate when the downstream cannot handle spikes.
Across many app replicas, counters live in a shared low-latency store. The refill, cost check, and decrement must be atomic, or two requests can both spend the last token. When the limit hits, return with so honest clients back off.
Defense in depth matters: edge absorbs garbage, gateway enforces product tiers, the app applies fine-grained route policy, and the database keeps connection pools bounded. When the counter store dies, choose or from the risk of the route, not habit.
Try it: spend and refill a token bucket
This is one key and one process. Each allowed request costs one token. Tokens refill continuously at the rate you choose, up to capacity. Distributed limiters store the same state atomically in a shared store; the refill math is the same.
- Simulated time
- 0s
- Tokens now
- 5.00
- Allowed
- 0
- Rejected (429)
- 0
Token bucket
live state5.00 of 5 tokens · refill 2/s · 100% full
Recent decisions
newest last- No requests yet.
The bucket starts full. Send requests to spend tokens, then advance time to watch steady refill. Bursts are allowed until the bucket empties.
Burst then settle. Send ten requests with capacity five to see allowed traffic followed by 429 responses. Advance time and send again to show how refill restores burst headroom without raising the long-term average.
Model scope. No per-instance warm tokens, no sliding window, and no Redis latency. Real deployments add replication, fail-open versus fail-closed policy, and dimension keys such as tenant plus route.
How to choose a limiter
1. Do short bursts matter? Use a when APIs should allow a quick spike, then settle to an average rate.
2. Must boundaries stay fair? Prefer a over a when users game minute edges.
3. What fails when the store is down? Password reset and money paths lean ; public search may degrade with an edge cap instead.
Simple rule of thumb
Start report-only, publish headers, enforce low-risk endpoints, then widen by tenant tier. Prefer algorithms your store can run atomically; alert on rising 429 ratios. They often precede saturation.
In simple terms: protect scarce capacity with clear keys, clear status codes, and a rollback plan.
Intent and when it helps
Intent: keep scarce downstream capacity fair and available when demand exceeds supply.
When it solves real pain
Protect login, checkout, search, and paid API tiers from abusive spikes, hot tenants, retries, or scraper traffic.
When it adds complexity
Premature per-endpoint quotas create confusing support cases; distributed counters add latency and failure modes.
Algorithms
A token bucket stores a balance with a maximum capacity and a refill rate. With capacity 100 and refill 10 tokens/s, an idle client can send a burst of 100 unit-cost requests, then sustain roughly 10 requests/s as tokens return. For elapsed time Δt, refill by rate × Δt, cap at capacity, and deduct the request cost atomically. The capacity controls burst size; the refill rate controls long-term admission.
capacity = burst_allowance
rate = steady_tokens_per_sec
allow():
refill_by_elapsed_time()
if tokens >= 1:
tokens -= 1
return OK
return 429A sliding-window counter estimates usage over the most recent interval by combining the current bucket with a fraction of the previous one. Halfway through a minute, it might count all current-minute requests plus half the previous minute’s count. This assumes previous traffic was spread fairly evenly. A concentrated burst violates that assumption, so describe the method as an approximation and use an exact timestamp log when strict rolling-window enforcement is required.
estimate = prev_count * overlap_frac + curr_count
if estimate < limit: allowA fixed window resets a counter at an agreed boundary, such as the start of each minute. A client limited to 100 requests/minute could send 100 just before 12:01 and another 100 just after, producing 200 requests in a very short period. The implementation remains useful for coarse quotas, but it needs an additional burst or concurrency limit when downstream capacity cannot absorb that boundary effect.
A queue-based leaky bucket accepts work into a bounded queue and releases it at a chosen pace. This smooths downstream arrivals, but accepted work now experiences queueing delay. If the queue is full or the projected wait exceeds the caller’s deadline, reject the request rather than hiding an unbounded wait. Some implementations use the same name for a virtual scheduling calculation, so specify whether requests actually wait or are immediately admitted or denied.
Distributed coordination
-- Sketch: sorted-set sliding window in a counter store
-- ZREMRANGEBYSCORE old entries
-- ZCARD vs limit → ZADD new stamp if under capCapacity math
Token memory
Token bucket needs roughly one row per active key: key hash, token count, and last refill timestamp. 10M active users × 64B is about 640MB before indexes, replication, and allocator overhead.
Sliding log cost
Exact per-request logs are expensive: 1M keys × 100 events/window × 16B timestamp entries is about 1.6GB before metadata. Prefer counters unless exact fairness is required.
Counter QPS
If every request checks a central counter, limiter QPS equals protected request QPS. Use or sharded keys when the limiter itself approaches the hot path budget.
memory ~= active_keys * bytes_per_key * replication_factor
10_000_000 keys * 64B * 3 replicas ~= 1.92GB raw
counter_qps ~= protected_request_qps * checks_per_requestLimiter state model
State shape by algorithm
- Token bucket: one record per active key with token count and last refill timestamp.
- Fixed or sliding counter: one or two counters per key per window.
- Exact sliding log: one timestamp per accepted request inside the window.
- Local warm tokens: fewer central checks but temporary overrun during partitions.
Memory examples
With 64B per token-bucket key and 3 replicas: 10M keys ≈ 1.92GB raw, 50M keys ≈ 9.6GB, 100M keys ≈ 19.2GB before indexes and allocator overhead.
Exact logs grow faster: active_keys × events_per_window × bytes_per_event × replicas.
exact_log_memory ~= active_keys * events_per_window * bytes_per_event * replicas
1_000_000 keys * 100 events * 16B * 3 ~= 4.8GB raw
temporary_overrun <= app_instances * warm_tokens_per_key
200 instances * 50 warm_tokens = 10_000 extra acceptsLayers of defense
Client or bot
CDN or WAF
global limit
API gateway
API key limit
App
user + route limit
Database pool
admission; slow/saturated feeds back to app
Rejected requests return 429 + Retry-After to the client.
CDN / WAF
and controls stop geographic and volumetric abuse before origin.
API gateway
Per-key or per-route quotas, TLS termination, coarse auth.
Application
Fine-grained user + endpoint composite limits; expensive mutations tighter than reads.
Data tier
Connection pools, statement timeouts, admission control.
Partition keys
Strategies
- IP: watch NAT aggregation
- Authenticated user or tenant
- API key / registered client
- Composite user + route + method
Multi-window quotas
Multiple windows protect different resources: a per-second cap limits instantaneous load, while a daily quota controls total consumption. A request must satisfy every applicable rule before admission. Define how reservations are refunded if a later rule denies the request; otherwise unsuccessful attempts can accidentally consume a customer’s full quota. Charge expensive operations by estimated work units when one request can represent very different backend cost.
Multi-dimensional quotas and fail modes
Useful dimensions
Combine global, tenant, user, route, method, read/write class, and concurrency limits. Login may need IP + account + device signals so one carrier NAT does not block valid users.
Rollout order
Start report-only, publish headers, enforce low-risk endpoints, widen by tenant tier, then enable stricter write limits with rollback tied to 429 ratio and support tickets.
Counter store down
Choose fail-open for low-risk reads, fail-closed for money or abuse-heavy writes.
Clock skew
Prefer server-side time and bounded windows; alert on skew and impossible reset times.
Retries after 429
Require Retry-After and jitter so rejected clients do not form a second burst.
High-cardinality key attack
Cap new key creation and aggregate unknown callers before storing per-key state.
Regional partition
Local limits keep serving but can overrun global quota until reconciliation.
Hot tenant
Shard by tenant and route, then enforce fairness before datastore saturation.
Break the improved design: retry amplification
A correct limiter still fails the fleet if clients and middleboxes retry without budgets. This is the cascading-failure pattern from SRE practice.
t=0 Steady 2_000 QPS; token bucket limit 2_500/s per tenant tier t=30s Spike to 8_000 QPS → ~5_500/s get 429 + Retry-After: 1 t=31s Clients ignore Retry-After; retry immediately (no jitter) t=32s Gateway + app + worker each retry once → ~3× offered load on origin t=45s DB pool saturates; healthy tenants now fail too Outcome Limit held on paper; user SLI collapses from retry amplification
Error-bound worksheet
limit = 1000 req/min per API key
instances = 200
warm_tokens_per_lease = 20
ε_partition <= 200 * 20 = 4_000 extra accepts
# Document ε; shrink leases if product risk cannot tolerate it
retry_amplification ~= layers_that_retry * retries_per_layer
# Prefer one budget: client OR gateway OR app, not all threeAdaptive and prioritized shedding
Health-linked limits
A concurrency limit controls work currently in flight, which directly protects scarce workers and connections. A request-rate limit alone cannot do that when latency rises: at the same arrival rate, slower requests occupy more slots. An adaptive controller can cautiously increase concurrency while latency is healthy and reduce it after overload signals. Smooth the feedback and bound adjustments so noisy measurements do not make admission oscillate.
Fair queuing
Weight tenants so bulk jobs cannot starve checkout-class traffic during saturation.
Responses and clients
429 + metadata (common conventions)
HTTP/1.1 429 Too Many Requests
Retry-After: 30
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: <unix_ts>Client discipline
- Honor Retry-After and backoff with jitter
- Treat 429 as demand signal: avoid tight loops
- Use bulk endpoints where available
Product APIs (illustrative)
Payments platforms
Separate read/write quotas, idempotency keys for retries, readable limit headers: verify current docs per account mode.
Developer portals
REST-style and graph-style query complexity budgets differ; conditional requests may spare quota where supported.
How to talk about this in an interview
Pattern selection
Token bucket for burst tolerance, sliding window for fairer boundaries, leaky bucket for strict smoothing, concurrency limits for overloaded services.
Failure modes
Counter-store outage, clock skew, NAT fan-in, global counter hot keys, retry storms after 429, and fail-open vs fail-closed decisions.
Observability
Track allowed/denied counts by rule, top limited tenants, counter latency, 429 ratio, and downstream saturation before and after enforcement.
Rollout strategy
At millions of users, start in report-only mode, publish headers, alert on would-block traffic, then enforce narrow rules before broad tenant-wide caps. Roll out by endpoint and tenant tier with automatic rollback when 429s or downstream errors spike.
Production deep dive: distributed limiter control
One atomic serialization point
Refill-to-now, cap, cost check, decrement, and expiry must execute together. A read-then-write client loop can admit two requests from the same last token.
Local-plus-global leases
Lease small token batches to app instances. This removes a central round trip, but worst-case partition overshoot is instances × tokens_per_lease; size it from a product risk budget.
Fairness and hot keys
Apply hierarchical budgets (platform → tenant → route → user), weighted fair queues, and dedicated shards for globally hot policies. Do not split one strict counter unless you can merge it without overshoot.
Time and policy versions
Use the counter store's clock inside an atomic operation, not client clocks. Attach a policy version to decisions so a bad quota rollout can be identified and rolled back deterministically.
-- Atomic token-bucket sketch; execute on the counter owner
now = store_time_ms()
state = get(key) or { tokens = capacity, updated_at = now }
refilled = min(capacity, state.tokens + (now - state.updated_at) * rate_per_ms)
if refilled < request_cost then
return { allowed = false, retry_after_ms = ceil((request_cost - refilled) / rate_per_ms) }
end
put(key, { tokens = refilled - request_cost, updated_at = now }, idle_ttl)
return { allowed = true, remaining = floor(refilled - request_cost), policy_version = version }| Route | Counter-store outage | Why | Recovery signal |
|---|---|---|---|
| Password reset | Fail closed or tiny local budget | Abuse cost is higher than brief rejection | Store healthy + policy version caught up |
| Checkout submit | Conservative local emergency lease | Preserve revenue while bounding database load | Downstream saturation and overshoot reconciled |
| Public search | Edge cap + degrade expensive filters | Availability matters, but origin work must stay bounded | p99 and queue age below exit thresholds |
Failure timeline: hot key, Redis lag, fail-open flood
Distributed limiters still fail when one counter key melts Redis, replication lags, or fail-open admits a flood.
T+0 Global hot key tenant:acme saturates one Redis shard (p99 2ms → 80ms) T+45s Gateway timeouts on INCR; policy is fail-open for checkout T+50s Offered load 12k QPS passes unchecked; DB pool waits climb T+2m Replica lag on secondary counters → edge admits while primary denies T+4m Fail-open flood becomes origin outage; 429s arrive too late Outcome Limit held only when the counter path is healthy; document fail-open blast radius
Exercises
- Product quota is 1,000 req/min. You lease 25 warm tokens to each of 80 instances. What is ε, and is it acceptable for password-reset?
- Sketch a client that honors Retry-After with full jitter. Then show how three stacked retry layers without a shared budget recreate the t=32s timeline above.
- Counter store is down. Choose fail-open vs fail-closed for public search vs checkout submit, and name the recovery signal for each.
Primary references
Topic sources for rate limiting and client signaling, not generic system-design books.
Takeaway
Hold accepted ≤ limit + ε with a documented ε. Return 429 with Retry-After. Bound retries across layers or the limiter cannot save you from cascading overload.
Practice and further reading
Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.
Focus for this lesson: Protect scarce capacity with atomic policy, fair keys, local-plus-global control, bounded overshoot, hot-key mitigation, and explicit fail modes.
Explain the decision
How would you build a low-latency global limiter without making one counter store the bottleneck?
Read the reasoning
Lease small local token batches from an atomic global budget, cap per-instance overshoot, shard hot policies, version rules, and reconcile usage asynchronously.
Apply it to a production scenario
The global counter store becomes unreachable during checkout and password reset. Should both fail open?
Read one approach
No. Preserve checkout availability with a conservative local emergency budget, but fail closed or heavily constrain abuse-sensitive password reset; decide per route.
Work through the numbers
Two hundred app instances each hold 30 emergency tokens for one key. What is worst-case partition overshoot?
Read the worked calculation
Up to 6,000 accepts beyond the latest global view; lower batch size or scope local pools when that violates the abuse/capacity budget.
Reason through a failure
What invariant must an atomic token-bucket update preserve?
Read the recovery reasoning
For one policy key, refill-to-now and token consumption occur as one serialization point; tokens never go below zero or exceed bucket capacity.
Sources and further study
Continue with Logging & Monitoring.