Rate Limiter

Interview scope and guarantees

Enforce per-user, per-tenant, and endpoint quotas with explicit burst behavior. Decide whether quotas are strict globally or approximate across regions. Return a useful retry hint without consuming unbounded memory for attacker-generated identities.

Capacity worksheet

Assume 100,000 requests/s and 2 million active bucket keys. At 100 bytes of logical state per key, raw state is 200 MB; allocator and replication overhead raise it. A network round trip to a central limiter can dominate a fast API, so distinguish edge protection from strict business quotas.

Concrete API contract

checkAndConsume {principal,policy,cost,requestId?} -> {allowed,remaining,retryAfter}
HTTP 429 for exceeded client quota
HTTP 503 for service overload when retry is appropriate
Policy versions are distributed separately from counters.

Data model and access paths

bucket(principal,policy,tokens,last_refill,policy_version)
policy(id,capacity,refill_rate,scope,fail_behavior)
lease(region,policy,allocated_tokens,expires_at) for regional token allocation

Evolve a solution and explain each change

Figure — Three architecture decisions for Rate Limiter, including the pressure each introduces.

Step 1: One atomic bucket

Refill tokens from elapsed time and deduct the request cost atomically. Independent workers with separate buckets multiply the allowance.

Step 2: Share authority

Route a key to a shared owner or atomic store operation; calculate retry time. That authority adds latency and can become unavailable.

Step 3: Choose partition behavior

Use bounded local allocations or fail-open/fail-closed according to the protected resource. Approximate availability spends a stated overshoot budget.

Responsibility overview

Figure — Connected responsibilities for Rate Limiter. Trace the authoritative and derived paths separately.

Worked end-to-end scenario

A tenant has capacity 100 and refill rate 10 tokens/s. After a burst consumes all tokens, a one-token request 50 ms later has only 0.5 token available and is rejected. At 100 ms it can succeed. Four API replicas must not each mint 100 tokens for that tenant. Put refill and consumption in one atomic operation on the tenant key or assign bounded local token leases. If the shared store fails, an expensive payment endpoint may reject while a low-risk read endpoint permits limited traffic. Explain the policy by endpoint rather than calling every outage fail-open.

Why these access paths matter

Key by the actual limiting dimension: tenant, endpoint, user, IP, or a defined combination. IP-only limits penalize shared networks and miss rotating clients. Use server time or monotonic elapsed-time handling consistently; clamp negative elapsed time. TTL removes idle bucket records but must not reset an active account’s quota unexpectedly.

Build the baseline first

1. Request → identity and policy → atomic bucket update.
2. Allowed → backend; denied → retry hint.
3. Idle bucket → expiry → bounded state cleanup.

Evolve the design under load

1. Edge local bucket → coarse abuse protection.
2. Regional token leases → bounded global allocation.
3. Strict quota path → authoritative conditional consumption.

Defend the hardest decision

A token bucket with capacity 20 and refill 5/s allows a burst of 20 then about 5/s sustained. At each atomic check, compute min(capacity, oldTokens + elapsed × rate), then subtract request cost only if enough tokens remain. A read followed by a separate write is unsafe under concurrency. Fixed windows are simpler but allow two bursts around a boundary; sliding logs are more exact but store more events.

Failure and recovery analysis

If Redis fails, fail-open may protect availability but violate a paid quota; fail-closed may break critical user requests. Define this per policy, not globally. Independent regional limits can overshoot a global quota. Token allocations make the overshoot or unused capacity explicit, while strict central coordination increases latency and reduces partition availability.

Security and privacy boundary

Use verified identity and tenant boundaries; trusting a client-supplied user header makes per-user limits bypassable.

Interview follow-ups with reasoning

Question: How do retries affect billing quotas?

Question: How do you prevent key explosion?

Question: How do weighted operations work?

Operate and verify the design

Allowed/denied rates by policy, decision latency, key cardinality and fail-open usage.

Partition regional limiters and quantify the maximum permitted overshoot under the chosen allocation policy.

A second scenario to test transfer

A bucket holds 20 tokens and refills at 5/s. A request costs 3 tokens. An atomic operation refills according to elapsed server time, subtracts 3, and returns the remaining budget. Two concurrent requests cannot both spend the same final tokens. A regional lease of 10 tokens can serve locally, but the global contract must account for those reserved tokens.

One tenant sends through three regions, each with a local cache of the same 100/minute quota. What violation is possible, and how could leased tokens bound it?

Compare alternatives

A design-changing exercise

A token bucket with 100 capacity and 10/s refill permits 100 instant requests. Is that a bug?

Design workshop: one atomic decision

Core scope is tenant/API-key admission with weighted request costs; abuse detection and billing are separate. Assume a two-millisecond local decision budget, bounded bursts and an explicit outage policy per route. A financial write fails closed or uses a genuinely reserved local budget; a public read may fail open with a measured overload allowance.

A token bucket has capacity B, refill rate r tokens/s, balance t and last timestamp. Compute t_new=min(B,t+r×max(0,now−last)). Admit only if t_new≥cost, then subtract cost. If rejected, retry delay is (cost−t_new)/r for positive r. Reject cost>B as an unsatisfiable policy, rather than returning an endless retry loop. The entire read/refill/check/debit/write occurs on one authority.

-- Teaching Lua sketch; validate policy arguments before calling.
local tm = redis.call('TIME')
local now = tonumber(tm[1]) + tonumber(tm[2]) / 1000000
local state = redis.call('HMGET', KEYS[1], 'tokens', 'last')
local cap, rate, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local old = tonumber(state[1]) or cap
local last = tonumber(state[2]) or now
local effective = math.max(now, last)
local tokens = math.min(cap, old + (effective-last)*rate)
local allowed = tokens >= cost and cost <= cap
if allowed then tokens = tokens-cost end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'last', effective)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap/rate*1000)+1000)
return {allowed and 1 or 0, math.floor(tokens*1000)}

This sketch assumes positive refill and bounded integer-scaled return values; handle zero-rate policies separately. Expiring idle state is safe only once elapsed time would have refilled the bucket. Redis atomicity protects concurrent commands, but an asynchronously promoted replica can lose prior debits. Decide whether that small overshoot is permitted; if not, choose stronger durable quota authority rather than claiming Lua removes failover loss.

Figure — Token bucket with B=20, r=5/s, cost=3.

Fixed windows can admit 100 requests just before a boundary and another 100 just after it. A sliding log removes timestamps older than the window and counts exactly within that definition but stores per-request state. Sliding counters approximate the previous/current windows and need a stated boundary error. A token bucket controls long-run rate and a burst of B; it is not exactly a rolling-window count.

For global 100/minute admission, allocate disjoint window-scoped budgets: region A 40, B 35, C 25. The durable coordinator deducts leased tokens when issuing them. Regions never replenish independently; a disconnected region can spend only its remaining lease. Do not reissue an expired region's unreported tokens within the same accounting window: expiry does not prove the old owner did not spend them. Return unused tokens only through an atomic close with a fenced owner, or strand them until window reset.

Figure — Lease issuance preserves a global budget.

Hierarchical limits require tenant, route and user budgets. To guarantee all-or-none spending, place their state at the same owner and evaluate them in one atomic script/transaction; Redis Cluster keys must share a hash slot for a multi-key script. Otherwise describe conservative partial spending or a reservation protocol. At one million active keys and an illustrative 160 bytes/key, state alone is 160 MB before replication and allocator overhead. Watch decision latency, policy misses, rejected cost, lease utilization and overshoot separately.

Exercise: A loses contact after spending an unknown part of its 40-token lease. Can the coordinator issue 40 replacement tokens to B?

Redis atomic rate limiting supports the read/decide/update primitive; the lease protocol here is an application design.

Technical references

Redis atomic rate limiting.

PostgreSQL transaction isolation and concurrent updates.