Lesson 11 of 15 Case Studies

Design a Rate Limiter

Rate limiter system design: token bucket, leaky bucket, fixed and sliding windows with Python code, then a distributed limiter on Redis at scale.

45-55 min intermediate 0/15 lessons done
Course contents Lesson 11 of 15 · 0 done
On this page (9 sections)
  1. The problem
  2. 1. Requirements
  3. 2. Where it runs
  4. 3. Algorithms
  5. 4. Distributed design
  6. 5. Failure handling and UX
  7. Key takeaways
  8. Exercises
  9. Quiz

The problem

Design a service that limits how many requests a client can make, for example 100 requests per minute per API key. It protects services from abuse and overload, enforces pricing tiers, and keeps one noisy customer from hurting the rest.

1. Requirements

  • Limit by a key (user id, API key, IP) with per-rule limits (/login: 5/min per IP; API: 1,000/min per key).
  • Reject excess requests with 429 Too Many Requests and a Retry-After header.
  • Low added latency (a millisecond or two); works across many API servers.
  • If the limiter itself fails, fail open (let traffic through) rather than taking the whole API down, for most endpoints.

2. Where it runs

In an API gateway or middleware in each service, consulting a shared store (Redis) so all servers agree on counts. Client-side limits are a courtesy, never enforcement.

3. Algorithms

Fixed window counter. Count requests per key per calendar minute. Simple and cheap. Flaw: a client can send 100 at 0:59 and 100 at 1:00, i.e. 200 in two seconds.

Sliding window log. Store each request’s timestamp; count those in the last 60 s. Exact, but memory grows with traffic.

Sliding window counter. Keep counts for the current and previous fixed windows and weight the previous by how much of it still overlaps the rolling window. Nearly exact, two counters per key.

Token bucket. A bucket holds up to capacity tokens and refills at rate per second; each request takes one. Allows short bursts up to capacity while enforcing the average rate. Used by many cloud APIs.

Leaky bucket. Requests enter a queue drained at a fixed rate; smooths output completely. Good for shaping traffic to a fragile downstream.

Here are the two most useful, with a fake clock so the output is deterministic:

"""Two rate limiters: token bucket and sliding-window counter."""
import time


class TokenBucket:
    """Allows bursts up to `capacity`, refills at `rate` tokens per second."""

    def __init__(self, capacity: int, rate: float, now=time.monotonic):
        self.capacity, self.rate, self.now = capacity, rate, now
        self.tokens = float(capacity)
        self.last = now()

    def allow(self) -> bool:
        t = self.now()
        self.tokens = min(self.capacity, self.tokens + (t - self.last) * self.rate)
        self.last = t
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False


class SlidingWindowCounter:
    """Approximates a rolling window using the current and previous fixed windows."""

    def __init__(self, limit: int, window: float, now=time.monotonic):
        self.limit, self.window, self.now = limit, window, now
        self.current_start = 0.0
        self.current = self.previous = 0

    def allow(self) -> bool:
        t = self.now()
        start = t - (t % self.window)
        if start != self.current_start:
            # moved into a new window; previous only counts if it was the adjacent one
            self.previous = self.current if start - self.current_start == self.window else 0
            self.current, self.current_start = 0, start
        overlap = 1 - (t - start) / self.window  # fraction of previous window still in view
        estimated = self.previous * overlap + self.current
        if estimated < self.limit:
            self.current += 1
            return True
        return False


class FakeClock:
    def __init__(self):
        self.t = 0.0

    def __call__(self):
        return self.t


if __name__ == "__main__":
    clock = FakeClock()
    bucket = TokenBucket(capacity=5, rate=1, now=clock)
    burst = [bucket.allow() for _ in range(7)]
    print("token bucket, 7 instant requests:", burst)
    clock.t += 2
    print("after 2 s:", [bucket.allow() for _ in range(3)])

    clock = FakeClock()
    sw = SlidingWindowCounter(limit=10, window=60, now=clock)
    clock.t = 50
    print("sliding window, 10 at t=50s:", sum(sw.allow() for _ in range(10)), "allowed")
    clock.t = 70  # new window; 10/60 of it elapsed, so ~83% of last window still counts
    print("12 more at t=70s:", sum(sw.allow() for _ in range(12)), "allowed")
token bucket, 7 instant requests: [True, True, True, True, True, False, False]
after 2 s: [True, True, False]
sliding window, 10 at t=50s: 10 allowed
12 more at t=70s: 2 allowed

The bucket allows a burst of 5, then refills 2 tokens in 2 seconds. The sliding window remembers that 10 requests happened 20 seconds ago in the previous window and only admits 2 more, avoiding the fixed-window boundary burst.

4. Distributed design

client -> load balancer -> API gateway (limiter middleware) -> services
                                |
                                v
                         Redis cluster (counters, sharded by key)
                                ^
                         rules config (loaded and cached by gateways)

Storing the counters in Redis: the check and update must be atomic, otherwise two gateways read “99”, both allow, and the count becomes 101. Options:

  • INCR key then EXPIRE key 60 for fixed windows (INCR is atomic; set the expiry when the value is 1).
  • A Lua script that reads, computes and writes the token bucket in one atomic step on the Redis server.

Each check is one round trip (~0.5 ms in the same data centre). Shard counters across Redis nodes by key.

Scaling tricks

  • Local pre-aggregation: each gateway keeps a small local budget and syncs with Redis every few hundred milliseconds. Slightly less accurate, far fewer Redis calls.
  • Multi-region: keep limits per region (simplest), or sync asynchronously and accept slight over-admission.
  • Hot keys: one enormous customer can be given a dedicated Redis shard.

5. Failure handling and UX

  • If Redis is unreachable, fail open (with an alarm) for normal APIs; fail closed for security-sensitive ones like login.
  • Return headers so clients can behave: X-RateLimit-Limit, X-RateLimit-Remaining, Retry-After.
  • Log rejected requests; spikes of 429s are an early signal of abuse or a buggy client.

Key takeaways

  • Fixed windows are simple but allow boundary bursts; sliding window counters fix that cheaply; token buckets allow controlled bursts.
  • Enforce limits server-side at the gateway with a shared store, and make check-and-increment atomic (INCR or Lua).
  • Decide fail-open vs fail-closed per endpoint.
  • Tell clients their limits with 429, Retry-After and remaining-quota headers.

Exercises

  1. Implement a sliding window log limiter and compare its memory use with the counter version for 10,000 requests.
  2. Write the Redis Lua script for a token bucket (store tokens and last-refill time in a hash).
  3. Design tiered limits: free 60/min, pro 1,000/min, enterprise custom. Where do the rules live and how do gateways get updates?

Quiz

  1. What’s the weakness of a fixed window counter?
  2. Why must the Redis check-and-update be atomic?
  3. When should a rate limiter fail closed?
Show answers
  1. Bursts at window boundaries: up to twice the limit can pass within a short span across two windows.
  2. Concurrent gateways could read the same count and all allow requests, exceeding the limit (a race condition).
  3. For security-sensitive endpoints such as login or password reset, where unlimited attempts are more dangerous than temporary unavailability.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).