Talking between services · Chapter 13

Rate limiting

How to cap requests per user with token buckets, leaky buckets and sliding windows, enforce limits across many servers with Redis and Lua, and reply with 429s clients can use.

IntermediateInterview priority: High55 min
On this page
  1. The problem: one client can ruin it for everyone
  2. The idea: a counter per key, checked before the work
  3. How it works: the five algorithms
  4. A token bucket in code
  5. Rate limiting across many servers
  6. Where to enforce the limit
  7. Telling the client what happened
  8. Where this breaks
  9. When not to use it
  10. In the interview
  11. Quiz

The problem: one client can ruin it for everyone

Your public API can handle about 2,000 requests per second, and normal traffic is 1,200. Then, in the same week:

  • A customer's app release retries every failed call in a tight loop: 40,000 phones now send 5 requests per second each.
  • A scraper on a few hundred cloud machines downloads your whole catalogue as fast as it can.
  • Someone tries 10 million leaked passwords against your login endpoint.

Each of these alone uses more capacity than you have. The servers cannot tell which requests are "fair", so they slow down for everybody, and your best customers see timeouts because of someone else's bug.

One noisy client overloads the API, and a limiter in front stops it

  1. Most users send a few requests a minute. But one buggy script, scraper or attacker can send thousands a second, and slow the service down for everybody.
  2. A rate limit caps how many requests each user, key or IP address may send, for example 10 per second. Requests over the limit are rejected straight away with status 429, Too Many Requests.

A rate limiter counts how many requests each client has sent recently and rejects the ones over an agreed limit, straight away and cheaply, before they reach the expensive parts of the system. The rejected client gets HTTP 429 Too Many Requests. Everyone else carries on as normal.

The idea: a counter per key, checked before the work

Every rate limiter answers one question per request: has this key used up its allowance? Three choices define it.

  1. The key: who is being limited. An API key, a user ID, an IP address, or a combination such as user:42:POST /orders.
  2. The limit: how many requests over what period, and how much bursting is allowed. "100 per minute, bursts of 20".
  3. The action: reject with 429 (the usual), queue the request until it can run, or just log it ("shadow mode", useful when you introduce a new limit and want to see who it would hit).

Limits serve several purposes, and it helps to say which one you are designing for:

PurposeExample limitKey
Protect capacity1,000 requests/s per API keyAPI key
Fairness between tenantsFree plan 60/min, paid plan 6,000/minAccount and plan
Stop abuse5 failed logins per account per 15 minAccount, and separately IP
Control cost20 SMS verification codes per phone number per dayPhone number
Protect a fragile dependency50 calls/s to a partner's APIDestination

Choosing the key is harder than it looks. IP address is the only option before login, but many people share one IP (offices, universities, mobile carriers using carrier-grade NAT), while one attacker can rotate through thousands. Account or API key is fairer and harder to dodge, so use it whenever the request is authenticated, and keep per-IP limits generous.

How it works: the five algorithms

All five keep a little state per key and decide in constant time. They differ in how they treat bursts and how much memory they use.

Fixed window counter

Split time into windows (each minute, say) and keep one counter per key per window. Increment it on each request; reject once it passes the limit. The key can include the window number, rl:42:28736541, and expire shortly after the window ends.

A fixed window lets a burst through at the boundary

  1. The simplest method is a fixed window: count requests in each one-second window, and refuse once the count hits the limit. Easy, but a client can squeeze two windows’ worth of requests around the boundary.

It is the cheapest option (one integer per key), but with a limit of 100 per minute a client can send 100 requests at 12:00:59.9 and another 100 at 12:01:00.0: 200 requests in a fraction of a second, all allowed, because they fall in two windows. A fixed window can let through twice the limit in a short burst.

Sliding window log

Store the timestamp of every accepted request per key, for example in a Redis sorted set. On each request, drop timestamps older than the window, count what is left, and accept if the count is under the limit.

This is exact: at no moment does any 60-second span contain more than 100 accepted requests. The cost is memory. A limit of 1,000 per hour means storing up to 1,000 timestamps per key; at roughly 60–80 bytes per sorted-set entry in Redis, one million active keys need tens of gigabytes. Use it when limits are small (5 logins per 15 minutes) or exactness matters.

Sliding window counter

A clever middle ground: keep the fixed-window counters for the current and previous window, and estimate the count over the last full window by weighting the previous one by how much of it still overlaps.

Worked example. Limit 100 per minute. The previous minute had 80 requests; this minute has had 30 so far, and we are 15 seconds (25%) into it. The sliding minute still overlaps the last 75% of the previous window:

estimate = 30 + 80 × 0.75 = 90 → under 100, allow.

The estimate assumes the previous window's requests were spread evenly, so it can be slightly off when they were bunched, but it removes the 2× boundary burst, needs only two counters per key, and is accurate in practice: Cloudflare reported that only about 0.003% of requests were wrongly allowed or limited when it measured this approach on real traffic.

Token bucket

Each key has a bucket holding at most B tokens (the burst size) that refills at r tokens per second. A request takes a token; if the bucket is empty it is rejected. You do not need a timer to add tokens: store the token count and the time of the last update, and on each request add (now − last) × r, capped at B.

A token bucket saves up tokens, so short bursts are fine

  1. A token bucket is smoother. Each user has a bucket that refills with tokens at a steady rate, say 2 per second, and holds at most, say, 6. Each request spends a token. Short bursts are fine; sustained floods are not.

Worked example. r = 10 per second, B = 20. A client that has been quiet can send 20 requests instantly, then 10 per second after that. Over any 60 seconds it can send at most 20 + 60 × 10 = 620 requests: the long-run rate is capped by r and the burst by B, and you tune them separately. That is why it is the most widely used algorithm: AWS API Gateway and Stripe describe their limits as token buckets.

A useful extension is cost: an expensive call (a search, a bulk export) can take 5 tokens instead of 1.

Leaky bucket

The name is used for two slightly different things, and interviewers may mean either:

  • As a queue: requests join a FIFO queue of size B and leave at a fixed rate r. Output is perfectly smooth, which suits a fragile downstream system, but requests wait (latency).
  • As a meter: the bucket "drains" at rate r, each request adds one unit, and a request that would overflow B is rejected. This is mathematically the mirror image of a token bucket. NGINX's limit_req works this way (with a burst parameter), and GCRA (the generic cell rate algorithm) is a compact version that stores a single timestamp per key: the "theoretical arrival time" of the next allowed request.

Comparing them

AlgorithmState per keyBurstsAccuracyUse when
Fixed window1 counterUp to 2× the limit at a boundaryRoughDaily quotas, cheap coarse limits
Sliding window log1 timestamp per requestNone beyond the limitExactSmall limits that must be exact (logins, OTPs)
Sliding window counter2 countersSmoothedVery closeLarge per-minute limits at scale
Token bucketTokens + timestampAllowed up to B, tunableExact for its modelThe default for API limits
Leaky bucket (queue)A queueAbsorbed, then released steadilyExactSmoothing traffic into a fragile consumer

A token bucket in code

On one server, a token bucket is a few lines. The bucket refills lazily when it is checked.

public final class TokenBucket {
    private final double capacity;       // B: the biggest burst
    private final double refillPerSec;   // r: the long-run rate
    private double tokens;
    private long lastNanos;

    public TokenBucket(double capacity, double refillPerSec) {
        this.capacity = capacity;
        this.refillPerSec = refillPerSec;
        this.tokens = capacity;          // start full
        this.lastNanos = System.nanoTime();
    }

    public synchronized boolean tryAcquire(double cost) {
        long now = System.nanoTime();
        double elapsed = (now - lastNanos) / 1e9;
        tokens = Math.min(capacity, tokens + elapsed * refillPerSec);
        lastNanos = now;
        if (tokens >= cost) {
            tokens -= cost;
            return true;
        }
        return false;
    }

    /** Seconds until `cost` tokens will be available: the value for Retry-After. */
    public synchronized double secondsUntil(double cost) {
        return Math.max(0, (cost - tokens) / refillPerSec);
    }
}

// one bucket per key, created on first use
ConcurrentHashMap<String, TokenBucket> buckets = new ConcurrentHashMap<>();
boolean ok = buckets.computeIfAbsent(apiKey, k -> new TokenBucket(20, 10)).tryAcquire(1);

Two details matter. Use a monotonic clock (nanoTime, time.monotonic), not wall-clock time, so a clock adjustment cannot hand out or take away tokens. And a map of buckets for every key ever seen grows forever; in production, evict idle buckets (a full bucket is the same as no bucket, so dropping it loses nothing).

Rate limiting across many servers

The in-memory version breaks as soon as you have more than one API server. With 10 servers behind a load balancer, each one sees about a tenth of a client's requests, so a limit of 100 per minute per server lets the client send 1,000. You have three options.

OptionHowGood atWeak at
Local limit ÷ NEach of N servers allows limit/NNo network call, no shared stateWrong when traffic is uneven or N changes; useless for small limits
Central store (Redis)Every server checks a shared counterAccurate global limit+0.2–0.5 ms per request; Redis must be highly available
Local + periodic syncServers count locally and push deltas every second or soCheap and close to accurateCan overshoot by up to one sync interval of traffic

The usual interview answer is Redis, because it is fast (about 100,000+ operations per second per node), supports expiring keys, and runs commands one at a time on each shard.

The race: check-then-set is not atomic

The obvious Redis code reads the count, compares it, then writes it back. With two API servers that is a race:

  1. Server A reads count = 99. Server B reads count = 99.
  2. Both decide 99 < 100 and allow the request.
  3. Both write 100. Two requests were allowed, but the counter only went up by one.

Under load this happens constantly, so the limit leaks. The fix is to make the read, decision and write one atomic step. For a fixed window, INCR already is one (it returns the new value, and you reject if it is over the limit). For a token bucket or sliding window, which need several commands, run them in a Lua script: Redis executes a script from start to finish without running any other command in between.

-- KEYS[1] = bucket key, e.g. "rl:{apikey_42}"
-- ARGV[1] = refill rate (tokens/s), ARGV[2] = capacity, ARGV[3] = cost
local rate     = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

local t   = redis.call('TIME')                       -- Redis's clock, same for every app server
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity        -- a new key starts full
local ts     = tonumber(state[2]) or now

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

local allowed, retry_after = 0, 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
else
  retry_after = (cost - tokens) / rate
end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) + 1)   -- idle keys clean themselves up
-- Lua numbers become integers when returned, so send the fractions as strings
return {allowed, tostring(tokens), tostring(retry_after)}
// Jedis; load the script once, then call it by its SHA on every request
String sha = jedis.scriptLoad(TOKEN_BUCKET_LUA);

List<Object> r = (List<Object>) jedis.evalsha(sha,
        List.of("rl:{" + apiKey + "}"),
        List.of("10", "20", "1"));                 // rate, capacity, cost
boolean allowed = ((Long) r.get(0)) == 1L;
double retryAfter = Double.parseDouble((String) r.get(2));

Using redis.call('TIME') means every app server uses the same clock, so skew between app servers cannot add or remove tokens. (Redis 5 and later replicate the script's writes rather than re-running it, which makes reading the time inside a script safe.) The braces in rl:{apikey_42} are a hash tag: in Redis Cluster, only the part inside braces decides the shard, so any other keys you add for the same client land on the same shard and can be used in one script.

A sliding window log in Redis

A sorted set per key, scored by time, does the sliding log. Run it as one script so the trim, count and add are atomic:

-- KEYS[1] = log key; ARGV[1] = window in ms; ARGV[2] = limit; ARGV[3] = unique request id
local t = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
local window = tonumber(ARGV[1])
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)    -- forget old requests
if redis.call('ZCARD', KEYS[1]) < tonumber(ARGV[2]) then
  redis.call('ZADD', KEYS[1], now, ARGV[3])                  -- the id keeps same-ms requests distinct
  redis.call('PEXPIRE', KEYS[1], window)
  return 1
end
return 0

Only accepted requests are recorded, so a client hammering away while blocked does not extend its own ban. Some APIs deliberately do the opposite (record rejected requests too) to punish clients that ignore 429s.

Where to enforce the limit

Limits work best in layers, each stopping a different kind of traffic as early and cheaply as possible.

Limits usually live in the gateway, in front of every service

  1. Rate limits usually live in an API gateway or load balancer in front of everything, so bad traffic is stopped before it costs you anything. They protect your servers, keep things fair, and limit the damage from bugs and abuse.
LayerLimits onCatches
Edge / CDN / WAFIP address, country, request signatureFloods and crude bots before they reach your data centre
API gatewayAPI key, user, plan, endpointPer-customer quotas and fairness: the main place
Inside a serviceBusiness keys (account, phone number, card)Logins, OTPs, coupon abuse: rules that need business data
Before a dependencyDestinationStaying under a partner's quota or a fragile database's capacity
ClientItselfWell-behaved SDKs that throttle themselves and honour Retry-After

A gateway limit is generic; "5 failed logins per account in 15 minutes" needs to know whether the password was wrong, so it lives in the login service.

Telling the client what happened

A good rejection is fast, cheap and tells the client exactly what to do.

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 3
RateLimit-Policy: 100;w=60
RateLimit: limit=100, remaining=0, reset=3

{"error": "rate_limited", "message": "Limit of 100 requests per minute reached. Retry in 3 seconds."}

Retry-After (seconds, or an HTTP date) is the standard header. The RateLimit-* headers come from an IETF draft that is still evolving; many APIs use the older X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset, as GitHub does. Sending the remaining allowance on successful responses too lets good clients slow down before they hit the wall.

Retry-After tells polite clients how long to wait

  1. Good limits also tell clients when to come back, with a Retry-After header. Well-behaved apps wait instead of hammering the server with instant retries.

Use 429 when one client exceeded its own limit, and 503 Service Unavailable (also with Retry-After) when the server itself is overloaded and shedding load from everyone (see circuit breakers and load shedding).

Clients that retry a 429 immediately make things worse, so client SDKs should honour Retry-After and otherwise back off exponentially with jitter (see timeouts, retries and circuit breakers).

Where this breaks

Two more to mention: a botnet of 100,000 IPs, each sending 2 requests a minute, never trips a per-IP limit (bot detection, CAPTCHAs and per-account limits are the other layers); and limits that are too tight hurt real users, so introduce new limits in shadow mode first and look at who would be blocked.

When not to use it

  • Internal batch jobs talking to systems you control. A queue with a fixed number of consumers controls throughput more simply than a limiter.
  • As your only overload protection. Per-client limits do not help when 50,000 well-behaved clients together exceed capacity. You also need autoscaling, load shedding and circuit breakers.
  • Where waiting is better than refusing. For a job that must eventually run (sending invoices), queue it and drain at the allowed rate (a leaky bucket as a queue) rather than rejecting it.

In the interview

Your turn: protect a login endpoint

Your login endpoint is under a credential-stuffing attack: millions of leaked username and password pairs, sent from about 20,000 IP addresses, each IP trying a few passwords a minute. Normal users log in a few times a day. Design the rate limits: what keys, what limits, what algorithm, what response, and what else you would add.

Compare with our answer
  • Per account: at most about 5 failed attempts per 15 minutes, using a sliding window log (small and exact). After that, slow down or require a CAPTCHA rather than locking the account outright, because a hard lockout lets an attacker lock real users out on purpose.
  • Per IP: a generous limit (say 50 failures an hour), since many real users share IPs; it catches lazy attackers but not this one.
  • Global signal: a jump in the overall login failure rate (2% to 60%) means an attack even if no single key trips a limit; respond with CAPTCHAs or extra checks for unfamiliar devices.
  • Count failures, not attempts, so a user who types the password right is never limited.
  • Respond the same way whether the account exists or not, so the limiter does not reveal valid usernames.
  • Beyond limits: check passwords against known-breached lists, offer two-factor authentication, and use device fingerprints.

A strong answer mentions: per-account and per-IP keys and why each alone fails · failures counted rather than attempts · soft responses (CAPTCHA, delay) instead of hard lockout · a global failure-rate alarm for distributed attacks · not leaking which accounts exist.

Your turn: spot the bug

A team implements a fixed window limit of 100 requests per minute like this. Users occasionally report being blocked "forever", and under load the limit lets through more than 100. Find both bugs and fix them.

def allow(user_id):
    key = f"rl:{user_id}:{int(time.time() // 60)}"
    count = int(r.get(key) or 0)
    if count >= 100:
        return False
    r.set(key, count + 1)
    if count == 0:
        r.expire(key, 60)
    return True
Compare with our answer

Bug 1, lost updates: GET then SET is check-then-act. Two servers both read 99, both allow, both write 100. Use INCR, which increments atomically and returns the new value, and reject when it exceeds 100.

Bug 2, the key may never expire: the expiry is a separate command after the write. If the process crashes or times out between them, the key has no TTL. Here the window number in the key means a stuck key only blocks one old window, but the same pattern on a key without a window number (rl:{user_id}) really does block a user forever. Set the TTL in the same step.

def allow(user_id):
    key = f"rl:{user_id}:{int(time.time() // 60)}"
    pipe = r.pipeline(transaction=True)      # MULTI/EXEC: both commands run together
    pipe.incr(key)
    pipe.expire(key, 120)                    # longer than the window; harmless to repeat
    count, _ = pipe.execute()
    return count <= 100

A strong answer mentions: the check-then-act race and INCR (or a Lua script) as the fix · the INCR/EXPIRE gap and setting both atomically · that rejected requests still increment the counter here (fine for a fixed window, but worth saying) · the boundary burst of up to 200 that remains · using the server's clock consistently (or Redis TIME) across app servers.

Rate limiting on one page
  • Limit = key (API key, user, IP, account) + rate and burst + action (429, queue, or shadow-log).
  • Fixed window: one counter, cheap, up to 2× bursts at the boundary. Sliding log: exact, one timestamp per request. Sliding counter: two counters, current + previous × overlap, very close.
  • Token bucket: refill r/s, hold B; long-run rate r, burst B; 60 s max = B + 60r. The default for APIs.
  • Leaky bucket: as a queue it smooths output (adds latency); as a meter it mirrors the token bucket (NGINX, GCRA).
  • Many servers: shared state in Redis; make check-and-update atomic with INCR or a Lua script; TTL on every key; hash tags in Redis Cluster.
  • Enforce in layers: edge (IP), gateway (API key, plan), service (business rules), before dependencies.
  • Respond: 429 + Retry-After + remaining-quota headers; 503 for whole-server overload. Clients back off with jitter.
  • Failure plan: Redis down → fail open with local limit ÷ N; fail closed only for security limits. Per-region shares for multi-region.
Interactive labPractise it: stop a bot flood without blocking real users' burstsOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. A public API allows 100 requests per minute per key using a fixed window. A partner complains that a client sent 190 requests within two seconds without being limited. What is the most likely explanation?

2. You need an API limit of 600 requests per minute on average, while letting a quiet client fire 50 requests at once when a page loads. Which configuration fits?

3. Ten API servers share a Redis-backed token bucket. Each server runs HGET to read the tokens, decides in application code, then runs HSET with the new value. What goes wrong under load?

4. A limit of 1,000 requests per hour per user must be exact, and you have 2 million active users. Which concern is the strongest argument against a sliding window log?

5. The Redis cluster behind your API gateway's rate limiter becomes unreachable. For the general per-key API limit, what is the best behaviour?

6. An endpoint is rate limited per IP address at 60 requests per minute. Users at a large university and on one mobile carrier report being blocked constantly, while a scraper still gets through. What change helps most?

7. A client exceeds its quota. What should the response look like?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.