Rate Limiting Like a Boss: Lessons from The Avengers

The Quest Begins (The "Why")

I was building a tiny internal API for a side‑project—a joke‑of‑the‑day service that pulled memes from a public feed and served them to a Slack bot. Everything worked fine locally, but the first time I pushed it to a cheap VPS and let a few friends hammer it with curl loops, the service started returning 500s like confetti at a New Year’s parade. My little server was getting DDoS‑ed by my own test script.

Honestly, I felt like I’d just walked into a boss fight without a health bar. The API was wide open, and I had no idea how to tell the difference between a genuine user and a rogue script. I needed a way to say, “Hey, you can only knock on this door three times per minute, otherwise you’re getting a polite 429.” That’s when the quest for a rate limiter began.

The Revelation (The Insight)

After a couple of sleepless nights scrolling through Stack Overflow, I realized the problem wasn’t whether to limit traffic—it was how to do it without introducing a new bottleneck or a race condition that would make things worse. The classic fixed‑window counter (e.g., “count requests in the last 60 seconds”) looks simple, but it suffers from the “burst at the edge” problem: if a client makes 59 requests at 0:59 and another 59 at 1:01, they’ve effectively sent 118 requests in a 2‑second span—double the intended limit.

The insight that changed everything was adopting a token bucket algorithm. Imagine a bucket that leaks tokens at a steady rate (the refill rate) and can hold a maximum number of tokens (the burst capacity). Each incoming request tries to consume a token; if there’s none, the request is rejected. The beauty is that the bucket smooths out bursts while still allowing short spikes up to its capacity.

Here’s a quick ASCII picture to make it concrete:

+-------------------+
|   Token Bucket    |
|  (capacity = 10)  |
+--------+----------+
         |
         v   (consume 1 token per request)
+--------+----------+
|   Request Handler |
+-------------------+
         |
         v   (if token available → proceed)
+-------------------+
|   Your API Logic  |
+-------------------+

Refill process (runs every second):
+-------------------+
|   Add refill_rate |
|   tokens (capped) |
+-------------------+

The trade‑off? We need a place to store the bucket state that multiple workers can update atomically. For a single‑process app, a simple mutex works; for a distributed service, Redis’ INCRBY and EXPIRE commands give us a lock‑free, O(1) solution.

Compared to the fixed window, the token bucket eliminates the edge‑burst problem and lets us tune burstiness independently from the sustained rate. Compared to a sliding window log (which keeps timestamps for every request), it’s far lighter on memory—we only store two integers per key (tokens and last‑refill timestamp).

Wielding the Power (Code & Examples)

The Struggle: Naïve Fixed Window (the “trap”)

Here’s what my first attempt looked like in Python. It seemed fine until I ran a quick benchmark with ab (ApacheBench) and saw the request count spike past the limit every minute.

# BEFORE: broken fixed‑window limiter
import time
from threading import Lock

class FixedWindowLimiter:
    def __init__(self, max_requests: int, window_sec: int):
        self.max_requests = max_requests
        self.window_sec = window_sec
        self.hits = 0
        self.window_start = time.time()
        self.lock = Lock()

    def allow(self) -> bool:
        now = time.time()
        with self.lock:
            # reset window if we've passed the boundary
            if now - self.window_start >= self.window_sec:
                self.hits = 0
                self.window_start = now
            if self.hits < self.max_requests:
                self.hits += 1
                return True
            return False

Why it’s a trap: The if now - self.window_start >= self.window_sec: check and the reset are not atomic with the increment. Two threads can slip through the reset at the same moment, both see hits == 0, and both increment, briefly exceeding the limit. Under load, this leads to the dreaded “burst at the edge” we talked about.

The Victory: Token Bucket with Redis (the “spell”)

Switching to a token bucket cleared the fog. The implementation below uses Redis as the single source of truth. The Lua script guarantees that the read‑modify‑write of tokens and timestamp happens atomically—no race conditions, no extra locks.

# AFTER: Redis‑backed token bucket limiter
import time
import redis

REDIS_URL = "redis://localhost:6379/0"
r = redis.from_url(REDIS_URL)

# Lua script that runs atomically inside Redis
LUA_SCRIPT = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])   -- tokens per second
local now = tonumber(ARGV[3])

local bucket = rcall('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(bucket[1]) or capacity
local last_refill = tonumber(bucket[2]) or now

-- refill based on elapsed time
local elapsed = now - last_refill
tokens = math.min(capacity, tokens + elapsed * refill_rate)

if tokens >= 1 then
    tokens = tokens - 1
    rcall('HMSET', key, 'tokens', tokens, 'last_refill', now)
    rcall('EXPIRE', key, math.ceil(capacity / refill_rate) + 5)
    return 1   -- allowed
else
    rcall('HMSET', key, 'tokens', tokens, 'last_refill', now)
    return 0   -- rate limited
"""
allow_script = r.register_script(LUA_SCRIPT)

def allow_request(user_id: str, max_per_minute: int, burst: int) -> bool:
    """
    Returns True if the request is allowed.
    max_per_minute: sustained rate (e.g., 60)
    burst: max tokens the bucket can hold (e.g., 10)
    """
    key = f"rate_limit:{user_id}"
    capacity = burst
    refill_rate = max_per_minute / 60.0   # tokens per second
    now = time.time()
    allowed = allow_script(
        keys=[key],
        args=[capacity, refill_rate, now]
    )
    return bool(allowed)

What makes this shine?

• Atomicity: The Lua script runs as a single Redis command, so there’s no window where two threads can both read the same token count and both decrement it.
• Efficiency: Only two fields (tokens and last_refill) are stored per user—constant memory.
• Flexibility: Adjust capacity for burst tolerance and refill_rate for the sustained limit without touching the core logic.
• Graceful expiration: The EXPIRE call automatically cleans old keys after they’re idle, preventing Redis from growing forever.

Common Pitfalls to Avoid

1. Forgetting to refill based on elapsed time – If you just add a fixed amount per request, you’ll either starve the bucket or let it overflow.
2. Using a non‑atomic GET/SET pair – This re‑introduces the race condition we fought so hard to escape. Always wrap the logic in a Lua script (or use Redis’ EVALSHA).
3. Picking a ridiculously low EXPIRE – If the bucket expires before the next refill, legitimate traffic gets cut off. Set the TTL to a few multiples of capacity / refill_rate.

Why This New Power Matters

Now that I’ve got this token‑bucket limiter in my toolbox, I can throw it onto any service—REST APIs, WebSocket gateways, even internal micro‑service calls—without worrying about a sudden traffic spike blowing up my instances. The API stays responsive, my monitoring charts stay sane, and I get to sleep at night knowing that a rogue script won’t turn my side‑project into a costly cloud bill.

It’s also a fantastic interview topic. When I explain the token bucket, I get to show off my grasp of concurrency, distributed systems, and a little bit of Redis wizardry—all while drawing that simple bucket diagram on a whiteboard. Pretty cool, right?

Your Turn

Grab a language of choice, spin up a local Redis instance, and try implementing the token bucket yourself. Start with a naïve fixed‑window version, feel the pain, then replace it with the atomic Lua script. Share your results, tweak the burst vs. rate parameters, and see how the behavior changes under load.

What’s the craziest traffic pattern you’ve ever had to tame? Drop a comment below—I’d love to hear your war stories and maybe swap a few war‑tales over a virtual coffee. Happy limiting!