How it works
Start with the policy: who is limited, which operations count, and what happens when the limit is reached. For example, limit each API key to 100 requests per minute on an expensive endpoint. Enforce this before expensive work; rejected HTTP requests typically receive 429 Too Many Requests, with Retry-After when a meaningful retry delay is known.
A fixed window counter tracks requests in a named interval, such as 12:00:00–12:00:59. Atomically admit and increment if the count is below 100. It needs little state, but 100 requests just before a boundary and another 100 just after can produce 200 requests in a very short interval.
A sliding window log stores the timestamps of admitted requests. For a 60-second limit, remove timestamps at or before now minus 60 seconds, count the remaining entries, and admit only if fewer than 100 remain. This enforces an exact rolling limit, but stores an entry per admitted request and requires atomic cleanup, checking, and insertion.
A sliding window counter approximates a rolling window using the current and previous fixed-window counts. Twenty seconds into a 60-second window, estimate usage as current_count + previous_count × 40/60. This uses constant-size state per key, but assumes requests were spread evenly through the previous window and can overcount or undercount.
A token bucket stores a token balance and last-refill time. On each request, calculate tokens = min(capacity, tokens + elapsed_time × refill_rate), then consume a token if available. A bucket with capacity 20 and refill rate 10 tokens per second permits an immediate burst of 20 while limiting the long-run admission rate; requests can also consume different token amounts.
With multiple gateway instances, route each limit key to shared authoritative state or explicitly divide its budget among instances. A Redis script can atomically refill, check, and consume tokens on one primary without a background refill job. Use a consistent time source, expire idle state safely, and decide whether a store timeout means rejection, admission, or a bounded local fallback.
A worked example
One API-key budget across three gateways
Suppose an endpoint allows 10 requests per second per API key, with a burst capacity of 20. Three gateways share a token bucket for each key in Redis. Each request runs an atomic script that refills from elapsed time, caps the balance at 20, and consumes one token if available. Starting with a full bucket, 25 effectively simultaneous requests admit 20 and reject five, regardless of which gateway receives them. With no intervening traffic, half a second replenishes five tokens. A rejected request needs about 100 milliseconds for one token to become available, though competing requests may consume it first. Redis timeouts use a documented failure policy rather than silently granting every gateway a fresh bucket.
Trade-offs to say out loud
- Fixed window: cheap state, boundary bursts
- A counter per key and window is simple, but it cannot enforce a strict limit over every rolling interval.
- Sliding log: precise, more state
- Exact rolling enforcement requires timestamp storage proportional to the admitted requests still in the window, plus cleanup work.
- Sliding counter: compact, approximate
- Weighted counters save memory but can admit too much or reject too early when traffic is uneven.
- Token bucket: controlled bursts, not perfectly smooth traffic
- Capacity controls the immediate burst and refill rate controls sustained admission, so neither value alone describes the policy.
- Shared enforcement: coordination versus latency
- A shared authority coordinates one budget but adds a dependency and possible hot key, while local budgets reduce coordination at the cost of accuracy or unused capacity.
- Failure policy: availability versus protection
- Fail-open preserves access but may overload the backend, while fail-closed protects the budget but can reject legitimate traffic during limiter failures.
When to reach for it
- The prompt asks for a distributed rate limiter, API quota, or per-tenant traffic policy.
- Login or account-recovery endpoints need protection before expensive password hashing or sensitive actions.
- A crawler must obey per-host request rates and avoid bursts against individual websites.
- Workers call an external provider with documented request quotas, and retries must stay within those quotas.
- A bursty endpoint needs admission control before database work, while legitimate short bursts should still be allowed.
How to bring it up in the interview
- State the contract before naming an algorithm: per account or per IP, which endpoints, allowed burst, and whether the limit is exact or approximate.
- Defend the algorithm with a concrete traffic pattern: use token bucket for bounded bursts, a sliding log for exact rolling limits, or a counter when approximation is acceptable.
- Walk through two simultaneous requests for the last token; interviewers will probe whether the check and update are one atomic operation rather than separate reads and writes.
- Explain how one budget spans gateway instances and regions; expect questions about hot keys, local quota allocation, replication lag, and overshoot after failover.
- Describe rejection and recovery behavior, including Retry-After, client backoff with jitter, store timeouts, and metrics for rejection rates and limiter latency.
Common mistakes
- Treating 100 requests per fixed minute as equivalent to 100 requests in every rolling 60-second interval.
- Configuring a token refill rate without specifying bucket capacity or the initial token balance.
- Giving every server the full per-user budget, unintentionally multiplying the effective limit by the server count.
- Assuming individually atomic Redis commands make a multi-command read-check-write sequence atomic, or that an atomic script also guarantees durability across failover.
- Confusing request rate with concurrent work: a rate limiter does not cap in-flight requests, and a queue does not create processing capacity.
Where it comes up
Interview questions where rate limiting algorithms is part of a strong answer, and why.
- Design a distributed rate limiterAlgorithm choice, atomic distributed enforcement, and failure behavior are the core design decisions.
- Design a login and authentication systemLayered account and network rate limits protect expensive password verification and sensitive recovery flows from abuse.
- Design a web crawlerPer-host rate enforcement and request spacing are central to coordinating polite crawling across distributed workers.
- Design a notification systemPer-provider and per-channel rate budgets keep dispatch and retries within external delivery quotas.
Questions people ask
Which rate limiting algorithm should I use?
Choose based on the admission contract, not a universal ranking. Token bucket fits APIs that allow short bursts, a sliding log fits exact rolling quotas, and fixed or sliding counters fit policies that tolerate boundary bursts or approximation.
What is the difference between token bucket and leaky bucket?
Token bucket accumulates permission to admit a burst, up to its capacity. In a queue-based leaky bucket, requests drain at a steady rate, smoothing output but adding waiting time and requiring a bounded queue. Some implementations use a leaky-bucket meter that rejects rather than queues, so clarify the behavior you mean.
Is sliding window rate limiting exact?
A sliding window log can enforce an exact rolling request count when expiration, checking, and insertion are atomic against authoritative state. A weighted sliding window counter is approximate because it does not retain the timing of requests within the previous window. Distributed failures or stale replicas can weaken either implementation's enforcement.