Rate Limiting Like Gandalf: Building a Distributed Cache with Redis

The Quest Begins (The "Why")

Ever had your API melt down because a sudden traffic spike hammered every endpoint at once? I remember a late‑night deploy where our “simple” in‑process counter crashed under a flash sale, and the pager started singing like a busted karaoke machine. We needed a way to throttle requests without turning every service into a bottleneck or rewriting the whole stack.

The problem boiled down to: how do we share a counter across many instances, keep it fast, and survive node failures?

A naïve approach—each service keeps its own local counter—fails the moment you scale beyond one node. A centralized DB works but adds latency that kills throughput. Enter Redis: an in‑memory key‑value store that can be replicated, clustered, and accessed with sub‑millisecond latency. It felt like discovering a hidden armory in a dungeon—suddenly we had the right tool for the job.

The Revelation (The Insight)

The magic insight is decoupling the rate‑limit decision from the storage mechanism by using a token bucket algorithm implemented with a single Redis key per client (or IP, or API key).

Here’s why this beats the usual alternatives:

Approach	Pros	Cons
Local in‑memory counter	Zero network latency	No shared state → limits are per‑instance, easy to bypass
Central SQL/NoSQL DB	Strong consistency	Higher latency, more operational overhead
Redis + Lua script	Atomic increment & expiry, O(1) time, built‑in TTL for auto‑cleanup	Requires Redis cluster, but that’s a solved problem for most teams

The critical insight is that we can let Redis do the heavy lifting atomically with a Lua script, so we never read‑modify‑write in two steps (which would invite race conditions). The script returns the current token count and, if allowed, decrements it—all in one round trip.

ASCII diagram of the flow

+----------------+      Lua Script (EVAL)      +----------------+
|  Service A     |  --------------------->    |   Redis Cluster  |
|  (or B, C…)   |  <--------------------     |   (key: bucket) |
+----------------+      (INCR + EXPIRE)       +----------------+
        |                                               |
        |  Decision: allow/deny based on tokens       |
        v                                               v
+----------------+                               +----------------+
|  HTTP Response |                               |  TTL refresh   |
+----------------+                               +----------------+

The bucket key holds two fields: tokens (remaining permits) and timestamp (last refill). On each request we:

1. Refill tokens based on elapsed time (now - last_refill).
2. Cap at the max bucket size.
3. If tokens >= 1, consume one and reply 200.
4. Else reply 429 Too Many Requests.

All of this happens inside Redis, guaranteeing that two concurrent requests can’t both see the same token count and both slip through.

Wielding the Power (Code & Examples)

The Struggle (Before)

# Bad: naive per‑process counter (race condition city)
import time
from flask import Flask, request, abort

app = Flask(__name__)
counter = 0          # ← only one process sees this
LIMIT = 100          # requests per minute
WINDOW = 60          # seconds

@app.before_request
def limit():
    global counter
    now = time.time()
    if not hasattr(limit, "reset"):
        limit.reset = now
        counter = 0
    if now - limit.reset > WINDOW:
        limit.reset = now
        counter = 0
    if counter >= LIMIT:
        abort(429)
    counter += 1

What’s wrong? If you run three Gunicorn workers, each gets its own counter. Three workers × 100 = 300 effective limit—your rate limit is basically useless. Plus, the global variable isn’t safe across threads or processes.

The Victory (After)

We’ll use the redis-py client and a Lua script that does the token‑bucket math atomically.

import time
import redis
from flask import Flask, request, abort

app = Flask(__name__)
r = redis.Redis(host='redis-cluster', port=6379, decode_responses=True)

# Lua script stored as a string; we'll load it once at startup
LUASCRIPT = """
local key = KEYS[1]
local limit = tonumber(ARGV[1])   -- max tokens
local refill_rate = tonumber(ARGV[2])  -- tokens per second
local now = tonumber(ARGV[3])

local bucket = rcall('HMGET', key, 'tokens', 'timestamp')
local tokens = tonumber(bucket[1]) or limit
local last = tonumber(bucket[2]) or now

-- refill
local delta = math.max(0, now - last)
tokens = math.min(limit, tokens + delta * refill_rate)

local allowed = 0
if tokens >= 1 then
    tokens = tokens - 1
    allowed = 1
end

rcall('HMSET', key, 'tokens', tokens, 'timestamp', now)
rcall('EXPIRE', key, math.ceil(limit / refill_rate) + 5)  -- auto‑clean
return allowed
"""

# Register the script (returns a SHA we can call with EVALSHA)
SCRIPT_SHA = r.script_load(LUASCRIPT)

def allow_request(client_id: str, limit: int = 100, per_seconds: int = 60) -> bool:
    """Return True if request is allowed, False otherwise."""
    key = f"rate_limit:{client_id}"
    now = time.time()
    refill_rate = limit / per_seconds  # tokens per second
    # EVALSHA returns 1 (allowed) or 0 (denied)
    result = r.evalsha(SCRIPT_SHA, 1, key, limit, refill_rate, now)
    return bool(result)

@app.before_request
def enforce_limit():
    # Use IP or API key as the client identifier
    client_id = request.remote_addr  # or request.headers.get('X-API-Key')
    if not allow_request(client_id, limit=100, per_seconds=60):
        abort(429)

@app.route('/api/hello')
def hello():
    return {"msg": "Hello, traveler!"}

What changed?

• We moved state to Redis, so every service instance sees the same bucket.
• The Lua script guarantees the read‑modify‑write cycle is atomic—no race conditions even under thousands of concurrent requests.
• Keys auto‑expire (EXPIRE) after a bit of idle time, keeping memory usage bounded.

Common Traps to Avoid

1. Using GET/SET separately – If you fetch the token count, then decrement it in a second command, two threads can interleave and both think they have a token. Always wrap the logic in a Lua script (or use Redis’ INCRBY with a custom TTL trick, but Lua is clearer).
2. Forgetting to set an expiration – Without EXPIRE, idle clients will linger forever, wasting memory. A short TTL (a few multiples of the refill interval) lets Redis reclaim keys automatically.

Why This New Power Matters

Now you can drop this snippet into any service—Flask, FastAPI, Node.js, Go—and instantly get a globally consistent rate limiter that scales horizontally with your Redis cluster. No more per‑instance guesswork, no more surprise 429s during a flash sale, and no extra latency that makes users feel like they’re stuck in a loading screen.

You’ve turned a flimsy, local counter into a resilient, shared guardrail—think of it as giving your API a magical shield that only lets through the worthy adventurers.

Your Turn

Grab a Redis instance (even a free tier on Redis Cloud works), copy the Lua script above, and try limiting a public endpoint with a different algorithm—maybe a fixed‑window counter or a sliding‑window log. Compare latency, memory usage, and ease of tuning. Share your findings in the comments; I’d love to hear what quest you embark on next!

Happy coding, and may your rate limits always be just right. 🚀