Walkthrough: Distributed Rate Limiter

A rate limiter caps how many requests a client can make in a time window, and rejects the rest with HTTP 429 ("Too Many Requests"). It protects your backend from abuse, buggy clients, and traffic stampedes. This is both a standalone interview question and a component you should mention at the gateway in almost any other design — so it pays to know it cold.

Step 1: Requirements

Functional ("users should be able to..."):

1. Limit requests per client per rule — e.g., 100 requests/minute per user for a given endpoint.
2. Rejected requests get a 429 response with a Retry-After header telling the client when to try again.
3. Rules are configurable per endpoint by the platform team, without redeploying.

Non-functional ("the system should be..."), quantified:

• Add under 10ms of latency per request — the limiter sits on every request, so it cannot be slow.
• Handle ~1M checks/second across the whole API.
• Be highly available — and we must decide what happens when the limiter itself is down (more on that in the deep dives).

Step 2: Core entities

Small list, shared vocabulary: Rule (endpoint, limit, window), Client identity (user ID, API key, or IP — pick per rule), and Counter state (the running count or bucket per client-rule pair).

Step 3: Interface

The check itself is not a public REST API — it is middleware inside the API gateway (the front door that already does auth and routing). The internal contract is one function:

is_allowed(client_id, rule) -> allow | deny(retry_after_seconds)

Admins manage rules through a normal REST API, and gateways pick up rule changes by polling a config store every ~30 seconds (or via pub/sub push).

Step 4: High-level design

Client → load balancer → API gateway (limiter middleware) → backend services. The counter state lives in Redis (an in-memory data store with ~1ms reads).

Why centralized state? You run many gateway instances. If each kept counts in its own memory, a client could send 100 requests to each of 10 gateways and get 10x its limit. Every gateway must read and update the same counter, so the state moves to a shared Redis.

Deep dive 1: Which algorithm?

Token bucket is the answer to lead with: it allows short bursts up to the bucket capacity B while enforcing a sustained rate R, and it needs only two numbers per client — the token count and the last-refill timestamp. Say those trade-offs out loud; naming one algorithm well beats listing five shallowly.

Deep dive 2: The race condition

The naive Redis flow is: GET the count, decide, SET the new count. Two gateways can both GET "1 token left" at the same moment and both allow — the limit leaks. The fix is to make check-and-update atomic (one indivisible operation). Redis runs Lua scripts atomically on its single-threaded core:

local tokens = tonumber(redis.call('GET', KEYS[1]) or capacity)
-- refill based on elapsed time, then:
if tokens >= 1 then
  redis.call('SET', KEYS[1], tokens - 1)
  return 1  -- allow
end
return 0    -- deny

"Move the check into a Lua script so it's atomic" is exactly the sentence interviewers want to hear.

Deep dive 3: Fail-open vs fail-closed

What if Redis is down? Fail-open means allow all requests: users are unaffected, but you have zero protection during the outage. Fail-closed means deny all requests: backends stay protected, but you have just turned a cache outage into a full API outage. There is no universally right answer — fail-open is common for consumer products (with loud alerting), fail-closed makes sense when the backend genuinely cannot survive unthrottled load. Present both and pick one for this system with a reason.

Deep dive 4: Scale and latency

Do the math when it matters: 1M checks/sec against a single Redis instance capped around 50–100k ops/sec means one node is not enough. Shard Redis by client ID using consistent hashing (a ring-based scheme where adding a node only moves ~1/N of keys). A given client's counters always land on the same shard, so no check ever spans shards.

For the <10ms budget: a Redis hit is ~1ms, so keep Redis in the same region as the gateways and reuse pooled connections instead of opening one per request.

One more probe to expect: a single huge client makes one shard hot. Options: give the biggest clients dedicated shards, or let gateways cache that client's verdict locally for a second — accepting slight over-admission for lower load.

Wrap-up

Recap against requirements: limits enforced accurately via atomic Lua on sharded Redis; 429 + Retry-After handled at the gateway; rules hot-reload from a config store; ~1ms checks fit the 10ms budget; and we made an explicit fail-open call with alerting. With more time: per-endpoint burst tuning and better hot-client isolation.