System Design: Rate Limiting

Comparison

If you are unsure which to pick, this flowchart gives a sensible default.

How to read it: most public APIs end at the token bucket. Fixed windows suit quotas where a boundary burst does not matter, and the exact log suits tiny limits such as login attempts.

A token bucket sketch

Here is a single-process token bucket in TypeScript. It shows the lazy refill idea; a distributed version needs atomicity, covered next.

type Bucket = { tokens: number; updatedAt: number };

const CAPACITY = 20;        // maximum burst
const REFILL_PER_SEC = 5;   // sustained rate
const buckets = new Map<string, Bucket>();

export function allow(key: string, cost = 1, now = Date.now()): boolean {
  const b = buckets.get(key) ?? { tokens: CAPACITY, updatedAt: now };
  const elapsedSec = (now - b.updatedAt) / 1000;
  b.tokens = Math.min(CAPACITY, b.tokens + elapsedSec * REFILL_PER_SEC);
  b.updatedAt = now;
  if (b.tokens < cost) {
    buckets.set(key, b);
    return false;
  }
  b.tokens -= cost;
  buckets.set(key, b);
  return true;
}

The bucket moves between three conditions as traffic and time pass.

Note the cost parameter: a search request might cost 5 tokens while a health ping costs 1, so the limit tracks real load, not just request count. Also note that this map grows forever as new keys arrive. A production version evicts idle keys (a bucket that has refilled completely is equivalent to a new one and can be deleted).

Distributed rate limiting

One server with an in-memory map is easy. Real systems run many gateway or application instances behind a load balancer. If each instance limits independently, a client hitting ten instances effectively gets ten times the limit, and the exact multiple depends on load balancer behaviour.

There are three common designs.

The shared store design is the most common. The hazard is a race condition. Suppose two instances both read a counter of 99, both decide "under the limit of 100", and both write 100. Two requests passed but only one was counted. At high concurrency the error grows.

The fix is atomic operations: the read-modify-write must happen as one indivisible step in the store. Options include an atomic increment command (enough for fixed windows), or a short server-side script (Redis supports Lua scripts that run atomically) that does the whole token bucket calculation in one call. The script reads the bucket, refills it, decides, writes back and returns the result, with no other client able to interleave.

Some design decisions deserve thought:

• Latency. The limiter sits on the hot path of every request. Keep the store close (same region, same zone if possible) and the operation to one round trip.
• Fail open or fail closed? If the store is unreachable, do you allow all requests or reject all? Failing open keeps the product alive but removes protection; failing closed protects the backend but turns a limiter outage into a full outage. Many teams fail open for general API limits and fail closed for security-sensitive limits such as login attempts. Decide and document it.
• Expiry. Set a time-to-live on each key so idle callers do not accumulate state forever.
• Hot keys. A single very popular key (one huge tenant) concentrates traffic on one store shard. Consider splitting its limit across several sub-keys.
• Clock skew. If instances compute timestamps themselves, clock differences distort refill. Prefer using the store's clock inside the script.
• Batching. To cut store traffic, an instance may reserve a chunk of tokens at once and spend them locally. This trades a little accuracy for far fewer round trips.

Where to enforce limits

You can rate limit at several layers, and mature systems usually use more than one.

A good pattern: coarse IP-based limits at the edge to absorb floods, per-key plan limits at the gateway, and special limits inside services for expensive or sensitive actions such as password reset or report export.

What to return when you reject

Use HTTP status 429 Too Many Requests. Tell the client when to come back with the Retry-After header, either as a number of seconds or an HTTP date. Many APIs also expose the current state with headers such as limit, remaining and reset time. A standard for these is still evolving, so conventions vary between providers; pick names, document them and keep them consistent (see API design).

A helpful error body names the limit that was hit, for example "per-minute request limit", so the developer knows whether to slow down or upgrade a plan.

Well-behaved clients respect Retry-After, and add jitter (randomness) to their backoff so that thousands of rejected clients do not all retry at the same instant. See reliability basics.

Fairness, tiers and identity

Choosing the key is as important as choosing the algorithm.

• IP address is easy but unreliable. Many users share one address behind corporate or mobile carrier networks, so strict per-IP limits punish innocent people, while attackers rotate addresses.
• API key or user id is accurate for authenticated traffic. Use it as soon as you know it.
• Tenant limits stop one customer from consuming the whole pool.
• Composite keys (user plus endpoint) allow different limits for cheap reads and costly writes.

Common fairness patterns: tiered plans looked up per key, a short-window limit for bursts plus a long-window quota for sustained use, reserved capacity for critical traffic such as payment callbacks, and a global ceiling alongside per-key limits so the ceiling is shared fairly.

In practice: a public geocoding and SMS-verification API with pricing tiers

The situation

A developer-facing API offers address geocoding and an SMS-verification endpoint, sold in three plans: Free, Pro and Enterprise. Eight engineers run it on Kubernetes behind Envoy, with six API pods, a PostgreSQL database holding keys and plans, Prometheus and Grafana, and a paid third-party SMS provider. One engineer is on call at a time.

Today each pod has its own in-memory fixed-window limiter. Three things hurt (all numbers assumed). Effective limits equal the configured limit times the pod count, so a Free key can pull roughly six times its quota. A scraper rotating IP addresses with throwaway Free keys pushes p99 from 120 ms to 900 ms for paying customers. And an SMS-pumping pattern, where abusers trigger verification messages to numbers they profit from, produced a provider bill that is a multiple of the month's forecast. Pod restarts also reset every counter.

Starting architecture

How to read it: limiter state is private to each pod, so nothing coordinates the pods, and the SMS provider is reachable without any spend control.

Options considered

The decision

Failure behaviour is a design input, not an afterthought: geocoding reads fail open into a per-pod local fallback limiter, while the SMS endpoint fails closed because every message costs money.

Rollout and verification

Run the new limiter in shadow mode for a week: it computes decisions and logs "would reject" but enforces nothing. Compare its verdicts with expectations per plan, then enforce for the Free tier first, behind a feature flag with a kill switch, then Pro and Enterprise. Add Retry-After and limit headers and announce the change to customers before enforcement.

Prove it with these panels: allowed versus rejected requests per plan, top ten keys by rejections, limiter latency p99 against the 2 ms budget, Redis CPU and memory, a counter of fail-open decisions (it should normally be flat at zero), paying-tier p99 during a scrape, and SMS spend per hour with an alert on rapid growth. Before enforcement, load test at about three times the assumed peak with a synthetic abusive key and confirm that other keys keep their latency.

The 2 a.m. failure

The page: "Limiter fail-open count above zero for 2 minutes, API p99 above 500 ms". A Redis primary failed over and the limiter's calls timed out for about 30 seconds (assumed). Geocoding traffic fell back to the per-pod limiters, which had been configured with the full plan limit rather than a share of it, so each key could again draw about six times its quota, and a scraper took the opening.

First three checks:

1. redis-cli -h <redis-host> INFO replication to confirm which node is the primary and that the replica caught up.
2. kubectl logs deploy/api --since=10m | grep limiter to see timeouts and fail-open decisions (the deployment name is an assumption).
3. kubectl top pods -n api to see whether the API pods are saturated.

Mitigation: once Redis is healthy, confirm the fail-open counter returns to zero. If the scraper persists, add its keys to a deny list and its networks to an edge rule. Follow-up fixes: set the local fallback to the plan limit divided by the pod count (and test that setting), use client timeouts shorter than the request deadline, and rehearse a Redis failover in a game day.

Architect's notes

• Measure the abuse before you design the limit. Pull a week of per-key request counts and find the real distribution. Limits set from guesses either punish customers or miss the abuser.
• Ask who pays for a rejected request. A limiter protects your application and database, not your bandwidth. Cost-bearing endpoints such as SMS need spend caps, not only request rates.
• Treat limits as a product. Plans, headers and error messages are customer-facing. Sales and support need a way to see why a key was throttled and to grant a temporary exception.
• Name an owner for the limiter fleet. Redis behaviour on the hot path should have an on-call owner and a documented failure mode per route.
• Watch the free tier. Account creation with no friction is what lets one abuser mint thousands of keys, so pair limits with signup checks.
• Defer sticky routing and local token reservation. Both cut Redis traffic but add complexity; adopt them only when you measure Redis as the bottleneck.

Common mistakes

• Using only fixed windows and being surprised by double bursts. Edge spikes hit your backend at twice the intended rate. Use a sliding counter or token bucket when bursts matter.
• Non-atomic check-then-increment across servers. Races let extra requests through. Use atomic store operations or scripts.
• Limiting only by IP. Shared addresses block legitimate users and attackers rotate IPs. Prefer authenticated identity where available, and combine it with IP for anonymous routes.
• Having no plan for limiter outages. Decide fail-open or fail-closed per route, and alert when the limiter store is unhealthy.
• Returning 429 without guidance. Clients retry immediately and make things worse. Send Retry-After and document the limits.
• Counting every request equally. A cheap lookup and an expensive export are not the same load. Use weighted costs.
• Never cleaning up state. Per-key counters pile up forever. Set expirations.

Key takeaways

• Rate limiting protects shared capacity. It stops noisy clients, bugs and abuse from harming everyone else.
• Fixed windows are cheap but spiky. Boundary bursts can double the intended rate.
• Token bucket is the general-purpose default. It allows bounded bursts while enforcing an average rate, with just two numbers per key.
• Leaky bucket smooths output. Use it to feed a downstream system that needs a constant rate.
• Distributed limits need atomicity. Check and update in one operation, usually a script or atomic command in a shared store.
• Decide fail-open or fail-closed explicitly. The right answer differs for general API traffic and security-sensitive routes.
• Enforce in layers. Edge for floods, gateway for plans, services for expensive actions.
• Tell clients how to behave. Use 429 with Retry-After, and have clients back off with jitter.

Practice exercises

Exercise 1 — Starter (30 min): A limit is 60 requests per minute using a fixed window. Show with a timeline how a client can make 120 requests in under 5 seconds without ever violating the rule. Then show how a sliding window log would reject some of those requests.

Exercise 2 — Intermediate (2 hours): Implement the token bucket from this lesson with capacity 10 and refill 2 per second, then write a test that simulates requests at specific timestamps and verifies bursts, refill and rejection. Extend it with a cost parameter and an eviction rule for fully refilled idle buckets.

Exercise 3 — Advanced (half day): Design a rate limiter for an API with 5 million keys, 50,000 requests per second at peak (assumed) and three plan tiers. Specify the algorithm, state layout, shared store topology, handling of a hot tenant, the behaviour when the store is down for each of three route types, response headers, and the metrics you would alert on. Draw the request path as a sequence diagram.

Related reading

• API gateway and service mesh — the usual place where per-key limits are enforced.
• API design — response conventions and idempotency that make limited APIs pleasant to use.
• Reliability basics — retries, backoff and jitter on the client side.
• Caching basics — a limiter store is a cache-like component with similar failure concerns.
• Security for system designers — abuse prevention beyond simple rate limits.