Skip to main content

Rate Limiter: Requirements & High-Level Design

Editorial

Problem Statement

Design a rate limiter for a public HTTP API that runs on many gateway instances. Every request is checked against its client's limits before any backend work is done, and a request over a limit is rejected with a response that tells the client when to try again. Clients are identified by API key and by the organization (tenant) that owns the key, and, before they authenticate, by IP address. A limit must allow short bursts while holding a long-term rate, and it must hold across all gateways: spreading requests over many instances must not multiply it. Operators change limits at any time without restarting a gateway. The API serves up to 1 million requests a second for 100 million API keys; the limiter may add at most 10 ms at p99, and its own failure must not take the API down.

The functional requirements below come from its verbs; the rest of the statement sets the non-functional ones.

Introduction

Every call to Stripe's API counts against a limit. Stripe measures its limits "in API requests per second, per Stripe account": 100 a second in live mode, 25 in a sandbox, stricter limits on some endpoints, and at most 50 requests in progress at once. A request over the limit gets 429 Too Many Requests, with a Stripe-Rate-Limited-Reason header that names the limit it hit. The component that makes this decision on every request is a rate limiter.

A rate limiter caps how many requests an identity — an API key, an organization, an IP address — may make in a period of time. It keeps the backend from being overloaded, keeps one client from taking capacity that belongs to the others, and makes abuse such as credential stuffing and scraping cheap to refuse. Every public API has one: GitHub allows an authenticated user 5,000 requests an hour; AWS API Gateway throttles every account with a token bucket, a steady rate plus a burst.

In this design we build a rate limiter that runs inside the API gateway, enforces limits per IP address, per API key and per tenant with room for bursts, and keeps one count per limit however many gateways share the traffic.

Why Rate Limiters Are Hard in Distributed Systems

On a single server a rate limiter is a few lines: keep a counter, compare it with the limit, reset it in time. The difficulty starts with the second server. An API runs many gateway instances behind a load balancer; if each keeps its own counters, a client whose requests are spread over 50 gateways gets 50 times its limit.

So the limiter needs three things: shared state that every gateway reads and writes in one network round trip, atomic updates so that two gateways checking the same client at the same moment cannot both spend its last request, and fault tolerance, so that the limiter is never the reason the API is down.

Every decision in this design traces back to one of those three.

Related lessons: the algorithms are written out in code in the low-level design problem Design a Rate Limiter (Design Problems - Low Level Design). The patterns behind this design are in Rate Limiting: Token Bucket, Leaky Bucket, Windows and Calling Services Safely: Timeouts, Retries & Backoff (Fundamentals of System Design), Circuit Breakers (Distributed Systems & Reliability) and Redis, Inside-Out (System Design Interview Mastery).

Under the limit, through; over it, a 429. Each request is checked against its limits before any backend work. Three CLIENTS, drawn as terminals, send requests to the API GATEWAY, where the rate limiter runs: a token bucket per client and limit. A request within its limit goes on to the SERVICES, the backend. The gateway makes one round trip to REDIS, where the buckets live. A request over its limit is answered by the gateway itself with 429 and Retry-After, and never reaches a service.

Functional Requirements

We extract the operations from the verbs of the problem statement:

FR1 — Check every request before backend work. Each request is counted against every limit that applies to it and decided — allow or reject — before it reaches a backend service. A rejected request costs only the check.

FR2 — Tell the client. A rejected request gets 429 Too Many Requests with Retry-After, the time after which a retry can succeed. Every response, allowed or not, carries the client's remaining allowance, so a well-behaved client can slow down before it is rejected.

FR3 — Identify the client. Each request is counted under a stable identity: its API key and the tenant that owns the key once it is authenticated, its IP address before that. Limits apply per identity, and one request usually falls under several.

FR4 — Allow bursts within a long-term rate. A client that has been quiet may send a short burst — a dashboard that fires 20 calls when it opens — as long as its long-run rate stays within its limit.

FR5 — One limit across all gateways. A limit of 100 a minute means 100 a minute in total, however the load balancer spreads the client's requests over gateway instances.

FR6 — Change limits without restarts. Operators create, change and roll back limits — tighten one during an attack, raise one for a customer — and every gateway applies the change within 60 seconds, without a restart or a deploy.

Out of Scope

  • Billing: prepaid credits and monthly quotas that roll over
  • Authentication: the gateway's auth step resolves the API key and its tenant before the limiter sees them
  • Concurrency limits, which cap how many requests a client has in progress at once (Stripe runs one next to its rate limits)
  • Pricing routes by cost; the design keeps a cost per request, set to 1
  • DDoS protection at the network layer (L3/L4); this limiter works on HTTP requests (L7)
  • WebSocket and streaming connections

Scale Requirements

MetricValue
Requests through the gatewaysup to 1,000,000 a second
API keys100,000,000
Latency the limiter may addunder 10 ms at p99
Time for a limit change to reach every gatewayunder 60 s

Non-Functional Requirements

The adjectives and constraints of the problem statement give the quality requirements:

  • "before any backend work", "at most 10 ms" → Low latency
  • "must hold across all gateways" → Correctness
  • "its own failure must not take the API down" → Availability
  • "1 million requests a second for 100 million API keys" → Scale
  • "identified by API key … by IP address" → Security: the identity must be one the client cannot forge

Low latency

  • Add less than 10 ms per request at p99
  • One network round trip to the shared state on the hot path, and no other blocking I/O

Correctness

  • A client never gets more than its burst plus what its rate refills over time: not N times that because there are N gateways, and not one request more because two arrived at the same instant
  • The exceptions are known and bounded: a Redis failover can forget the last moments of a few buckets, and while Redis is unreachable the gateways fall back to coarse local limits (both in the deep dives)

Availability

  • A slow or failed limiter must not fail the API: it degrades to coarse local limits, not to errors

Scale

  • 1 million requests a second and 100 million API keys
  • Memory that does not grow with clients that have gone quiet

Security

  • A client cannot change what it is counted as: the API key is authenticated, the tenant comes from the key's record, the IP address from our own load balancer — never from headers the client writes

Operability

  • A limit change is live everywhere within 60 seconds, can be tried in shadow mode first, and can be rolled back

Resource Estimation

Traffic

MetricValue
Peak requests1,000,000 a second
Limits checked per request3: per IP address (before authentication), per API key and per tenant (after)
Bucket checks on Redis at peak3,000,000 a second

Redis Throughput

Each limit check is one call of the token-bucket script (part 5 of the High-Level Design). In a test for this lesson, one Redis 8 process ran the script about 121,000 times a second on a laptop (Apple M5, macOS) and about 180,000 times a second in a Linux VM on the same machine, from 50 connections without pipelining; each call took about 3 µs of server time, against 0.3 µs for a plain INCR. Production servers and real networks are slower than a laptop talking to itself, so plan for half the lower figure, 60,000 calls a second per process:

3,000,000 ÷ 60,000 = 50 Redis primaries, each with a replica.

Redis runs every command and script on one thread, so this is a Redis Cluster of 50 shards, not one bigger machine. Pipelining raises what one process can do — 230,000 to 260,000 calls a second in the same test, with 16 commands in flight per connection — at the cost of a little latency.

Memory

A bucket is a small Redis hash (the tokens left and the time they were counted) with an expiry. Measured in Redis 8 on Linux, it takes 132 bytes: more than eight times the 16 bytes of its two numbers, because the key name, the hash's encoding and the expiry entry cost more than the numbers.

BucketsHow many at mostMemory
API keys100,000,000, if every key were active at once~13 GB
Tenantsone per organization132 bytes each
IP addressesone per address seen while its bucket refills132 bytes each

Spread over 50 primaries, that is well under 1 GB each. A bucket lives only until it would be full again (part 5), so clients that have gone quiet cost nothing. Memory is not what limits this design; throughput is.

Latency

One round trip to Redis per request: the three checks go together, pipelined, and in a cluster in parallel to their shards. A round trip inside a data center takes a few hundred microseconds — Redis's documentation gives about 200 µs on a 1 Gbit/s network — and the script itself a few microseconds. The 10 ms p99 budget is for the tail: a slow moment on the network, a busy shard, a pause in the gateway.

Policies

A few thousand rules — tiers, routes, per-customer overrides — take kilobytes, and every gateway keeps them all in memory.

The estimate: throughput sets the size. Three checks a request on a single-threaded store: 50 Redis primaries. Three sums. THROUGHPUT: 1,000,000 requests a second × 3 limits each = 3,000,000 checks a second; ÷ 60,000 a Redis process = 50 primaries. MEMORY: 100,000,000 API keys × 132 bytes a bucket, measured = about 13 GB in all; ÷ 50 primaries = about 0.3 GB each. LATENCY: the 10 ms budget at p99, drawn to scale as a bar 10 ms long: one round trip to Redis takes about 0.2 ms, 2% of the budget; the rest is for the tail, a slow moment on the network or a busy shard. Memory is not the limit. Throughput is.

Data Model

Two kinds of data with nothing in common: the rules operators write (a few thousand, changed rarely, with a history worth keeping) and the bucket state the gateways update (millions of entries, changed on every request, disposable).

Rules: PostgreSQL

The policy store is the source of truth for rules. The gateways never query it on the hot path; they keep a copy in memory (part 6 of the High-Level Design).

CREATE TABLE rate_limit_rules (
    rule_id        TEXT PRIMARY KEY,                           -- 'key-default', 'ip-login'
    scope          TEXT NOT NULL CHECK (scope IN ('ip', 'key', 'tenant')),
    route          TEXT,                                       -- NULL: every route
    capacity       INTEGER NOT NULL CHECK (capacity > 0),      -- the largest burst
    refill_tokens  INTEGER NOT NULL CHECK (refill_tokens > 0), -- refill_tokens every refill_ms:
    refill_ms      INTEGER NOT NULL CHECK (refill_ms > 0),     -- 100 every 60,000 ms = 100 a minute
    mode           TEXT NOT NULL DEFAULT 'enforce' CHECK (mode IN ('enforce', 'shadow')),
    rollout_pct    SMALLINT NOT NULL DEFAULT 100               -- applies to this share of identities, by hash
                   CHECK (rollout_pct BETWEEN 1 AND 100),
    deleted        BOOLEAN NOT NULL DEFAULT FALSE,
    version        BIGINT NOT NULL,                            -- from one sequence for both tables
    updated_at     TIMESTAMPTZ NOT NULL DEFAULT now()
);

CREATE TABLE rate_limit_overrides (                            -- per-customer exceptions
    rule_id        TEXT NOT NULL REFERENCES rate_limit_rules,
    identity       TEXT NOT NULL,                              -- 'ak_abc123', 'org_acme'
    capacity       INTEGER,
    refill_tokens  INTEGER,
    refill_ms      INTEGER,
    exempt         BOOLEAN NOT NULL DEFAULT FALSE,             -- TRUE: not limited by this rule
    deleted        BOOLEAN NOT NULL DEFAULT FALSE,
    version        BIGINT NOT NULL,
    PRIMARY KEY (rule_id, identity)
);

A rate is stored as two integers, tokens per milliseconds, so that "100 a minute" is exact; written as 1.67 a second it would be 100.2 a minute. Every change gets the next version from one sequence, and deletions are flags rather than removed rows, so a gateway can ask for "everything changed after version N" and miss nothing. mode and rollout_pct let a rule be tried before it applies to everyone (the deep dive on policies).

Bucket State: Redis

KeyFieldsExpires
rl:ip:203.0.113.42tokens (with a fraction), ts (milliseconds, Redis's clock)when the bucket would be full again
rl:key:ak_abc123the samethe same
rl:tenant:org_acmethe samethe same
rl:key:ak_abc123:/v1/chargesthe same, for a rule on one routethe same

A missing key means a full bucket. That is what makes the expiry exact: when the key disappears, the bucket would have refilled to capacity anyway, so deleting it changes nothing.

Two stores: the rules and the buckets. Rules are few and kept; buckets are many and disposable. POSTGRESQL holds the rules, which change rarely, in two tables. rate_limit_rules: rule_id TEXT (primary key), scope TEXT, route TEXT, capacity INTEGER, refill_tokens INTEGER, refill_ms INTEGER, mode TEXT, rollout_pct SMALLINT, deleted BOOLEAN, version BIGINT, updated_at TIMESTAMPTZ. rate_limit_overrides, the per-customer exceptions: rule_id TEXT (primary key and foreign key to rate_limit_rules), identity TEXT (primary key), capacity INTEGER, refill_tokens INTEGER, refill_ms INTEGER, exempt BOOLEAN, deleted BOOLEAN, version BIGINT. REDIS holds the buckets, which change on every request. The bucket rl:key:ak_abc123 is a hash of two fields: tokens, here 57.4, and ts, a time in milliseconds; a pail of tokens is drawn under it. It expires when it would be full again. No key means a full bucket.

Interface

The Check

Inside the gateway, the limiter builds one key per rule that applies to the request and calls the token-bucket script once per key:

EVALSHA <sha1> 1 rl:key:ak_abc123 100 100 60000 1

The arguments are the bucket's capacity, the tokens added per period, the period in milliseconds and the cost of this request; <sha1> is the digest SCRIPT LOAD returned for the script. The reply is {allowed, remaining, retry_ms}: {1, 57, 0} lets the request through with 57 left; {0, 0, 600} rejects it, and a token will be back in 600 ms.

The Response to the Client

Allowed responses carry the remaining allowance of the tightest rule. A rejection adds Retry-After:

HTTP/1.1 429 Too Many Requests
Retry-After: 1
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 60
Content-Type: application/json

{"error": "rate_limited", "rule": "key-default", "retry_after_ms": 600}
  • Retry-After is a whole number of seconds (RFC 9110), so 600 ms is rounded up to 1.
  • X-RateLimit-* headers are a convention, not a standard. GitHub sends them for its hourly window, with x-ratelimit-reset as the epoch second at which the window resets. A token bucket has no window, so here X-RateLimit-Reset is the number of seconds until the bucket is full again — 60, from empty — and the API documentation says so.
  • The IETF's HTTP APIs working group is standardizing the fields as RateLimit-Policy and RateLimit (draft 11, May 2026); earlier drafts named them RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset, the names some gateways still send.
  • A 429 response must not be stored by a cache (RFC 6585).

Change a Rule

PUT /v1/rate-limit/rules/{rule_id}

Request:

{"scope": "key", "route": null, "capacity": 100, "refill_tokens": 100, "refill_ms": 60000, "mode": "shadow"}

Response (200 OK): {"rule_id": "key-default", "version": 4182}

Fetch Changes

GET /v1/rate-limit/rules?after_version=4181

Every rule and override changed after that version, deleted ones included, in version order. Gateways call it every 30 seconds, and as soon as a push says a newer version exists.

High-Level Design

We'll build the design requirement by requirement, starting with where the check runs, because that choice shapes everything else.

1. Where the Check Runs

Requirement: every request is checked before it reaches a backend service (FR1).

There are two separate decisions here, and they are easy to mix up:

  1. Where the check runs: in the API gateway, in a separate rate-limit service that the gateway calls, or in each service instance (in its own process or in a sidecar next to it).
  2. Where the counts live: in each process's memory, or in a store that every instance shares.

Option A: A Filter in the API Gateway

The gateway is the entry point: it terminates TLS, authenticates the API key and routes the request to a service. A filter in the gateway sees every request before any service does, so a rejected request never costs a database query or a line of business logic. With the counts in a shared store, the check costs one network round trip.

Option A: the check in the gateway. Rejected before any backend work, for one round trip to Redis. A CLIENT sends a request through the LOAD BALANCER to the API GATEWAY, which does four steps: 1 a per-IP limit, 2 authenticate the key, 3 the per-key and per-tenant limits, 4 route. Allowed requests go to the SERVICES. For its limits, the gateway makes one round trip to the REDIS CLUSTER, which holds the buckets. A rejected request goes back to the client as 429; no service is touched.

Option B: A Dedicated Rate-Limit Service

The gateway asks a separate service, "may this request go?", and that service keeps the counts in the shared store. Envoy works this way: its rate limit filter calls an external rate limit service, and the open-source one (envoyproxy/ratelimit) keeps its counters in Redis. The limiter's logic changes without redeploying any gateway, and gateways written in different languages share one implementation.

The cost: two hops instead of one (gateway → service → store), one more service to run, and a decision for when it cannot be reached. Envoy lets the request through unless failure_mode_deny is set.

Option B: a rate-limit service, one hop more. The gateway asks a separate service, and that service counts in Redis. A CLIENT sends a request to the GATEWAY, which asks the RATE-LIMIT service whether it may go (hop 1); the service counts in the REDIS CLUSTER that holds the buckets (hop 2). Allowed requests go on to the SERVICES. Envoy works this way: its rate limit filter calls an external rate limit service, and the open-source one keeps its counters in Redis. If it cannot be reached, the request passes.

Option C: In Each Service, With Local Counts

The check runs in the service's own process, or in a sidecar proxy next to it — Envoy's local rate limit filter is a token bucket in each proxy. There is no network hop at all, but each instance sees only its share of a client's traffic. With 10 instances and a limit of 10, a client that spreads 100 requests evenly gets all 100 through, 10 on each.

Local counts are good for a coarse cap ("no instance takes more than 1,000 requests a second"), not for a client's limit.

Option C: local counts, one limit per instance. Each of 10 instances allows 10: a client spread over all of them gets 100. A CLIENT sends 100 requests through the LOAD BALANCER, which spreads them over 10 instances, numbered 1 to 10. Each instance counts on its own with a limit of 10, and each shows 10 of 10 used. A note: a limit of 10, counted ten times: all 100 requests pass. Good for a coarse cap per instance, not for one client's limit.

Our Choice: A Filter in the Gateway, Counts in Shared Redis

Check runs inCounts live inRound trips per requestOne count per limit?
A: gateway filterthe gatewayshared Redis1 (gateway → Redis)Yes
B: rate-limit servicea separate serviceshared Redis2 (gateway → service → Redis)Yes
C: in-process or sidecareach instancethat instance's memory0No: N instances, N counts

A gateway filter rejects before any backend work, costs one round trip, and keeps one count per limit. Option B is the better call when many gateways or languages must share one limiter, or when the rules are complex enough to deserve their own deploys; its cost is one more hop of a few hundred microseconds.

Inside the Gateway

The order of the filters matters. A per-IP rule runs before authentication: it is the only identity an unauthenticated request has, and it also protects the authentication step itself from a flood of bad keys. The per-key and per-tenant rules run after authentication, which resolves the API key into a key ID and the tenant that owns it. Then the request is routed.

It helps to think of the limiter as two parts:

  • The filter, in the gateway, holds the decision logic: it finds the rules that apply, builds the keys, calls the store and decides. It keeps the rules in memory.
  • The state store holds the buckets. With one gateway it could be memory; with many it must be shared — Redis (part 5).
Inside the gateway: limit, authenticate, limit. A per-IP limit before authentication, per-key and per-tenant after it. A CLIENT's request passes five steps in the API GATEWAY: TLS (decrypt), the IP LIMIT (before auth), AUTH (which resolves the key and its tenant), the KEY and TENANT limits, and ROUTE (to a service). Either limit can answer 429 at once. The limiter has two parts: THE FILTER, which keeps every rule in memory, and THE STATE STORE, a Redis cluster holding one bucket per rule and identity, which both limit steps call.

2. Telling the Client

Requirement: a rejected request gets a response that tells the client when to try again (FR2).

Reject or Queue?

A request over its limit can be rejected at once or held in a queue and released at the allowed rate.

Reject at once: return 429 immediately. The gateway stays stateless, every request is either forwarded or answered at once, and nothing waits in memory.

Queue and release later: hold the request and release it at the allowed rate, so the backend sees smooth traffic. NGINX's limit_req does this up to a burst size and rejects beyond it. But every queued request waits — with 50 queued and 100 released a second, the 51st waits 500 ms — the gateway holds state for every waiting request, and a client that has given up may still be served.

Our choice: reject with 429. A client can decide what to do with a fast "no"; it cannot do anything with a slow "yes".

Allowed and rejected: one round trip each. A rejected request is answered by the gateway; the service never sees it. A sequence across CLIENT, GATEWAY, REDIS and SERVICE. ALLOWED: the client sends POST /v1/charges; the gateway calls the script on Redis (EVALSHA), which answers {1, 57, 0}: allowed, 57 left; the gateway sends the request to the service and answers the client 200 OK with Remaining: 57. REJECTED: the same request; Redis answers {0, 0, 600}: rejected, the next token in 600 ms; the gateway answers 429 with Retry-After: 1, the 600 ms rounded up. The service is never contacted.

Retry-After and the Thundering Herd

Retry-After tells a client when a retry can succeed. A token bucket knows this exactly: with 0 tokens left and one token added every 600 ms, the next request can pass in 600 ms, sent as Retry-After: 1 (whole seconds, rounded up).

The same value sent to a thousand clients brings all thousand back in the same second. Clients should add random jitter to their retries — Stripe's documentation asks for exactly that, "to avoid a thundering herd effect" — and the server can spread the value it sends.

Do not count on clients to back off on their own. Some SDKs do; plain HTTP libraries — Python's requests, the browser's fetch, Go's net/http — return the 429 to the caller without retrying it.

3. Who Is Asking

Requirement: every request is counted under a stable identity (FR3).

Before "10 requests a second" means anything, we need to say per what. We don't pick one identity: a request is checked against every scope that applies, and it is rejected if any of them says no.

Per IP address, before authentication: the only identity a login, sign-up or password-reset request has, and the first line against brute force and floods. Its weakness is shared addresses: a whole office behind one NAT gateway looks like one client, so this limit has to be generous.

Per API key, after authentication: fairness between customers' integrations. Its weakness is many keys: an attacker who creates 100 free accounts gets 100 limits. The per-IP and per-tenant rules are what stop that.

Per tenant, after authentication: one budget for an organization, matching what it pays for. Its weakness: one runaway script can spend the whole organization's budget. The per-key rule bounds each key inside it.

Where Each Identity Comes From

  • API key and tenant: authentication resolves the Authorization header into a key ID; the tenant is read from the key's record, never from a header the client sends.
  • IP address: from our own load balancer. X-Forwarded-For is a list that proxies append to, and the client can write the first entries itself. Take the address your load balancer added — the last entry, or the right number from the end if there are several proxies you run — or have the load balancer replace the header. Never the leftmost entry.
  • IPv6: one machine can rotate through the 2^64 addresses of its /64 subnet (temporary addresses do it on their own), so count IPv6 clients by their /64 prefix.

The Keys

One scheme, rl:{scope}:{id}, with the route appended for a rule that covers one route:

  • rl:ip:203.0.113.42
  • rl:key:ak_abc123
  • rl:tenant:org_acme
  • rl:key:ak_abc123:/v1/charges
Three identities, three buckets. Each identity comes from something the client cannot forge. A request card shows POST /v1/charges, X-Forwarded-For: 1.2.3.4, 203.0.113.42, and Authorization: Bearer sk_live_…; 1.2.3.4 was written by the client, 203.0.113.42 added by our load balancer. The last entry gives the bucket rl:ip:203.0.113.42; authentication gives the key, rl:key:ak_abc123; the key's record gives the tenant, rl:tenant:org_acme. Checked together: the request is rejected if any of the three says no. IPv6 addresses are counted by their /64 prefix.

4. A Burst-Tolerant Algorithm

Requirement: a client may send short bursts while its long-term rate stays within its limit (FR4).

A user opens a dashboard, and it fires 20 API calls at once for its widgets. A strict "10 requests a second" check allows 10 and rejects 10, and the page loads half-broken — although this user sends 20 requests a minute on average, far below the limit. We need an algorithm that lets the burst through and still holds the long-term rate. There are five standard ones.

Fixed Window

Count requests in fixed periods: one counter per client per window, named by the window (rl:key:ak_abc123:29863666 for the 29,863,666th minute since 1970), created with INCR, deleted by its expiry. One command per request, about 92 bytes per counter in our measurement.

The boundary problem: with 10 a minute, a client can send 10 requests at 12:00:59 and 10 more at 12:01:00. Each window sees 10, so all 20 pass — twice the limit within two seconds. A fixed window can let through up to twice its limit in any span as long as one window.

That makes it a poor fit for short limits where bursts matter, and a fine fit for long quotas, where letting a client double up for a moment at the turn of the hour is acceptable. It is common in production: GitHub's REST API limit is a fixed hourly window (its x-ratelimit-reset is when the window resets), and Envoy's rate limit service counts per second, minute, hour or day.

Fixed window: twice the limit at the boundary. 10 a minute: 10 requests at 12:00:59 and 10 at 12:01:00 all pass. Top, to scale: the two minutes 12:00:00 to 12:02:00, each a window; the window of 12:00 counts 10 of 10 and the window of 12:01 counts 10 of 10, from two tight clusters of dots on either side of 12:01:00. Below, a zoom on 12:00:58 to 12:01:02: 10 requests at 12:00:59 pass, then 10 at 12:01:00 pass, 20 within 1.45 s: twice the limit. Up to 2× the limit in any span as long as one window. Fine for long quotas, poor for bursts.

Sliding Window Log

Keep the timestamp of every request; on each new one, drop the timestamps older than the window and count the rest. In Redis, a sorted set: ZREMRANGEBYSCORE removes the expired entries, ZCARD counts, ZADD records. The count is exact, and there is no boundary to exploit.

The cost is memory. A client at a limit of 1,000 a minute holds 1,000 entries, and a sorted set of 1,000 timestamps took 103 KB in our measurement — about 100 bytes per entry, not the 8 bytes of a timestamp. At a limit of 100 a minute, 3.2 KB. Each check does not scan the set: it removes only the entries that have expired since the last check and counts the rest in constant time. But the memory grows with the limit, for every client at its limit.

Sliding Window Counter

Keep two fixed-window counters, the current and the previous window, and weight the previous one by how much of it still overlaps the sliding window. Cloudflare's example: 42 requests in the previous minute, 18 in the current one, which started 15 seconds ago, gives

42 × (60 − 15) / 60 + 18 = 42 × 0.75 + 18 = 49.5

It assumes the previous window's requests were spread evenly, so it is an estimate; Cloudflare measured that "0.003% of requests have been wrongly allowed or rate limited" over 400 million requests from 270,000 sources. Two counters took 184 bytes in our measurement. (Cloudflare keeps these counters inside each data center, in a memcached fork, rather than in one global store.)

Sliding window counter: weigh the last window. Two counters stand in for the last 60 seconds; this is Cloudflare's example. A two-minute time axis from 12:00:00 to 12:02:00, drawn to scale. PREVIOUS MINUTE: 42 requests; CURRENT MINUTE: 18 so far, 15 seconds in, the rest still to come. The last 60 seconds, ending now (12:01:15), still cover 45 of the previous minute's 60 seconds: 75%. So the estimate is 42 × 0.75 = 31.5 for the previous minute, weighed, plus 18 for the current one: 49.5. It is an estimate: it assumes the 42 were spread evenly over their minute.

Leaky Bucket

The name covers two different things.

As a meter: a bucket drains at a constant rate; each request adds one unit; a request that would overflow the bucket is rejected. This makes exactly the same decisions as a token bucket with the same size and rate — the water in one is the missing tokens of the other — and our test confirmed it on 400 random requests.

As a queue: requests wait in the bucket and leak out to the backend at a constant rate. The output is perfectly smooth, but every request in the queue waits: with 50 waiting and 100 released a second, the 51st waits half a second. A burst is not rejected but delayed — the dashboard's 20 calls trickle out over 2 seconds. NGINX's limit_req "uses the leaky bucket method": it delays requests up to its burst size (or passes them at once with nodelay), and rejects the rest with 503 by default.

The queue form fits places that genuinely need smooth input: shaping network traffic, feeding a slow downstream at a steady pace. It is rarely right for a user-facing API.

Token Bucket

Each identity gets a bucket with a capacity (the largest burst) and a refill rate. Tokens are added continuously at the refill rate, up to the capacity. A request takes one token if there is one, and is rejected if there is not.

A client that stays quiet saves up tokens and can spend them all at once; a client that sends continuously can never exceed the refill rate. Back to the dashboard: with a capacity of 20 and 10 tokens a second, a user idle for 2 seconds has 20 tokens, and all 20 calls pass. Sustained, the user still cannot send more than 10 a second.

The state is two values — the tokens left and when they were counted — and the refill is computed from the time that has passed, not by a background process. That also gives the exact Retry-After: with 0.3 tokens and 10 tokens a second, the next token arrives in (1 − 0.3) ÷ 10 = 0.07 seconds, sent as 1 second.

Stripe uses it ("We use the token bucket algorithm to do rate limiting", with the buckets in Redis), and so does AWS API Gateway, where a stage's throttling rate is "the rate … that tokens are added to the token bucket" and its burst "the capacity of the token bucket".

Token bucket: bursts pass, the rate holds. Capacity 20, refilled at 10 tokens a second, over six seconds. A chart of the tokens in one bucket against time, with a lane of passed requests and a lane of 429s under it. The bucket starts full at 20. At 1 s a burst of 20 arrives: all pass, and the bucket drops to 0. It gains 10 tokens a second and is full again at 3 s, where it stops at 20. Then 30 requests a second arrive, from 4 s: the saved 20 are spent in about a second (29 of the first 30 requests pass); then 10 a second pass and 20 get 429. A quiet client saves up a burst of 20. A busy one gets the refill rate, no more.

The same bucket can be stored as a single number. The generic cell rate algorithm (GCRA) keeps only the time at which the bucket will next be full — its "theoretical arrival time" — and makes the same decisions; the redis-cell module implements it as one command, CL.THROTTLE. One string with an expiry took 84 bytes in our measurement, against 132 for the two-field hash.

Our Choice: Token Bucket

AlgorithmBurstsMemory per client (measured, Redis 8)AccuracyUsed by
Fixed windowUp to 2× the limit at a window boundary~92 bytesExact count per windowGitHub (hourly), Envoy's rate limit service
Sliding window logExact~100 bytes per request in the window (3.2 KB at 100, 103 KB at 1,000)ExactWhere every request must be counted
Sliding window counterSmooths the boundary~184 bytesEstimate (0.003% wrong at Cloudflare)Cloudflare
Leaky bucket as a queueDelayed, not rejecteda queue of requestsExact output rateNGINX limit_req
Token bucketUp to the capacity, then the rate~132 bytes (84 as GCRA)ExactStripe, AWS API Gateway

The token bucket wins for an API:

  1. The burst is a setting: the capacity is how big a burst may be, separate from the rate.
  2. Small: one small hash per client, gone when the bucket is full again.
  3. One atomic step: the check and the update fit in one short script on the server (part 5).
  4. An exact Retry-After: the time until the next token is a division.
Memory per client: only the log grows. Bytes per client, measured in Redis 8 with a million keys of each kind. A bar chart, with one scale for the four small ones. Fixed window: 92 bytes, one counter. Sliding window counter: 184 bytes, two counters. Token bucket, our choice: 132 bytes, a hash holding the tokens and a time. Token bucket as GCRA: 84 bytes, one string holding a time. The two sliding-log bars are broken because they do not fit on that scale: at a limit of 100, 3.2 KB, as much as 24 token buckets; at a limit of 1,000, 103 KB, about 780 token buckets. A sliding log keeps every request's timestamp, so it grows with the limit. The other four are the same size at any limit.

5. One Limit Across Gateways

Requirement: a limit holds across all gateway instances (FR5).

The Multi-Gateway Problem

The gateway runs as many instances behind a load balancer. If each keeps its own buckets, a client with a limit of 100 a minute whose requests are spread over 10 gateways is counted 10 times, 100 on each: 1,000 a minute get through.

Ten gateways, ten times the limit. A limit of 100 a minute, counted separately by each of 10 gateways. A CLIENT sends 1,000 requests a minute through the LOAD BALANCER, which spreads them over 10 API GATEWAYS; each keeps its own buckets, and each of the ten shows "100 passed" beside its emptied bucket. All of them go on to the SERVICES: 1,000 got through; the limit was 100. Each gateway saw 100, exactly the limit. Together they let through 10 times the limit.

Shared State in Redis

All gateways read and write the same bucket for a client, in a store they share. It has to answer in one round trip, update a bucket atomically, and forget buckets on its own. Redis fits: it keeps everything in memory, runs a short script atomically, and expires keys by itself. A Redis Cluster spreads the buckets over shards by key, so every bucket lives on exactly one shard, and 50 shards carry the 3 million checks a second from the estimate.

Atomic Updates

A check reads a bucket, decides, and writes it back. If two gateways read the same bucket at the same moment, both see the last token, both allow, both write back zero: two requests for one token.

Redis runs one command or script at a time, on one thread, so a Lua script that reads, decides and writes is atomic: no other command runs in the middle. The script also takes the time from Redis's own clock (TIME) rather than from each gateway, so that gateways whose clocks disagree cannot add or take away tokens; and it sets the key to expire when the bucket would be full again, so idle buckets disappear exactly when they stop mattering. The script and how to call it are in the deep dive on atomic updates.

Living with the Latency

The three checks of a request travel together: pipelined on one connection, and in a cluster sent in parallel to the shards that hold the keys. A request pays about one round trip, a few hundred microseconds inside a data center. Keep connections open and pooled; opening a TCP connection per request would cost more than the check.

When Redis Fails

Redis is now on the hot path. Calls to it get a timeout of a few milliseconds, not the seconds that client libraries default to; a circuit breaker stops calling a Redis that keeps failing; and while it is unreachable, the gateways fail open to coarse local limits. The deep dive on failures has the details.

One count, shared by every gateway. Every gateway asks one Redis Cluster: one bucket per client and rule. A CLIENT's request goes through the LOAD BALANCER to the API GATEWAYS (GW 1, GW 2, GW 3); any of them may get the request, and no gateway keeps a count of its own. The gateways make 3 checks in 1 round trip to the REDIS CLUSTER, which holds one bucket per client and rule; allowed requests go on to the SERVICES. In one place: a check is one atomic script, the time is Redis's clock, and idle buckets expire.

6. Changing Limits Without Restarts

Requirement: operators change limits at any time, and every gateway applies the change within 60 seconds (FR6).

An attacker starts hammering /v1/login. The limit there has to go from 100 a minute to 10 — now. If the limits live in the gateways' configuration files, that is a rolling restart of every gateway, and the attack continues meanwhile. Limits must change without restarts.

The Policy Store and the Gateways' Copy

The rules live in PostgreSQL, behind a small admin API (the Interface section). The gateways never read the store per request: each keeps every rule in memory and refreshes that copy in the background.

Push and pull. When a rule changes, the admin API publishes the new version number; gateways that hear it fetch the changes at once, so the change is live in seconds. The push is not enough on its own: Redis Pub/Sub, for example, delivers at most once, and a gateway that was disconnected at that moment never hears it. So every gateway also polls for changes every 30 seconds: a lost push delays a change by at most one poll, well inside the 60 seconds the requirement allows. Each poll asks for everything after the last version it has, so nothing is missed and nothing is fetched twice.

What Happens to the Buckets

Nothing needs resetting. The script takes the capacity and the rate as arguments on every call, so a new rule applies from the next check: a lower capacity caps the tokens on the next check, a new rate refills from then on.

Shadow Mode First

A new or tighter rule can start with mode: shadow: the gateways evaluate it and log what it would have rejected, and let the request through. Once the logs show it catches abuse and not customers, switch it to enforce. The deep dive on policies covers this, exceptions, and rolling back.

Example Rule

{"rule_id": "key-default", "scope": "key", "route": null, "capacity": 100, "refill_tokens": 100, "refill_ms": 60000, "mode": "enforce"}
A new limit, live without a restart. Rules live in the policy store; every gateway keeps a copy in memory. An OPERATOR sends PUT a rule to the ADMIN API, which numbers it and stores it as version 4182 in the POLICY STORE (PostgreSQL). The admin API pushes the number 4182 to every gateway (a dashed arrow: asynchronous), and every gateway also polls it every 30 s. EVERY API GATEWAY: 1 hears the push, or polls; 2 fetches what changed after version 4181; 3 swaps its copy in memory: no restart, no deploy. A push makes the change live in seconds, but a push can be lost. So every gateway also polls every 30 seconds: a lost push delays a change by one poll, inside the 60 s allowed.

The Whole Design

Clients reach the gateways through a load balancer. In each gateway, a per-IP check runs before authentication and the per-key and per-tenant checks after it, all against buckets in a Redis Cluster; the rules come from the policy store, cached in every gateway. Allowed requests go on to the services; rejected ones get a 429 with Retry-After.

The whole design: one filter, one shared count. Checked in the gateway, counted in Redis, configured from the policy store. A CLIENT's request goes through the LOAD BALANCER to the API GATEWAYS, which do four steps: 1 a per-IP limit, 2 authenticate the key, 3 the per-key and per-tenant limits, 4 route; they keep the rules in memory. Allowed requests go on to the SERVICES. For its limits a gateway makes 1 round trip to the REDIS CLUSTER: 50 primaries, each with a replica. The rules come from the POLICY STORE (PostgreSQL) along a dashed arrow, refreshed in the background. A rejected request goes back to the client as 429 with Retry-After.