API infrastructure & backend engineering

English

Scaling

Rate limiting at the edge: token buckets, sliding windows and fair quotas

Rate limits protect capacity, enforce commercial quotas and blunt abuse. Choosing an algorithm is the easy part; the harder questions are what to key limits on, how to keep counters consistent across many gateway instances, and how to tell well-behaved clients when to come back.

Published 6 min read

What a limit is for

Before choosing an algorithm, decide what the limit protects. Capacity limits keep a service inside the load it can handle and are set from load tests. Quota limits implement commercial plans – requests per month or per second per customer. Abuse limits slow down credential stuffing, scraping or enumeration and are tuned on attack patterns. Each needs a different key, threshold and response, and mixing them into one number produces limits that are too strict for customers and too loose for attackers. Write down, for every limit, who owns it, what it protects and what evidence its threshold is based on.

The main algorithms

AlgorithmBehaviourTrade-off
Fixed windowCount requests per calendar intervalCheap; bursts of up to 2× the limit at window edges
Sliding logStore a timestamp per requestExact; memory grows with traffic
Sliding-window counterWeight the previous window’s count by overlapClose approximation with two counters
Token bucketTokens refill at rate r up to capacity b; each request takes oneAllows bursts of b; average rate r
Leaky bucket / GCRARequests conform to a theoretical arrival timeSmooth output; one timestamp per key

For API gateways, the token bucket is usually the right default: clients naturally send small bursts – a page load, a batch of parallel calls – and a bucket tolerates them while still capping sustained rate. The generic cell rate algorithm (GCRA) gives equivalent behaviour with a single stored timestamp per key, which makes it attractive for counter stores where memory and round trips matter.

Choosing the key

Limits are only as fair as their keys. Authenticated APIs should limit primarily per client credential or account, and secondarily per route for expensive operations. IP addresses are a poor primary key: many legitimate users share addresses behind carrier-grade NAT or corporate proxies, while attackers rotate through large address pools. Use IP-based limits as a coarse outer layer for unauthenticated endpoints such as login and sign-up, combined with signals like the target account.

Behind a CDN or proxy, the client address arrives in a header such as CF-Connecting-IP or X-Forwarded-For. Trust that header only when the request demonstrably came through your proxy; otherwise anyone can choose their own rate-limit key.

Consistency across replicas

A gateway fleet of ten instances with purely local counters allows roughly ten times the intended rate. There are three practical options:

  • Central counter store: instances update counters in a shared, in-memory store with atomic operations or scripts. This is accurate but adds a round trip to every request; keep the store in the same zone and budget for its latency.
  • Local limits with division: each instance enforces limit ÷ instance count. It needs no coordination but becomes inaccurate when load balancing is uneven or the fleet scales.
  • Hybrid: local token buckets that periodically synchronise with a central store. Slight overshoot is accepted in exchange for lower latency.

Decide what happens when the counter store is unavailable. For capacity limits, failing open preserves availability; for abuse limits on login, failing closed or falling back to strict local limits may be safer.

Talking to clients

Reject over-limit requests with 429 Too Many Requests and a Retry-After header stating when to try again. Many APIs also expose remaining quota; an IETF draft standardises RateLimit and RateLimit-Policy header fields for this purpose. Document limits per plan and route, and make sure SDKs back off with jitter instead of retrying immediately – synchronised retries from many clients can turn a short overload into a long one.

Limits also need a lifecycle. Publish them in the API documentation and developer portal, give customers a way to see their current consumption, and announce reductions well in advance. When a client consistently hits a quota, that is often a commercial conversation rather than an abuse case – the gateway logs should make it easy to tell the difference. Internally, review limits after every major load test and every incident in which a limit either fired unexpectedly or failed to fire. A limit that nobody has looked at for a year is usually either irrelevant or wrong.

Test limit enforcement itself: send traffic just below and just above each threshold, across several gateway replicas, and confirm that responses, headers and metrics match the documentation.

Fairness, priorities and load shedding

Per-client limits keep one customer from consuming another’s share, but they do not protect the service when many clients are busy at the same time. That is the job of load shedding: when a service approaches saturation, it rejects some work early and cheaply instead of accepting everything and timing out on all of it.

Shedding works best with priorities. Classify requests at the gateway – interactive traffic above background synchronisation, paying plans above free tiers, health checks above everything – and shed from the bottom when queue depth or concurrency crosses a threshold. A concurrency limit, adjusted adaptively from observed latency, often reacts faster than a requests-per-second limit because it responds directly to how much work is in flight.

Weighted fair queuing extends the same idea within a class: requests are drawn from per-client queues in turn, so a client that floods the gateway waits behind its own backlog instead of everyone else’s.

Whatever the mechanism, rejected requests should cost almost nothing. Reject before authentication-heavy work or body parsing where possible, return a small response with Retry-After, and record the rejection with its reason so that capacity planning can distinguish genuine demand from abuse.

Worked example: Protecting a login endpoint

A login route suffered credential-stuffing bursts from thousands of addresses. The team applied three layers: a token bucket per client IP (10 requests, refilling at 1 per 6 seconds), a bucket per target username across all IPs (5 failures per 15 minutes, after which a step-up challenge is required) and a global capacity limit for the route set from load tests. Counters lived in a zone-local in-memory store using GCRA scripts, adding under 2 ms at p99. Legitimate users rarely touched the limits; the attack traffic was reduced to a level the authentication service handled without degrading.

Common pitfalls

  • One global limit that mixes capacity, quota and abuse concerns.
  • Keying authenticated traffic primarily by IP address.
  • Trusting forwarded-for headers from any source.
  • Purely local counters on a horizontally scaled gateway.
  • Returning 429 without Retry-After, so clients retry immediately.

Questions & answers

Token bucket or sliding window?

Token bucket when short bursts are legitimate and should be allowed; sliding window when you want a strict count over a rolling period, for example for quota billing.

Should we rate-limit internal services?

Yes, at least with generous capacity limits. Internal callers can overload a service just as easily as external ones, especially through retries.

Where should limits live – gateway or service?

Coarse limits belong at the gateway, before expensive work. Business-specific limits, such as transfers per day per account, belong in the service that understands the business rule.

Checklist

  • Separate capacity, quota and abuse limits.
  • Choose keys per limit: credential, account, route, IP as an outer layer.
  • Use token buckets or GCRA as the default algorithm.
  • Enforce consistently across replicas and define fail-open or fail-closed.
  • Trust client-IP headers only from your own proxy.
  • Return 429 with Retry-After and document limits.
  • Make SDK retries back off with jitter.

Primary sources

  • RFC 6585 – Additional HTTP Status Codes (429 Too Many Requests)
  • RFC 9110 – HTTP Semantics (Retry-After)
  • IETF HTTPAPI working group, “RateLimit header fields for HTTP”, Internet-Draft (work in progress at the time of writing)
  • ATM Forum Traffic Management Specification – Generic Cell Rate Algorithm (GCRA)

All research