DevPath
Tracks

Design a Rate Limiter

Compare fixed window, sliding window, and token bucket algorithms, implement two with an injected clock, and design where limits live in a distributed system.

intermediate45 min#rate-limiting#token-bucket#sliding-window#system-design#worked-example

Prerequisites: A Framework for System Design, Caching Strategies

Why it matters

Any public service eventually meets a client that sends too much: a buggy retry loop, a scraper, a password guesser, or one noisy customer who starves everyone else. A rate limiter caps how often a caller can act. It protects availability, keeps costs predictable, enforces fair use and paid tiers, and slows abuse. It is also a favorite interview problem because the algorithms are small but the distributed version is full of trade-offs.

Intuition

A bouncer at a club with a clicker allows a fixed number of people per hour. The question is how to count "per hour". Reset the clicker at the top of each hour (simple, but a crowd arriving at 9:59 and another at 10:00 doubles the intended rate)? Or look back over the last sixty minutes at every arrival (accurate, but you must remember arrivals)? Or hand out tokens that refill slowly and let people spend them as they like (allows short bursts but caps the long-run rate)? Those three answers are the main algorithms.

How it works

First, the requirements. Functional: limit by a key (user id, API key, or IP address), with configurable limits per rule, and return a clear rejection (HTTP 429 Too Many Requests, ideally with a Retry-After hint). Non-functional: very low added latency, high availability (should the limiter fail open or closed?), accuracy that is good enough, and correctness across many app servers.

Algorithms

  • Fixed window counter: count requests in each clock window (for example each minute) and reject above the limit. One counter per key, very cheap. Weakness: a burst at the end of one window plus a burst at the start of the next can pass up to double the limit in a short span.
  • Sliding window log: store the timestamp of every accepted request, drop those older than the window, and accept only if fewer than the limit remain. Exact, but memory grows with the limit per key.
  • Sliding window counter: keep counts for the current and previous fixed windows and estimate the sliding total by weighting the previous count by how much of it still overlaps. Tiny memory, close approximation.
  • Token bucket: a bucket holds up to capacity tokens and refills at a steady rate. Each request spends one token; with none left, it is rejected. It allows bursts up to the capacity while enforcing the average rate. Cheap: two numbers per key (token count and last refill time), refilled lazily on each request.
  • Leaky bucket: requests enter a queue that drains at a fixed rate, smoothing output. Good when downstream needs a steady flow.
 token bucket (capacity 3, refill 1 per second)

 t=0   [###]  3 requests allowed -> [   ]  4th rejected
 t=1   [#  ]  1 token refilled    -> 1 request allowed
 t=3   [## ]  2 tokens refilled   -> up to 2 allowed

Here is that bucket (capacity 3, refill 1 per second) handling the same request times the code below uses: 0, 0, 0, 0, 1, 1, 3, 3, 3. Each filled circle is one token.

●
0
●
1
●
2
t=0: the bucket starts full with 3 tokens.
step 1 / 8

Spending drains the bucket instantly, refilling is slow and steady, and the bucket never holds more than 3. The result Y Y Y N Y N Y Y N matches the code.

0403time (seconds)tokens
tokens in bucketcapacity
The same run as a graph. Each vertical drop is a burst of requests spending tokens; each climb between drops is the steady refill of 1 token per second. The refill can never rise above the capacity line.

Where it lives

  • Local per server: fast and simple, but with N servers a client can get N times the limit unless traffic is pinned to a server.
  • Central store (for example a shared in-memory store): all servers update one counter per key, giving a true global limit. The update must be atomic (use an atomic increment or a small server-side script) or two servers will both read the same value and both admit the request. The cost is a network hop per request and a dependency to keep available.
  • Hybrid: each server keeps a local allowance and syncs with the center periodically. Faster and cheaper, slightly looser.

Place the limiter at the edge (API gateway or middleware) so rejected requests never reach your application. Decide the failure mode up front: fail open (allow traffic if the limiter is down, protecting availability) or fail closed (block, protecting the backend or security-critical endpoints like login).

ClientGateway with limiterShared storeApprequestatomic refill and spend for this keyallowedforward requestanother request (bucket empty)atomic refill and spend for this keyno tokens429 with Retry-After
The limiter sits at the edge. An allowed request is forwarded to the app, but a rejected one is answered with 429 at the gateway and never reaches the app. The store holds one bucket per key so all gateways share one global limit.
OperationTimeNotes
Fixed window counterO(1) time, O(1) space per keyBoundary bursts up to 2x
Sliding window logO(1) amortized, O(limit) space per keyExact but memory heavy
Sliding window counterO(1) time, O(1) space per keyApproximate
Token bucketO(1) time, O(1) space per keyAllows bursts up to capacity

Code: token bucket and sliding window log

Both take an injected clock, so tests control time and the output is deterministic. Times are in seconds.

class Clock:
    def __init__(self):
        self.now = 0.0
 
class TokenBucket:
    def __init__(self, capacity, refill_per_sec, clock):
        self.capacity, self.rate, self.clock = capacity, refill_per_sec, clock
        self.tokens = float(capacity)
        self.last = clock.now
 
    def allow(self):
        now = self.clock.now
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False
 
class SlidingWindowLog:
    def __init__(self, limit, window, clock):
        self.limit, self.window, self.clock = limit, window, clock
        self.log = []
 
    def allow(self):
        now = self.clock.now
        self.log = [t for t in self.log if t > now - self.window]
        if len(self.log) < self.limit:
            self.log.append(now)
            return True
        return False
 
def run(limiter, clock, times):
    out = []
    for t in times:
        clock.now = t
        out.append("Y" if limiter.allow() else "N")
    return " ".join(out)
 
c1 = Clock()
bucket = TokenBucket(capacity=3, refill_per_sec=1, clock=c1)
times = [0, 0, 0, 0, 1, 1, 3, 3, 3]
print("token bucket:  ", run(bucket, c1, times))
 
c2 = Clock()
window = SlidingWindowLog(limit=3, window=10, clock=c2)
times = [0, 1, 2, 3, 10, 11, 12, 13]
print("sliding window:", run(window, c2, times))

Both versions print:

token bucket:   Y Y Y N Y N Y Y N
sliding window: Y Y Y N Y Y Y N

Read the token bucket line against the diagram: three requests at time 0 drain the bucket and the fourth is rejected. At time 1 one token has refilled, so one passes. By time 3 two tokens have accumulated, so two of the three pass. In the window log, the request at time 10 is allowed because the one at time 0 has just left the 10-second window, and the one at time 13 is rejected because the window still holds three requests.

Here is the sliding window log from the code (limit 3, window 10 seconds) step by step. Each cell is one logged timestamp.

t=0
0
1
2
t=0: log is empty, so allow and record 0 (Y).
step 1 / 8

The log keeps only timestamps newer than now minus 10. Old entries expire one by one, which is why the t=10 request fits but t=13 does not. Output matches the code: Y Y Y N Y Y Y N.

Common pitfalls

  • Race conditions in a shared store. Read-then-write on a counter lets concurrent requests slip through. Use atomic operations.
  • Clock skew between servers. If servers disagree about the time, windows misalign. Use the shared store's clock or tolerate small error.
  • Choosing the wrong key. Limiting by IP punishes users behind one shared address; limiting by account misses unauthenticated abuse. Often you limit on several keys.
  • Unbounded memory. One log or bucket per key forever fills memory. Expire idle keys.
  • Silent rejections. Return 429 with Retry-After so well-behaved clients can back off instead of hammering.
  • No failure plan. Decide fail open or fail closed deliberately, per endpoint.
  • Counting retries as new load. Clients that retry immediately worsen the problem. Encourage exponential backoff with jitter.

Practice

Show the fixed-window boundary problem easy

Hint

Place requests just before and just after a window boundary.

Show solution

With a limit of 100 per minute, a client sends 100 requests at 0:59 and another 100 at 1:00. Each fixed window sees exactly 100 and accepts all, yet 200 requests arrived within two seconds, double the intended rate. A sliding window or token bucket would reject the extras.

Token bucket parameters easy

Hint

Capacity controls burst size, refill rate controls the long-run average.

Show solution

To allow 10 requests per second on average with bursts of up to 50, use capacity 50 and refill 10 per second. A client that has been idle can send 50 at once, then is held to 10 per second. A smaller capacity makes traffic smoother; a larger one is more forgiving.

Make it work across servers medium

Hint

Where does the shared state live, and how do you update it safely?

Show solution

Keep each key's tokens and last-refill time in a shared store. Perform the refill-and-spend step atomically, for example in a single server-side script or with a compare-and-set loop, so two servers cannot both spend the last token. Add a short local cache of "this key is currently blocked" to cut round trips.

Sliding window counter hard

Hint

Weight the previous window by how much of it still overlaps the sliding window.

Show solution

Keep prev and curr counts for fixed windows of length W. If you are a fraction f (from 0 to 1) into the current window, estimate the sliding count as prev * (1 - f) + curr. Admit the request if that estimate is below the limit. It uses constant memory and is close to the exact log, assuming traffic was evenly spread across the previous window.

Interview questions

  1. Which algorithm would you choose? Token bucket is a strong default: constant memory, allows bursts, and enforces an average rate. Use a sliding window when bursts at boundaries are unacceptable and you want precise counts.
  2. How do you rate limit across many servers? A shared store with atomic updates for a global limit, or local limits with periodic syncing when slight looseness is fine.
  3. What do you return when a request is limited? HTTP 429 with a Retry-After header and a clear message.
  4. Fail open or fail closed? Usually fail open for general API traffic to preserve availability, and fail closed for sensitive endpoints like login attempts. State the reasoning.
  5. How do you handle different limits for different users? Store a limit per key or plan, look it up (and cache it), and construct the bucket with those parameters.

Interviewers look for: comparing at least two algorithms with their trade-offs, thinking about atomicity and distribution, and explicitly choosing the failure mode.

Quick check

A token bucket has capacity 5 and refills 1 token per second. It is full, then 5 requests arrive at once, then 1 more arrives immediately. What happens?

Finished this lesson?

Further resources

Related lessons