Dev

Your Rate Limiter Is Lying To You

Most rate limiters fail under the exact conditions they exist to prevent. Here's what actually happens at 50k RPS when your Redis cluster hiccups, and why the algorithm you chose in 2019 is probably wrong for 2024.

The Night Our Rate Limiter Made Things Worse

In 2021, my team at a fintech with 8M daily active users watched our rate limiter cause a cascade failure during a traffic spike. The irony was perfect. We'd built rate limiting specifically to survive traffic spikes. The fix cost us 11 days of engineering time and roughly $340k in incident costs, SLA credits, and emergency infrastructure. The root cause? We'd picked the wrong algorithm for our traffic shape, and we didn't know it until production told us violently.

Let me save you that lesson.

Fixed Window Is Almost Always Wrong

Here's the algorithm most tutorials teach:

if redis.incr(f"{user_id}:{current_minute}") > limit:
    return 429

It's simple. It's fast. It's broken in a specific, nasty way called the boundary problem. A user can send limit requests at 11:59:59 and another limit requests at 12:00:00. You've just allowed 2x your intended limit in two seconds. At 50k RPS, that two-second window is enough to take down an unprotected downstream service.

The fix everyone reaches for is sliding window. But the naive Redis sliding window using sorted sets — storing a timestamp per request — costs O(log N) per operation and O(N) memory per user. At scale, that's a Redis memory problem waiting to happen.

Token Bucket Is What You Actually Want

Token bucket is the algorithm that's been quietly running inside every serious API gateway for 20 years. The intuition: imagine each user has a bucket that holds capacity tokens. Tokens refill at rate r tokens per second. Each request consumes one token. No tokens? 429.

The math that makes this work in Redis without storing per-request timestamps:

now = time.time()
last_refill, tokens = redis.hmget(key, "ts", "tokens")
elapsed = now - float(last_refill)
new_tokens = min(capacity, float(tokens) + elapsed * refill_rate)
if new_tokens >= 1:
    redis.hset(key, {"ts": now, "tokens": new_tokens - 1})
    return ALLOW
return DENY

Two fields in a hash. Constant space per user. Constant time per check. The refill is computed lazily on each request, so you're never running background jobs to top up buckets. This is how Kong, Nginx's limit_req module, and AWS API Gateway all do it under the hood.

The Distributed Problem Nobody Talks About

Here's where people get overconfident. The Lua script above is atomic on a single Redis node. But your Redis is probably a cluster, and your user ID is probably hashing to different nodes across requests during a resharding event or a failover. I've seen this cause a 3x effective rate limit for 90 seconds during a Redis Cluster rebalance, because each node thought the user had a fresh bucket.

Two real options. First: pin users to nodes deterministically and accept that a node failure means some users get a temporary free pass — usually acceptable. Second: use Redis with Redlock across three nodes, accept the 3-5ms latency hit, and sleep better. Cloudflare published a detailed breakdown in 2022 of why they abandoned centralized rate limiting entirely for edge-local approximate counting with periodic sync. For most companies, that's overengineering. For Cloudflare, it's existential.

The Header Nobody Sends Correctly

RFC 6585 defined 429 in 2012. In 2024, I still see APIs return 429 with no Retry-After header, which means every client immediately retries, which means your rate limiter just created a retry storm. Always send Retry-After in seconds. Always send X-RateLimit-Remaining and X-RateLimit-Reset. Clients that respect these headers will back off. Clients that don't are someone else's problem, and you can now identify them in Datadog by filtering for 429s with no subsequent pause in requests.

The algorithm choice is 20% of the problem. Observability, client behavior, and failure modes are the other 80%. Ship the Lua script. Instrument everything. Then fix what production breaks.

OPEN IN REEDL_ FEED →← Back to feed