Skip to content
Tutorials Center
My learning

Topics

Lesson 47 of 65 ยท Case Studies: Classic Designs

Design a Rate Limiter

Design a distributed rate limiter: where it sits, token bucket, fixed and sliding windows, Redis-style counters, race conditions and the headers to return, with Python.

A rate limiter caps how many requests a client can send in a period. It protects services from abusive clients, runaway scripts and accidental retry storms, and it lets you sell fair usage tiers ("1,000 calls per minute on the free plan"). Nearly every public API has one.

The interesting design question is not "how do I count to 100" but where the counters live, how they stay correct across many servers, and what the limiter does when it breaks.

Requirements

  • Limit by a key: user ID, API key, or IP address; different rules per endpoint.
  • Reject excess requests quickly with HTTP 429 Too Many Requests and tell the client when to retry.
  • Work across many API servers, so the count must be shared.
  • Add very little latency (a few milliseconds).
  • Fail open: if the limiter's store is down, let traffic through rather than take the whole API down (a choice you should state out loud).

Where does it sit?

flowchart LR
    C["Client"] --> G["API gateway with rate limiter"]
    G -- allowed --> S["Backend services"]
    G -- 429 --> C
    G <--> R[("Shared counters, e.g. Redis")]

The gateway checks a shared counter before the request reaches a backend.

Putting the limiter in the gateway (or a sidecar) keeps the logic in one place. Doing it inside each service works but duplicates code. A client-side limiter is useful for politeness but can never be trusted.

Algorithm 1: fixed window counter

Divide time into windows (for example one minute). Keep one counter per key per window. If the counter exceeds the limit, reject. It is cheap (one integer) but has a boundary problem: a client can send the full limit at the end of one window and again at the start of the next, doubling the rate for a moment.

Algorithm 2: sliding window log

Store a timestamp for every request in the last window and count them. It is exact but costs memory proportional to the limit per key.

Algorithm 3: sliding window counter

Keep the current and previous window counts, and weigh the previous one by how much of it still overlaps the sliding window: estimated = prev * (1 - elapsed_fraction) + current. It is a small, close approximation.

Algorithm 4: token bucket

A bucket holds up to capacity tokens and refills at rate tokens per second. Each request spends one token. If the bucket is empty, the request is rejected. Bursts up to the capacity are allowed, while the long-run rate is capped. This is the most common choice in practice.

Python Fixed window vs token bucket

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fixed window let all 10 through within one second (the boundary problem). The token bucket allowed the 5-request burst, had refilled only half a token one second later, and rejected the other five.

Sliding window in practice

Python Sliding window counter with a retry hint

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice how the limiter reports Retry-After. Always tell well-behaved clients when to come back so they back off instead of hammering you.

Making it distributed

With many gateway nodes the counters must be shared. A common choice is Redis with an atomic increment and an expiry. Two things matter:

  • Race conditions. "Read the counter, check it, then write it" lets two nodes both see 4 and both allow the fifth and sixth request. Use one atomic operation (INCR, or a Lua script that does read, check and write together).
  • Latency and single points of failure. One shared store adds a network hop. Reduce it by keeping local counters and syncing in the background, accepting a small overshoot. Shard counters by key so no single node holds everything.

Other design points:

  • Rules in config, not code, so you can change limits without a deploy.
  • Layered limits: per IP at the edge, per API key in the gateway, and per endpoint for expensive routes.
  • Soft vs hard limits: a soft limit adds delay or lowers priority; a hard limit rejects.
  • Return headers: X-RateLimit-Limit, X-RateLimit-Remaining, Retry-After.
  • Observability: log and graph rejected requests per rule, so a mis-set limit is noticed fast.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the boundary problem of a fixed window counter?

    The counter resets at the window edge, so a burst straddling the edge can briefly double the allowed rate.
  2. 2. Which algorithm allows short bursts while capping the long-run rate?

    A full bucket lets a burst through; refilling at a fixed rate caps the average.
  3. 3. Two gateway nodes read the counter value 4, both allow a request and write 5. What went wrong?

    Use an atomic increment or a script so that check and update happen as one step.
  4. 4. Which HTTP status code and header should a limiter return?

    429 Too Many Requests, with Retry-After telling the client when to try again.

Summary

  • A limiter protects services, enforces fairness and supports pricing tiers.
  • Fixed window is cheapest but bursty at the edge; sliding window and token bucket are smoother.
  • Token bucket permits bursts up to its capacity and caps the average rate.
  • In a cluster, share counters in a fast store and update them atomically.
  • Decide and state the failure mode (usually fail open), and return 429 with Retry-After.

Next: Design a Key-Value Store