Chapter 4: Design a Rate Limiter

Rate limiting is essential for preventing resource starvation resulting from Denial of Service (DoS) attacks, whether intentional or accidental, lowering operational costs by filtering excess requests, and protecting backend servers from being overloaded by bots or user misbehavior. While client-side limiting is discouraged due to unreliability, server-side implementation often takes the form of a middleware component, frequently utilizing an API gateway in microservice architectures to intercept and throttle requests before they reach the API servers. The system must handle a large number of requests in a distributed environment, maintain low latency, and utilize minimal memory. Five primary algorithms for achieving rate limiting are discussed: the Token Bucket algorithm, known for its simplicity and ability to allow bursts of traffic as long as tokens remain; the Leaking Bucket algorithm, which uses a FIFO queue to process requests at a stable, fixed outflow rate; the Fixed Window Counter algorithm, which is memory efficient but vulnerable to traffic spikes that occur at the time window edges, potentially allowing twice the permitted quota; the highly accurate Sliding Window Log algorithm, which tracks the timestamp of every request but consumes significant memory; and the memory-efficient Sliding Window Counter algorithm, a hybrid approach that approximates the current rate by combining the current window's count with an overlap percentage of the previous window's requests, smoothing traffic spikes. The high-level architecture utilizes a fast, in-memory cache like Redis for storing counters and managing expiration using commands like INCR and EXPIRE, avoiding the slowness of disk access. In a distributed system, challenges include ensuring synchronization across multiple rate limiter servers, which is solved via centralized data stores, and handling race conditions when concurrently incrementing counters, which can be addressed using methods like Lua scripts. When a request is throttled, the rate limiter returns a HTTP status code 429, and provides informative headers such as X-Ratelimit-Remaining and X-Ratelimit-Retry-After to the client. Performance optimization techniques include using multi-data center setups with edge servers to reduce latency and implementing eventual consistency for data synchronization.