System Design Interview Questions: Rate Limiting Patterns

A token bucket rate limiter does allow short bursts above its refill rate. Unused tokens accumulate up to the bucket's capacity during idle periods, and a burst can consume them, so throughput briefly exceeds the steady refill rate until the bucket empties.

Rate limiting caps how many requests a single client or source can make within a given time window. Its purpose is to protect the server or API from being overwhelmed by excessive traffic, which prevents abuse, denial-of-service conditions, and resource exhaustion while keeping the service available for legitimate users.

At least one token must be available in the bucket at the time of the request. If the bucket is empty, the request is denied or queued until a token is refilled.

The token bucket algorithm maintains a bucket that holds up to a maximum number of tokens. Tokens are added at a fixed refill rate, and each incoming request consumes one token; if the bucket is empty, the request is rejected or delayed.

The token bucket algorithm holds up to N tokens, refilled at R tokens per second. Each request consumes one token. Empty bucket → reject/delay. Capacity N = max burst; refill rate R = steady throughput. It permits bursts but averages to R over time.

The token bucket algorithm. It maintains a fixed-capacity pool of tokens that refill at a constant rate; each request consumes one token, so short bursts up to the bucket's capacity are allowed while the average rate stays bounded.

In a token bucket rate limiter, each incoming request must consume one token from the bucket to be allowed through. If none is available, the request is rejected. The bucket refills at a constant rate up to a maximum capacity, which determines the long-term average request rate.

Each server counts only the requests it sees, so a tenant whose traffic is spread across all 10 servers can send 100 requests per second to each one, for a total of about 1,000 requests per second. To fix this, share one counter across the servers, for example a central store such as Redis that every server increments atomically. Another option is to split the limit into per-server quotas (100 / 10 = 10 per server each second), though that wastes capacity when traffic is uneven.

Token Bucket is a rate-limiting algorithm where tokens are added to a bucket at a fixed refill rate. Each request consumes one token; if the bucket is empty, the request is rejected. The bucket has a maximum capacity, so tokens can accumulate up to that cap during idle periods, allowing short bursts of traffic up to the bucket size. This makes it well-suited for APIs that need to allow bursts while enforcing an average rate over time. Alternative approaches include fixed-window counters and sliding-window logs.

Token Bucket

A burst can occur at the boundary of two consecutive windows, allowing up to 2 times (double) the configured limit in a brief period. The Sliding Window approaches (Sliding Window Counter and Sliding Window Log) mitigate this by considering the previous window's count (weighted) or by logging individual timestamps, so the limit is never fully reset at a hard boundary.

A fixed-window counter rate limiter can serve up to twice its per-window limit in a short interval. Clients can send N requests just before a window ends and N more right after the counter resets at the next window's start. Sliding-window algorithms are a common fix for this boundary burst.

In rate limiting, the leaky bucket algorithm smooths incoming traffic by enqueuing requests and releasing them at a constant output rate, in contrast to the token bucket algorithm, which allows bursts up to the bucket's capacity.

The limiter stores a log of request timestamps, one per recent request, for each client, typically in a sorted list or deque. When a new request arrives, it first removes all timestamps older than the current window start. If the remaining count is below the configured limit, it appends the new request's timestamp and allows the request; otherwise it rejects it.

Token bucket is the rate limiting algorithm built to allow short bursts up to a configured bucket capacity while enforcing a configurable long-term average rate set by its refill rate. Leaky bucket queues traffic to a constant output rate, and fixed window and sliding window log have no dedicated burst-capacity parameter.

In the token bucket rate limiting algorithm, the bucket capacity sets the maximum burst size by capping how many tokens can accumulate, while the refill rate sets the steady-state average request rate at which new tokens are added.

Use a token bucket. It refills tokens at the sustained rate and lets unused tokens accumulate up to the bucket size, so an idle client banks capacity and can spend it in a burst — exactly the behaviour required. A leaky bucket deliberately flattens bursts to a fixed drain rate, and a fixed-window counter is bursty across boundaries in the wrong way.

Algorithm: I would use a sliding window counter. Each minute is split into fixed windows, and the count is estimated as a weighted mix of the current and previous window counts. This gives close to rolling-window accuracy with two integers of state per key, which matters at 50K RPS across millions of keys. A sliding window log would store a timestamp per request and cost far more memory. A plain fixed window can admit up to twice the limit across a window boundary, violating the quota. If the contract also allows bursts, a token bucket can sit alongside for short-burst control.

Shared state: Local per-instance counters undercount, because one API key's requests are spread across instances by the load balancer. I would keep counters in Redis. The check-and-increment must be atomic, for example a Lua script run via EVALSHA that reads the window counts, checks the limit, and increments only if under quota, all in one round trip. Separate GET and INCR calls would allow lost updates when instances race on the same key. Each key gets a TTL so stale windows expire.

Hot keys: One API key at 50K RPS would saturate a single Redis shard. I would split that key's quota into K sub-counters on different Redis nodes, each with a budget of roughly limit/K, enforced atomically by the same Lua script, and route each request to a sub-counter at random. This spreads load across shards. A short-lived local cache on each application instance can absorb some repeated checks, at the cost of a small overshoot bounded by the cache window.

Degradation: If Redis is unreachable, I would fail open so legitimate traffic is not blocked by a non-critical dependency. I would pair this with a circuit breaker to stop hammering Redis during the outage, alerting that pages on-call, and a local in-memory fallback that enforces a per-instance share of the global limit (global limit divided by the expected instance count), which prevents an unbounded free-for-all until Redis recovers.

Sliding window log is the rate-limiting algorithm that stores each request's timestamp and evicts entries older than the window, so the remaining count is the exact number of requests in a rolling window. Sliding window counter approximates this with weighted buckets, while token bucket and fixed window counter do not give an exact rolling-window count.

Four statements are accurate: a token bucket allows short-term bursts up to the bucket capacity while enforcing an average refill rate, a sliding window log tracks per-request timestamps and prevents the burst-at-boundary problem, a fixed window counter can allow up to 2× the limit at a window boundary, and distributed rate limiting requires a shared counter (e.g. in Redis) to enforce limits accurately. Token buckets do not guarantee zero burstiness — that is the leaky bucket.

The token bucket rate-limiting algorithm refills capacity at a steady rate while permitting short bursts up to its capacity, whereas the leaky bucket algorithm smooths output to a strictly constant rate by draining queued requests at a fixed pace.

Requirements. The limit is per API key over a rolling window (1,000/min), checked on every request. I'd confirm: is a brief burst above the steady rate acceptable (token bucket says yes, up to the bucket size), and — most importantly — if the counter store is unavailable, do we fail open (let requests through, protect availability) or fail closed (reject, protect the backend)? For a public gateway I default to fail-open with alerting, since rate limiting is a guardrail, not the product.

Algorithm. I'd use a sliding-window counter (or token bucket). Fixed-window counters are simplest but allow ~2× the limit across a boundary: a client sends 1,000 in the last second of minute N and another 1,000 in the first second of N+1. The sliding-window counter weights the previous window's count by the overlap fraction, smoothing that out at a fraction of the cost of a full per-request log. Token bucket is the equivalent framing when you want to allow controlled bursts: refill at limit/60 per second, cap the bucket at the burst size.

Distributed counter. Counters live in a shared in-memory store (Redis) so all gateway nodes see the same count. The check must be atomic — a read-modify-write from two nodes races and under-counts — so I use INCR + EXPIRE (or a small Lua script that does increment, TTL, and the limit comparison in one round trip). The API key is the Redis key, so all operations for one key land on one shard.

Accuracy vs latency. A central store is exact but adds a network hop to every request. To hold <5 ms p99, I keep the store cell-local (one Redis per region/cell, no cross-region hop) and accept that limits are enforced per-region. If even one hop is too much, the alternative is local per-node token buckets that sync counts every few hundred ms — fast and highly available, but approximate (a key can briefly exceed the global limit by roughly the number of nodes). I'd start central-per-cell and only move to local+sync if the hop proves too costly.

Failure modes. Store down: fail open, serve requests un-limited, and alert. Hot key: a single key's counter is one Redis key on one shard, so a 200K-req/sec key hammers that shard — I'd detect it and shard that key's counter into N sub-counters (key:0..N) summed on read, or shed it at the edge. Clock skew: window algorithms key off time, so I rely on the store's clock (single source) rather than each node's wall clock.

Scaling. At ~500K ops/sec the counter store is sharded by key across a Redis cluster; because each key's ops stay on its shard, adding shards scales throughput linearly. Replicas give availability, and per-cell stores keep latency flat as we add regions. The bottleneck is always the hottest single key, handled by sub-sharding as above.

I would use a token bucket algorithm per API key, stored in a Redis cluster with consistent hashing on the API key to partition state across shards. Token bucket is the right choice here because it naturally supports both per-second and per-minute limits as two separate buckets, and it tolerates short bursts without rejecting legitimate traffic—important for clients with spiky workloads. For each request, both buckets are checked: if both have at least one token, both are decremented and the request is allowed; otherwise it is rejected with HTTP 429 and a Retry-After header. For the per-minute limit, a second bucket with a 60-second refill window is maintained alongside the per-second bucket, both keyed by the same API key and therefore hashed to the same Redis shard. The check-and-decrement operation must be atomic. A naive read-then-write (GET remaining tokens, check > 0, then DECR) creates a race condition where two concurrent requests both see one remaining token and both decrement, over-allowing by one. I would implement this as a single Redis Lua script that atomically checks both the per-second and per-minute buckets, decrements both if both have tokens, and returns the decision plus the remaining counts. Lua scripts execute atomically in Redis, eliminating the race window without requiring distributed locks. For the failure strategy, I would fail open (allow the request) when Redis is unreachable. The prompt states that the system must not reject valid traffic due to infrastructure issues, so failing open aligns with this requirement. To bound the risk of unlimited over-allowing during an outage, each edge node would maintain a local in-memory fallback counter—a generous fixed-window limiter (e.g., 2× the configured limit per second)—that activates when Redis is unreachable, providing a degraded but still rate-limited mode. A circuit breaker would trip after N consecutive Redis failures to avoid hammering a downed cluster, and an alert would fire so operators can restore the rate-limit store quickly.

Use a token bucket per API key: capacity equals the configured burst limit and the refill rate equals the sustained rate (for example, capacity 100 with a refill of 10 tokens/sec). Share state through a sharded Redis Cluster, with a hash tag on the API key so each tenant's bucket lives on one shard. Each gateway pod's embedded limiter sends one Lua script per request; the script atomically refills based on elapsed time, checks the count, and decrements, so concurrent pods cannot race on check-and-decrement. Tier rules live in a rules table (free 100/min with burst 50, pro 1000/min with burst 200, enterprise 10000/min with burst 2000). Admins push rule changes over a Redis pub/sub channel, and each pod caches the active rule set locally so lookups never touch Redis. For availability, a circuit breaker with a short timeout (about 50 ms) and a health poller detect Redis trouble; when it trips, the limiter fails open to a conservative per-pod local token bucket (each pod gets roughly its share of the global limit), so the API keeps serving while abuse stays bounded. Across the two data centres, either run a Redis cluster per region with each tenant's quota split between regions, or keep one authoritative cluster and avoid synchronous cross-DC calls on the request path. For observability, return X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset headers; emit Prometheus counters for requests and rejections by tier, a Redis latency histogram, and a gauge showing fallback mode; alert on sustained rejection spikes and on any pod entering fallback.

Token buckets allow bursts up to their capacity while still enforcing a long-term average rate. Fixed-window counters can admit up to twice the configured rate across a window boundary, and a Lua script makes a Redis token-bucket check-and-decrement atomic. The sliding-window counter is only an approximation; the sliding-window log is the exact variant.