System design · Token bucket, distributed state

How to design a distributed rate limiter

A rate limiter caps how many requests a client can make in a window of time, protecting a service from abuse, runaway clients and accidental overload. The algorithm is the easy half of the interview question. The deep half is enforcing one limit across a fleet of servers without race conditions letting traffic through, and deciding what happens when the limiter itself fails.

Updated October 2, 2026 · 4 min read

Practise system design on the simulator

Requirements

Functional: limit requests per client (API key, user or IP) per rule, for example 100 requests per minute per API key, with different rules per endpoint.
Functional: tell rejected clients when they may retry.
Non-functional: add very little latency (well under a millisecond in-process, a few milliseconds over the network), stay accurate across many servers, and keep working - or degrade safely - when a dependency fails.

Where the rate limiter sits

Enforce limits as early as possible so rejected traffic costs almost nothing. The usual place is the API gateway or a middleware layer in front of every service. Limits can also exist per service for internal protection, but the edge limit is what stops abusive clients before they reach the backend.

Choosing an algorithm

Algorithm	How it works	Trade-off
Fixed window counter	Count requests per clock window (e.g. per minute)	Cheap; allows up to 2× the limit around window boundaries
Sliding window log	Store a timestamp per request; count those in the last window	Exact; memory grows with the limit
Sliding window counter	Weight the previous window's count by how much of it overlaps	Close to exact with two counters per client
Token bucket	Tokens refill at a steady rate up to a capacity; each request spends one	Allows controlled bursts; two numbers per client
Leaky bucket	Requests drain from a queue at a fixed rate	Smooths output; adds queueing delay

Token bucket is the most common default because it is cheap and allows short bursts. Choose a sliding window counter when the limit must be smooth and burst-free.

Token bucket in detail

Each client has a bucket with a capacity (the burst size) and a refill rate. On each request, add the tokens earned since the last request, cap at capacity, and allow the request if at least one token remains.

tokens = min(capacity, tokens + (now - last_refill) * refill_rate)
last_refill = now
if tokens >= 1:
    tokens -= 1
    allow()
else:
    reject(retry_after = (1 - tokens) / refill_rate)

The distributed problem

On one server, a counter in memory is enough. Behind a load balancer, each server only sees part of a client's traffic. If every server keeps its own counter, a client spread across ten servers gets ten times its limit. The counter has to be shared.

Sharing creates a race: two servers read the count at the same moment, both see 99 of 100, and both allow the request. The read-check-write sequence must be atomic.

Redis as the shared counter

Fixed window: INCR a key such as rate:{client}:{minute} and set EXPIRE on first use. INCR is atomic, so concurrent servers cannot race.
Token bucket or sliding window: run the whole read-refill-check-write sequence in a Lua script, which Redis executes atomically.
Shard the counters across a Redis cluster by client ID so no single node holds every key.
To cut latency for very high-volume clients, servers can take small batches of tokens locally and sync with Redis periodically, trading a little accuracy for fewer network round trips.

Telling clients they were limited

Reject with HTTP 429 Too Many Requests and a Retry-After header. Many APIs also return the limit, the remaining requests and the reset time in headers (commonly X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset), so well-behaved clients can slow down before they hit the limit.

When the rate limiter fails

If Redis is unreachable, you must choose between failing open and failing closed.

Fail open: allow requests. The service stays available, but it is unprotected until Redis recovers.
Fail closed: reject requests. The service is protected, but the limiter has caused an outage.
Most public APIs fail open with a generous local in-memory limit per server as a fallback, so protection degrades gradually instead of disappearing.

What interviewers look for

You compared at least two algorithms and picked one for a stated reason.
You placed the limiter at the edge.
You explained why per-server counters fail behind a load balancer and how atomic operations in Redis fix the race.
You returned 429 with Retry-After.
You chose a failure mode deliberately.

Frequently asked questions

What is the best rate limiting algorithm?

Token bucket is the most common default because it is cheap and allows controlled bursts. A sliding window counter is better when limits must be smooth and close to exact. The right choice depends on whether bursts are acceptable.

How do you rate limit across multiple servers?

Keep the counter in a shared store such as Redis and update it atomically - with INCR for fixed windows or a Lua script for token bucket and sliding window - so concurrent requests on different servers cannot race past the limit.

Where should a rate limiter sit in the architecture?

At the edge, usually in the API gateway or a middleware layer, so excess traffic is rejected before it consumes backend resources.

What HTTP status code does a rate limiter return?

429 Too Many Requests, ideally with a Retry-After header telling the client when it may try again.

What happens if the rate limiter's Redis goes down?

You choose between failing open, which keeps the service available but unprotected, and failing closed, which protects the service but causes an outage. Most systems fail open with a local in-memory fallback limit.