Problem Statement
The Question: Design a rate limiter that can handle 100,000+ requests per second across many servers.
What is a rate limiter? Think of it like an API rule that allows a fixed number of requests in a given time window. For example, you can make 5 requests per minute. If you send the 6th request too soon, it’s rejected and you’re told to retry after some time.
Why do we need rate limiting? (most important first):
-
Stop abuse and attacks - A bad person might try to crash your website by sending millions of requests (DDoS attack). Rate limiting stops them at the door.
-
Fair sharing - If one customer uses all the resources, other customers suffer. Rate limiting keeps things fair. Think of it like a buffet - everyone gets a plate, no one takes everything.
-
Control costs - APIs cost money to run. A bug in a client app could send 1 million requests by accident. Rate limiting prevents surprise bills.
-
Keep the service running - If too many requests come at once, servers can crash. Rate limiting is like a circuit breaker that protects your backend.
-
Meet SLAs - If you promise 99.9% uptime, you cannot let one bad actor take down the system for everyone.
What the interviewer really wants to see (this separates good from great):
-
Distributed thinking - Do you understand this is hard because of multiple servers?
-
Tradeoff awareness - Perfect accuracy means slow. Fast means slightly inaccurate. Can you explain WHY?
-
Failure handling - What happens when Redis is down? Do you block everyone or let everyone through?
-
Algorithm knowledge - Do you know Token Bucket vs Sliding Window? When would you use each?
-
Client experience - Do you mention HTTP headers like Retry-After? This shows you think about the full system.
-
Production mindset - Do you talk about monitoring and alerts? How would you know if rate limiting is working?
Clarifying Questions
Before you start designing, ask questions to understand what you are building. Good questions show the interviewer you think before you code.
Question 1: How big is this?
How many requests per second do we need to handle? How many different users or API keys do we need to track?
Why ask this: If we only have 100 requests per second, one server can handle it easily. If we have 100,000 per second, we need many servers working together.
What interviewers usually say: 100,000 requests per second, 1 million different API keys to track.
How this changes your design: With this scale, we cannot use just one server. We need a distributed system with multiple rate limiters.
Question 2: How accurate does it need to be?
If the limit is 100 requests per minute, is it okay if sometimes we allow 105? Or must it be exactly 100, never more?
Why ask this: Perfect accuracy needs all servers to talk to each other before every request. This is slow. A little bit of error lets us be much faster.
What interviewers usually say: Small overrun is fine. We are not charging per request.
How this changes your design: We can use simpler and faster methods. We do not need complex locks that slow everything down.
Question 3: Fixed or sliding time window?
Should we count requests per clock minute (like 2:00 to 2:01) or any 60-second period (like the last 60 seconds from now)?
Why ask this: Fixed windows are simpler but have a problem - someone can make 100 requests at 2:00:59 and another 100 at 2:01:01. That is 200 in 2 seconds! Sliding windows are more accurate but harder to build.
What interviewers usually say: Sliding window is preferred to prevent this gaming.
How this changes your design: We need to use the sliding window counter method (I will explain later) instead of simple counting.
Question 4: One region or global?
Is the rate limit for one data center only, or should it count requests from all around the world together?
Why ask this: If someone in New York and someone in Tokyo both count toward the same limit, we need to share data across the world. This is much harder.
What interviewers usually say: Start with one region, mention global as a future improvement.
How this changes your design: We can start simpler with everything in one place, then talk about how to make it global later.
Summarize your assumptions
Let me summarize what I will design for: 100,000 requests per second, 1 million API keys, sliding window is preferred, small overrun (like 5%) is acceptable, and we will start with one region. I will mention global rate limiting as a future feature.
BONUS Question 5: What limits apply where?
Should we limit by API key? By IP address? By user ID? By endpoint? Can we have different limits for different endpoints (like 10/min for uploads, 1000/min for reads)?
Why ask this: Different rate limit keys serve different purposes:
- API key: Limits a customer or application. Most common for paid APIs.
- User ID: Limits a logged-in user across all their devices.
- IP address: Stops attackers who do not have valid credentials. Watch out for shared IPs (offices, VPNs)!
- Endpoint: Different limits for expensive vs cheap operations.
What interviewers usually say: Start with API key. Mention that you can combine multiple (like API key + endpoint).
How this changes your design: Your Redis key becomes something like rate_limit:{api_key}:{endpoint}:{window}. You might need to check multiple limits per request.
The Hard Part
Distributed Counting
The hardest part is counting accurately when you have many servers. Imagine you have 10 rate limiter servers. User A sends a request to Server 1. At the exact same moment, User A sends another request to Server 2. Both servers need to know the total count - but they do not know about each other!
Why distributed counting is tricky (explained simply):
-
The race condition problem - Two servers read the count at the same time. Both see 99. Both think "okay, limit is 100, I can allow this." Both allow. Now the real count is 101.
-
The speed problem - We could make all servers ask a central place before every request. But that central place becomes slow. And talking between servers takes time (network latency).
-
The time boundary problem - If the limit is 100 per minute, what happens at minute boundaries? Someone could make 100 requests at 2:00:59 (end of one minute) and 100 more at 2:01:01 (start of next minute). That is 200 requests in just 2 seconds!
-
The clock problem - Different servers have slightly different times. Server A thinks it is 2:00:00, Server B thinks it is 2:00:01. Their counts for "this minute" might not match.
Common mistake candidates make
Many people say: just use a counter and increment it! This works for one server, but breaks completely when you have many servers. Always think about the distributed case first - what if there are 10 servers?
The fundamental choice you must make:
Option 1: Be perfectly accurate (slow)
- Before every request, all servers must agree on the count
- This is called "distributed consensus" and takes 50-100 milliseconds
- Your API becomes slow because of rate limiting
Option 2: Be very fast but slightly inaccurate (recommended)
- Each server makes its own decision quickly
- Sometimes the total count goes a bit over the limit
- Your API stays fast
For rate limiting, we almost always pick Option 2. Why? If someone makes 105 requests instead of 100, nothing terrible happens. But if every API call takes 50ms longer, users will leave.
Scale and Access Patterns
Before designing, let me figure out how big this system needs to be. This helps us choose the right tools.
| What we are measuring | Number | What this means for our design |
|---|---|---|
| Requests per second | 100,000 | One server cannot handle this alone - Redis can do 100K+ operations per second, so it works |
| Unique API keys | 1,000,000 | Need to track 1 million different users - this fits in memory easily |
The Challenge
At 100K requests per second with 1 million keys, the data easily fits in memory (about 100 MB). Redis can handle this throughput on a single node with room to spare. The challenge is not storage or throughput - it is coordinating counts across multiple rate limiter instances while staying under 5ms latency.
How people use the rate limiter (from most common to least common):
-
Check and allow - Most requests (99%) are under the limit and pass through. This must be super fast.
-
Check and block - About 1% of requests hit the limit. We return "429 Too Many Requests" error.
-
Near the limit - When someone is close to their limit, they might slow down or retry later.
-
Way over limit - Bad actors or bugs that send way too many requests. Block quickly.
How much space does one user's rate limit data need?
- API key: about 30 bytes
- Current count: 8 bytesKey insight about hot keys
Some API keys are much busier than others. One big customer might make 10,000 requests per second, while most make 1 per second. We call the busy keys "hot keys" and might need special handling for them (like local caching).
High-Level Architecture
Now let me draw the big picture of how all the pieces fit together. I will keep it simple and explain what each part does.
Approach
Put the rate limiter in front of our API servers. Every request must pass through the rate limiter first. Use Redis to store the counts because it is super fast (in-memory) and has atomic operations (no race conditions).
What each part does and WHY it is there:
| Part | What it does | Why we need it (what to tell interviewer) |
|---|---|---|
| Load Balancer | Spreads incoming requests across multiple rate limiters | One rate limiter cannot handle 100K requests per second. We need several working together. |
| Rate Limiter | Checks if this user has made too many requests. If yes, block. If no, allow. | This is the core of our system. It makes the allow/block decision for every request. |
| Redis | Stores the count of requests for each user. Super fast because it is all in memory. | We need a central place to keep counts. Redis is perfect because: (1) in-memory = fast, (2) atomic operations = no race conditions, (3) TTL = automatic cleanup. |
| API Servers | Do the actual work (whatever the API does). | Only get requests that passed the rate limit check. Protected from overload. |
Common interview question: Why not put rate limiting in the API server itself?
You could! For simple cases, this works fine. We use a separate rate limiter layer when: (1) we have many different API servers and want consistent limits, (2) we want to block bad traffic before it reaches our expensive API servers, (3) we want to change rate limit rules without redeploying all API servers.
Why we picked these tools:
Redis (Recommended for rate limiting)
- Why we chose it: Super fast (in-memory), atomic operations (INCR command), automatic expiry (TTL), everyone uses it so lots of help available
- Other options we considered:
- Memcached: Also fast, but no atomic increment with expiry in one command
- In-memory in each rate limiter: Would not share counts across servers
- Database (PostgreSQL): Too slow for 100K operations per second
How real companies do it
Stripe uses Redis for rate limiting. GitHub uses a combination of Redis and in-memory caches. Cloudflare does rate limiting at the edge (their servers around the world) with local counting and periodic sync. For most companies, Redis works great.
API Design and HTTP Headers
CRITICAL: Most candidates forget this!
Rate limiting is not just about blocking requests. It is about telling clients their status so they can behave well. Always mention HTTP headers in your interview - this shows you think about the full system, not just the backend.
The HTTP Response Headers (you MUST mention these):
Every response from a rate-limited API should include these headers:
EVERY response (success or failure) should include:
X-RateLimit-Limit: 100 # The maximum requests allowed in the windowWhy these headers matter:
-
Good clients use them - A well-written client checks X-RateLimit-Remaining and slows down before hitting the limit. This reduces load on your system.
-
Debugging is easier - When a customer complains "my requests are failing," you can ask them to check these headers.
-
Retry-After prevents thundering herd - Without it, 1000 blocked clients might all retry at the same time. With it, they spread out their retries.
Pro Tip
Return rate limit headers on every response, not just when blocking. This lets clients track their usage and slow down proactively. When we do block, we return HTTP 429 with a Retry-After header so clients know when to try again.
The Rate Limiter API Interface:
class RateLimitResult:
allowed: bool # Can this request proceed?
limit: int # The max requests allowedReal-world example: GitHub API
GitHub returns these exact headers on every API call. Try it: curl -I https://api.github.com/users/octocat and look for X-RateLimit headers. They give you 60 requests per hour without authentication, 5000 with authentication.
Data Model and Storage
Now let me show how we store the rate limit data in Redis. The key design is simple but important.
Approach
Use Redis as the single source of truth for request counts. The key pattern is rate_limit:api_key:window_id. Use Redis Lua scripts to make check-and-increment atomic (no race conditions).
How we name the keys in Redis:
Think of Redis keys like file names. We need a naming system that is easy to understand and look up.
Key pattern: rate_limit:{api_key}:{time_window}
Examples:Making it atomic (no race conditions):
The problem: If we do "read count, check if under limit, then increment" as separate steps, two requests can sneak through between the steps.
The solution: Use a Lua script that Redis runs as ONE atomic operation. Nobody can interrupt it.
-- This script runs as ONE atomic operation in Redis
-- Nobody can interrupt it, so no race conditions!
Why Lua scripts?
When Redis runs a Lua script, it blocks everything else until the script finishes. This means no other request can sneak in between our read and write. It is like putting a "do not disturb" sign on the door.
For Sliding Window (better accuracy):
The simple version above uses fixed windows (like 2:00 to 2:01). But someone could game it at the boundary. The sliding window counter is smarter:
-- Sliding Window Counter - More accurate than fixed windows
-- Uses a weighted average of current and previous window
Why sliding window is better
Imagine the limit is 100 per minute. With fixed windows, you could make 100 requests at 2:00:59 and 100 more at 2:01:01 (200 in 2 seconds!). With sliding window, we look at the last 60 seconds from RIGHT NOW, so this trick does not work.
Rate Limiting Algorithms Deep Dive
There are several ways to count requests and enforce limits. Let me explain the main ones in simple terms.
| Algorithm | How it works (simple explanation) | Good things | Bad things | When to use |
|---|---|---|---|---|
| Fixed Window | Count requests in each clock minute (2:00-2:01, 2:01-2:02) | Super simple, very fast | Can be gamed at boundaries (200 requests in 2 seconds) | Simple cases where boundary gaming is okay |
| Sliding Window Log | Keep a list of all request timestamps, count how many in last 60 seconds | Most accurate | Uses lots of memory (storing every timestamp) | When accuracy is critical and memory is not a problem |
| Sliding Window Counter | Keep counts for current and previous window, calculate weighted average | Accurate enough, low memory | Slightly approximate | Best choice for most real systems |
| Token Bucket | Imagine a bucket of tokens. Each request takes one. Tokens refill over time. | Allows bursts (use saved tokens) | More complex to implement | When you want to allow occasional bursts |
| Leaky Bucket | Requests go into a bucket that leaks at a steady rate | Very smooth output rate | Does not allow any bursts | When you need strictly steady traffic |
Algorithm 1: Fixed Window Counter (Simplest)
Think of this like a taxi meter that resets at the start of each minute.
The Problem: 200 requests in 20 seconds while the limit is 100 per minute! This happens because we reset the count at minute boundaries.
Algorithm 2: Sliding Window Counter (Recommended)
Instead of hard resets, we use a weighted average. It is like looking at a 60-second window that slides with time.
def check_rate_limit(user_id, limit=100, window_seconds=60):
"""
Example: It is now 2:00:30 (30 seconds into minute 2:00)Algorithm 3: Token Bucket (When you want to allow bursts)
Imagine a bucket that can hold 100 tokens. Each request needs one token. Tokens refill at a steady rate (like 1 per second).
def token_bucket_check(user_id, bucket_size=100, refill_rate=1.67):
"""
bucket_size: How many tokens the bucket can hold (burst capacity)Which algorithm should you pick?
For most API rate limiting: use Sliding Window Counter. It is simple, uses little memory, and accurate enough. Use Token Bucket only if you specifically want to allow bursts (like letting a user make 10 quick requests, then slow down).
What Can Go Wrong and How We Handle It
Failure Modes
Good engineers think about what can break. Walk through the things that can go wrong and how we protect against them. Interviewers love when you bring this up without being asked!
Common failures and how we handle them:
| What breaks | What happens to users | How we fix it | Why this works |
|---|---|---|---|
| Redis goes down | Cannot check rate limits | Allow all requests (fail open) + alert the team | Better to let some extra traffic through than block everyone |
| Redis is slow | Every API request becomes slow | Set a 5ms timeout + fail open if timeout | If Redis does not respond in 5ms, just allow the request and move on |
| One rate limiter crashes | Traffic shifts to other rate limiters | Use health checks + auto-restart | Since rate limiters are stateless, any one can handle any request |
| Network split between servers | Different servers see different counts | Accept some inaccuracy during the split | When network heals, counts become accurate again |
| One user sends millions of requests | Their requests flood Redis | Use local cache for hot keys | Cache the count locally for a few milliseconds to reduce Redis load |
The big decision: Fail Open vs Fail Closed
When Redis is down, what should we do?
Fail Open (Allow all requests)
- User experience: API keeps working
- Risk: Some users might exceed their limits
- When to use: Most rate limiting (protecting resources)
Fail Closed (Block all requests)
- User experience: API stops working completely
- Benefit: Strict limit enforcement
- When to use: Only when overrun is truly dangerous (like billing, critical resources)
def check_rate_limit_safely(user_id, limit):
"""
Check rate limit with proper error handling.Circuit Breaker Pattern (Smart failure handling)
If Redis keeps failing, we do not want to keep trying and failing. Instead, we "trip the circuit" and skip Redis entirely for a while.
class RateLimiterWithCircuitBreaker:
def __init__(self):
self.failure_count = 0What is a circuit breaker?
Like an electrical circuit breaker that trips when there is too much current, this pattern trips when there are too many failures. It protects Redis from being hammered when it is already struggling, and gives it time to recover.
Hot Keys and Local Caching
The Hot Key Problem - Interviewers love this!
Imagine one customer makes 50,000 requests per second. Every request hits Redis with the same key. That single key becomes HOT - it can overload Redis even though other keys are fine. This is a classic distributed systems problem.
Why hot keys are a problem:
Redis is fast, but it is still single-threaded for commands. If 50,000 requests per second all ask about the same key, that key becomes a bottleneck.
Real example: A popular API user (like a big company using your API) might have millions of requests. All their requests hit the same rate limit key. That one key can slow down your entire Redis.
Solution 1: Local Caching (Recommended)
Cache the rate limit decision locally for a short time (like 100 milliseconds). This reduces Redis calls dramatically.
class RateLimiterWithLocalCache:
def __init__(self):
# Local cache: key -> (allowed, remaining, expires_at)How much does local caching help?
Without cache: 50,000 Redis calls per second for hot user With 100ms cache: 10 Redis calls per second for hot user
That is 5000x fewer Redis calls! The tradeoff: counts might be up to 100ms stale, meaning we might allow a few extra requests during that window.
Solution 2: Key Sharding
Split one hot key into many keys. Instead of rate_limit:user123, use rate_limit:user123:shard0, rate_limit:user123:shard1, etc.
def get_sharded_key(user_id, num_shards=10):
"""
Split one key into multiple shards.Approach
For hot keys, Use use local caching first because it is simpler. Each rate limiter caches decisions for 100ms. This reduces Redis load by 1000x for hot users with minimal accuracy loss. If that is not enough, shard the key across multiple Redis keys.
Monitoring and Observability
Interviewers ask: How do you know it is working?
A rate limiter that silently fails is dangerous. It might let through attacks or block legitimate users. You MUST have monitoring. Bring this up proactively in your interview!
Key Metrics to Track (mention these in your interview):
1. Request counts by outcome:
rate_limit.allowed- Requests that passed throughrate_limit.blocked- Requests that were rate limitedrate_limit.error- Rate limit check failed (Redis down, etc.)
2. Latency:
rate_limit.latency_p50- Median time for rate limit checkrate_limit.latency_p99- 99th percentile (catches slow outliers)- Alert if p99 goes above 5ms
3. Redis health:
redis.connection_count- How many connections to Redisredis.memory_usage- Is Redis running out of memory?redis.ops_per_second- Is Redis overloaded?
4. Business metrics:
rate_limit.unique_keys_limited- How many different users hit limitsrate_limit.top_limited_users- Who is hitting limits most (might be a bug or attack)
def check_rate_limit_with_metrics(user_id, limit):
start_time = time.time()
Alerts to Set Up:
- High block rate: If more than 10% of requests are blocked, something might be wrong
- High error rate: If Redis is failing, we need to know immediately
- High latency: If rate limit checks take more than 5ms, investigate
- Single user spike: If one user suddenly makes 10x their normal requests, might be a bug or attack
What to tell the interviewer
I would track three things: (1) how many requests are allowed vs blocked, (2) how fast the rate limit check is, and (3) Redis health. I would alert if block rate spikes, latency goes above 5ms, or Redis errors increase. This helps us catch problems before users complain.
Growing the System Over Time
What to tell the interviewer
This design works great for one region with up to 500K requests per second. Let me explain how we would grow it if we need to go bigger or serve users around the world.
How we grow step by step:
Stage 1: Single Redis (up to 100K requests per second)
- One Redis server handles everything
- Super simple, strongly consistent
- Single point of failure (use a replica for backup)
- This is enough for most companies!
Stage 2: Redis Cluster (up to 1M requests per second)
- Split users across multiple Redis servers
- User A goes to Redis 1, User B goes to Redis 2
- Each Redis handles fewer users = more capacity
- Still in one data center
Stage 3: Multi-Region (Global users)
- Users in US talk to US servers
- Users in Europe talk to Europe servers
- Either: separate limits per region, OR sync counts across regions
Global Rate Limiting (The hard mode)
If a user has a limit of 100 per minute globally, but they are making requests from both US and Europe, how do we count?
Option 1: One central Redis (Simple but slow for distant users)
- All rate limit checks go to one Redis in, say, US
- Users in Europe have extra latency (crossing the ocean)
- Simple and accurate
Option 2: Regional Redis with sync (Complex but fast)
- Each region has its own Redis
- Counts sync between regions every few seconds
- Fast for users, but counts might be slightly off during sync delays
| Approach | How it works | Good things | Bad things |
|---|---|---|---|
| Single global Redis | Everyone talks to one Redis | Simple, always accurate | Slow for distant users (100ms+ latency) |
| Regional with budget | Each region gets a share (US: 50, EU: 50) | Fast, no sync needed | Unfair if user only uses one region |
| Regional with sync | Local Redis + sync counts every 1-5 seconds | Fast and fairly accurate | Complex, can have brief overruns during sync delay |
Cool features we can add later:
1. Different limits for different endpoints
- POST /upload: 10 per minute (expensive operation)
- GET /status: 1000 per minute (cheap operation)
- Just use different Redis keys for different endpoints
2. Different limits for different users
- Free users: 100 per minute
- Paid users: 10,000 per minute
- Store user tier in Redis or database, look it up when checking
3. Graduated response
- First warning: slow down the response (add delay)
- Second warning: return 429 error
- Repeated abuse: block the user completely
What would you do differently for...
Billing-critical limits (like AWS billing quotas): Use stronger consistency - it is worth the extra latency because money is involved.
DDoS protection: Use local counting at the edge without any sync. Speed matters more than accuracy when you are being attacked.
Per-user monthly quotas: Store in a database with proper transactions. Checked less often (not every request), so accuracy matters more than speed.
Interview Cheat Sheet
Quick Reference for Your Interview
Print this section or review it 30 minutes before your interview. These are the key points that separate great candidates from good ones.
The 5-Minute Structure (how to spend your 45 minutes):
Minutes 0-5: Clarify requirements
- Scale: How many requests per second?
- Accuracy: Is 5% overrun okay?
- Scope: Per user? Per IP? Per endpoint?
- Response: What happens when rate limited?
Minutes 5-10: High-level design
- Draw: Load Balancer -> Rate Limiters -> Redis -> API Servers
- Explain why each component exists
Minutes 10-20: Algorithm deep dive
- Explain Sliding Window Counter (recommended)
- Show the race condition problem
- Explain how Lua scripts make it atomic
Minutes 20-30: Handle failures
- Redis down: Fail open (allow requests)
- Hot keys: Local caching
- Circuit breaker pattern
Minutes 30-40: Production concerns
- HTTP headers (X-RateLimit-Limit, Remaining, Reset)
- Monitoring and alerts
- Scaling to multiple regions
Minutes 40-45: Questions and polish
- Ask interviewer if they want to dive deeper anywhere
- Mention tradeoffs you would explore with more time
Key Phrases That Impress Interviewers:
-
"The core challenge is distributed counting with low latency."
-
"I would use Sliding Window Counter because it prevents boundary gaming while using minimal memory."
-
"Every response includes X-RateLimit headers so clients can self-regulate."
-
"For hot keys, I would add local caching with 100ms TTL to reduce Redis load by 1000x."
-
"I would fail open if Redis is down - slight overrun is better than blocking everyone."
-
"I would monitor block rate, latency p99, and Redis health, with alerts if any spike."
Common Mistakes to Avoid:
-
Forgetting distributed case - "Just increment a counter!" does not work with multiple servers.
-
Ignoring failures - Always explain what happens when Redis is down.
-
Missing HTTP headers - Rate limiting without headers is only half the solution.
-
Over-engineering - Start with single Redis, only add complexity when needed.
-
Ignoring hot keys - One popular user can overload your entire system.
-
No monitoring - How do you know rate limiting is working? You need metrics.
Final Tip
The interviewer knows rate limiting is a solved problem. They want to see HOW you think: Do you ask good questions? Do you consider tradeoffs? Do you think about failures? Do you know when to keep it simple? Show your thought process, not just the answer.