Design a Rate Limiter (System Design)

Problem Statement

Design a rate limiter that controls how many requests a user/client can make within a time period. For example: allow at most 100 requests per minute per user.

The system should work across multiple application servers (distributed), not just a single instance.

Requirements

• Configurable limits (e.g., 100 req/min, 1000 req/hour)
• Per-user and/or per-IP limiting
• Work correctly across multiple app servers
• Low latency (shouldn't slow down requests noticeably)
• Handle race conditions (concurrent requests from the same user)

What the Interviewer Expects

1. Know the algorithms and their trade-offs:

   • Fixed Window — simple counter reset per window. Problem: bursts at window boundaries.
   • Sliding Window Log — store timestamps, count within window. Accurate but memory-heavy.
   • Sliding Window Counter — hybrid, weighted average of two windows. Good balance.
   • Token Bucket — tokens refill at a rate, request consumes one. Allows controlled bursts.
   • Leaky Bucket — requests processed at a fixed rate. Smooths traffic.

2. Distributed implementation — a single server counter doesn't work with multiple app servers. Use Redis as a centralized store.

3. Atomicity — use Redis atomic operations (INCR + EXPIRE, or Lua scripts) to avoid race conditions when multiple requests hit simultaneously.

4. TTL/expiration — keys expire automatically to reset windows.

5. Practical considerations — what happens if Redis goes down? (fail open vs fail closed). Per-user vs per-IP. Response headers (X-RateLimit-Remaining).

Follow-ups

1. How do you prevent the "boundary burst" problem in fixed window? (Sliding window solves it)
2. How would you handle rate limiting when Redis itself is a bottleneck?
3. Fail open or fail closed when the rate limiter service is down? Trade-offs?
4. How would you implement different tiers (free users: 100/min, premium: 1000/min)?
5. How does Token Bucket allow bursts while still enforcing an average rate?