Rate Limiter Design: Token Bucket, Sliding Window, and Distributed Enforcement

Rate limiting appears in almost every system design interview because it sits at the intersection of correctness, performance, and distributed consistency — three properties that conflict in interesting ways.

The problem sounds simple: allow a user to make at most N requests per time window T. The implementation reveals depth at every layer: choosing the algorithm (token bucket vs sliding window), handling distributed state (one Redis cluster vs per-region counters), dealing with race conditions (atomic Lua scripts vs Redis WATCH/MULTI), and degrading gracefully when the rate limiter itself is unavailable.

Why the algorithm choice matters: a fixed-window counter allows 2× the rate limit in burst — a user gets N requests at the end of window 1 and another N at the start of window 2, for 2N requests in the window boundary zone. This is the boundary burst problem and it is the single most common interview follow-up. Any candidate who proposes fixed-window without addressing this gets marked down.

The distributed challenge: a single-machine rate limiter is trivial — an in-memory token bucket or counter. The hard problem is ensuring consistency when traffic is distributed across 10 API gateway nodes. If each node tracks its own counter, a user can hit N/10 requests on each of 10 nodes, totaling N requests with no rate limiting enforcement. The solution requires shared state — typically Redis — and atomic operations to avoid race conditions.

What most candidates miss: the rate limiter must fail open gracefully. If Redis is unreachable, the correct default for most production systems is to allow requests through (fail open) rather than reject all traffic (fail closed), because the rate limiter outage should not take down the API. This is a conscious tradeoff between abuse prevention and availability.

Fixed Window Counter: divide time into fixed windows (e.g., 1-minute slots: 12:00–12:01, 12:01–12:02). Count requests per window. Reset counter at window boundary. Implementation: Redis key ratelimit:{user}:{window_start} with INCR and EXPIRE at window_start + window_duration.

Problem — boundary burst: a user sends N requests at 12:00:59 (within window 1) and another N at 12:01:01 (within window 2). Both are within limits, but in a 2-second span the user sent 2N requests — twice the intended rate. This is the canonical fixed-window failure mode.

Sliding Window Log: store a timestamp for every request in a sorted set. On each new request, remove all timestamps older than now - window and count the remaining. If count < limit, allow and add the new timestamp. Accurate — no boundary burst. Cost: O(limit) memory per user (storing every timestamp); for 1000 req/min, that's 1000 entries per user. At 1M users this is 1B entries. Impractical for large-scale APIs.

Sliding Window Counter (the best general-purpose algorithm): approximates the sliding window using two fixed windows. Current window count + (previous window count × fraction of window remaining). Example: limit=100/min, current window (12:01–12:02) has 30 requests, previous window (12:00–12:01) had 70 requests. 40% of the current window has elapsed. Effective count = 30 + 70 × (1 - 0.4) = 30 + 42 = 72. Allow if 72 < 100. Memory: 2 counters per user (current + previous window). Accuracy: within ~1% of true sliding window. This is what Cloudflare, GitHub, and most production systems use.

Token Bucket: a "bucket" holds up to capacity tokens. Tokens refill at rate tokens/sec. Each request consumes one token. If the bucket is empty, deny the request. Implementation requires storing {current_tokens, last_refill_time} per user and computing tokens added = (now - last_refill) × rate on each check. Pros: naturally allows bursts (up to capacity tokens can be consumed instantly). Cons: more state, requires floating-point arithmetic in Lua, drift in distributed scenarios.

Leaky Bucket: requests enter a FIFO queue (the "bucket"); a worker drains the queue at a fixed rate. Excess requests that overflow the queue are rejected. Smooths bursty traffic into a constant output rate. Used in network devices (traffic shaping). For API rate limiting: the queue adds queuing latency and complexity without the burst-handling benefit of token bucket. Rarely the right choice for API gateways.

The naive implementation of a Redis rate limiter has a critical race condition. Consider this pseudo-code:

count = INCR ratelimit:{user}:{window}
if count == 1:
    EXPIRE ratelimit:{user}:{window} 60
if count > limit:
    return deny
return allow

The race: two requests arrive simultaneously. Both execute INCR and get count=1 and count=2. Both try to set EXPIRE. This looks fine — but what if the key already existed from a previous window without a TTL? Both requests check count=1 and count=2 but skip the EXPIRE (because count != 1 for the second). The key never gets a TTL and the counter grows forever.

A subtler race: between INCR and EXPIRE, the process crashes. The key now exists with no expiry — permanent rate limiting for this user.

Fix: Lua scripts. Redis executes Lua scripts atomically — no other Redis command runs between lines of the script. The following script is the canonical sliding window counter implementation:

local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

local count = redis.call('INCR', key)
if count == 1 then
    redis.call('EXPIRE', key, window)
end
return {count, redis.call('TTL', key)}

This script increments the counter and sets the TTL atomically. No race condition is possible. The caller receives {count, ttl} and decides allow/deny + computes X-RateLimit-Remaining and X-RateLimit-Reset.

Alternative: Redis SET with NX and EX. For token bucket: SET key value NX EX ttl sets the key only if it doesn't exist, with a TTL in one atomic command. Combined with DECRBY in a pipeline, this implements token bucket without Lua. However, updating tokens without a Lua script still requires WATCH/MULTI/EXEC transactions, which are less efficient than Lua under contention.

Hot key problem: a viral API endpoint or a single power user generates 100K+ RPS. All rate limit checks for this user hash to the same Redis shard, creating a hot partition. The shard handles ~100K ops/sec, but a single Redis instance handles ~100K ops/sec total — one hot key consumes the entire shard's capacity.

Solutions — three options:

1. Key sharding with local aggregation: split the rate limit key across N virtual shards: ratelimit:{user}:{window}:{random(0,N)}. Each gateway node picks a random shard. The effective limit per shard is total_limit / N. This reduces per-shard load by N× but under-counts when a single gateway node hits different shards (a node might allow limit/N requests per shard, totaling limit across N shards from one node). Use for approximate enforcement where slight over-counting is acceptable.

2. Local counter with periodic Redis sync: each gateway node maintains a local in-memory counter. Every 100ms, it publishes its local count to Redis (INCRBY) and reads the global count back. Between syncs, requests are checked against the local estimate. This reduces Redis calls by 100× but introduces up to 100ms of over-counting window. Appropriate for per-minute or per-hour limits where 100ms of over-counting is acceptable. Twitter and Stripe use variants of this approach.

3. Dedicated rate limit service with connection pooling: instead of each gateway node directly calling Redis, a dedicated rate limiter service (10-instance fleet) handles all Redis calls. Gateway nodes call the rate limiter service via gRPC with keepalive connections. The service maintains Redis connection pools efficiently. This reduces the number of Redis connections from (gateway_nodes × connections_per_node) to (rl_service_nodes × connections_per_node) — important when gateway autoscales to 1000 nodes.

Multi-region rate limiting:

For global APIs, a user in EU and a user in US both hit the same global limit. Strong consistency (cross-region Redis) adds ~100ms RTT per request — unacceptable.

Recommended approach: rate limiting is enforced per-region with a fraction of the global limit. Allocate global_limit / num_regions to each region. For a 1000 req/min global limit across 3 regions: each region allows 333 req/min. A user cannot exceed the global limit by spreading requests unless they are load-balanced across regions, which is uncommon. For strict global enforcement, use periodic quota reconciliation: every minute, regions report usage to a central store and adjust their allocation for the next window.