Engineering Atlas › System Design Fundamentals

Protecting services with rate limiting

14 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

What you are limiting, and by what key

A limit is a rule of the form "key K may use R units per period with burst B". The key decides who is being made fair to whom: per API key for partners, per user for a consumer app, per tenant for a SaaS, per IP only as a last resort for anonymous traffic, since thousands of users can share one carrier NAT address. Cost-weighted units are often better than request counts: a search that scans a million rows can cost 50 units while a point read costs 1.

The algorithm families

A fixed window counter increments count[key, floor(now / 60s)]. It is one integer per key, but a client can send its full quota at 0:59 and again at 1:00, twice the rate across the boundary. A sliding window log keeps every timestamp in the window and is exact, but memory grows with the limit. A sliding window counter blends the previous and current fixed windows, weighting the previous one by how much of it still overlaps; it is cheap and close enough for most APIs.

A token bucket refills at rate R up to capacity B and spends a token per request, which states burst and sustained rate separately. A leaky bucket has two readings: as a meter it is the same as a token bucket, and as a queue it smooths traffic by delaying requests rather than rejecting them, which suits outbound calls to a fragile partner but adds latency.

GCRA is the leaky bucket meter written as arithmetic. Instead of storing tokens and a last-refill time, it stores one number per key: the theoretical arrival time (TAT), when the bucket would be empty if the caller stopped now. Each allowed request pushes TAT forward by the emission interval T = period / rate. A request is allowed if TAT, after the push, is no further than T x B into the future.

Concurrency limits are different

Rate limits count arrivals; concurrency limits count requests in flight. A caller making 10 requests per second of 30-second report exports holds 300 server slots, which a rate limit never notices. Limit expensive endpoints by concurrency as well, and release the slot in a finally block or with a lease that expires.

The problem shapes

Rate limiting is the overload and contention shapes: many callers contend for one capacity, and the limiter decides who gets it. It appears far from HTTP. A job queue limits how fast one tenant's jobs are dequeued, a database limits connections per role, and an AI agent framework limits tool calls per task so a looping agent cannot exhaust a paid API in a minute.

Down the stack

Layer 1The contract

For a limit of rate R per period with burst B, the limiter promises that over any interval of length t, a key is allowed at most B + R x t / period requests, and that a key that has been idle long enough can always send B requests back to back. A rejected request costs nothing: it does not consume quota. The response is 429 Too Many Requests (RFC 6585) with Retry-After, which may be a number of seconds or an HTTP date (RFC 9110). Many APIs add quota headers. Many, GitHub among them, still use informal x-ratelimit-limit, -remaining and -reset headers (GitHub docs); the IETF's replacement is still an Internet-Draft (version -11, May 2026) and defines two fields, RateLimit-Policy (quota q per window w) and RateLimit (remaining r, seconds to reset t) (IETF draft). A distributed limiter usually weakens this to "approximately, within one sync interval or one per node", and the design review should state the slack in numbers.

Layer 2The mechanism

GCRA per request, with T the emission interval and tau = T x B:

tat     = max(stored_tat or now, now)
new_tat = tat + T * cost
if new_tat - now > tau: deny, retry_after = new_tat - tau - now
else: store new_tat, remaining = floor((tau - (new_tat - now)) / T)

There is no refill loop and no second field, so the update is one read and one conditional write. In Redis it runs as a Lua script through EVALSHA, which executes atomically: the server blocks all other work while a script runs (Redis docs). The script should read the time with TIME so all gateway nodes share one clock. That is safe on Redis 5.0 and later, where replicas receive the script's writes rather than re-running it; on older versions a write after TIME was refused unless the script first switched to effects replication. The redis-cell module packages this as CL.THROTTLE key max_burst count period quantity, returning whether the call was limited, the limit, the remaining quota, the retry-after and the reset time. Set a key TTL of about tau so idle keys disappear.

Cloudflare's sliding window counter keeps two counters per key and estimates previous x (window - elapsed) / window + current. They measured it over 400 million requests from 270,000 sources and found 0.003% of requests wrongly allowed or limited, with the estimated rate on average 6% off the real one (Cloudflare). Envoy offers both styles: local_ratelimit is a token bucket in each proxy, and global limiting sends descriptors such as ("api_key", "k-123"), ("path", "/search") to a rate limit service over gRPC (ShouldRateLimit), which keeps counters in Redis (Envoy docs). Stripe runs four limiters side by side, all token buckets in Redis: request rate, concurrent requests, and two load shedders that reserve capacity for critical traffic (Stripe).

Layer 3The machine

A same-zone Redis round trip is roughly 0.2 to 0.5 ms, and one Redis core handles on the order of 100,000 small scripts per second. At 200,000 requests per second, central checking on every request needs a sharded cluster and adds a network hop to every request, which is why gateways check locally first and centrally only for keys with strict contracts. Memory is dominated by Redis per-key overhead, around 50 to 90 bytes for a small string with a TTL, not by GCRA's 8-byte timestamp: 10 million active keys cost about 1 GB, where a sliding log of 1,000 timestamps per key would need about 80 GB.

Time is the subtle part. Wall clocks on different gateway nodes can differ by milliseconds or jump when NTP steps them, and a limiter that trusts each node's clock can over-allow after a backwards jump. Use the store's clock for shared state, and a monotonic clock (CLOCK_MONOTONIC) for local buckets.

Why it's built this way

  1. Capacity is shared and some callers misbehave, so each caller gets a budget instead of first come, first served.
  2. Real traffic is bursty, so the budget has two numbers, a sustained rate and a burst, rather than a hard per-second cap.
  3. The check runs on every request, so the state per key must be tiny and the update a single atomic step, which is GCRA's appeal.
  4. A central store adds latency and a dependency, so most enforcement is local and approximate, with central checks only where accuracy is paid for.
  5. Rejections are only useful if clients react, so the protocol returns when to retry and how much quota is left.

Diagram

sequenceDiagram
  participant C as Client
  participant G as Gateway
  participant R as Redis
  C->>G: POST /search (key k-123)
  G->>R: EVALSHA gcra k-123 T=100ms B=3
  R->>R: tat=max(stored,now), new_tat=tat+T
  R-->>G: allowed, remaining=2
  G-->>C: 200
  C->>G: 4th call in same instant
  G->>R: EVALSHA gcra k-123
  R-->>G: denied, retry_after=100ms
  G-->>C: 429, Retry-After: 1

Worked example

A partner API sells plans of 600 requests per minute with a burst of 30. The emission interval is 60,000 / 600 = 100 ms, and tau is 100 x 30 = 3,000 ms.

A partner's batch job wakes at t = 0 and fires 40 requests at once. The first 30 are allowed: after the 30th, TAT is 3,000 ms ahead, exactly tau. The 31st would push TAT to 3,100 ms, so it is denied with retry_after = 3,100 - 3,000 = 100 ms. Denied requests do not move TAT. If the job then sends one request every 100 ms, every one is allowed with 0 remaining: it is running at exactly the sustained rate. If it pauses for 2 seconds, TAT falls back toward now and 20 requests of burst become available again.

Compare a fixed one-minute window of 600. The same job could send 600 requests at 0:59.9 and 600 more at 1:00.0, 1,200 requests in 100 ms, the kind of spike that the plan was meant to prevent.

Across 20 gateway nodes, a pure local split gives each node 30 requests per minute per partner, which throttles a partner whose traffic lands unevenly. The team runs local buckets at 2x the per-node share to absorb skew, plus a central GCRA in Redis for enterprise partners, about 6,000 scripts per second at peak, well within one shard.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Fixed window counterOne integer per key, trivial in any storeAllows 2x the rate across window edgesCoarse daily or hourly quotas
Sliding window logExactMemory grows with the limitLow limits where exactness matters, such as login attempts
Sliding window counterTwo counters, smooth, good accuracyApproximate; assumes even spread in the previous windowHigh-volume APIs with per-minute limits
Token bucket or GCRASeparate burst and rate, tiny state, GCRA is one timestampBurst must be tuned; needs an atomic updateMost API rate limits
Leaky bucket as queueSmooth output, no rejectionsAdds latency, needs a queueOutbound calls to a fragile dependency
Concurrency limitCatches slow, expensive requestsNeeds reliable release of slotsReports, exports, long queries

Pitfalls in production

Leadership lens

Check yourself

  1. Why can a fixed one-minute window of 100 allow 200 requests in one second?

    Show answer

    The client sends 100 at the end of one window and 100 at the start of the next. Both windows see 100, so both batches pass.

  2. In GCRA, why does a denied request leave the stored TAT unchanged?

    Show answer

    A denial should cost nothing; if it advanced TAT, a client retrying too early would push its own next allowed time further away and could starve itself.

  3. A partner sends 5 requests per second, each taking 40 seconds. Which limiter catches this and why?

    Show answer

    A concurrency limiter, because 200 requests are in flight at once. A rate limiter of, say, 10 per second never triggers.

  4. Why should a distributed limiter use the store's clock rather than each gateway's clock?

    Show answer

    Gateway clocks differ and can jump, so TAT values written by one node would be interpreted wrongly by another. One clock keeps the arithmetic consistent.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →