Design a Distributed Rate Limiter

1Requirements

2Back-of-envelope estimation

3API design

4High-level design

Place the rate limiter as middleware in the API gateway, in front of all application services. Every incoming request is mapped to one or more limit keys (user:123:route:/search, ip:1.2.3.4) and each key is checked against its rule before the request is forwarded. Rejected requests get a 429 with Retry-After, so clients can back off instead of hammering.

Counter state cannot live in per-server memory because a load balancer spreads one client across many servers; each server would enforce N times the intended limit. So counters live in a shared, fast store: Redis, sharded by limit key using consistent hashing. Each check is a single Lua script executed atomically on the shard owning that key, which reads the counter, applies the algorithm, and returns allow or deny in one round trip.

Rules live in a configuration store (e.g., a small database or etcd) and are cached in each gateway worker's memory, refreshed on change notification. This keeps the hot path free of rule lookups: the only network call per request is the one Redis operation.

For resilience, each gateway also keeps a small local fallback limiter (an in-memory token bucket with a generous limit). If Redis times out, the gateway applies the local limiter and allows the request (fail-open), emitting metrics so operators see degraded accuracy. Throttling events are logged asynchronously to a queue for abuse analytics and alerting.

5Data model

6Deep dives

7Rapid implementation: build the MVP

Theory is table stakes. Here is how you would stand up a working version fast, on a budget, with the core algorithm in real code.

1. 01Run Redis locally with docker run -p 6379:6379 redis and connect with ioredis.
2. 02Write the token bucket as a Lua script (refill from elapsed time, decrement, return allowed + remaining) and load it once with redis.defineCommand.
3. 03Store per-key state in a Redis hash rl:{key} with fields tokens and last_refill_ms, and set PEXPIRE to 2x the refill window so idle keys evict themselves.
4. 04Wrap the script call in an Express middleware that builds the key from user id (or req.ip as fallback) plus route, with a 5 ms timeout on the Redis call.
5. 05On deny, respond 429 with X-RateLimit-Limit, X-RateLimit-Remaining, and Retry-After headers computed from the script's return values.
6. 06On Redis timeout or error, fail open: allow the request, apply a small in-process fallback bucket per key, and increment a limiter_degraded metric.
7. 07Keep rules in a rules.json (routePattern, limit, windowSeconds) loaded at boot and hot-reloaded on file change; match longest prefix per request.
8. 08Verify atomicity by hammering one key from two processes with autocannon and asserting admitted count never exceeds the limit.

// KEYS[1] = bucket key, ARGV = [capacity, refillPerSec, nowMs, cost]
export const TOKEN_BUCKET_LUA = [
  "local capacity = tonumber(ARGV[1])",
  "local rate = tonumber(ARGV[2])",
  "local now = tonumber(ARGV[3])",
  "local cost = tonumber(ARGV[4])",
  "local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')",
  "local tokens = tonumber(state[1]) or capacity",
  "local ts = tonumber(state[2]) or now",
  "tokens = math.min(capacity, tokens + (now - ts) / 1000 * rate)",
  "local allowed = 0",
  "if tokens >= cost then",
  "  tokens = tokens - cost",
  "  allowed = 1",
  "end",
  "redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)",
  "redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 2000))",
  "return { allowed, tostring(tokens) }",
].join("\n");

redis.defineCommand("tokenBucket", { numberOfKeys: 1, lua: TOKEN_BUCKET_LUA });

export function rateLimit(limit: number, windowSeconds: number) {
  const ratePerSec = limit / windowSeconds;
  return async (req: any, res: any, next: any) => {
    const key = "rl:" + (req.user?.id ?? req.ip) + ":" + req.path;
    try {
      const [allowed, tokens] = await withTimeout(
        redis.tokenBucket(key, limit, ratePerSec, Date.now(), 1),
        5 // ms budget; fail open past this
      );
      res.set("X-RateLimit-Limit", String(limit));
      res.set("X-RateLimit-Remaining", String(Math.floor(Number(tokens))));
      if (allowed === 1) return next();
      const retryMs = Math.ceil(((1 - Number(tokens)) / ratePerSec) * 1000);
      res.set("Retry-After", String(Math.ceil(retryMs / 1000)));
      return res.status(429).json({ error: "rate limited" });
    } catch {
      metrics.increment("limiter_degraded");
      return next(); // fail open, backed by a local fallback bucket
    }
  };
}

type Bucket = { tokens: number; ts: number };
const local = new Map<string, Bucket>();

export function localAllow(key: string, capacity: number, ratePerSec: number): boolean {
  const now = Date.now();
  const b = local.get(key) ?? { tokens: capacity, ts: now };
  b.tokens = Math.min(capacity, b.tokens + ((now - b.ts) / 1000) * ratePerSec);
  b.ts = now;
  if (b.tokens < 1) {
    local.set(key, b);
    return false;
  }
  b.tokens -= 1;
  local.set(key, b);
  if (local.size > 50_000) local.clear(); // crude memory cap for an MVP
  return true;
}