Rate Limiting

Your public API is sized for 3,000 requests a second in total. One customer ships a script with a retry bug, and it starts sending 2,500 a second on its own. Latency climbs for everyone and the database starts timing out. Nobody was malicious; that client had no ceiling.

#The idea

Pick a key (an API key, a user id, an IP address), count that key's requests over time, and reject the ones over the limit with 429 Too Many Requests and a Retry-After header saying when to come back. Limits protect capacity, keep customers from hurting each other, enforce plans, and slow attacks such as password guessing.

The cost: a check on every request, shared state across servers, and rejected good traffic if the limit or key is wrong.

#Five ways to count

Fixed window. One counter per key per minute, reset each minute. Cheap, but the edges leak: with a limit of 100 a minute, a client can send 100 at 0:59 and 100 more at 1:00, so 200 requests land within about a second, double the limit.

Sliding window log. Store every request's timestamp, drop those older than a minute, count the rest.

Sliding window counter. Keep only this minute's and last minute's counts, and weight the old one by how much of it still overlaps the last 60 seconds. With a limit of 100, 80 requests last minute, 30 so far this minute, and 15 seconds into it: 30 + 80 × 45/60 = 30 + 60 = 90, so the request passes. It assumes last minute was evenly spread: an approximation.

Token bucket. Each key has a bucket that holds up to capacity tokens and refills at rate tokens a second. A request takes one token or is rejected.

Leaky bucket. Requests join a queue drained at a fixed rate; when it is full, new ones are rejected.

#A token bucket, step by step

Capacity 5, refill 1 token a second. No timer refills buckets: each request works out how many tokens arrived since the last one.

on request at time now:  tokens = min(capacity, tokens + (now - last) * rate)  last = now  if tokens >= 1:    tokens = tokens - 1    allow  else:    reject with 429

class TokenBucket {
  constructor(capacity, ratePerSec) {
    this.capacity = capacity;
    this.rate = ratePerSec;
    this.tokens = capacity;   // start full
    this.last = 0;            // time of the last refill
  }
 
  allow(now) {
    const elapsed = now - this.last;
    this.tokens = Math.min(this.capacity, this.tokens + elapsed * this.rate);
    this.last = now;
    if (this.tokens >= 1) {
      this.tokens -= 1;
      return true;
    }
    return false;
  }
}

class TokenBucket:
    def __init__(self, capacity, rate_per_sec):
        self.capacity = capacity
        self.rate = rate_per_sec
        self.tokens = capacity   # start full
        self.last = 0            # time of the last refill
 
    def allow(self, now):
        elapsed = now - self.last
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

#Where the limiter lives

• At the edge, by IP: cheap protection against floods.
• At the API gateway, by API key or user: plan quotas and fairness between customers. This is the usual answer.
• Inside a service: protecting one dependency, like a payment provider that allows 50 calls a second.

#Counting across many servers

Ten gateway nodes with their own counters each allow the full limit, so a limit of 100 a minute lets 1,000 through. Three fixes:

• A central counter store, an in-memory store such as Redis. Exact, but it costs a hop (about 0.5 ms) per request and adds a dependency. The check and the update must be one atomic operation: if two nodes both read 99 and both write 100, the client got 101. Use an atomic increment or a small script that refills and takes a token in one step.
• Split the limit: each of the 10 nodes allows 10 a minute. No shared state, but only right if each client's traffic is spread evenly.
• Local counts, synced every second. Fast; overshoots by what slips through between syncs.

Use the central store for customer quotas, local counters for flood protection. Then decide what happens when the store is down. Fail open (allow everything) for a general API, so a limiter outage is not a full outage. Fail closed, or fall back to strict local limits, for login and other endpoints attackers target.

#Numbers worth remembering

• A token bucket is two numbers per key: about 16 bytes plus the key.
• A sliding log is one timestamp (8 bytes) per request in the window, per key.

#In the interview

Mention a rate limit when an API is public, an endpoint is expensive, or you call a third party with limits. Name the key, algorithm and response: "Per API key, token bucket of 100 with a refill of 10 a second, enforced at the gateway with counters in a shared store, returning 429 with Retry-After."

Follow-ups to expect:

• "Why not limit by IP?" Offices and mobile networks share IPs, and attackers rotate them. Use IP only before login; use the account or key after.
• "And across regions?" Give each region its own counter store and a share of the limit. One global store would add a cross-region round trip to every request.
• "What should a client do with a 429?" Wait for Retry-After, then back off with jitter.

#Common mistakes

#What to practise next

The full design, with rules per endpoint, a counter store across regions and its failure modes, is in Design a Rate Limiter. Counters spread over many cache nodes rely on consistent hashing.