Rate Limiter

Token bucket, sliding window, Redis counters and where to place a limiter.

• Advanced
• 38 min read
• 3 objectives

Before this lessonLesson 6: URL Shortener

A rate limiter caps how often a client may call an API. You will add one to every public endpoint in later designs. Goals: stop abuse, protect downstreams, keep quotas fair, return HTTP 429 with a Retry-After header.

Step 1 — Clarify

• Limit by IP, user id, API key, or all three? Different rules per route (POST /login vs GET /public)?
• Average rate, burst, or both? Hard block vs delay?
• Must the limit be exact across 20 app servers, or is slightly soft OK?
• Who configures rules — engineers, or an admin API?

Assumptions: 1000 req/min per API key, bursts of 50, many app boxes, p99 of the allow/deny check under a few milliseconds, 429 + headers on deny. Login endpoints get a tighter separate rule.

Step 2 — Where it sits

flowchart TB C[Client] --> Edge[CDN / API gateway] Edge --> RL[Rate limiter] RL -->|allow| APP[App servers] RL -->|429| C RL --> Redis[(Redis cluster)]

The gateway is the usual place: one policy, before you spend app CPU. Redis holds shared counters so all boxes agree.

In-process memory on each app server is wrong: 10 boxes × 100 req/s allowed = 1000 req/s to the backend. A library inside each app that talks to Redis is acceptable if you have no gateway. CDN WAF limits are coarse (IP) and do not know your API keys — use them as a first shield, not the product limiter.

Step 3 — Algorithms

Token bucket (default)

Tokens refill at rate r per second. The bucket holds at most c tokens. Each request costs one token. Bursts up to c are allowed, then steady r. This matches how people actually use APIs.

import time

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate, self.capacity = rate, capacity
        self.tokens, self.last = capacity, time.monotonic()

    def allow(self):
        now = time.monotonic()
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

bucket = TokenBucket(rate=5, capacity=10)
print(sum(bucket.allow() for _ in range(12)))

10

Leaky bucket

Queue requests and drain at a fixed rate. Smooths bursts; adds latency. Useful when a downstream cannot take spikes at all (some payment processors).

Fixed window counter

Count hits in the current minute; reset on the minute boundary. Cheap (INCR + EXPIRE). Edge burst: a client can fire limit at 12:00:59 and again at 12:01:00 — twice the intended rate. Mention this flaw.

Sliding window log

Store a timestamp per request, drop those older than the window. Accurate, memory-heavy at high QPS.

Sliding window counter

Weight the previous window by how much of it still overlaps. Good Redis compromise: two integers, not a log.

def allow(key, limit, now_s, counts):
    window = now_s // 60
    prev, cur = counts.get(window - 1, 0), counts.get(window, 0)
    frac = (now_s % 60) / 60
    approx = cur + prev * (1 - frac)
    return approx < limit, round(approx, 1)

print(allow("user:42", 100, 60 + 15, {1: 40, 2: 30}))

(True, 60.0)

Step 4 — Distributed implementation

Use Redis. Shard by client key (consistent hash) so one hot API key hits one Redis slot, not a broadcast. A Lua script makes refill + consume atomic for a token bucket. For a fixed window, INCR then EXPIRE on first increment.

• Cache the last allow/deny in the gateway for 10–50 ms so a hot key does not hit Redis on every request.
• Fail open vs fail closed: if Redis is down, a public read API might fail open (serve traffic, log); a login or SMS send should fail closed (429).
• Return 429, Retry-After, X-RateLimit-Limit, X-RateLimit-Remaining.

Step 5 — Rules you should name

• Global API quota per key, plus per-route overrides (login, password reset, create-short-url).
• Paying customers get a larger bucket, not a different algorithm.
• Store rules in a config service, cache them; changing a limit should not require a deploy.

// Write your solution here