Rate Limiting Algorithms in System Design Interviews
By the BuildTheSystem team

Rate limiting is one of the most frequently tested topics in software architecture discussions. Whether an interviewer asks you to build an API gateway, secure an authentication service, or protect a checkout pipeline, controlling traffic velocity is always central to the solution. Candidate answers often falter because they treat rate limiters as a generic black box rather than explaining the exact mechanics, storage costs, and edge cases of each approach.
Understanding rate limiting algorithms in a system design interview requires connecting mathematical algorithms to physical infrastructure constraints. A solid response explains what the algorithm does, how state is stored in distributed memory like Redis, and how concurrency issues are handled.
The Two-Minute Whiteboard Explanation
When an interviewer asks how you would prevent client abuse, you need a structured pitch that takes under two minutes. Start by defining the core boundary before diving into internal details.
First, state the goal: rate limiting caps request volume per key, such as a user ID, IP address, or API token, returning an HTTP 429 Too Many Requests status code when a client exceeds their allowance. Next, explain that state must be stored in a centralized, low-latency key-value store like Redis so that multiple stateless application servers can evaluate limits consistently.
Finally, summarize the algorithmic decision in one clear sentence: for general API traffic, choose a token bucket because it natively tolerates client bursts while capping average throughput. For strict billing quotas or precise security boundaries where bursts cannot be tolerated, choose a sliding window counter to enforce a smooth cap with minimal memory.
Core Algorithms and How They Work
Rate limiting algorithms differ in three key areas: burst allowance, memory efficiency, and boundary accuracy. Knowing these differences allows you to pick the right tool for any scenario.
Token Bucket
The token bucket algorithm maintains a bucket with a maximum capacity $C$. Tokens refill at a steady rate $R$ per second. Every incoming request attempts to consume a token. If tokens are available, the request proceeds; if empty, the request is rejected.
In a distributed environment like Redis, you do not need a background thread constantly refilling tokens. Instead, you store two fields per key: the remaining token count and the timestamp of the last request. When a new request arrives, calculate elapsed time since the last timestamp, add generated tokens up to capacity $C$, decrement by one, and update the record. This provides exact tracking with minimal memory overhead.
Fixed Window Counter
This algorithm divides time into fixed blocks, such as one-minute windows, and tracks a simple counter for each key within that block. While trivial to implement with Redis INCR and EXPIRE commands, it suffers from the boundary spike problem. A client can send its full quota at the very end of one window and another full quota at the beginning of the next. This allows up to twice the rate limit within a short time frame, potentially overloading downstream services.
Sliding Window Log
Sliding window log stores a timestamp for every request in a sorted set. When a request arrives, entries older than the current time window are removed, and the remaining entry count is evaluated. If below the limit, the new timestamp is added. While perfectly accurate, this algorithm consumes memory proportional to request volume, making it unsuitable for high-throughput public APIs.
Sliding Window Counter
This algorithm combines the memory efficiency of fixed windows with the accuracy of sliding logs. It tracks request counts in the current and previous time windows. To check a request, it calculates a weighted sum based on how much of the previous window overlaps with the current rolling time frame. For example, if 30 seconds have passed in a 60-second window, the estimate equals 50 percent of the previous window count plus the current count. This prevents boundary spikes while using only two integers per client.
Comparing Algorithm Behavior
| Algorithm | Memory Overhead | Burst Support | Accuracy | Primary Use Case |
|---|---|---|---|---|
| Token Bucket | Low (2 fields) | Yes | High | General API Gateway |
| Fixed Window | Very Low (1 key) | No (2x Spike) | Low | Basic IP Rate Caps |
| Sliding Window Log | High (O(N) items) | No | Exact | Audit Log Security |
| Sliding Window Counter | Low (2 keys) | No | Near-Exact | Strict Billing Quotas |
How Algorithms Change Across Interview Scenarios
To demonstrate depth in an interview, adapt your algorithm choice to the requirements of the specific system design question.
Scenario 1: High-Throughput URL Shortener
In a public URL shortener like Bitly, client requests arrive in irregular bursts. An SDK or automated script might send 20 requests in a single second and then remain idle for several minutes.
If you choose a fixed window limiter, those bursts might trigger boundary spikes that strain your database layer. If you pick a sliding window counter, you enforce a strict uniform rate that rejects legitimate client bursts, creating a frustrating developer experience. Here, a token bucket is the ideal choice. It allows clients to consume accumulated capacity quickly while ensuring long-term average traffic remains bounded. To practice articulating these trade-offs live, AI mock interviews for system design provide real-time audio and diagram feedback as you structure your architecture. You can also explore Design a Rate Limiter: A System Design Interview Walkthrough for a step-by-step review of standard architecture patterns.
Scenario 2: High-Concurrency Ticket Booking
Consider a high-demand ticketing system like Ticketmaster, where thousands of users attempt to reserve seats at the exact same second during a seat drop.
In this environment, burst tolerance is a liability rather than a feature. Allowing a client to burst 100 requests in a millisecond gives automated bots an unfair advantage over human buyers. A sliding window counter or a leaky bucket is much better suited here. The sliding window counter enforces strict fairness across time boundaries, ensuring no single user bypasses rate limits during the flash sale.
Implementation Bottlenecks and Trade-Offs
Choosing an algorithm on paper is only half the battle; explaining how it scales under heavy load is where candidates earn top scores.
Concurrency and TOCTOU Race Conditions
In distributed systems, checking and updating rate limit state across multiple app servers introduces time-of-check to time-of-use (TOCTOU) race conditions. If two requests hit different app instances simultaneously, both might read the same token count from Redis, determine capacity is available, and decrement the balance independently, allowing extra traffic through.
To solve this, execute your rate limiting logic inside an atomic Redis Lua script. Redis runs Lua scripts single-threaded, ensuring the read, calculation, and write steps complete atomically without interleaving operations. For deeper insight into handling high-concurrency bottlenecks under heavy traffic, read Design a Rate Limiter at 10x Scale: How Architecture Breaks.
Memory and Storage Footprint
At scale, storing rate limiter state for hundreds of millions of active keys requires careful memory management. While a sliding window log offers exact precision, storing 1,000 timestamps per active client per hour quickly consumes gigabytes of memory. Token bucket and sliding window counter algorithms keep memory flat per active key, making them significantly cheaper to run at scale. To practice sketching rate limiting layers alongside caches and databases, check out the free system design playground.
How to Narrate Your Decision in the Interview
When presenting your rate limiter design, structure your commentary to walk the interviewer through your reasoning step by step.
- State the functional goal clearly: "I will place a distributed rate limiting layer at the API Gateway to protect downstream microservices from overload and enforce fair usage."
- Justify the key selection: "We will rate limit based on a combination of User ID and API key for authenticated endpoints, falling back to IP addresses for unauthenticated traffic."
- Defend the algorithm choice: "I am selecting a token bucket algorithm here because our API traffic is naturally bursty, and token buckets allow short spikes while strictly bounding the average rate."
- Address distributed consistency: "To ensure atomic state updates across app instances, we will execute our token bucket checks in Redis using Lua scripts to prevent TOCTOU race conditions."
- Explain failure modes: "If the Redis cluster becomes unreachable, our rate limiter will fail open to prioritize availability over strict enforcement, accompanied by automated alerting."
By articulating both the mathematical approach and the underlying distributed mechanics, you show the interviewer that you can design systems ready for real-world production demands.
Frequently asked
Which rate limiting algorithm is best for system design interviews?
Token bucket is the most versatile default choice because it tolerates bursty client traffic while holding sustained throughput steady. However, sliding window counter is preferred when you need strict quota enforcement without allowing boundary spikes.
How do you handle rate limiter state in a distributed system?
Store rate limiter state in a fast, in-memory cache like Redis that is shared across all application servers. Execute checking and updating logic inside atomic Lua scripts to prevent race conditions during concurrent requests.
What happens if the rate limiter service goes down?
Most production APIs choose a fail-open policy, allowing requests to pass through so that a cache failure does not cause a total system outage. High-severity alerts should immediately trigger so engineers can recover the rate limiter layer.
Rehearse this out loud, not just on paper
BuildTheSystem runs a live mock interview on a typed-component whiteboard — the interviewer listens, waits while you draw, and reacts the moment you connect something questionable.
Start a mock interviewRead next
Design a Rate Limiter at 10x Scale: How Architecture Breaks
Discover how a basic Redis rate limiter breaks as traffic grows 10x, and learn the architectural updates needed for memory, hot keys, and distributed consistency.
Design a Rate Limiter: A System Design Interview Walkthrough
How to answer the rate limiter system design question — token bucket vs. sliding window, where to enforce the limit, and how to make it work across multiple servers.
Design a News Feed: Mistakes That Cost Candidates the Round
Discover the common mistakes candidates make when asked to design a news feed, including fan-out traps, bad pagination, missing feed ranking, and weak interview narration.