Rate Limiting

An unlimited login endpoint is a password-guessing service with a pleasant JSON API. An unlimited search endpoint is a way for one buggy client to consume your entire database. Rate limiting is how a public API stops being a shared resource that anyone can monopolise.

It is also a small, self-contained distributed-systems problem: a counter that several machines update at once, where getting the atomicity wrong produces a limiter that passes every test and does nothing.

The four algorithms

They differ in what happens at the edges, and the edges are where limiters are attacked.

Fixed window

Count requests per calendar minute. Reset the counter when the minute changes.

   key = "user:42:2026-08-22T14:31"
   INCR key ; EXPIRE key 60 ; allow if count <= limit

Two commands and one counter. It also has a bug that makes it unsuitable for anything security related:

   limit = 100/minute

   14:31:59   ████████████████ 100 requests   (window A)
   14:32:00   ████████████████ 100 requests   (window B — counter reset)
              └────── 200 requests in ~1 second ──────┘

Twice the stated limit, delivered in a burst, by simply straddling a boundary that is trivial to predict. Fine for rough quota accounting; not fine for a login endpoint.

Sliding log

Store a timestamp per request; count the ones inside the window. Exactly correct, no boundary effect, and unaffordable: a limit of 1,000 per hour means storing 1,000 timestamps per client. Memory scales with traffic, which is the property you least want in the component that exists to handle excess traffic.

Sliding window counter

The pragmatic compromise: keep two fixed-window counters and interpolate.

   30% into the current minute:

   estimate = current_count + previous_count x 0.7

   Two counters, no boundary doubling, slightly approximate.

Good, cheap, and what several large CDNs use. It is an estimate, so it can be marginally generous or strict at the edges.

Token bucket

A bucket holds up to capacity tokens and refills continuously. Each request spends one; an empty bucket means refusal.

   capacity 20, refill 20/minute (1 every 3s)

   ┌────────────────────┐  full — 20 requests may arrive at once
   │ ● ● ● ● ● ● ● ● ●  │
   └────────────────────┘
            │ spend 1 per request
            │ refill 1 every 3s, never above capacity
            v
   empty -> refuse, and say when to come back

Two numbers of state — tokens remaining, and when they were last counted — regardless of traffic. And the burst allowance is a feature you set independently of the rate, which none of the others give you: a page firing six requests on load should not be throttled by a “one per second” rule, and a bucket of 20 refilling at 1/second permits that page load while still holding the long-run average to one per second.

Which to pick

In practice the choice collapses quickly. Use a token bucket unless you have a reason not to — it is the only one where you set burst and rate independently, and its state does not grow with traffic.

Reach for the sliding window counter when you need a hard “never more than N in any window” guarantee with no burst at all, which is occasionally a contractual requirement rather than an engineering preference. Reach for the sliding log only when N is tiny and exactness matters — five password resets a day, say, where storing five timestamps is nothing.

And avoid fixed window for anything an adversary touches, while accepting it is perfectly reasonable for rough internal quota accounting where a boundary burst costs nothing.

The bug that makes a limiter decorative

Here is the implementation almost everyone writes:

tokens = redis.get(key)            # process A reads 1.0    process B reads 1.0
if tokens >= 1: tokens -= 1        # A decides: allow       B decides: allow
redis.set(key, tokens)             # A writes 0.0           B writes 0.0

Two requests, one token, both allowed. That is a lost update, and it is not an unlucky interleaving — it is the normal outcome when a client sends requests concurrently, which is precisely what an abusive client does.

Under four API workers the effective limit becomes roughly four times what it says. And the limiter passes every sequential test ever written for it, because sequentially it is correct. This is the check-then-act race from the concurrency post, in three lines.

Making it atomic

The logic is three steps — refill for elapsed time, decide, write back — which is too much for a single Redis command. So the logic goes to where the data is. Redis executes a Lua script as one indivisible unit; no other command from any connection interleaves with it.

local now_pair   = redis.call('TIME')
local now        = tonumber(now_pair[1]) + tonumber(now_pair[2]) / 1000000

local bucket     = redis.call('HMGET', key, 'tokens', 'ts')
local tokens     = tonumber(bucket[1])
local ts         = tonumber(bucket[2])

if tokens == nil then
  tokens = capacity
  ts = now
end

local elapsed = math.max(0, now - ts)
tokens = math.min(capacity, tokens + elapsed * refill)

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

redis.call('HSET', key, 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', key, ttl)

Four details in there are decisions rather than incidentals.

Nothing runs on a timer. The bucket is recomputed from how long it has been since anyone last looked: tokens + elapsed * refill. No background job refills anything, which is what keeps the state to two numbers.

math.min(capacity, ...). Without the cap, a client idle for an hour returns with an hour of accumulated tokens and can spend them all at once — a limiter permitting exactly the burst it was deployed to prevent.

redis.call('TIME'), not a timestamp from the caller. The API runs on several machines whose clocks disagree by tens of milliseconds. One clock — the server’s — is the only way every worker refills the same bucket consistently.

The EXPIRE is refreshed every call. A bucket that expires while a client is still being limited hands them a fresh full one; the TTL exists only to reclaim keys for clients that have gone away.

One more, invisible in the script: the key is passed as a key rather than built inside the script body. Redis Cluster routes a script by its declared keys, so a script that constructs key names internally works on a single node and silently misroutes the day the cache is sharded.

The state it keeps

The rule is expressed as capacity plus a window rather than as a refill rate, and that is a readability decision worth copying:

@dataclass(frozen=True)
class Rule:
    name: str
    capacity: int
    per_seconds: int

    @property
    def refill_per_second(self) -> float:
        return self.capacity / self.per_seconds

“Twenty at once, twenty a minute sustained” is something a human can reason about and argue with. “0.333 tokens per second” is the same statement in a form nobody can sanity-check, and it is derived rather than configured.

The stored state per client is genuinely just the two numbers the bucket needs:

   key: stayhub:v1:ratelimit:login:ip:203.0.113.5
   ├── tokens  7.34            fractional, because refill is continuous
   └── ts      1787425138.21   when they were last counted

   TTL: 2x the window, refreshed on every call.

   Two fields per client, whether they made one request or a million.

The TTL being twice the window is deliberate: a bucket must outlive the period it is limiting even for a client that goes quiet halfway through, or the client returns to a full bucket.

The keys are also namespaced and versioned by the same helper the cache uses, which matters because both live in the same Redis. Sharing a keyspace with no prefix is how one component starts reading another’s data, and the symptom is not an error — it is a counter that behaves strangely.

Proving it

Sequential tests cannot tell the two implementations apart. The test has to be concurrent and has to assert an exact total:

        with cf.ThreadPoolExecutor(max_workers=50) as pool:
            allowed = list(pool.map(lambda _: rate_limit.check(rule, "swarm").allowed, range(50)))

        assert sum(allowed) == 20, (
            f"{sum(allowed)} of 50 allowed against a capacity of 20 — the check is not atomic"
        )

50 threads, a bucket of 20, and exactly 20 get through. That runs green against the Lua version. Against the read-modify-write version it produces 23, or 27, or 21, depending on timing — which is why the assertion is an exact equality rather than “at most”. A racy limiter does not fail dramatically; it overruns slightly and irregularly.

The window is deliberately an hour long so that refill cannot mask a lost update by handing out extra tokens mid-test.

Who is being limited?

A limiter is only as good as its notion of “who”. Get it wrong and you either limit everyone together — one noisy client throttles the site — or limit nobody, because every request looks unique.

def identify(request, user=None) -> str:
    if user is not None:
        return f"user:{user.public_id}"
    return f"ip:{client_ip(request)}"

The account wins when there is one. An IP is a poor identity in both directions: an office or a university NATs thousands of people behind one address, and a single abusive client can rent thousands of addresses.

The header that turns the limiter off

This is the security bug worth knowing, because the naive implementation is what most tutorials show:

ip = request.headers.get("X-Forwarded-For", request.client.host)

X-Forwarded-For is set by the client. Anyone can send a random value on every request and receive a fresh bucket each time; the limiter then diligently tracks millions of clients that made one request each. It is a header a proxy sets, and it means nothing unless you know a proxy you trust set it.

    if TRUSTED_PROXY_COUNT > 0:
        forwarded = request.headers.get(FORWARDED_FOR, "")
        hops = [h.strip() for h in forwarded.split(",") if h.strip()]
        if len(hops) >= TRUSTED_PROXY_COUNT:
            return hops[-TRUSTED_PROXY_COUNT]

Two rules. Honour the header only when a trusted proxy is genuinely in front — the default is to ignore it entirely. And count hops from the right: the rightmost entries were appended by infrastructure you control, and everything to the left is whatever the client chose to claim.

Telling a client how much is left

A well-designed limiter is one clients can cooperate with, and cooperation needs information before the refusal rather than after it.

@dataclass(frozen=True)
class Decision:
    allowed: bool
    remaining: int
    retry_after: int
    reset_at: int

Returning the decision on success as well as failure is what makes that possible — a route can put X-RateLimit-Remaining on a 200, so a client watching it drop can slow down before it hits zero. A limiter that only speaks when refusing has forced every client into trial and error.

The corresponding client-side discipline is worth naming because it is the other half of the contract: on a 429, wait for Retry-After, and add jitter. If every refused client retries at exactly the moment the header specifies, they arrive together and are refused together.

Distributed by construction

One reason the counter lives in Redis rather than in the application: an in-memory limiter on N servers is N independent limiters.

   limit: 10 per 5 minutes, counted IN PROCESS

   [ app 1 ]  10 allowed
   [ app 2 ]  10 allowed        the load balancer spreads an attacker
   [ app 3 ]  10 allowed        across all of them
   [ app 4 ]  10 allowed
              ── effective limit: 40, and it grows every time you scale up

This is the in-memory state problem from the load balancing post, with a security consequence attached: the limiter gets weaker precisely when traffic is high enough that you added servers.

Shared state is the answer, and it costs one network round trip per limited request — sub-millisecond to a local Redis, and only on the endpoints that carry a limit. That is a very cheap round trip for a correct answer.

At extreme volume the round trip does start to matter, and the usual escape is a hybrid: allow each server a local allowance drawn from a shared pool, and reconcile periodically. It is approximate by design, and the approximation is acceptable when the limit is a quota rather than a security boundary.

Where the limiter goes

StayHub applies limits as route dependencies rather than as middleware, and both the choice and its cost are worth stating.

Middleware sees every request, which sounds ideal and makes per-endpoint limits awkward — you end up with a path-prefix table inside the middleware, which is a router, badly. Middleware also runs before authentication, so it can only ever limit by IP.

A dependency runs after authentication, so it can limit the account; it sits on exactly the routes that need it; and it appears in the API documentation. The cost is that a new expensive endpoint is unprotected until somebody adds it.

LOGIN_RULE = rate_limit.Rule(
    name="login",
    capacity=settings.rate_limit_login_capacity,
    per_seconds=settings.rate_limit_login_seconds,
)

Two endpoints are limited and the asymmetry is the design. Login gets 10 requests per 5 minutes — strict, because the endpoint guards a password. Someone who mistypes twice never notices; a script working through a wordlist gets ten tries per five minutes per address, which turns a feasible attack into an infeasible one.

Search gets 60 requests per minute — generous, because it protects a server rather than a secret. Nobody browsing can reach it; a runaway loop reaches it in under a second.

In production a coarse limit also belongs at the edge, in the load balancer or CDN, because a request refused there costs no worker, no database connection and no log line. The fine-grained layer behind it is not a replacement for that.

Do not key login on the email address

A tempting refinement that creates a weapon. Limiting by submitted email lets an attacker lock any user out of their own account by deliberately failing logins on their address — a limiter that becomes a denial-of-service tool against the person it protects.

Serious deployments key on both: a per-account limit that slows attempts and a per-IP limit that stops them, so neither alone can be abused this way.

The response

A 429 with no further information is a request to retry immediately, and a limiter that provokes a retry storm has made the load problem worse than the one it was deployed to fix.

            headers={
                "Retry-After": str(retry_after),
                "X-RateLimit-Limit": str(limit),
                "X-RateLimit-Remaining": "0",
                "X-RateLimit-Reset": str(reset_at),
            },

Retry-After is the contract. The X-RateLimit-* headers let a well-behaved client slow down before being refused, which is the whole point of publishing them.

Over HTTP that produces exactly what you want:

request 11 -> 429
  body   : {'message': 'Too many sign-in attempts. Please wait a moment and try again.',
            'fieldErrors': {}}
  retry-after           : 30
  x-ratelimit-limit     : 10
  x-ratelimit-remaining : 0

Two things that are easy to get wrong. The body keeps the same error shape as every other error in the API, so the frontend needs one parser rather than a special case. And the response still carries CORS headers — a 429 without them is reported by the browser as a network failure, so the user sees “something went wrong” instead of “you are being rate limited”.

Fail open, and say so

If Redis is unreachable, StayHub’s limiter allows the request. That is a real trade with a real downside, so it should be a decision rather than an accident.

Fail closed and a Redis outage takes down login for everybody — a cache outage becomes a total outage, which is exactly the coupling the caching post works to avoid, reintroduced by the back door. Fail open and for the duration of the outage login is unprotected against brute force, while the passwords behind it are still hashed and the application’s own lockout rules still apply.

The right answer depends on what the limiter protects. For quota enforcement somebody is billed against, fail closed — giving away free usage is worse than refusing service. For availability protection, which this is, fail open.

And a guarantee is only as wide as its narrowest try. This limiter originally wrapped the Lua call but not the script registration:

        try:
            client = cache._client()
            if client is None:
                return None
            _script = client.register_script(_TOKEN_BUCKET)
        except Exception as exc:  # noqa: BLE001
            _fail_open(exc)
            return None

Registration looks like a local operation — it hashes a string — but it runs on a client object that a malformed connection URL makes unbuildable. So a misconfigured redis_url failed closed: every login returning 500, which is precisely the outcome the fail-open decision existed to prevent. A test caught it, and only because the test patched the client to raise rather than to be absent.

Choosing the numbers

“Rate limit the API” is not a design until there are numbers on it, and picking them by feel produces limits that either annoy real users or stop nobody.

The method that works is to measure first and set the limit above observed legitimate use:

   1  log request rates per client for a week, WITHOUT enforcing
   2  find the p99 of legitimate users        say 12/min
   3  set the limit well above it             say 60/min
   4  enable in "report only" — log what WOULD have been refused
   5  read that log. Anything surprising is a real user you nearly broke.
   6  enforce

Steps 4 and 5 are the ones that get skipped and the ones that prevent an incident. The clients you are about to refuse are frequently your own: a mobile app that retries aggressively, an internal dashboard polling every second, a partner integration nobody documented.

Which leads to the practical necessity of tiers. One global limit is always wrong for somebody:

And the off switch matters more than it looks. StayHub keeps one:

    rate_limit_enabled: bool = True

Rate limiting you cannot disable without a deploy is rate limiting you cannot disable during the incident it is causing. That is a small piece of configuration bought cheaply, and the day you need it you will need it urgently.

What rate limiting is not

Worth being clear about the boundary, because it gets asked as a follow-up.

A rate limiter counts requests per client and refuses the excess. That defends against one abusive client, a buggy integration, and credential stuffing from a small set of addresses. It is the right tool for those.

It is not a defence against a distributed denial of service, where the traffic comes from a hundred thousand hosts each making a handful of requests. None of them exceeds any per-client limit, and your servers are still saturated — frequently at a layer beneath HTTP, where the limiter never sees the packets. That is a problem for network-level scrubbing, upstream capacity, and a CDN absorbing the load, which is one more argument for the coarse layer living at the edge.

Nor is it a defence against an expensive legitimate request. Sixty allowed searches a minute is still sixty searches, and if one of them can trigger an unbounded query the limit is irrelevant. Pagination caps, query timeouts and result limits are what protect against that — different mechanisms, aimed at cost per request rather than requests per client.

The summary

• Token bucket by default. Two numbers of state, and burst is a parameter rather than an accident.
• Never fixed window for anything security-related — the boundary gives away double the limit.
• The counter must be atomic. Read-modify-write multiplies your limit by the number of workers and passes every sequential test.
• Test it concurrently, with an exact assertion.
• Key on the account when you have one, and never trust X-Forwarded-For without a trusted proxy in front.
• Different limits for different endpoints. Strict where a secret is guarded, generous where a server is.
• Return Retry-After, keep your normal error shape, and keep the CORS headers.
• Decide fail-open or fail-closed deliberately, and check that no code path escapes the decision.

Two ideas here generalise well beyond rate limiting. The first is that a decision depending on a shared value must read and write it in one operation — the same principle that made a database constraint the right answer for double booking, applied to a different store. The second is that every protective component needs an explicit answer for what it does when it is broken, because the default answer is usually to fail closed, and a security component that takes down the thing it protects has traded one problem for a worse one.

Next: generating unique ids — the last of the mechanisms before the case studies begin.