The Rate Limiter Strikes Back: Designing a Token Bucket from Scratch

The Quest Begins (The "Why")

I still remember the first time our API started choking under a sudden traffic spike. It was a Friday afternoon, the kind where you’re just about to log off, and the monitoring dashboard lit up like a Christmas tree. Requests were piling up, latency shot through the roof, and our users began seeing those dreaded “429 Too Many Requests” errors.

We had a naive rate limiter in place—a simple fixed‑window counter that reset every minute. It worked fine when traffic was steady, but as soon as a burst hit, the counter would either let too many through (because we hadn’t hit the limit yet) or block everything for the whole minute (because we’d already exhausted the quota). It felt like trying to hold back a tsunami with a sandbag.

Honestly, I was frustrated. I knew there had to be a smarter way to smooth out those bursts without penalizing honest users or over‑protecting the system. That’s when I dove into the world of rate‑limiting algorithms, and the token bucket caught my eye like a shiny loot drop in a dungeon.

The Revelation (The Insight)

The token bucket is deceptively simple, yet it solves the exact pain points we were experiencing. Imagine a bucket that holds a fixed number of tokens. Tokens drip into the bucket at a steady rate (say, 10 tokens per second). Each incoming request consumes a token. If the bucket is empty, the request is denied or delayed; if there’s a token, the request proceeds and the token is removed.

Why does this beat the fixed‑window counter?

1. Burst tolerance – The bucket can store up to its capacity, allowing a short burst of requests up to that limit without waiting for the next window.
2. Smooth throttling – Because tokens are added continuously, the limiter adapts to the actual request rate rather than resetting abruptly at arbitrary intervals.
3. Memory‑light – We only need to track two numbers: the current token count and the last time we refilled the bucket. No arrays of timestamps per key.

Here’s a quick ASCII sketch to visualize the flow:

+-------------------+      +-------------------+
|   IncomingReq    | ---> |  Token Bucket?    |
+-------------------+      +-------------------+
          |                         |
   (if token)                     | (no token)
          v                         v
+-------------------+      +-------------------+
|   Process Request|      |   Reject/Delay    |
+-------------------+      +-------------------+
          |
          v
   (remove token)

The magic is that the bucket refills while we’re processing, so if traffic slows down, tokens accumulate again, ready for the next burst. It’s like having a mana pool that regenerates over time—perfect for handling those “just‑in‑case” spikes without over‑engineering.

I was shocked at how elegant it felt. After a few hours of sketching on a whiteboard, the algorithm clicked, and I felt like I’d uncovered a secret spell that made the server breathe easier.

Wielding the Power (Code & Examples)

Let’s go from the painful fixed‑window approach to a clean token‑bucket implementation. I’ll use Python because it’s easy to read, but the idea translates to any language.

The Struggle: Fixed‑Window Counter (the “before”)

import time
from collections import defaultdict

class FixedWindowLimiter:
    def __init__(self, max_requests: int, window_sec: int):
        self.max_requests = max_requests
        self.window_sec = window_sec
        self.hits = defaultdict(int)      # key → count
        self.reset_time = defaultdict(int)  # key → window start

    def allow(self, key: str) -> bool:
        now = int(time.time())
        window_start = (now // self.window_sec) * self.window_sec

        # Reset counter if we moved to a new window
        if self.reset_time[key] != window_start:
            self.hits[key] = 0
            self.reset_time[key] = window_start

        if self.hits[key] >= self.max_requests:
            return False   # reject

        self.hits[key] += 1
        return True        # allow

Pros: Simple to understand.

Cons:

• At the edge of a window, a burst can let through up to 2 * max_requests (the tail of the old window + the head of the new).
• After a burst, the limiter stays silent for the whole remaining window, even if traffic drops.

The Victory: Token Bucket (the “after”)

import time
import math

class TokenBucket:
    def __init__(self, rate: float, capacity: int):
        """
        rate    – tokens added per second (e.g., 10.0)
        capacity – max tokens the bucket can hold (burst size)
        """
        self.rate = rate
        self.capacity = capacity
        self.tokens = capacity          # start full
        self.last_refill = time.time()

    def _refill(self):
        now = time.time()
        elapsed = now - self.last_refill
        # Add tokens based on elapsed time, but don't exceed capacity
        new_tokens = elapsed * self.rate
        self.tokens = min(self.capacity, self.tokens + new_tokens)
        self.last_refill = now

    def allow(self, key: str = "default") -> bool:
        self._refill()
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

What changed?

• We keep a floating‑point token count that gets topped up continuously.
• The allow method first refills based on real elapsed time, then checks if we have at least one token.
• No per‑window reset logic, no arrays of timestamps—just two scalars per key.

Using the limiter

limiter = TokenBucket(rate=5.0, capacity=10)   # 5 req/sec, bursts up to 10

def handle_request():
    if limiter.allow():
        process()          # your actual work
    else:
        return TooManyRequests()

Common Pitfalls (the “traps”)

1. Integer division for refill – If you compute new_tokens = int(elapsed) * rate, you lose fractional tokens and the limiter becomes overly strict. Keep the math in floats (or use a high‑resolution fixed‑point).
2. Not capping the bucket – Forgetting min(self.capacity, …) lets the token count grow unbounded during idle periods, which can cause a massive burst when traffic spikes again.
3. Using a shared mutable state without locks – In a multi‑process or multi‑threaded service, you need either a thread‑safe structure (like threading.Lock) or an external store (Redis) that supports atomic operations.

I spent a solid afternoon debugging the first version because I’d accidentally used int(elapsed) and wondered why the limiter seemed to reject legitimate traffic after a few seconds of low load. Fixing that was a “wait, that’s it?” moment—pure relief.

Why This New Power Matters

Switching to a token bucket transformed how our service behaved under load:

• Burst‑friendly – Legitimate spikes (like a user refreshing a page or a batch job kicking off) are absorbed without hurting latency.
• Fair & smooth – Traffic shaping is gradual; we avoid the “all‑or‑nothing” cliff of fixed windows.
• Operational simplicity – With just two numbers per key, monitoring and debugging become trivial. You can even expose the current token count as a metric for autoscaling decisions.

The best part? The algorithm scales horizontally. Throw a Redis-backed token bucket behind a load balancer, and you get a distributed rate limiter that’s still lightweight enough for high‑throughput services.

If you’re building APIs, webhooks, or any service that needs to protect itself from abusive or unpredictable traffic, the token bucket is a tool worth keeping in your belt. It’s the kind of solution that, once you see it, makes you wonder how you ever lived without it.

---

Your Turn

Try implementing a token bucket for a side project—maybe a simple Flask endpoint that limits login attempts. Play with the rate and capacity values to see how they affect burst handling.

What trade‑offs did you notice when you tweaked those numbers? Did you hit any surprising edge cases? Share your findings in the comments—I’d love to hear how your own quest went!

Happy rate‑limiting! 🚀