Design an API Rate Limiter

What is it? #

A distributed rate limiter enforces request limits consistently across many application servers.

The single-server version from the earlier lesson is straightforward. Distributed is harder because the count must be shared, the check must be atomic, and the limiter itself must be fast enough to sit in front of every request.

Three requirements pull against each other: accuracy, latency and availability. A perfectly accurate limiter that adds 50 milliseconds to every request is worse than a slightly approximate one that adds one.

The design decision that matters most is what happens when the shared store is unavailable.

Think of it like this #

Several doors into one venue, all enforcing a shared capacity limit.

Each door could count independently, which is fast but lets in too many people. Or every door could radio a central counter before each admission, which is accurate but slow. Real venues use a mix: a central count, checked efficiently, with a sensible rule for what to do if the radio fails.

Simple example #

An API across 20 servers must enforce 1,000 requests per minute per API key, adding under 2 milliseconds per request, and continuing to serve traffic if Redis becomes unavailable.

Code #

1. Requirements

functional      per-key limits, different limits per endpoint tier,
                accurate 429 responses with Retry-After
non-functional  under 2ms added latency, correct across all servers,
                must not take down the API if the store fails
scale           50K requests/s across 20 servers, 1M distinct keys

-- 2. Atomicity: the check and the increment must be one operation.
-- A Lua script runs atomically inside Redis, avoiding a read-then-write race.
-- KEYS[1] = bucket key, ARGV = capacity, refill_rate, now_ms, cost

local capacity    = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])   -- tokens per millisecond
local now         = tonumber(ARGV[3])
local cost        = tonumber(ARGV[4])

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'updated')
local tokens = tonumber(state[1]) or capacity
local updated = tonumber(state[2]) or now

tokens = math.min(capacity, tokens + (now - updated) * refill_rate)

local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end

redis.call('HMSET', KEYS[1], 'tokens', tokens, 'updated', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / refill_rate) + 1000)

local retry_after_ms = 0
if allowed == 0 then
  retry_after_ms = math.ceil((cost - tokens) / refill_rate)
end
return {allowed, math.floor(tokens), retry_after_ms}

# 3. Client side: one round trip, and a decision about failure
class DistributedLimiter:
    def __init__(self, redis_client, script_sha, fail_open: bool = True):
        self.redis = redis_client
        self.sha = script_sha
        self.fail_open = fail_open

    def check(self, key: str, capacity: int, per_seconds: int, cost: int = 1):
        refill = capacity / (per_seconds * 1000)          # tokens per ms
        try:
            allowed, remaining, retry_ms = self.redis.evalsha(
                self.sha, 1, f"rl:{key}", capacity, refill, int(time.time() * 1000), cost)
        except redis.RedisError:
            metrics.increment("ratelimit.store_unavailable")
            # fail open: serve traffic without limits, and alert
            # fail closed: reject everything — correct only for critical endpoints
            return (True, capacity, 0) if self.fail_open else (False, 0, 1000)
        return bool(allowed), remaining, retry_ms

4. Reducing load on the shared store

local pre-check    keep an in-process approximate counter; only call Redis
                   when a key is near its limit — cuts round trips sharply
batching           for very high volume, sync counts periodically rather
                   than per request, accepting slight over-admission
sharding           partition keys across Redis instances by hash
tiered limits      coarse limit at the edge (CDN/gateway), precise limit
                   in the application

5. Failure policy

fail open   traffic is served if the limiter is down — protects availability,
            leaves you unprotected during the outage. Right for most APIs.
fail closed requests are rejected if the limiter is down — protects a fragile
            backend, but an outage of the limiter becomes an outage of the API.

Choose deliberately per endpoint, and alert loudly either way.

How it works #

Atomicity is the core problem. Reading the counter and then writing it back is a race: two servers can both read 999 and both allow the request. The Lua script makes the read, compute and write one atomic operation inside Redis.

The token bucket is computed rather than stored per second. Tokens are refilled based on elapsed time at the moment of the check, so no background process is needed.

PEXPIRE keeps memory bounded. With a million keys, entries for idle keys must expire or the store grows indefinitely.

Returning the retry time from the script means the 429 response can carry an accurate Retry-After rather than a guess.

The fail-open decision is the most consequential line in the client. For a public API, a limiter outage should not become an API outage, so failing open is usually right — with loud alerting, because you are unprotected until it recovers. For an endpoint that would collapse under unlimited load, failing closed is defensible.

The local pre-check is what makes this affordable at 50,000 requests per second. Most keys are nowhere near their limit, so an approximate in-process counter can skip the network call entirely until a key approaches its threshold.

Real-world use #

Most teams use an existing implementation — a gateway feature, an Envoy or Nginx module, or a library — rather than writing this. The value of understanding it is in configuring it correctly and diagnosing it when the numbers look wrong.

Tiered limiting is standard: a CDN or WAF absorbs obvious floods, the gateway applies coarse per-IP limits, and the application applies precise per-user and per-endpoint limits where it has the context.

Communicating limits matters. Publishing them in documentation and returning X-RateLimit-* headers lets well-behaved clients self-regulate, which reduces 429s for everyone.

Different customer tiers usually mean different limits, which turns the limiter into a product feature with billing implications rather than purely infrastructure.

Monitoring the limiter itself is easy to forget. The rate of 429 responses, the store's latency and availability, and the number of tracked keys are all worth watching.

Common mistakes #

• Read-then-write without atomicity, so concurrent servers both allow the same request.
• No expiry on counter keys, so memory grows without bound.
• Calling the shared store on every request without a local pre-check at high volume.
• Failing closed by default, turning a limiter outage into a full API outage.
• Returning 429 without an accurate Retry-After, so clients retry immediately.

Practice #

Implement the Lua token bucket against a local Redis and verify it from two processes at once that the combined rate is correct. Then add a local pre-check that avoids the Redis call when the key is below half its limit, and measure the reduction in round trips.