In the previous article we talked about why rate limiting matters so much. Now we move to the more fun part: the algorithms themselves. 🤔
Building a rate limiter is not just checking request_count > 100. Behind every modern API
Gateway, whether it is Kong, NGINX, or Cloudflare,
there is a calculation that decides how your traffic gets treated.
Four algorithms show up most often in the industry. Each one behaves differently, and picking the wrong one can leak your quota or block real users. Let's take them one at a time.
Key takeaways
- Token Bucket is the most tolerant of short bursts, Leaky Bucket releases requests at an even rate, Fixed Window is the easiest but is prone to a boundary spike, and Sliding Window Counter is the best balance between accuracy and memory.\n- Token Bucket is the de facto standard in modern API Gateways like AWS API Gateway, Kong, and NGINX because it is friendly to burst capacity.\n- The boundary spike in Fixed Window can let through twice the quota right at the turn of an interval.\n- Sliding Window Counter needs Redis Hashes and a Lua Script so the quota check stays atomic and free of race conditions in a microservices architecture.
Token bucket, the flexible favorite
Token Bucket is the de facto standard in most modern API Gateways, including AWS API Gateway and Google Cloud Armor.
The mechanics are simple. Picture a bucket with a limited token capacity, say 10 tokens.
- Every second the system adds new tokens at a constant rate (2 tokens/second, for example). If the bucket is already full, the new tokens spill and get thrown away.
- Every HTTP request from a client must take 1 token to be allowed through.
- Tokens left? Go ahead and process it. Tokens gone? The request is rejected immediately with
429 Too Many Requests.
The nice part is that this algorithm is very friendly to bursts. If a client stays quiet for a few seconds, the bucket fills up. It can fire 10 requests in one millisecond without being rejected, as long as the long-term average stays inside the quota.
The trade-off is that you have to tune two parameters at once. Bucket size sets how large a burst you tolerate, refill rate sets how fast the quota comes back. Get either number slightly wrong and the limiter feels too loose or too harsh.
Leaky bucket, the one that smooths queues
Where Token Bucket governs the number of tokens, Leaky Bucket governs the outgoing rate of requests (throughput smoothing).
Think of a bucket with a small hole in the bottom.
- Client requests pour in from the top and land in a FIFO queue.
- Water drips out of the bottom hole at a steady rate, exactly 5 requests per second, however hard it pours in above.
- If the pour is heavy enough to overflow the bucket, the excess is discarded and those requests get
429.
The upside is that the flow becomes very stable (constant rate). That fits nicely in front of a service that is sensitive to sudden load, like a legacy banking payment system that cannot absorb a spike.
The downside is harsh: it tolerates no burst at all. Requests that are perfectly legitimate pick up latency because they have to wait in the buffer, even though your server could have served them.
Fixed window counter, simple but with a trap
This is the easiest algorithm, and the one junior developers write most often.
Time is cut into fixed windows, one minute each: 00:00-00:01, 00:01-00:02, and so on.
- Each request in that interval bumps a counter by 1.
- If the counter crosses the threshold (100 req/minute, say), later requests are rejected until the window turns over and the counter resets to 0.
The problem sits at the seam between windows. Assume a quota of 100 req/minute:
- A client fires 100 requests at second 00:59. All of them pass.
- The client fires 100 more at second 01:01. Those pass too, because the counter just reset.
The result: the server takes 200 requests in a 2-second span! A capacity you planned for a full minute is eaten in an instant. This is what people call a boundary spike, and during a flash sale it can take your backend down. 😅
Sliding window counter, accurate without wasting memory
To close the boundary spike gap without storing a log of every request (that is Sliding Window Log, and it eats memory), the industry moved to the Sliding Window Counter.
The idea: estimate the request count inside the current sliding window by folding in a proportion of the previous window.
An example, with a quota of 100 req/minute:
- The previous window (00:00-01:00) recorded 80 requests.
- It is now 01:15, so we are only 25% into the current window. The other 75% still hangs off the previous window.
- The current window already holds 30 new requests.
Estimated traffic in the last minute: 30 + (80 × 0.75) = 30 + 60 = 90 request.
Since 90 is still under 100, the request goes through.
This approach is very accurate, the boundary spike problem disappears, and it only needs two counter numbers per client. Compare that with Sliding Window Log, which has to store a timestamp per request — far more expensive.
So, are the differences starting to make sense? Not done yet, there is still a fun part left. 😎
When should you pick which?
| Algorithm | Burst Tolerance | Memory Efficiency | Complexity | Best Use Case |
|---|---|---|---|---|
| Token Bucket | ⭐⭐⭐ Very Good | ⭐⭐⭐ Very Light | Medium | Public API, SaaS Gateway, general REST API |
| Leaky Bucket | ❌ None (Smooth) | ⭐⭐ Moderate (Queue) | Medium | Queue in front of a third-party payment gateway |
| Fixed Window | ❌ Prone to Boundary Spikes | ⭐⭐⭐ Very Light | Very Easy | Coarse internal protection / cron jobs |
| Sliding Window | ⭐⭐ Good Enough | ⭐⭐⭐ Very Light | Medium | API with a per-hour or per-day quota and tight limits |
Practical implementation: token bucket with Redis and Lua
In a distributed microservices system you have to use a shared store like Redis so a client's quota stays in sync across every API Gateway instance.
To keep out race conditions, the whole check-and-take logic has to run atomically through a Lua Script. Two requests must never read a token at the same moment and both pass.
-- Redis Lua Script for Token Bucket
local key = KEYS[1]
local limit = tonumber(ARGV[1]) -- Bucket capacity (e.g. 10)
local current_time = tonumber(ARGV[2]) -- Current timestamp in seconds
local refill_rate = tonumber(ARGV[3]) -- Tokens per second (e.g. 2)
-- Fetch bucket data: [tokens, last_updated]
local data = redis.call("HMGET", key, "tokens", "last_updated")
local tokens = tonumber(data[1])
local last_updated = tonumber(data[2])
if tokens == nil then
tokens = limit
last_updated = current_time
else
-- Count the tokens added since the last request
local delta = math.max(0, current_time - last_updated)
tokens = math.min(limit, tokens + (delta * refill_rate))
last_updated = current_time
end
-- Check whether there are enough tokens
if tokens >= 1 then
tokens = tokens - 1
redis.call("HSET", key, "tokens", tokens, "last_updated", last_updated)
redis.call("EXPIRE", key, 3600) -- TTL of 1 hour
return 1 -- Allow the request
else
redis.call("HSET", key, "tokens", tokens, "last_updated", last_updated)
return 0 -- Reject the request (429)
end
The simple integration on the backend side (FastAPI / Python):
import time
import redis
from fastapi import FastAPI, HTTPException, Request
app = FastAPI()
r = redis.Redis(host="localhost", port=6379, db=0)
rate_limit_lua = r.register_script(open("token_bucket.lua").read()) # Load the Lua script into Redis
@app.middleware("http")
async def rate_limit_middleware(request: Request, call_next):
client_ip = request.client.host
key = f"rate_limit:{client_ip}"
# Capacity of 10 tokens, refill of 2 tokens per second
allowed = rate_limit_lua(keys=[key], args=[10, int(time.time()), 2])
if not allowed:
raise HTTPException(status_code=429, detail="Too Many Requests. Pelan-pelan ya!")
return await call_next(request)
So, which algorithm fits you?
In the end, no algorithm wins in every situation. Token Bucket takes first place for a public API because it is friendly to bursts. Leaky Bucket wins when you need a genuinely even flow. Fixed Window only fits coarse protection that does not need high precision. Sliding Window Counter is the most balanced compromise for tight per-hour or per-day quotas.
What matters most is that the quota arithmetic lives in a shared store and gets checked atomically. A rate limiter that miscounts because of a race condition is like a cashier counting money with their eyes closed: it looks like it works, but the balance has been wrong from the start.
Happy algorithm picking, and may your bucket never leak during peak hours! 👋