Rate Limiting

Rate limiting controls how often a client, tenant, API key, or other identity may perform an operation over time, and rejects or delays the excess. The purpose can be fairness between customers, abuse prevention, cost control on a paid dependency, or protection of finite capacity. A rate limit is a policy, such as "100 requests per minute per API key"; an algorithm such as a token bucket is how that policy is enforced.

It exists because shared resources have no sense of who is asking. CPU, database connections, memory, and third-party quota are finite, and one client that sends a hundred times its normal volume consumes capacity every other client was counting on. The sender is not always malicious. A misconfigured retry loop, a runaway cron job, or a new integration that forgot to throttle produces the same load as an attacker. A limiter is the enforcement point that turns those accidents into 429 responses for one caller rather than slowness for everyone.

The mental model is a metered on-ramp: each identity gets a measured entry rate, and a bounded amount of saved-up credit lets it enter in short bursts. Everything in this lesson, from window boundaries to distributed counters, is about how that credit is tracked, who the identity is, and what happens at the moment the credit runs out.

A rate limiter is not an overload controller. A system can be inside every per-user limit and still be crushed by aggregate traffic or a slow dependency. Conversely, a perfectly healthy system may reject one customer who exceeded a contractual quota. Rate limiting answers "is this caller exceeding its allowance?"; the next section separates it from the two questions it is most often confused with.

A rate limit bounds arrivals per unit of time. It says nothing about how many requests are in flight, and the two diverge as soon as latency changes. Little's law ties them together: average in-flight work equals arrival rate times average time in the system, L = λ × W. At 100 requests per second and 200 ms per request, about 20 requests are in flight. If a dependency slows the same requests to 2 seconds, the same admitted rate of 100 per second now means about 200 in flight, ten times the concurrency, and the rate limiter has not rejected anything because no caller broke its limit.

That is why expensive endpoints often carry both controls. Take a public image-processing API. A per-tenant rate limit stops one customer from submitting jobs faster than the contract allows. A separate concurrency limit caps how many of that tenant's jobs hold GPU workers at once. And a global admission controller may still refuse work when the whole fleet is saturated, regardless of whose turn it is. The last of these is load shedding: it reacts to the service's state rather than to a caller's allowance. A downstream-aware control such as backpressure pushes the same information back to producers.

So the distinction to carry forward: rate limiting is proactive and per identity, concurrency limiting bounds work in progress, and load shedding is reactive and driven by system health. They compose, and most of the production failures later in this lesson come from using one where another was needed.

A fixed-window limiter keeps one counter per identity per time bucket, such as 12:00:00 to 12:00:59. With a policy of 100 requests per minute, requests 1 through 100 are admitted, request 101 is rejected, and at the next minute boundary a fresh counter starts at zero. State is a single integer per key and the check is one atomic increment, which is why it is the default in many gateways.

# one counter per (identity, window); limit = 100, window = 60 s
window = floor(now / 60)
key    = "rl:" + identity + ":" + window
n      = INCR key                 # atomic increment
if n == 1: EXPIRE key 120         # a crash between these two lines leaves a key with no TTL;
                                  # set the TTL in the same atomic step (script, or SET NX EX first)
allow  = (n <= 100)

The weakness is the boundary. A client can send 100 requests at 12:00:59 and another 100 at 12:01:00. Each window sees exactly 100 and admits everything, yet 200 requests arrived within about a second, twice the intended rate, and the same trick works at every boundary. Fixed windows therefore do not enforce a strict rolling-minute limit; they enforce "at most N per calendar bucket", which is a weaker statement.

When that is acceptable, the simplicity wins: coarse protection of an internal admin tool, or a daily and monthly quota where the boundary is the contract. When the boundary burst could hurt the backend, move to one of the next two algorithms.

A sliding-window log stores a timestamp for every admitted request and discards entries older than the window. To decide, it counts the timestamps still inside the window and admits the request if the count is below the limit. This gives precise rolling-window enforcement for the requests it tracks. The cost is memory proportional to the limit per key: a 10,000-requests-per-minute policy may hold up to 10,000 timestamps for a single busy identity, and each decision touches that structure (in Redis, typically a sorted set trimmed by score, counted, and appended to in one atomic step).

A sliding-window counter avoids that memory by keeping only two integers, the previous and the current fixed-window counts, and assuming the previous window's requests were spread evenly. The rolling window ending now overlaps the previous window by the fraction of it that has not yet scrolled away:

estimated = current + previous × (window − elapsed) / window

window = 60 s, elapsed = 20 s into the current window
previous = 84, current = 36
estimated = 36 + 84 × 40/60 = 36 + 56 = 92        -> below 100, admit (it becomes 93 once counted)

The result is an estimate, not exact enforcement. If the previous window's 84 requests were all in its final seconds, the true rolling count is higher than the weighted figure, and a limit can be briefly exceeded; if they were all early, legitimate callers can be rejected too soon. The error is small for steady traffic and larger for bursty traffic, so describe the limiter as approximate. Implementations that need tighter accuracy use several sub-windows (for example sixty one-second buckets summed over the last minute), trading memory for precision on a dial between the counter and the log.

The same arithmetic works at any point in the window. At 30% of the way into the current window, with 84 requests in the previous window and 36 so far in this one, the previous window still contributes 70% of its count: 84 × 0.7 + 36 = 94.8. That is below a limit of 100, so the request is admitted, and the limiter will admit five more (estimates of 95.8 up to 99.8) before the estimate reaches 100.8 and requests are rejected. The sketch below keeps the two counters for one key in process; across several instances the read, the comparison and the increment must happen atomically in a shared store, as in the Redis script later in this lesson.

function allow(state, limit, windowMs, now) {
  const index = Math.floor(now / windowMs);
  if (state.index !== index) {
    // Entering a new window: the old count becomes "previous" only if it was the immediately preceding window
    state.previous = state.index === index - 1 ? state.count : 0;
    state.count = 0;
    state.index = index;
  }
  const elapsed = (now % windowMs) / windowMs;
  const estimated = state.count + state.previous * (1 - elapsed);
  if (estimated >= limit) return false;
  state.count += 1;
  return true;
}

The token bucket algorithm admits a request only if a token is available, which bounds the sustained rate while allowing short bursts. A token bucket holds up to B tokens and earns tokens at r per second. Each admitted request spends one token, or a weighted number for expensive operations. Tokens stop accumulating at capacity, so idle time buys a burst of at most B and no more. The two parameters are separate on purpose: r is the sustained rate and B is the largest burst the policy tolerates.

Nothing ticks in the background. Refill is computed lazily from the elapsed time whenever a request arrives:

# state per key: tokens (float), last (timestamp). No timer: refill is computed lazily.
function allow(key, cost):
    now    = clock()                       # monotonic in-process; the store's clock when shared
    tokens = min(B, state.tokens + (now - state.last) * r)
    state.last = now
    if tokens >= cost:
        state.tokens = tokens - cost
        return ALLOW
    state.tokens = tokens
    return DENY(retry_after = (cost - tokens) / r)

In algebra, with elapsed time Δt: tokens = min(B, tokens + r × Δt), and a request of cost c is admitted when tokens ≥ c, after which c is deducted. If not, the policy either rejects immediately or delays the caller. The delay is computable: the wait for a deficit is (c − tokens) / r, which is also where a truthful Retry-After comes from.

The guarantee this buys is a clean upper bound. Over any interval of length T, a token bucket admits at most B + r × T units of cost. With B = 20 and r = 5, a client that starts with a full bucket can send 20 requests instantly and then about 5 per second; over 10 seconds it can have at most 20 + 50 = 70 admitted. The trace below walks a bursty client through the policy, including the cap on saved credit.

Bucket B = 20 tokens, refill r = 5 tokens/s, cost 1 per request, bucket starts full.

t = 0.0 s   tokens 20   30 requests arrive   -> 20 admitted, 10 rejected   tokens 0
t = 1.0 s   tokens  5   10 requests arrive   ->  5 admitted,  5 rejected   tokens 0
t = 3.0 s   tokens 10   (idle 2 s)  10 arrive -> 10 admitted                tokens 0
t = 9.0 s   tokens 20   (idle 6 s: 30 tokens earned, capped at B = 20)
                         25 requests arrive  -> 20 admitted,  5 rejected   tokens 0

Try the same arithmetic in the figure: a bucket that is larger than the offered burst never rejects, a bucket of 1 behaves almost like a strict pacing rule, and once the offered load exceeds r the admitted rate settles at r no matter how much more is offered.

Two cautions. First, B is the maximum saved burst credit, not a statement that the backend can safely absorb a burst of that size; choose it against measured behavior, since 20 simultaneous requests may be fine for a profile lookup and ruinous for a report query. Second, correctness details matter. Use a monotonic clock in-process and handle backward steps (a wall-clock adjustment must never produce negative elapsed time, hence the max(0, …) in the script later), and make the read, refill, and deduct one atomic step, or two concurrent callers can both see one token and both spend it.

"Leaky bucket" names more than one algorithm, so say which you mean. In the queue-based model, incoming work enters a bounded queue that drains at a fixed rate. The output is a steadier stream than the input, but queued requests wait, may time out while waiting, and when the queue is full new arrivals are dropped or rejected. This is shaping: it changes the timing of admitted work. A token bucket that rejects on an empty bucket is policing: it decides yes or no and never holds the request.

The second meaning is the meter variant, which keeps a counter that drains at a constant rate and rejects when adding a request would overflow it. Implemented as the generic cell rate algorithm (GCRA), it stores a single timestamp per key and admits the same traffic a token bucket with the same parameters would. If your documentation says "leaky bucket" for that, the behavior matches a token bucket rather than a queue.

Neither is better in general. A public API usually wants an immediate 429 with guidance, because silently holding a request for seconds makes clients time out and retry, adding load. An internal worker calling a rate-capped partner API may prefer bounded smoothing so that bursts are delayed rather than dropped. The queue must be bounded and its wait must be less than the caller's timeout, or the smoothing just converts rejections into timeouts; this is the same bounded-queue reasoning that appears in backpressure. Calling the output "perfectly smooth" overstates it: smoothness is limited by the drain granularity and by what the backend does with each request.

The algorithms differ in three things you can measure: how much state each key needs, how they treat a burst, and how closely they follow the stated policy.

As a rule of thumb: use a token bucket when short legitimate bursts are normal (an app opening and firing several calls at once) and you want a hard bound on sustained rate; use a sliding window when the boundary burst matters and you want the policy to read as "N in any 60 seconds"; use a fixed window for billing-period quotas or where cheapness dominates; use a queue-based leaky bucket when you are shaping your own outgoing calls to a capped partner. The choice matters less than choosing the limit key and the numbers well.

The key decides who shares an allowance, and each choice has a failure mode. A per-IP limit is easy and works before authentication, but penalizes many people behind one NAT or corporate proxy, and is evaded by rotating addresses. If requests come through proxies, read the client address only from a header your own trusted proxy sets: X-Forwarded-For from the open internet is attacker-controlled. For IPv6, individual addresses are cheap, so limit by a prefix such as the /64 rather than the full address. A per-user limit is more precise after login but cannot protect unauthenticated endpoints. A per-API-key or per-tenant limit matches SaaS contracts but needs rules for key rotation and for a customer who creates many keys. A global limit protects aggregate capacity but does nothing for fairness: one caller can use all of it.

Production APIs therefore layer: an unauthenticated edge limit, a tenant quota, an operation-specific rate, and sometimes a global concurrency cap. Each layer rejects what it was built to catch, and the order is deliberate. The cheap, identity-free check runs first so abusive traffic is turned away before spending effort on authentication and body parsing; the identity-aware checks run after.

State the unit for every policy: per second, per minute, rolling, burstable, or tied to a billing period. A monthly billing quota is not an instantaneous traffic rate. A tenant can be far under 1,000,000 requests this month and still send 5,000 in one second, so billing quotas and rate limits are usually separate policies with separate counters. Decide too whether rejected requests consume allowance (usually they do not, which lets a polite client recover) and what the limiter itself costs: the check must be much cheaper than the work it guards, and it will see every rejected request.

A shared "100 requests per minute" rule treats GET /profile, which costs a few milliseconds, the same as POST /export, which launches a large analytical query. A client can stay inside the limit and still overload the database with exports. Two remedies are common and they combine.

The first is a weighted token bucket. With B = 100 and a refill of 100 tokens per minute (about 1.67 per second), charge 1 token per profile lookup and 10 per export. A client can now make 100 profile calls a minute, or 10 exports, or a mix, and the budget is spent in proportion to cost. The second is a separate pool for the expensive operation: exports get their own lower rate and a concurrency limit of, say, 2 simultaneous jobs per tenant, so a slow export cannot pile up the way Little's law warned about earlier.

Which model fits depends on the scarce resource. If CPU is the constraint, weight by CPU time; if database I/O, by query cost; if it is third-party spend, by the vendor's own pricing; if it is queue capacity, by the work added to the queue (see Queues & Workers). Weights should come from measurement and be revisited when the endpoint changes, otherwise they drift into the same inaccuracy as a flat count.

With five API replicas, five independent in-memory token buckets each set to 100 requests per minute can admit up to 500 per minute in total when the load balancer spreads one caller across all of them. With 50 replicas the ceiling becomes 5,000. If the requirement is a global 100, replicas need shared coordination or a deliberately divided budget. Splitting 100 into 20 per replica is cheap, but it is only fair if traffic is spread evenly: a caller pinned to one replica is limited to 20 while 80 go unused.

The standard exact approach is a shared store that holds the counter or bucket and makes the decision. The read-modify-write must be atomic. Separate GET, arithmetic, and SET calls race: two replicas read "1 token left" and both admit. In Redis that usually means a Lua script or an equivalent server-side operation, which also lets the script use the store's clock and so avoids skew between replicas.

-- KEYS[1] = bucket key; ARGV = capacity, refill per second, cost
-- Runs as one atomic unit on the store, using the store's own clock (Redis 5+ allows TIME in scripts).
local B, r, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local t   = redis.call('TIME')
local now = t[1] * 1000 + math.floor(t[2] / 1000)               -- milliseconds
local s   = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(s[1]) or B
local ts     = tonumber(s[2]) or now
tokens = math.min(B, tokens + math.max(0, now - ts) * r / 1000)
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(B / r * 1000))        -- an idle bucket is full again after B/r s
local retry_ms = 0
if not allowed then retry_ms = math.ceil((cost - tokens) / r * 1000) end
return { allowed and 1 or 0, math.floor(tokens), retry_ms }

A central limiter costs a network round trip per decision, becomes a dependency of every request, and creates a hot-key risk: one very active tenant maps all its traffic to one key on one node, and a single key cannot be spread over shards without splitting its budget. Plan for the store being slow or down by choosing a failure policy in advance. Fail open admits traffic when the limiter is unavailable, which keeps the service up but removes the protection exactly when something is wrong. Fail closed rejects it, which keeps the policy but turns a limiter outage into a full outage. The right answer depends on what the limit protects: a login or one-time-code limiter guarding against brute force leans toward failing closed or toward a strict local fallback; a general performance limiter usually fails open with a short timeout, a local fallback bucket, and an alert. A common middle path is falling back to a conservative per-replica budget, which degrades precision instead of availability.

At very high throughput, strict global accuracy becomes the expensive part. Alternatives give up a bounded amount of precision for availability and speed: local budgets with periodic reconciliation, regional partitions with a share of the limit each, or token leasing, where a replica fetches a chunk of tokens (say 10) from the shared bucket and spends them locally without further round trips. The overshoot or undershoot is bounded by what you hand out: unspent leases that expire make the limiter stricter than configured, and over-granting makes it looser. State that bound explicitly ("at most 10 tokens per replica in flight") rather than promising exact global consistency.

When a caller exceeds its limit, 429 Too Many Requests (RFC 6585) is the usual status. It means this caller is sending too much. Use 503 Service Unavailable when the cause is the service's own overload or maintenance, which is the load-shedding case; clients and dashboards read the two differently. Either may carry Retry-After, which RFC 9110 defines as either a number of seconds or an HTTP-date. It is a hint to the client, not a promise that the next request will succeed.

HTTP/1.1 429 Too Many Requests
Retry-After: 4
Content-Type: application/problem+json

{
  "type": "https://api.example.com/problems/rate-limited",
  "title": "Rate limit exceeded",
  "status": 429,
  "detail": "The export quota is exhausted. Retry after the indicated interval."
}

Advertising the policy lets clients throttle themselves before they hit it. Two header families exist, and neither should be presented as a universal contract. The X-RateLimit-* names are a long-standing convention whose semantics vary by vendor (some report the reset as an epoch timestamp, others as seconds remaining). The IETF HTTP API working group has published a draft for RateLimit-* fields, but it is a draft, not a standard, and its syntax has changed between revisions. Document exactly which fields your API sends and what each means, and do not infer another provider's semantics from its field names.

# Widely copied convention (names and units vary by vendor; GitHub's reset is an epoch timestamp):
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1723812601

# IETF HTTP API working-group draft (not an RFC; field names and syntax have changed between revisions):
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 30

The server-side Retry-After is easy to compute from the bucket arithmetic. If a bucket holds 4 tokens, an export costs 10, and the refill is 100 per minute, the deficit of 6 takes 6 / 1.67 ≈ 3.6 seconds, so the gateway rounds up to Retry-After: 4. For a fixed window it is the time until the window resets. If clients behave well they will all return exactly then, which can recreate the spike you just limited, so a client should wait the indicated time plus bounded random jitter, and give up after a bounded number of attempts rather than retrying forever. This is the same discipline as retry with backoff. A 429 is a comparatively safe retry because the rejected request was never processed, but idempotency still matters when a timeout leaves the outcome of an earlier attempt unknown, and a client should never treat 429 as a generic failure to repeat immediately.

No limit at all. A bot sends 100,000 requests a minute against an API whose normal users send ten. CPU saturates, database connections run out, and every user sees slowness. The fix is a per-identity limit at the gateway, before requests reach the backend.

A limit that is too tight. A limit of 10 per minute is set by guess while legitimate power users normally send 15. Support tickets arrive and the limiter is blamed. Base limits on observed usage, for example a high percentile of real per-identity traffic with headroom, and roll new limits out in a report-only mode first.

A limit that is too loose. A limit of 10,000 per minute protects nothing when abusive traffic is 500,000 per minute, and when the backend saturates at 3,000. Derive the ceiling from backend capacity divided sensibly among identities, not from expected traffic; note that many compliant clients each under their own limit can still exceed capacity in aggregate, which is a load-shedding problem.

Per-IP limits on an authenticated API. Five hundred engineers at one company share a NAT address, so one runaway script throttles the entire organization. Key authenticated traffic by user or API key and keep the IP limit for the unauthenticated edge.

Per-replica counters. Fifty servers each enforcing 100 a minute give a real ceiling near 5,000 for a caller spread across them, as covered above. Use shared state with an atomic update, or a known-bounded local budget.

Flat limits that ignore cost. GET /health and POST /search both get 100 a minute, but each search fans out into dozens of database calls. The backend overloads while every client stays within its limit. Weight by cost or give the expensive route its own pool.

The limiter as a failure source. A hot tenant can saturate one shared Redis key. A clock mismatch can distort a naive refill calculation that trusts each replica's wall clock. A limiter outage can either block every customer (fail closed) or remove all protection (fail open). Raw user IDs as metric labels can overload the monitoring system. And a client that reads 429 as an ordinary error and retries immediately turns the limit into a retry storm.

Measure allowed and rejected requests per policy, per tenant class, and per endpoint, so a rise in 429s can be tied to a specific rule. Track limiter decision latency and error rate, and count fail-open or fallback decisions separately: that number shows how often protection was absent. Watch bucket occupancy (how close identities run to empty) as an early signal that limits are about to bite, and compare against actual backend saturation (CPU, pool usage, queue depth) to confirm the limits track real capacity. Also watch what clients do after a rejection: the retry rate within a few seconds of a 429 tells you whether clients honor Retry-After.

Keep metric cardinality bounded: aggregate by tenant class or plan, sample the top offenders into logs, and never log raw API keys or secrets. For tests, cover the boundary burst for your chosen algorithm, concurrent callers racing for the last token, regional failover (does the budget double, reset, or disappear?), clock behavior, and limiter unavailability with the failure policy you declared.

Consider a fixed 100-requests-per-minute policy on a simple endpoint. Requests 1 through 98 are admitted and the response headers show the remaining count falling to 2. Requests 99 and 100 are admitted and the count reaches 0. Request 101 returns 429 with a Retry-After, and so does every request until the window resets (for a token bucket, until enough tokens refill). Sending the remaining count on every response, not only on 429s, is what lets well-behaved clients slow down before the wall; it reduces 429s and the retry traffic they create.

Now put it behind the stack the earlier sections built. An unauthenticated edge limit absorbs obvious floods. After authentication the tenant's weighted bucket (B = 100, 100 tokens a minute) charges 1 for profile reads and 10 for exports. Exports also pass a concurrency gate of 2 per tenant. A client that fires 12 exports at once gets the first 10 charged and admitted by the bucket, but only two run at once under the gate while the rest are rejected or queued according to policy; the eleventh and twelfth find the bucket empty and receive 429 with a computed Retry-After. Each layer is doing a different job, and no single layer would have given this behavior.

Public APIs are the clearest case: any public surface can be abused or accidentally flooded. Authentication endpoints need strict limits against credential stuffing and brute force. APIs that fan out to metered third parties need limits to keep spend bounded. Internal services benefit when one team's service can overwhelm another's; scheduled batch jobs can be throttled so they do not collide with peak-hour traffic. It is rarely worth it for pure in-memory computation with no shared resource to protect.

For real numbers, take published limits as examples of policy shape, not benchmarks: GitHub's REST API documents 60 requests per hour for unauthenticated clients per IP and 5,000 per hour for authenticated users, at the time of writing, and it communicates the state through response headers. Check the provider's current documentation before relying on any figure.

Where it sits among the other patterns is a common source of confusion. Rate limiting protects your service from its callers; a circuit breaker protects it from a failing dependency; retries with backoff help callers recover from transient failures, and rate limiting reduces the chance that callers create those failures. Load shedding is the reactive counterpart: when aggregate demand exceeds safe capacity even though every caller is within its limit, the limiter will not help, and shedding or bulkheads will. A one-customer overage is a rate-limiting problem; many compliant customers overloading the system is not.

• Rate, concurrency and overload are three different controls: a rate limit caps one identity's frequency, and does not stop many compliant callers from saturating the backend together (that is load shedding).
• Fixed windows are cheapest but allow a boundary burst of up to 2× the limit; sliding windows close the gap and the token bucket gives an explicit rate plus burst allowance (capacity B, refill r).
• Choose the limit key deliberately: per-IP limits punish shared NATs, so key authenticated traffic by user or API key and keep IP limits for the unauthenticated edge. Weight by request cost where requests are not equal.
• Per-replica counters multiply the limit (5 replicas × 100/min can admit 500/min); use a shared store with an atomic update such as a Lua script, or a deliberately divided budget.
• Return 429 for a caller exceeding its limit and 503 for service overload, with Retry-After, and derive limits from observed usage and backend capacity, rolling out new limits in report-only mode first.
• Decide fail-open versus fail-closed for the limiter itself, and monitor throttle rates per key and limiter latency so it does not become the outage.

A 429 is only as useful as the client's reaction to it, so continue with Retry & Backoff for jitter and retry budgets, then Load Shedding and Backpressure for the system-wide overload that per-caller limits cannot see. For how limits show up in an API surface, see API Design and Idempotency; for queue-based smoothing of work, see Queues & Workers.