Design a Rate Limiter: System Design Interview Guide

Rate limiting is a critical component in modern distributed systems. It protects APIs and services from abuse, ensures fair usage, and maintains system stability. In system design interviews, designing a rate limiter is a classic question that tests your understanding of algorithms, distributed systems, and trade-offs. This guide will walk you through everything you need to know: from basic algorithms like token bucket and sliding window to advanced distributed implementations using Redis. You'll also learn how to handle edge cases, common pitfalls, and how to articulate your design under interview pressure. By the end, you'll be ready to tackle any rate limiter question with confidence.

Requirements and Constraints

Before diving into algorithms, clarify the requirements. Ask your interviewer: What are we rate limiting? (e.g., API requests per user per second). What is the scale? (e.g., millions of users). Should the rate limiter be accurate or memory-efficient? Do we need to support burst traffic? Typical requirements: limit requests per user, per IP, or globally; low latency (sub-millisecond); high throughput; distributed across multiple servers; handle bursts gracefully. Non-functional: availability, durability of rate limit state, consistency (eventual vs strong).

Rate Limiting Algorithms

Several algorithms exist, each with trade-offs. Token Bucket: a bucket holds tokens that refill at a fixed rate. Each request consumes a token. Allows bursts up to bucket size. Leaky Bucket: requests are processed at a constant rate, with a queue for overflow. Fixed Window: count requests in a time window (e.g., 1 minute). Simple but can allow bursts at window boundaries. Sliding Window Log: keep a log of timestamps for each request; count requests in the last window. Accurate but memory-intensive. Sliding Window Counter: combine fixed window with a sliding average; more memory efficient. For interviews, token bucket and sliding window counter are popular choices.

import time

class TokenBucket:
    def __init__(self, capacity, refill_rate, refill_interval=1):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate
        self.refill_interval = refill_interval
        self.last_refill = time.time()

    def allow_request(self, tokens=1):
        now = time.time()
        elapsed = now - self.last_refill
        if elapsed >= self.refill_interval:
            self.tokens = min(self.capacity, self.tokens + self.refill_rate * (elapsed // self.refill_interval))
            self.last_refill = now
        if self.tokens >= tokens:
            self.tokens -= tokens
            return True
        return False

Distributed Rate Limiting with Redis

For distributed systems, a centralized store like Redis is common. Use Redis INCR with expiry to implement a sliding window counter. For token bucket, store token count and last refill timestamp in Redis. Use Lua scripting for atomic operations. Example: a sorted set for sliding window log. Considerations: Redis is single-threaded, so Lua scripts are atomic. Network latency adds overhead; consider using local counters with periodic sync for lower latency. Also handle Redis failures gracefully (e.g., fallback to local rate limiting).

-- Sliding window counter using sorted set
local key = KEYS[1]
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local max_requests = tonumber(ARGV[3])

-- Remove old entries
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)

-- Count current requests
local count = redis.call('ZCARD', key)

if count < max_requests then
    redis.call('ZADD', key, now, now)
    redis.call('EXPIRE', key, window)
    return 1
else
    return 0
end

Handling Burst Traffic and Edge Cases

Burst traffic can overwhelm a system if not handled. Token bucket naturally allows bursts up to bucket size. For sliding window, bursts at window boundaries can double the rate. Mitigation: use a smaller window or add a jitter. Edge cases: clock skew between servers (use NTP), race conditions (use locks or atomic operations), and large number of keys (use sharding). Also consider rate limiting at different layers: API gateway, application, and database. For interview, discuss how you would handle a sudden spike in traffic (e.g., viral event).

System Design: High-Level Architecture

A typical rate limiter sits in the API gateway. For each request, extract the client identifier (user ID, IP, API key). Check the rate limit in a cache (Redis). If allowed, forward the request; else return 429. For high availability, use Redis cluster with replicas. For low latency, use local counters with periodic sync (eventual consistency). Also consider a two-tier approach: local token bucket for first line, Redis for global coordination. Discuss trade-offs: accuracy vs. performance, consistency vs. availability.

Interview Tips and Follow-Up Questions

In an interview, start with requirements, then propose an algorithm, then discuss scaling. Be prepared for follow-ups: How do you handle rate limiting for unauthenticated users? (Use IP address). How do you prevent a user from creating many accounts? (Use device fingerprint). How do you handle rate limit headers? (Return X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset). Also discuss how to test your rate limiter (unit tests, load tests). Finally, mention monitoring and alerting (e.g., track 429 rate).