Interview Walkthrough: Rate Limiter

A rate limiter controls the number of requests a client can make to a service within a given time window. It is a critical component for protecting services from abuse, preventing resource exhaustion, ensuring fair usage among clients, and defending against denial-of-service attacks. In a system design interview, the rate limiter question tests your ability to reason about distributed state, concurrency, and trade-offs between accuracy and performance.

Four algorithms dominate the rate limiting landscape. The fixed window counter divides time into fixed intervals (e.g., one-minute windows) and counts requests per window. It is simple to implement with Redis INCR and EXPIRE but suffers from the boundary problem: a client could send the maximum allowed requests at the end of one window and the beginning of the next, effectively doubling their rate for a brief period. The sliding window log stores the timestamp of every request and counts how many fall within the trailing window. It is perfectly accurate but consumes significant memory because every request timestamp must be stored. The sliding window counter is a hybrid that combines the current window's count with a weighted portion of the previous window's count, offering near-perfect accuracy with minimal memory. The token bucket maintains a bucket of tokens that refills at a steady rate; each request consumes a token, and requests are rejected when the bucket is empty. Token bucket is the most flexible algorithm because it naturally handles burst traffic -- the bucket accumulates tokens during idle periods that can be spent during bursts.

In a distributed deployment, the central challenge is maintaining accurate counts across multiple rate limiter instances. If your API runs on 10 servers, each must agree on the current request count for a given client. The standard solution is a centralized Redis instance (or cluster) that stores counters. For the fixed window counter, a Lua script atomically increments the counter and sets an expiry, ensuring that the increment-and-check operation is atomic even under high concurrency. For the sliding window log, a Redis sorted set stores timestamps, and a Lua script atomically adds the new timestamp, removes expired entries, and checks the set size. Race conditions are the primary concern: without atomic operations, two concurrent requests could both read the same count, both decide to allow, and both increment, exceeding the limit by one. Redis Lua scripting or Redis transactions (MULTI/EXEC) solve this by executing the read-check-increment as a single atomic operation.

Placement is another key decision. The rate limiter can live at the API gateway level (centralized, easy to manage, but adds latency to every request), at the application level (more granular control, but harder to enforce uniformly), or as a service mesh sidecar (transparent to the application, but requires service mesh infrastructure). Most large-scale systems use a combination: a coarse-grained rate limiter at the API gateway for DDoS protection and a fine-grained application-level limiter for per-user or per-endpoint quotas. HTTP response headers (X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, Retry-After) communicate rate limit status to clients, enabling them to self-throttle and avoid hitting limits.

A rate limiter works like a nightclub bouncer who counts people entering. The club has a capacity of 100 people per hour. The bouncer uses a clicker counter and resets it every hour (fixed window). If 100 people have entered this hour, the next person is told to wait (429 Too Many Requests) or come back later (Retry-After header). A more sophisticated bouncer might use a rolling count -- checking how many people entered in the last 60 minutes regardless of clock boundaries (sliding window). A token bucket approach would let the bouncer allow a short burst (10 people enter at once) as long as the average rate stays under 100 per hour.