Design a Distributed Rate Limiter for an API Platform

Listen

Listen first. We limit requests by API key, user, IP address, or a key plus endpoint. Rules depend on the plan: say a hundred a minute on free and a thousand on pro. Rejected requests get a four twenty-nine with helpful headers. Rules change without a deploy. Non-functional: the check adds under a millisecond, limits hold across all servers, and if the limiter breaks, the API must keep working.

Scope it. Volumetric network attacks are handled by the edge provider, not by us. Monthly billing quotas are a different system. Then ask the questions that shape the design. Must limits be exact? Usually a few percent over is acceptable, which opens up cheaper designs. One region or several? Say three. And will this be a library in the gateway or a separate service? A library inside the gateway avoids an extra network hop.

Ask scale

Ask about scale. Peak traffic is half a million requests a second across fifty gateways, ten thousand each. Ten million active clients. A token bucket needs only a token count and a last refill time, about a hundred bytes per key including overhead, so the whole state is around one gigabyte. Memory is easy. Operations are the constraint: at roughly a hundred thousand operations a second per Redis node, we need at least five shards, so plan eight to ten.

peak traffic: 500,000 req/s
50 gateways ≈ 10,000 req/s each

active keys: 10M clients
state per key (token bucket):
  tokens + last_refill ≈ 100 B
  with Redis overhead
  10M × 100 B ≈ 1 GB

Redis node ≈ 100k ops/s
  500k / 100k → 5, run 8-10

Define API

Define the API. There are two faces. Rules are data, not code: match on plan and route, choose which field is the key, and set the limit, window and burst. And the response contract: over the limit returns four twenty-nine with Retry-After saying how many seconds to wait, plus remaining and reset headers on every response, so well-behaved clients slow down before they hit the wall.

rule (config, not code):
  { match: { plan: "free",
      route: "/v1/search" },
    key: "api_key",
    limit: 100, per: "1m",
    burst: 20 }

response on reject:
  429 Too Many Requests
  Retry-After: 12
  RateLimit-Remaining: 0

Data model

The data model. Rules live in the rules service database and every gateway caches them in memory, refreshing every few seconds, so a rule lookup costs nothing. Bucket state lives in Redis: one small hash per key and rule, holding tokens and the last refill time in milliseconds. Give each entry an expiry of about twice the window, so idle clients disappear on their own instead of piling up.

rules: rules service DB,
  cached in every gateway,
  refreshed every 10 s

state in Redis, one hash per
  key and rule:
  rl:{api_key}:search
    tokens      14.2
    last_ms     1729771200123
  EXPIRE 2 × window
  (idle keys clean themselves)

High-level design

Draw the high-level design. Requests arrive at a fleet of API gateways, each running the limiter as middleware. The gateway finds the matching rule in its in-memory copy, then asks Redis to take one token from that client's bucket, in a single round trip. If a token was available, the request goes on to the backend. Redis is the shared memory that makes fifty gateways behave like one.

Now the rejected path. The bucket is empty, so Redis replies with no token and the time until the next refill. The gateway answers four twenty-nine with Retry-After twelve straight away. The backend never sees the request, which is the whole point: rejections should cost almost nothing, so a flood of them cannot hurt the services behind the gateway.

Deep dive: algorithm

Deep dive one: the algorithm. Concepts episode thirty covers all four. Fixed window is one counter but allows double bursts at window edges. A sliding log is exact but stores every timestamp. A sliding window counter is a good approximation with two numbers. Pick the token bucket: two numbers per key, a steady refill rate, and a capacity that allows controlled bursts. Many real gateways, such as AWS API Gateway and Envoy, use it.

              memory  bursts  exact
fixed window  1 int   edge x2 no
sliding log   1/req   none    yes
sliding count 2 ints  smooth  ~yes
token bucket  2 nums  capped  ~yes

choice: token bucket
  rate = limit / window
  capacity = burst
  2 numbers, allows short
  bursts, used by many gateways

Deep dive: atomicity

Deep dive two: correctness across servers. If a gateway reads the bucket, decides, and writes back as separate commands, two gateways can both see one token left and both allow the request. The fix is to run the whole check as a single Lua script inside Redis, which executes atomically. It reads the bucket, adds tokens for the elapsed time, takes one if possible, writes it back and sets the expiry, all in one round trip.

race: two gateways GET 1 token
  left, both allow, both SET

fix: one Lua script, run
  atomically inside Redis:
  t, last = HMGET key
  t = min(cap, t + rate*(now-last))
  if t < 1: return reject, wait
  HSET key t-1, now
  PEXPIRE key ttl
  return allow, t-1

Deep dive: latency

Deep dive three: latency. Keep Redis in the same zone as the gateways, where a round trip is a fraction of a millisecond, and use pooled, pipelined connections. Add a local fast path: when Redis says a key is empty until a given time, remember that in the gateway and reject further requests locally until then. If the budget is tighter still, keep local buckets and sync counts to Redis every hundred milliseconds, accepting a small overshoot.

Deep dive: hot keys

Deep dive four: sharding. Redis Cluster hashes each key to a slot, so each client's bucket lives on exactly one shard and the script stays single-key and atomic. The trouble is one huge partner sending forty thousand requests a second, all landing on one shard. Split that client's bucket into eight sub-buckets, each with an eighth of the limit, chosen at random per request, or give it a local bucket per gateway.

Deep dive: failure

Deep dive five: failure. The limiter must never be the reason the API is down. Call Redis with a short timeout, a few milliseconds, behind a circuit breaker. If Redis is unreachable, fail open: allow the request, but apply a generous local limit per gateway so one client still cannot run wild. For a few security rules, like login attempts, failing closed may be the right call. Alert either way.

Deep dive: regions

With three regions, never call one global Redis; a cross-ocean round trip is seventy milliseconds or more. Either split the limit, giving each region a third, which is simple but unfair if a client's traffic is uneven; or keep a Redis per region and exchange counts asynchronously every second, which is fair but can overshoot briefly. Since we agreed a few percent over is fine, the second option works well.

Deep dive: rollout

Running it in production. Rules are layered: a global ceiling, per IP, per key, and per key and endpoint, and a request must pass all of them. Launch every new rule in shadow mode first, logging would-reject without blocking, so a typo does not lock out your biggest customer. Rules hot reload with versions and instant rollback, and dashboards show the most-rejected keys and the reject rate per rule.

Trade-offs

Trade-offs to say out loud. A central Redis is accurate but costs a round trip; local buckets are cheaper but overshoot. Failing open favours availability over protection. Token bucket deliberately allows bursts. Monitor the limiter's own latency, Redis CPU per shard, timeouts and the reject rate per rule. At ten times the traffic, add shards and move more counting into local pre-aggregation.

Interview summary

The summary. The limiter is middleware in the gateway. Rules are data, cached locally. Each client has a token bucket in Redis, two numbers with an expiry, updated by one atomic Lua script per request. Over the limit returns four twenty-nine with Retry-After. A local deny cache and sub-buckets handle hot keys. If Redis fails, fail open with local limits. Each region has its own Redis, synced asynchronously.