Start practising

SYSTEM DESIGN · BUILDING BLOCKS · 11 OF 14

Rate Limiter as a Service: Rules, Redis, Failures and Regions

The rate limiter as a production component rather than an algorithm: where it runs, how rules are modelled and pushed, an atomic token bucket in Redis, the latency budget, sharding counters and hot keys, local-plus-global hybrids, fail-open versus fail-closed, limits across regions, concurrency limits and load shedding, client headers, and sizing memory and operations.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
1 / 15

Press play to hear the narration, or step through at your own pace.

Notes

Requirements

Start with requirements, as you would in the interview. Limit by API key, user, IP or route, with different rules per plan, changeable without a deploy. Each check should add less than a millisecond at p ninety-nine, handle a million checks a second across the fleet, and be accurate within a few percent. Clients should be told their limits. And the limiter must never be the reason the API is down.

Requirements
  • limit by API key, user, IP,
  • route, or a combination
  • rules per plan, change live
  • adds under ~1 ms at p99
  • 1M+ checks per second
  • accurate within a few %
  • tells clients the limit
  • never takes the API down

Placement

Where can it run? As a library inside each service, which adds no network hop but is hard to update across many languages. In the gateway or a sidecar proxy, the most common choice, one place for all traffic. Or as a separate limiter service that the gateway calls for each request, like Envoy's global rate limit service; that's clean but adds a network call of about a millisecond.

Where it can run
  • client library in each
  • service: no hop, hard to
  • update everywhere
  • gateway / sidecar: one
  • place, all languages (common)
  • separate limiter service:
  • gRPC call per request (Envoy
  • global rate limit service)
  • + ~0.5-1 ms per check

Rules

Model the rules as data. Each rule has a match, like route POST slash login or plan free, a key to count by, like IP or API key, and a limit with an optional burst. Store them in a rules service, push them to every limiter, and cache them in memory, so a request never waits on a rules lookup. Version them so a bad change can be rolled back in seconds.

Rule model
- match: {route: POST /login}
  key: ip
  limit: 5 per minute
- match: {plan: free}
  key: api_key
  limit: 60/min, burst 20
- match: {plan: pro}
  key: api_key
  limit: 1,000/min, burst 200

cached locally, versioned

The check

Here's the check itself, a token bucket stored as a small hash in Redis. A Lua script reads the token count and last refill time, adds the tokens earned since then up to the cap, takes one if available, writes back, and sets an expiry so idle keys disappear. Because Redis runs a script atomically, two gateways can't both take the last token. And it's one round trip, a few hundred microseconds inside a data centre.

Token bucket in Redis (Lua)
tokens, ts = HMGET key t ts
now = redis TIME
tokens = min(cap,
  tokens + (now - ts) * rate)
if tokens >= 1:
  tokens -= 1; allowed = 1
HSET key t tokens ts now
PEXPIRE key ttl
return allowed, tokens

one script = atomic, 1 RTT

Races

Two classic bugs. If the gateway reads the count, decides, then writes it back, two gateways can both read one remaining token and both allow. Do the whole read-modify-write inside the store, as one script. And if each gateway uses its own clock to compute refills, skew between machines leaks extra tokens, so use the store's clock. Also decide whether client retries should count twice.

Correctness traps
  • GET then SET from the app:
  • two gateways both read 1
  • token → both allow (race)
  • → do it in one script
  • clock skew between gateways:
  • use the store's clock
  • retries count twice: count
  • once per request id, or
  • accept it

Sharding state

One Redis shard handles maybe fifty to a hundred thousand script calls a second, so shard buckets by key across a cluster. The trap is a hot key: one enterprise customer making eighty thousand calls a second lands entirely on one shard. Split its bucket into eight sub-buckets, each with an eighth of the limit, and pick one at random per request. Or move that customer to the local approach on the next beat.

Scaling the store
  • shard by limit key (Redis
  • Cluster hashes the key)
  • one Redis shard: roughly
  • 50-100k script calls/s
  • hot key: one tenant at 80k/s
  • lands on one shard
  • → split its bucket into 8
  • sub-buckets of limit / 8
  • → or local pre-allocation

Local + global

At very high volume, a store call per request is too much. The hybrid approach: each gateway keeps a local bucket per key in memory and decides in microseconds. Every hundred milliseconds or so, it reports how much it used to the shared store and gets back the global remaining count. Store traffic drops by orders of magnitude. The cost is accuracy: the fleet can overshoot briefly, which is fine for quotas but not for login protection.

Hybrid limiting
  • each gateway keeps a local
  • bucket per key in memory
  • → decision in microseconds
  • every ~100 ms: report usage
  • to Redis, receive the global
  • remaining count
  • + far fewer store calls
  • - can overshoot briefly
  • (accept a few % error)

Failure handling

When the store is slow or down, the limiter must not become the outage. Give the check a tight timeout, a few milliseconds, behind a circuit breaker. For normal traffic, fail open, but fall back to a coarse per-instance limit so capacity is still protected. For security-sensitive routes like login, one-time passwords and payments, fail closed. Either way, alert that limiting is degraded.

When the store fails
  • tight timeout on the check
  • (e.g. 5 ms), circuit breaker
  • fail open: allow, but apply
  • a coarse per-instance limit
  • (protects capacity)
  • fail closed: login, OTP,
  • password reset, payments
  • alert: limiter degraded

Multiple regions

Across regions, a single global store would add a cross-ocean round trip to every request. Instead, split each limit between regions by their traffic share, say six hundred a minute in the US and four hundred in Europe, and rebalance the split every minute or so. Or replicate counters asynchronously between regions and accept brief overshoot. Exact global limits and low latency don't go together.

Limits across regions
  • one global Redis: +80 ms
  • cross-region per check → no
  • split quota: 1,000/min →
  • US 600, EU 400 by traffic
  • share; rebalance each minute
  • or async replicate counts
  • (CRDT counters) and accept
  • brief overshoot

Related limits

Two relatives worth mentioning. A concurrency limiter caps requests in flight rather than per second, which suits slow endpoints like exports or model calls where one request can take thirty seconds. And load shedding is adaptive: when the service itself is overloaded, measured by latency or queue depth, it drops the lowest-priority traffic first, regardless of quotas. Rate limits give fairness; these two protect capacity.

Rate vs concurrency limits
  • rate: N requests per second
  • concurrency: N in flight
  • (protects slow endpoints:
  • reports, exports, LLM calls)
  • load shedding: when the
  • service is overloaded, drop
  • low-priority traffic first
  • (adaptive, from latency or
  • queue depth)

Client contract

The client contract matters. Reject with 429 Too Many Requests and a Retry-After header. Send limit, remaining and reset headers on every response, not only rejections, so well-behaved clients slow down before they hit the wall. And log each rejection with the rule that fired, because the first support ticket will be 'why am I being limited?'

Response headers
HTTP/1.1 429 Too Many Requests
Retry-After: 12
RateLimit-Limit: 1000
RateLimit-Remaining: 0
RateLimit-Reset: 12

also on successful responses
so clients can pace
themselves
log every 429 with rule id

Sizing

Sizing. Ten million active keys at about a hundred bytes per bucket is roughly a gigabyte, tiny. Operations are what matter. Five hundred thousand checks a second at about sixty thousand script calls per shard is nine shards, so run twelve with replicas. Switch the heaviest keys to the hybrid approach and store traffic can fall to tens of thousands a second.

Sizing
10M active keys
× ~100 B per bucket (hash +
  key + overhead)
  ≈ 1 GB → tiny

500k checks/s at peak
÷ ~60k per shard
  ≈ 9 shards → run 12
  + replicas for failover

hybrid sync: 500k → ~20k/s

Say it like this

In the interview, cover rules as data, the gateway as the place it runs, a token bucket updated atomically in Redis with the store's clock, sharding by key with a plan for hot keys, fail open with local limits but fail closed for login, split quotas across regions, and 429 with rate limit headers. Then give the sizing: memory is small, operations decide the cluster.

In the interview
  • rules: match + key + limit
  • runs in the gateway
  • token bucket, Lua in Redis
  • (atomic, store clock)
  • sharded by key; hot keys
  • split or local
  • store down: fail open with
  • local limits; login fails
  • closed
  • regions: split quotas
  • 429 + RateLimit headers

Interview questions

Where would you place a rate limiter?

Usually in the API gateway or a sidecar proxy, so all traffic passes one enforcement point before doing expensive work, with counters in a shared low-latency store; a separate limiter service is an option when many gateways need one policy.

How do you avoid race conditions with many gateway instances?

Perform the read, decide and update in one atomic operation inside the store, such as a Redis Lua script or INCR with EXPIRE, and use the store's clock rather than each gateway's clock.

How do you handle a single very hot key in the limiter store?

Split its bucket into several sub-buckets with a share of the limit each on different shards and pick one per request, or enforce that key with local in-memory buckets that sync usage to the store periodically.

What happens if the limiter's Redis goes down?

Checks should time out within a few milliseconds behind a circuit breaker; most routes then fail open with a coarse per-instance limit, while sensitive routes like login and payments fail closed, and an alert fires.

How do you rate limit across multiple regions?

Avoid a synchronous global store; split each limit between regions according to traffic share and rebalance periodically, or replicate counters asynchronously and accept brief overshoot.

What is the difference between a rate limiter and a concurrency limiter?

A rate limiter caps requests per unit of time for fairness and quotas, while a concurrency limiter caps how many requests are in flight at once, which better protects slow or expensive endpoints.

How would you store rate limit rules?

As versioned configuration with a match condition, a key to count by and a limit with burst, held in a rules service and pushed to and cached by every limiter so checks never wait on a rules lookup.

How much memory does a rate limiter need?

Very little: about a hundred bytes per active key for a token bucket, so ten million active keys fit in around a gigabyte; operations per second, not memory, determine the number of shards.