Designing a Distributed Rate Limiter: The Matrix

The Quest Begins (The "Why")

Hey friend, picture this: you’ve just shipped a shiny new API that lets users upload photos. Everything’s going great until a sudden surge of traffic hits—think Black Friday meets a flash mob. Suddenly, a few noisy clients start hammering the endpoint, and your servers start sweating. You scramble to add a rate limiter, slap a simple INCR on a Redis key per user, and call it a day.

But then you notice the weird spikes: sometimes a user gets through with double the allowed requests, other times they’re blocked too early. You dig into the logs and realize the classic race‑condition bug: two requests read the same counter, both increment, and both write back, blowing past your limit. It’s like trying to catch smoke with your bare hands—frustrating and futile.

That moment was my “aha!”—I needed a limiter that could make the decision atomically across a distributed system, without turning my Redis instance into a bottleneck. The quest for a robust, sliding‑window rate limiter began.

The Revelation (The Insight)

The breakthrough came when I stopped thinking about the limiter as a bunch of independent counters and started seeing it as a time‑ordered list of events stored in a Redis sorted set. Each request adds a timestamp (the score) to a set keyed by the user ID. Then, before granting the request, I simply trim the set to keep only timestamps that fall inside the sliding window (e.g., the last 60 seconds) and count what remains.

If the count is below the threshold, the request is allowed; otherwise, it’s rejected. Because all of this happens inside a single Lua script executed with EVAL, Redis guarantees atomicity—no two requests can interleave and corrupt the window.

Here’s the mental model:

user:<id>  -->  ZSET  (score = unix time in ms, value = unique request id)

When a request arrives:

1. Add current time as a new member to the ZSET.
2. Remove all members with score < now - window_size.
3. ZCARD the set → current request count.
4. Compare to limit → allow/deny.

The beauty? No lock juggling, no external coordination, and the data self‑expires because old timestamps are stripped each call. Memory usage stays bounded by limit * window_size (roughly), which is predictable and easy to size.

Trade‑offs vs. Other Designs

Approach	Pros	Cons
Simple INCR + TTL	Super easy, O(1) per call	Race condition → inaccurate limits; needs extra locking
Fixed‑window counter	Easy to reason about	“Burst at edge” problem – can allow up to 2× limit per window
Token bucket (lazy)	Smooth traffic shaping	Requires background refill or complex scripts; drift risk
Sliding‑window ZSET	Accurate, atomic, self‑cleaning	Slightly higher CPU (ZREM + ZCARD) but still O(log N)

In practice, the extra logarithmic cost is negligible compared to the network round‑trip you already pay for talking to Redis. And the accuracy gain—no more “lucky” bursts—means your downstream services stay sane under load.

Wielding the Power (Code & Examples)

The Struggle: Naïve Per‑Key Counter

# WARNING: This version has a race condition!
def allow_request_naive(user_id, limit=100, window_sec=60):
    key = f"rl:{user_id}"
    current = redis.incr(key)          # increment
    if current == 1:                   # first hit in this window
        redis.expire(key, window_sec) # set TTL
    return current <= limit

If two requests hit incr at almost the same time, both may see the same current value before the expiration is set, letting them both slip through.

The Victory: Atomic Sliding‑Window Lua Script

Save this script as rate_limiter.lua and load it once with SCRIPT LOAD (or just EVAL it each time if you prefer simplicity).

-- rate_limiter.lua
-- KEYS[1] = Redis key for the user, e.g., "rl:user_id"
-- ARGV[1] = now in milliseconds
-- ARGV[2] = window size in milliseconds
-- ARGV[3] = limit (max requests allowed)

local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])

-- Add current request timestamp
redis.call('ZADD', KEYS[1], now, now)

-- Remove timestamps outside the sliding window
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)

-- Count remaining requests
local current = redis.call('ZCARD', KEYS[1])

if current <= limit then
    return 1   -- allowed
else
    return 0   -- denied
end

Using it from Python (or any client):

def allow_request(user_id, limit=100, window_sec=60):
    lua = redis.register_script(open('rate_limiter.lua').read())
    key = f"rl:{user_id}"
    now_ms = int(time.time() * 1000)
    window_ms = window_sec * 1000
    allowed = lua(keys=[key], args=[now_ms, window_ms, limit])
    return bool(allowed)

Common Traps to Avoid

1. Forgetting to trim old entries – If you only ZADD without ZREMRANGEBYSCORE, the set grows forever, eating memory.
2. Using separate GET/SET calls – That re‑introduces the race condition; the Lua script must be one atomic operation.
3. Choosing a too‑granular timestamp – Millisecond precision is fine for most APIs; microsecond precision just bloats the set without real benefit.

Give it a spin with a quick benchmark:

# Simulate 10k requests from 100 users, limit 5/sec
hey -z 10s -c 50 -m POST http://localhost:8000/upload

You’ll see the request count hover tightly around the limit, with virtually no overshoot—thanks to that sweet, atomic sliding window.

Why This New Power Matters

Now you’ve got a limiter that behaves like a vigilant bouncer at an exclusive club: it lets in exactly the right number of guests, no more, no less, even when the line gets crazy long. Because the logic lives inside Redis, you can drop it into any service—Go, Node, Java, Ruby—without rewriting the core algorithm.

Imagine scaling your API to thousands of instances behind a load balancer; each instance talks to the same Redis cluster, and the limiter stays consistent. No more painful “sharding the counter” headaches, no extra consensus protocols, just a simple sorted set and a Lua script.

The payoff? Predictable latency, protected downstream services, and the peace of mind to ship features knowing you won’t be DOS‑ed by a stray script or an enthusiastic user.

Your Turn

Grab the script, plug it into your service, and watch the magic. Try tweaking the window size or swapping the sorted set for a hybrid approach (e.g., combine with a token bucket for smoother burst handling). And if you hit a snag—don’t sweat it; that’s just part of the quest.

What’s the next system you’ll tame with a similar “ordered‑set + atomic script” trick? Drop your ideas in the comments—I’d love to hear how you’re pushing the limits!

---

P.S. Writing this felt like dodging bullets in *The Matrix—except instead of avoiding agents, I was avoiding race conditions. 🚀*