Mastering Rate Limiting: Algorithms, Scenarios, and Practical Implementations

What Is Rate Limiting?

Rate limiting (also called flow control) restricts the number of incoming requests a system can handle, ensuring stability by allowing only a portion of user traffic through when the backend’s processing capacity is limited.

Why Rate Limit?

Sudden traffic spikes—such as flash sales, news events, or malicious crawlers—can overwhelm backend services. Limiting traffic protects against overload, DDoS attacks, and ensures fair resource usage for third‑party platforms.

Common Rate‑Limiting Algorithms

Below are the most frequently used algorithms, each with its core idea and typical implementation.

Counter Limiting

The simplest approach keeps a counter of concurrent requests. When a request arrives, the counter increments; when it finishes, the counter decrements. If the counter exceeds a threshold, the request is rejected.

When the counter is stored in memory, it works for single‑machine scenarios; storing it in a distributed store such as Redis enables cluster‑wide rate limiting.

Pros: easy to implement, works with Java Atomic or Redis INCR. Cons: cannot smooth burst traffic; a massive burst within a short interval can exceed capacity.

Fixed Window Limiting

This algorithm adds a time window. The counter resets after each window (e.g., every second).

If request count < threshold, allow and increment.

If request count > threshold, reject.

When the window expires, reset the counter to zero.

While straightforward, it suffers from edge‑case bursts when requests span two adjacent windows.

Fixed Window Edge Case

For a limit of 100 requests per second, 100 requests arriving at 0.55 s and another 100 at 1.05 s cause 200 requests within a 0.1 s span, exceeding the intended rate.

Sliding Window Limiting

Sliding windows record the timestamp of each request, allowing precise counting over any recent interval (e.g., the last 1 s).

Record each request’s arrival time.

Count requests whose timestamps fall within the past window; discard older entries.

If the count < threshold, allow and record the timestamp; otherwise reject.

This method eliminates the fixed‑window burst problem but requires more memory to store timestamps.

Leaky Bucket Algorithm

Imagine water droplets (requests) continuously poured into a bucket that leaks at a constant rate. If the bucket overflows, incoming requests are dropped.

Enqueue incoming requests into the bucket.

If the bucket is full, reject new requests.

Process requests from the bucket at a fixed outflow rate.

Characteristics: "wide‑in, narrow‑out"—requests arrive at any speed, but are served at a steady pace, smoothing traffic but potentially increasing latency for bursts.

Token Bucket Algorithm

Similar to the leaky bucket, but tokens are added to the bucket at a fixed rate. A request can proceed only if it successfully takes a token.

Add tokens to the bucket at a constant rate.

Discard tokens when the bucket is full.

When a request arrives, consume a token; if none are available, reject.

Compared with the leaky bucket, the token bucket allows bursty traffic up to the number of stored tokens, making it more suitable for handling sudden spikes.

Rate‑Limiting Summary

The algorithms above represent the basic ideas; real‑world implementations often include variations and hybrid strategies to balance smoothness, latency, and burst handling.

Single‑Machine vs Distributed Rate Limiting

The key difference lies in where the threshold value is stored. Single‑machine limiting keeps counters locally, while distributed limiting stores them in a shared store such as Redis.

For example, a sliding‑window implementation can use a Redis zset to record timestamps, ZREMRANGEBYSCORE to purge old entries, and ZCARD to count current requests. Token buckets can also store token counts in Redis.

Because each request would need a Redis round‑trip, a common optimization is batch fetching: retrieve a batch of tokens or counters at once, reducing the number of Redis calls at the cost of a small accuracy loss.

Challenges in Rate Limiting

Setting the correct threshold is difficult: too high overloads the server; too low wastes capacity and harms user experience. A typical approach is to log requests without enforcing limits, analyze the logs to estimate safe thresholds, then replay traffic to validate the configuration.

Dynamic environments (e.g., auto‑scaling) require adaptive thresholds, often based on latency percentiles (P90, P99) or TCP‑style congestion control signals.

Rate‑Limiting Components

Many libraries and tools provide ready‑made implementations:

Google Guava RateLimiter (token bucket with warm‑up support).

Alibaba Sentinel’s uniform‑queue strategy (leaky bucket).

Nginx limit_req_zone module (leaky bucket).

OpenResty resty.limit.req library.

These components encapsulate the core algorithms, allowing developers to focus on integration rather than low‑level details.

Conclusion

Rate limiting is a crucial technique for maintaining system stability, but it must be combined with degradation, circuit breaking, and other resilience patterns. Future articles will explore those complementary mechanisms.