Rate limiting

A rate limiter decides, for each request, whether this caller may make it now. It counts what a key has done recently. A key is a user, an API key, an IP, or a tenant. It compares that count with a rule, such as “100 a second, bursts of 200”. And it answers yes, or “429, try again in 300 ms”. The algorithm fits on an index card. The hard parts are choosing what to count, and where to count it. Plus what to do when the counter is unreachable, and knowing when a rate limit is the wrong tool.

This page is the reference on the concept. The distributed rate limiter problem designs one end to end for 330 gateways, and the low level design builds the classes.

The problem it solves

An orders API runs comfortably at 20,000 requests a second, with a database that tops out near 30,000. Four things go wrong without limits:

1. Abuse. A credential stuffing bot tries 3,000 passwords a second against /login. A scraper walks every product page. Without a limit per account and per network, both run at whatever speed their hardware allows.
2. Fairness. One customer ships a bug that retries in a tight loop at 15,000 requests a second. Every other customer shares the remaining headroom with it, and their p99 latency triples. Nobody did anything wrong except one tenant.
3. Cost. Some requests cost real money: an SMS at about a cent each, a call to a paid third-party API, a GPU inference. A runaway loop on /send-sms is a bill, not just load.
4. Protecting downstreams. A payment provider allows you 500 calls a second. The database has 5,000 connections. If you send more, they refuse or fall over, and the failure comes back to you.

A rate limiter answers all four by bounding what each key may do. It does not, on its own, bound what the whole system receives: 100,000 keys each under their limit can still overload the database. That job belongs to load shedding, which this page covers too, because the two are often confused.

Four words get used loosely:

Term	What it bounds	What the caller sees
Rate limit	Requests per key per unit of time	429 with Retry-After
Quota	A total over a long period (10,000 calls a month)	429 or 403 until the period resets
Throttling	Delaying requests to a steady rate instead of refusing	Slower responses, no errors
Load shedding	Total work in the server, whoever sent it	503, ideally lowest priority first

How it works

Every algorithm below enforces the same rule, “5 requests a second”, and differs in what it remembers per key and how it treats a burst.

Step 1: Count per fixed window

The simplest limiter keeps one counter per key per clock window. In Redis it is two commands: INCR rl:key_8f3:1730102400 and EXPIRE on the first increment. If the count passes the limit, refuse until the window rolls over.

It is cheap (one integer per key), and wrong in a specific way. A client can send 5 requests in the last 100 ms of one window, and 5 in the first 100 ms of the next. That’s 10 requests in 200 ms, twice the limit, and every one is admitted. At “1,000 an hour”, that is 2,000 within a few minutes, across the top of the hour. Windows aligned to the clock also synchronize clients. Everyone who was refused retries at :00, so the first second of every window is a spike.

Step 2: Remember every request

The sliding log stores a timestamp per admitted request and counts those newer than one window ago. In Redis it is a sorted set: ZREMRANGEBYSCORE to drop old entries, ZCARD to count, ZADD to record. It is exact: never more than 5 in any 1 second span, wherever the span starts.

The price is memory proportional to the limit. A limit of 1,000 a minute keeps up to 1,000 entries per key, about 80 KB at roughly 80 bytes per sorted set entry. A million active keys is 80 GB for the limiter alone. The sliding log is right for small limits that must be exact (5 login attempts per 15 minutes) and wrong for high-volume API limits.

Step 3: Weight the previous window

The sliding window counter keeps two fixed-window counters: this window’s, and the last one’s. It estimates the rolling count by assuming the previous window’s requests were spread evenly:

estimate = previous × (time left in the current window ÷ window) + current

Say it’s 1.1 s into a 1 s window scheme. 90% of the previous window still overlaps the rolling second. If the previous window held 10, the estimate starts at 9, and only one more fits. That’s two integers per key, and the instant burst at the boundary is gone. Cloudflare measured the error on 400 million requests: 0.003% of requests were wrongly allowed or refused.

The error that remains is in the “spread evenly” assumption. Say all 10 previous requests came in the last 50 ms. The estimate undercounts them. A client that then paces itself through the new window can approach 2× the limit over one rolling second. It cannot do that in 200 ms, as with a fixed window. And real traffic rarely has that shape, which is why the measured error is tiny. If the previous requests came early, it overcounts, and refuses a little too soon.

JSlidingWindowCounter.javaPysliding_window_counter.pyC#SlidingWindowCounter.csGosliding_window_counter.goTSsliding-window-counter.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.HashMap;
import java.util.Map;

// Two counters per key: the current fixed window and the one before it.
final class WindowPair {
    long startMs;
    int current;
    int previous;

    WindowPair(long startMs) {
        this.startMs = startMs;
    }
}

// "At most N per window", without the fixed window's double burst at the boundary and without
// the sliding log's timestamp per request.
final class SlidingWindowCounter {
    private final int limit;
    private final long windowMs;
    private final Map<String, WindowPair> keys = new HashMap<>();

    SlidingWindowCounter(int limit, long windowMs) {
        this.limit = limit;
        this.windowMs = windowMs;
    }

    boolean tryAcquire(String key, long nowMs) {
        long start = nowMs - nowMs % windowMs; // windows align to the clock, like INCR keys
        WindowPair w = keys.computeIfAbsent(key, k -> new WindowPair(start));
        if (w.startMs != start) {
            // Roll forward. If a whole window passed with no traffic, the previous count is 0,
            // not the stale one: the key was idle for that window.
            boolean justBefore = w.startMs == start - windowMs;
            w.previous = justBefore ? w.current : 0;
            w.current = 0;
            w.startMs = start;
        }
        // The rolling window covers the end of the previous window and the start of this one.
        // Assume the previous window's requests were spread evenly and count the overlapping
        // share. This assumption is the whole approximation, and it is usually close.
        double overlap = (double) (windowMs - (nowMs - start)) / windowMs;
        double estimate = w.previous * overlap + w.current;
        if (estimate + 1 > limit) return false; // refused requests are not counted, so a hammering client recovers
        w.current++;
        return true;
    }
}

class Main {
    static int admitted(SlidingWindowCounter limiter, long atMs, int attempts) {
        int n = 0;
        for (int i = 0; i < attempts; i++) if (limiter.tryAcquire("key_8f3", atMs)) n++;
        return n;
    }

    public static void main(String[] args) {
        var limiter = new SlidingWindowCounter(10, 1000); // 10 a second
        System.out.println(admitted(limiter, 900, 12)); // 10: the first window fills at 0.9 s
        // A fixed window would allow 10 more at 1.1 s: 20 requests in 0.2 s. Here 90% of the
        // previous window still overlaps, so it counts as 9 and only one more fits.
        System.out.println(admitted(limiter, 1100, 12)); // 1
        System.out.println(admitted(limiter, 1500, 12)); // 4: half the old window has slid out
        System.out.println(admitted(limiter, 3200, 12)); // 10: a full window of silence clears the history
    }
}

Step 4: Think in rate and burst: the token bucket

Most real limits are stated as a sustained rate plus a tolerance for bursts: “100 a second, bursts of 200”. The token bucket models that directly. A bucket holds up to b tokens and refills at r per second. Each request spends one token (or several, for an expensive call). No token, no admission. The refill is lazy: on each request, add elapsed × r, capped at b, so the state is two numbers per key: tokens and last-update time.

A key idle long enough has a full bucket. It can spend all b at once, then r per second after that. So a token bucket of “5 a second, bursts of 5” can admit close to 10 in a single second: 5 saved, plus up to 5 refilled. That is the rule doing what it says. It surprises people who read the limit as “at most 5 in any second”.

The leaky bucket has two meanings. As a meter, it is the token bucket upside down: a level that drains at r, and fills with each request. It behaves identically. As a queue, it holds requests and releases them at exactly r a second. It refuses only when the queue is full.

The queue version does not refuse a burst. It delays it. That is traffic shaping. It’s right in front of a fragile downstream that needs a smooth rate, like an SMTP relay, or a partner API with a strict per-second cap. It’s wrong for an API that should answer at once.

Step 5: One timestamp: GCRA

The generic cell rate algorithm (GCRA), from ATM networks, gives exactly token bucket behavior with one number per key. That number is the theoretical arrival time (TAT): the moment the key’s bucket would be full again, if nothing else arrived.

• The emission interval T is 1 ÷ r: 200 ms for 5 a second.
• On a request at time now, compute new_tat = max(tat, now) + T.
• If new_tat − now exceeds b × T, refuse. The wait is exactly new_tat − now − b × T.
• Otherwise store new_tat and admit.

There is no refill loop and no second field to keep consistent. A refused request changes nothing, so a client hammering the limit does not push its own recovery further away. The exact retry delay falls out for free, and a TAT in the past means “full bucket”, so the key can expire at the TAT. redis-cell and several popular libraries implement it.

JGcra.javaPygcra.pyC#Gcra.csGogcra.goTSgcra.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// Allow or refuse, plus the two numbers the 429 response and the headers need.
record GcraDecision(boolean allowed, int remaining, double retryAfterMs) {}

// GCRA (generic cell rate algorithm): "rate r a second, bursts of b", as a token bucket would
// enforce it, but stored as ONE number per key: the theoretical arrival time (TAT), the moment
// this key's bucket would be full again if nothing else arrived.
final class Gcra {
    private final double intervalMs;
    private final double burstOffsetMs;
    private final Map<String, Double> tat = new HashMap<>();

    Gcra(double ratePerSec, int burst) {
        // Emission interval: the gap between requests at exactly the sustained rate.
        this.intervalMs = 1000 / ratePerSec;
        // How far ahead of now the TAT may run. b intervals means b requests at once.
        this.burstOffsetMs = intervalMs * burst;
    }

    GcraDecision check(String key, double nowMs) {
        // A TAT in the past means the bucket is full: start from now. There is no refill
        // loop and no second field to keep in step, which is why one SET can store it.
        double t = Math.max(tat.getOrDefault(key, nowMs), nowMs);
        double newTat = t + intervalMs;
        double ahead = newTat - nowMs;
        if (ahead > burstOffsetMs) {
            // Refused: nothing is stored, so a client hammering the limit does not push its
            // own TAT further out. The wait is exact, not a rounded window reset.
            return new GcraDecision(false, 0, ahead - burstOffsetMs);
        }
        tat.put(key, newTat);
        int remaining = (int) Math.floor((burstOffsetMs - ahead) / intervalMs);
        return new GcraDecision(true, remaining, 0);
    }

    void evictIdle(double nowMs) {
        // A key whose TAT has passed behaves exactly like a key that was never seen, so it
        // can be dropped. In Redis the same fact becomes a TTL of (TAT - now).
        tat.values().removeIf(t -> t <= nowMs);
    }
}

class Main {
    public static void main(String[] args) {
        var limiter = new Gcra(5, 5); // 5 a second, bursts of 5
        List<GcraDecision> burst = new ArrayList<>();
        for (int i = 0; i < 7; i++) burst.add(limiter.check("key_8f3", 0));
        System.out.println(burst.stream().map(GcraDecision::allowed).toList()); // five true, then false, false
        System.out.println(burst.get(5).retryAfterMs()); // 200.0: the next request fits one interval later
        System.out.println(limiter.check("key_8f3", 200).allowed()); // true
        System.out.println(limiter.check("key_8f3", 200).allowed()); // false: only one interval has passed
    }
}

All six side by side, on the same request stream. Every lane is set to 5 a second:

Off2 req/s8 req/s

Burst of 1512 across a window edgeStartReset

ShowFixed windowSliding logSliding window counterToken bucketLeaky bucket (queue)GCRA

Every limiter allows 5 requests a second. Tall green ticks were admitted, short red ticks were refused with a 429. The leaky bucket delays instead: amber runs from arrival to release. A red border means a lane admitted more than 5 in some 1 second span, shaded on its timeline.

Fixed windowidlekeeps 1 counter + window idadmitted 0 · refused 0

Sliding logidlekeeps 1 timestamp per requestadmitted 0 · refused 0

Sliding window counteridlekeeps 2 countersadmitted 0 · refused 0

Token bucketidlekeeps 2 numbersadmitted 0 · refused 0

Leaky bucket (queue)idlekeeps a queue + 1 timestampadmitted 0 · refused 0

GCRAidlekeeps 1 timestampadmitted 0 · refused 0

−10 s−5 snow

Press Start, then fire a burst. Watch the right edge of each lane: who admits the burst, and who spreads it out.

Things to try:

• Turn background traffic off, then fire 12 across a window edge. The fixed window admits 10 within about 0.3 s: 5 before the edge, and 5 after. The sliding log and the sliding window counter admit 5.
• Fire a burst of 15. Token bucket and GCRA admit the 5 tokens they saved, plus one that refills during the burst. They refuse the rest at once. The leaky bucket admits about as many, but queues them, and the last one waits a second.
• Watch token bucket and GCRA. Their lanes are identical, request for request. Their “most in any 1 s” reaches 9 after an idle period: 5 saved, plus 4 refilled. (The next token lands exactly at the 1 s mark.) That’s burst plus refill, as designed.
• Switch to 8 requests a second. Everyone refuses some all the time. The leaky queue stays full, so every admitted request waits about a second: the cost of shaping under sustained overload. The sliding window counter’s peak can creep to 6: its estimate, not an exact count.

Step 6: Choose where to enforce

A request passes several places that could refuse it. Each sees different information and costs a different amount to reject at.

Layers that can refuse a request

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database

Layer	Knows	Good for	Cannot
Client	Its own traffic	Pacing to the published limit, backing off on 429, saving round trips	Be trusted: attackers do not run your SDK
Edge / CDN / WAF	IP, prefix, TLS fingerprint, path	Floods and bots, rejected before TLS and app work reach your origin	See the user or tenant unless it parses tokens
API gateway	Authenticated key, user, tenant, plan	Plan limits and fairness, the main place for per-key limits	Know what a request costs inside the service
Service	The operation, its cost, its own load	Business limits (5 password tries per account), concurrency, shedding	Refuse before the request already used a connection
Per dependency (egress)	Calls to one downstream	Staying under a partner’s quota, bulkheads so one slow dependency cannot take every thread	Help callers upstream unless it pushes back

Production systems use several layers at once. The cheap, coarse limits run first. Per IP at the edge stops a flood before it reaches your origin. The precise ones run later, like per tenant at the gateway. The ones that need business context run last, like per account in the login service.

Step 7: Beyond fixed rates: load shedding and adaptive limits

A rate limit is a number someone chose. The server’s real capacity changes: a cold cache, a slow disk, a database failover, a deploy. Little’s law says requests in flight = arrival rate × latency. At 1,000 requests a second and 50 ms, the service holds 50 in flight.

Now say the database slows, and latency hits 500 ms. The same admitted rate means 500 in flight. The 200-thread pool is exhausted, queues grow, and every request times out. Every client was under its limit the whole time.

Two tools handle this, and neither is a per-key rate limit:

• Load shedding. The server refuses work when it is overloaded, measured by its own signals: in-flight requests, queue time, CPU. It sheds the least important work first. Google’s internal RPCs carry a criticality (critical, sheddable) for exactly this, and Stripe describes shedding non-critical traffic when its fleet is near capacity. A shed request gets 503, not 429, because the caller did nothing wrong.
• Adaptive concurrency limits. Instead of a configured rate, the server learns how many requests it can have in flight, by watching latency. It’s the way TCP finds a path’s bandwidth. Grow the limit slowly while latency is fine. Cut it by a fraction when latency rises. (This is called additive increase, multiplicative decrease, or AIMD.) Netflix’s concurrency-limits library and Envoy’s adaptive concurrency filter both do this.

JAimdLimiter.javaPyaimd_limiter.pyC#AimdLimiter.csGoaimd_limiter.goTSaimd-limiter.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// An adaptive concurrency limit: how many requests may be in flight at once, learned from
// latency instead of configured. A fixed rate cannot know that the database just got slower;
// this limit finds out within a few round trips and backs off, the way TCP does.
final class AimdLimiter {
    double limit;
    private final int min;
    private final int max;
    private final double targetMs;
    private int inFlight;
    private int sinceCut; // completions since the last decrease

    AimdLimiter(double initial, int min, int max, double targetMs) {
        this.limit = initial;
        this.min = min;
        this.max = max;
        this.targetMs = targetMs;
    }

    boolean tryAcquire() {
        // Over the limit means refuse NOW (a fast 503), not queue: a queue would only turn
        // the overload into latency for every request behind it.
        if (inFlight >= Math.floor(limit)) return false;
        inFlight++;
        return true;
    }

    void release(double latencyMs) {
        inFlight--;
        sinceCut++;
        if (latencyMs > targetMs) {
            // Multiplicative decrease, at most once per window of requests. Cutting on every
            // slow reply would collapse the limit within one round trip of a blip.
            if (sinceCut >= limit) {
                limit = Math.max(min, limit * 0.9);
                sinceCut = 0;
            }
        } else {
            // Additive increase: +1 for every `limit` fast replies, about +1 per round trip.
            // Probing upward slowly is what lets it find new capacity after a recovery.
            limit = Math.min(max, limit + 1 / limit);
        }
    }
}

class Main {
    // Each round, 100 requests arrive at a service that runs `capacity` at once in 40 ms.
    // Anything above capacity waits its turn, so latency grows by 40 ms per extra batch.
    static int simulate(AimdLimiter limiter, int rounds, int capacity) {
        for (int r = 0; r < rounds; r++) {
            int admitted = 0;
            for (int i = 0; i < 100; i++) if (limiter.tryAcquire()) admitted++;
            double latency = 40 * Math.ceil((double) admitted / capacity);
            for (int i = 0; i < admitted; i++) limiter.release(latency);
        }
        return (int) Math.floor(limiter.limit);
    }

    public static void main(String[] args) {
        var limiter = new AimdLimiter(10, 5, 200, 100);
        System.out.println(simulate(limiter, 60, 30)); // 55: healthy, it saws between 50 and 61 at 80 ms
        System.out.println(simulate(limiter, 30, 10)); // 21: the database slows, it backs off to about 20
        System.out.println(simulate(limiter, 60, 30)); // 54: recovered, it climbs back by about 1 a round
    }
}

In the run above, the limit settles between 50 and 61 while the service is healthy. It falls to about 20 within a few rounds when the database slows. And it climbs back by about 1 a round when it recovers. No one edited a config.

TradeoffPer-key rate limits plus a server-side concurrency limit

We gain

Rate limits give each customer a predictable, documented share and stop abusers. The adaptive limit protects the server from total overload, including the case where every key is within its limit.

We give up

Two mechanisms to tune and two kinds of refusal (429 and 503) for clients to handle. The adaptive limit is less predictable: a tenant can be shed while under its published rate.

Options and tradeoffs

The algorithm

Algorithm	State per key	Bursts	Accuracy	Retry-After	Wins when
Fixed window	1 counter (~70 bytes in Redis)	Up to 2× the limit across a window edge	Off by up to 2× at edges	Next window start	Coarse limits where the edge burst does not matter
Sliding log	1 timestamp per request (~80 B each)	Exactly N in any window	Exact	Oldest entry + window	Small limits that must be exact (login attempts)
Sliding window counter	2 counters	Small overshoot, near 2× if paced adversarially	Approximate (0.003% in Cloudflare’s data)	Estimated	“N per minute/hour” stated as a window, high volume
Token bucket	2 numbers (tokens, last time)	Up to b at once, then r a second	Exact for “rate r, burst b”	Exact	Limits stated as rate plus burst; weighted request cost
Leaky bucket (queue)	A queue of up to b requests + 1 time	Delayed, never passed through faster than r	Exact output rate	Not refused, delayed	Shaping traffic to a fragile downstream
GCRA	1 timestamp (TAT)	Same as token bucket	Same as token bucket	Exact	Token bucket semantics with the least state and one SET

TradeoffToken bucket or GCRA for API limits, sliding window counter for windowed quotas

We gain

Bursts that match how clients really behave: a page load fires 20 calls, then nothing. Constant memory per key, and an exact retry time for the 429. The sliding window counter covers rules that users read as “1,000 per hour”.

We give up

A bucket’s worst second admits burst plus rate, about twice the headline number. When a contract says “never more than N in any minute”, that needs a sliding log or a smaller burst.

Common mistake

"A token bucket of 100 a second never admits more than 100 in a second"

It admits up to b + r in any one second: the burst it saved while idle plus what refills. A bucket of 100 a second with a burst of 100 can admit close to 200 in one second, then 100 a second after. The demo’s “most in any 1 s” shows it. If a downstream truly cannot take more than 100 in a second, set the burst small, or shape with a queue in front of it.

The key

What you count by decides who shares a budget.

Key	Wins when	Pitfall
API key	Public APIs, machine clients	One key shared by a customer’s whole fleet: 200 servers share one budget
User ID	Logged-in products, per-person actions	Unavailable before login, which is where abuse starts
Tenant / org	B2B fairness, plan limits	One big tenant’s users starve each other; pair with per-user limits inside it
IP address	Before authentication: login, signup, floods	Carrier-grade NAT puts hundreds to thousands of users behind one IPv4 address; IPv6 gives one user 2^64 of them
IPv6 /64 (or /56)	The IPv6 equivalent of “one client”	Some providers hand each customer a /56 or /48, so a determined client still rotates
Account + action	Security limits (password tries, OTP sends)	Lets an attacker lock a victim out, so refuse with backoff or a challenge, not a hard lock

Two IP mistakes deserve names. Trusting X-Forwarded-For: the leftmost entry is whatever the client wrote, so a limiter keyed on it lets an attacker pick a fresh key per request. Use the address your own edge appended (the rightmost entry added by a proxy you trust). Per-address IPv6 limits: a home connection typically gets a /64, so limiting each address limits nothing. Key IPv6 on the /64 and, for abuse, also on the /48.

TradeoffLayered keys: IP before login, user or API key after, tenant on top

We gain

Anonymous floods stop at the edge, each authenticated caller gets its own fair share, and one tenant cannot crowd out the rest.

We give up

Several counters checked per request, and each refusal must say which rule fired, or support cannot explain it to the customer.

Counting across many servers

Behind a load balancer, one key’s requests land on every gateway. Where the count lives is the distributed systems part of rate limiting.

Option	How	Accuracy	Cost
Local only, limit ÷ N	Each of N gateways enforces its share in memory	Poor when traffic spreads unevenly or limits are small	Nothing: no network call
Central store, atomic script	Redis holds the counter, a Lua script reads, decides and writes in one step	Exact	A round trip per check (~0.3 to 1 ms), a store to run
Local + periodic sync	Gateways count locally, push deltas and pull totals every 100 ms to 1 s	Overshoot up to what all N admit in one sync interval	Background traffic, more complex code
Cell-based	Each cell (a full stack serving a slice of tenants) has its own limiter store	Exact within a cell, approximate for limits across cells	Tenants must be routed to a home cell

The central store needs one property above all: check and update in one atomic step. Read, then write from the gateway, and two gateways can both see the last token:

Why the check and the update must be one step

Scroll or pinch to zoom, drag to pan

• Color key
• Cache
• Service

Redis runs a script to completion before any other command, which is why the script is the unit of correctness. GCRA keeps it short:

-- KEYS[1]: the key's TAT. ARGV[1]: interval in ms. ARGV[2]: burst.
local t = redis.call('TIME')                     -- the store's clock, not 300 gateway clocks
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local interval, burst = tonumber(ARGV[1]), tonumber(ARGV[2])
-- TIME in a script that writes needs effect replication: the default since Redis 5, the only mode in 7.
local tat = math.max(tonumber(redis.call('GET', KEYS[1])) or now, now)
local ahead = tat + interval - now
if ahead > interval * burst then
  return {0, ahead - interval * burst}            -- refused, and the exact retry delay
end
redis.call('SET', KEYS[1], tat + interval, 'PX', math.ceil(ahead))  -- gone once the bucket is full
return {1, 0}

At very high rates per key, even a central store becomes a hot spot. The usual answers are token leases (a gateway takes a batch of tokens, and spends them locally) and a refusal cache. Both are built in stage 5 of the rate limiter problem.

TradeoffA central store with atomic scripts, local fallback when it is down

We gain

Exact limits whatever the load balancer does, one place to change rules, and an exact retry delay.

We give up

Under a millisecond added to every request, a sharded Redis tier to operate, and a failure mode that must be designed (next section).

Telling the client

A refusal is part of the API. It should tell the client when to come back, and responses that succeed should tell it how close it is.

HTTP/1.1 429 Too Many Requests
Retry-After: 2
RateLimit-Policy: "default";q=100;w=60
RateLimit: "default";r=0;t=2
Content-Type: application/problem+json

{ "title": "Too many requests", "detail": "100 requests per 60 s for this API key." }

• 429 Too Many Requests (RFC 6585): this caller, specifically, is over a limit.
• Retry-After (RFC 9110): seconds, or an HTTP date. Whole seconds only, so round up.
• RateLimit-Policy and RateLimit: the IETF httpapi working group’s draft, in its recent structured-field form. It gives the policy’s quota q per window w, and the remaining r, with t seconds until it resets. It is still an Internet-Draft, and its syntax has changed between revisions, so name the revision you implement. Earlier drafts used RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset. Most public APIs still send the X-RateLimit-* family. GitHub, for example, sends x-ratelimit-limit, -remaining, -used and -reset (a Unix timestamp).

Clients must add jitter to Retry-After. If 5,000 clients are refused at once and all retry in exactly 2 seconds, the limiter sees the same spike again 2 seconds later.

Go deeperHeader details that cause support tickets1 min

The most common confusion is whether Reset is seconds-until or a Unix timestamp. Document which. Prefer seconds-until, which needs no clock agreement. Send the headers of the tightest rule, the one closest to refusing. Do not send limit headers for security rules (login attempts). They tell an attacker exactly how fast to go.

For a shed request, send 503 with Retry-After, never 429. Then clients do not conclude they personally misbehaved. Some APIs return 403 for abuse limits. That tells well-behaved clients to stop forever, which is rarely what you mean.

How it fails

The limiter’s store is down or slow. Every request now waits on a timeout, and the limiter has become the outage. Decide per rule what happens, and bound the time it takes to decide:

A limiter check with a bounded failure path

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database

Fail open for fairness limits: a few seconds without per-key limits is far better than refusing every customer. Fail closed for limits that are the security or cost control: login attempts, password resets, SMS sends. A local fallback sits in between and keeps a runaway client within about twice its limit. The rate limiter problem’s deep dive walks through the numbers.

Limits that protect no one. Every key is limited. A botnet of 50,000 IPs each sends 2 requests a second, well under the per-IP limit of 10. The service receives 100,000 a second. Per-key limits bound each caller, never the total. Detect it as total traffic far above normal, with no single key over its limit. Fix it with a global concurrency limit or load shedding at the service. And add edge rules that look at wider signals (prefix, fingerprint, path).

Synchronized retries. Fixed windows reset on the clock, so refused clients all come back at :00. Retry-After without client jitter does the same. The limiter sees a sawtooth of spikes at exactly the moment it has the least headroom. Use sliding windows or buckets, and jitter retries.

The wrong key. Keying on a spoofable header lets attackers rotate keys freely. Keying on a shared IP refuses a whole office, or a mobile carrier’s customers, because one of them misbehaves. Detect it as many refusals for one key, from many distinct user agents or accounts. Or as one user’s requests spread across thousands of keys.

A bad rule push. Someone sets a limit to 10 instead of 10,000, and every customer gets 429. Ship new rules in shadow mode first: evaluate and log would-be refusals, but refuse nothing. Roll them out gradually. And alert on the refusal rate per rule.

Hot keys. One tenant at 300,000 requests a second lands on one store shard however many shards there are. Token leases and a refusal cache keep that shard’s load bounded.

Failure	Blast radius	Detect	Fix
Store down or slow	Every request, through latency	Limiter p99 and timeout rate per shard	5 ms timeout, breaker, fail mode per rule
Distributed abuse under limits	The whole service	Total load high, no key over its limit	Concurrency limit, load shedding, edge rules
Synchronized retries	Spikes at window resets	Request rate sawtooth aligned to the clock	Buckets or sliding windows, jittered retries
Wrong or spoofable key	Innocent users refused, or no limit	Refusals per key vs distinct users behind it	Trusted client IP, IPv6 /64, layered keys
Bad rule push	Every customer under that rule	Refusal rate per rule jumps after a deploy	Shadow mode, gradual rollout, fast rollback
Hot key	One shard, everyone on it	Calls per key per shard	Token leases, refusal cache, dedicated shards

At scale

Numbers to remember.

What	Typical figure
Redis round trip in the same zone	0.2 to 0.5 ms; budget about 1 ms for the whole check
One Redis shard running short Lua scripts	Tens of thousands to about 100,000 a second
Token bucket or GCRA state per key in Redis	About 60 to 100 bytes; 10 million active keys is about 1 GB
Sliding log at 1,000 a minute	About 80 KB per key
Sliding window counter error (Cloudflare)	0.003% of 400 million requests decided wrongly
GitHub REST API	5,000 requests an hour per authenticated user, 60 per IP unauthenticated
AWS API Gateway default account throttle	10,000 requests a second, bursts of 5,000, per Region (token bucket)
Carrier-grade NAT	Hundreds to thousands of subscribers per public IPv4 address

At 10x (from 10,000 to 100,000 checks a second), one Redis instance is no longer enough. Shard the counters by key, with a hash tag, so all of one key’s rules live on one shard. Then one script sees them all. Load the scripts once, and call them by SHA. Put a short-lived refusal cache in each gateway. Then a client stuck at its limit costs one store call per retry interval, instead of one per request.

At 100x (millions of checks a second, several regions), the round trip to a central store is too expensive for every request. Gateways spend leased tokens locally, and sync in batches, accepting a small overshoot.

Global limits across regions split each key’s budget between regions, and rebalance every few seconds. That’s because a cross-region call (60 to 150 ms) on the hot path is out of the question. Cell-based designs keep each tenant’s counters inside its home cell. Server-side concurrency limits matter more, because no configured rate tracks the real capacity of a fleet that large.

What to monitor:

• Refusals per rule and per key, with the top keys by refusals. A new key at the top is either an incident at a customer or an attack.
• Limiter check latency (p99) and store timeout rate per shard. The limiter’s latency is added to every request.
• Fail-open time: how many seconds a rule ran without enforcement, and how many requests passed.
• Shadow mode would-be refusals for every rule before it enforces.
• Total traffic against the sum of what the limits allow, to see how far the limits are from protecting capacity.
• For adaptive limits: the current limit and the shed rate. A limit falling steadily is an early warning that a dependency is slowing down.

Go deeperClient-side adaptive throttling1 min

Google’s SRE book describes clients that refuse their own requests, before sending them. Each client tracks two counts over the last two minutes: requests (attempted) and accepts (accepted by the backend). It drops a new request locally with probability max(0, (requests − K × accepts) ÷ (requests + 1)), with K typically 2.

While the backend accepts everything, nothing is dropped. When the backend starts refusing, clients stop sending most of the traffic that would have been refused anyway. So refusals stop costing the backend work. It suits internal service-to-service calls, where you control the clients.

In the interview

Interviewer asksToken bucket or sliding window counter for a public API? Defend the choice.

It depends on how the limit is stated. Most API plans read as a rate with a burst: “100 a second, bursts of 200”. A token bucket enforces exactly that, with two numbers per key (or GCRA with one). And it gives an exact Retry-After. Bursts are normal for API clients. A page load fires 20 calls, and then goes quiet. If the product promises a window, “1,000 an hour, resets at the top of the hour”, a sliding window counter fits better. It’s still two integers per key, without the fixed window’s double burst at the edge. I would not use a sliding log above small limits: 1,000 a minute is 80 KB a key. And I would point out that a bucket can admit burst plus rate in one second. So a downstream that truly cannot take more needs a smaller burst.

Interviewer asksEvery API key is rate limited, yet a traffic spike still took the database down. How?

Per-key limits bound each caller, not the total. It happens two ways. Many keys are each under their limit (a launch, a botnet, a partner onboarding thousands of users). Or the database got slower, so the same request rate meant many more requests in flight, and the connection pool ran out. The fix is a second mechanism that measures the server. Put a concurrency limit at the service, ideally adaptive. It sheds load with 503 when in-flight requests or latency climb, lowest-priority traffic first. Rate limits stay, for fairness and abuse.

Interviewer asksWhere in the system would you enforce rate limits?

In layers. At the edge, coarse per-IP and per-prefix limits stop floods, before they cost TLS and app work. At the API gateway, limits per API key, user and tenant enforce plans and fairness. They’re backed by a shared store, so the count is right across all gateways. Inside services, business limits that need context, such as 5 password attempts per account per 15 minutes. Plus a concurrency limit for overload. On the way out, limits per dependency keep us under a partner’s quota. Clients get headers and Retry-After, so well-behaved ones pace themselves.

Interviewer asksThe Redis cluster behind the limiter goes down. What happens?

Nothing should wait more than a few milliseconds. The check has a 5 ms timeout, and a circuit breaker per shard, so we stop paying even that. Then each rule’s fail mode applies. Fairness limits fail open. Or better, they fall back to local buckets at the limit divided by the gateway count. So a runaway client stays within about twice its limit. Security and cost limits, like login attempts and SMS sends, fail closed. Failing them open is a brute-force window. We alert on time spent failed open.

Common mistake

Keying anonymous limits on the client IP from X-Forwarded-For

The leftmost entry of X-Forwarded-For is whatever the client sent. So an attacker gets a fresh key per request, and is never limited. Use the address your own edge appended. And remember what an IP is. One IPv4 address can be a whole mobile carrier’s customers behind NAT. And one IPv6 user owns a /64, so key IPv6 on the prefix.

Common mistake

Using 429 for overload

429 says “you are sending too much”. When the server is overloaded and the caller is within its limit, the answer is 503 with Retry-After. Mixing them breaks client retry logic and misleads dashboards: refusals per key look like misbehaving customers when the real problem is capacity.

Mid-level covers

Describes fixed window, sliding window and token bucket correctly, and picks one with a reason. Keeps the counter in Redis, with an atomic operation. Returns 429 with Retry-After.

Senior adds

Ties the algorithm to how the limit is stated, and knows a bucket admits burst plus rate. Chooses keys, with their pitfalls (NAT, IPv6 /64, spoofed headers). Layers enforcement from edge to dependency. Designs the failure path per rule. Adds load shedding or adaptive concurrency, because per-key limits never bound total load.

Seen in

• Rate limiter: the full distributed design, with token buckets in sharded Redis, local leases, hot keys, fail modes per rule and limits across regions.
• Job scheduler: a token bucket per tenant on claims, and 429 on create past a pending-runs quota. So one tenant’s burst drains at its share.
• Notification system: limits per producer, and honoring each push provider’s 429 and Retry-After with jitter on the way out.
• Pastebin: per account, IP and network limits on creates, in front of the size limit and the malware scan.
• Ticketmaster: why a rate limiter is the wrong tool for an on-sale spike (random winners reward bots). A waiting room is used instead, with limits as the backstop.
• Web crawler: rate limiting turned inside out, a politeness limit per host on our own requests, backing off on 429 and 503.
• Metrics and monitoring: per-team ingest limits at the distributor, so one team’s surge cannot slow every other team’s writes.
• Chat: sends limited per device, about 20 a second, and new conversations limited per account to slow spam.

Recap

The job. Bound what each key does per unit of time, for abuse, fairness, cost and protecting downstreams. Per-key limits never bound the total: that is load shedding’s job.

Algorithms. Fixed window is cheap but admits 2× at the edge. Sliding log is exact and costs a timestamp per request. Sliding window counter is two integers and nearly exact. Token bucket and GCRA enforce “rate plus burst” exactly, GCRA with one timestamp, and admit up to burst plus rate in one second. Leaky bucket as a queue delays instead of refusing.

Where. Client paces itself, edge stops floods by IP, gateway enforces per key and tenant, service applies business limits and concurrency, egress limits protect dependencies.

Keys. API key, user, tenant after login, IP before it. NAT puts thousands behind one IPv4, IPv6 keys on the /64, and never trust the leftmost X-Forwarded-For.

Distributed. A central store with an atomic script, for exact counts. Local leases and sync, for very high rates. Cells or regional budgets, at global scale.

Responses. 429 with Retry-After for over-limit callers, 503 for overload, limit headers on every response, jitter in every client.

Failure. Bounded timeout and breaker, fail open for fairness, fail closed for security and cost, local fallback in between, shadow mode for new rules.

Further reading

• The distributed rate limiter problem, and the rate limiter class design, on this site. Plus load balancing, for retry budgets and shedding at the balancer.
• Scaling your API with rate limiters, Stripe: request rate limits, concurrency limits and two kinds of load shedder in production.
• RateLimit header fields for HTTP, the IETF draft for RateLimit and RateLimit-Policy.
• Netflix concurrency-limits: adaptive concurrency limits (AIMD, Vegas, Gradient) as a library, with the reasoning behind them.