Design: a rate limiter

The prompt

"Design a rate limiter" usually means a distributed one: many API servers, one set of limits. The algorithm is a small part of the answer; the rest is where state lives, how rules change, and what the limiter does when it breaks.

1. Requirements

Functional

• Limit by API key, IP address and route, with limits that depend on the customer's plan.
• Reject excess requests with 429 Too Many Requests, a Retry-After header, and headers saying how much quota is left.
• Change limits and add rules without deploying the API.

Non-functional

• Adds under 2 ms at p99.
• Limits hold across all 40 servers, give or take a few percent.
• The limiter failing must not take the API down.

2. Estimates

• State: 2 million keys × about 3 rules each = 6 million buckets. At about 100 bytes each with Redis overhead, that's 600 MB: it fits in memory, comfortably.
• Operations: 200,000 requests × 2 rules on average = 400,000 checks a second. If one Redis primary handles about 50,000 scripted checks a second within the latency target (measure your own), that's 8 primaries, plus replicas.

So the counter store is a small Redis cluster. The cost to design around is the round trip on every request.

3. Entities and API

Rule    { name, match: (api_key | ip | route), per_plan: { rate, burst }, mode: enforce | shadow }
Bucket  { rule:key → tokens, updated_at }        in Redis, sharded by key

check(request) → { allowed, remaining, retry_after }      called by the gateway, in process

HTTP/1.1 429 Too Many Requests
Retry-After: 1
X-RateLimit-Limit: 10
X-RateLimit-Remaining: 0

4. High-level design

5. Deep dives

The decision logic, run here in process with an in-memory map in place of Redis:

type Req = { apiKey: string; ip: string; route: string };
type Rule = { name: string; match: (r: Req) => string | null; perSecond: number; burst: number };
type Bucket = { tokens: number; at: number };

export class Limiter {
  private buckets = new Map<string, Bucket>();
  constructor(private rules: Rule[]) {}

  check(req: Req, now: number) {
    let retryAfter = 0;
    const touched: Bucket[] = [];
    for (const rule of this.rules) {
      const key = rule.match(req);
      if (key === null) continue; // the rule doesn't apply to this request
      const b = this.buckets.get(`${rule.name}:${key}`) ?? { tokens: rule.burst, at: now };
      b.tokens = Math.min(rule.burst, b.tokens + ((now - b.at) / 1000) * rule.perSecond);
      b.at = now;
      this.buckets.set(`${rule.name}:${key}`, b);
      if (b.tokens < 1) retryAfter = Math.max(retryAfter, Math.ceil((1 - b.tokens) / rule.perSecond));
      touched.push(b);
    }
    if (retryAfter > 0) return { allowed: false, retryAfter };
    for (const b of touched) b.tokens -= 1; // spend only when every rule allows it
    return { allowed: true, remaining: Math.min(...touched.map((b) => Math.floor(b.tokens))) };
  }
}

Tested with a key rule of 5 a second (bursts of 10) and a creation rule of 1 a second per IP (bursts of 3): 12 requests at once gave 10 allowed and 2 rejected with retryAfter: 1; one second later the next request was allowed with 4 remaining. Twenty link creations at once from one IP gave 3 allowed and 17 rejected, and afterwards the key's own bucket still had 6 tokens: the 17 rejected requests hadn't spent any.

Changing rules safely. A new rule starts in shadow mode: the limiter evaluates it and logs what it would have rejected, without rejecting anything. Once the logs show it catches abuse and not good customers, it's switched to enforce. Rules are versioned, so a bad change is rolled back in seconds (14.05 Safe deploys).

6. Wrap-up

What breaks first is usually the hot key: one large customer's bucket, checked 20,000 times a second, all on one Redis primary. After that, cost: if the counters dominate the bill, approximate local counting synced every second (14.04 Where to put a rate limiter) removes most of the round trips for limits that tolerate a brief overshoot.

Recap

Interview questions