Rate Limiting Like a Jedi: Designing a Rate Limiter from Scratch

The Quest Begins (The "Why")

I still remember the night our API started throwing 429s like confetti at a parade. Users were complaining, the monitoring dashboard flashed red, and I felt like I was trying to bail out a sinking ship with a teaspoon. The problem? Our rate limiter was a naive fixed‑window counter that reset every minute. It allowed bursts that slammed our backend, then blocked legitimate traffic for the rest of the window — classic “all‑or‑nothing” behavior that made both power users and casual callers unhappy.

I dug into the logs and saw a pattern: spikes of traffic that lasted a few seconds, followed by lulls. The fixed window treated each second as if it were isolated, ignoring the recent history. I realized we needed something that could remember the recent request flow and allow short bursts while still enforcing a long‑term average. That was the dragon I had to slay: design a limiter that feels fair, smooth, and doesn’t punish honest users for occasional bursts.

The Revelation (The Insight)

The breakthrough came when I read about the token bucket algorithm. Imagine a bucket that leaks tokens at a steady rate — say, 10 tokens per second. Each incoming request must grab a token to proceed. If the bucket is full (holding up to a burst limit, e.g., 20 tokens), the request can consume a token immediately; otherwise it waits (or gets rejected) until enough tokens have refilled.

Why does this beat the fixed window?

• Burst tolerance – Users can spike up to the bucket size without being throttled.
• Smooth enforcement – Over any longer interval, the average rate can’t exceed the refill rate because tokens are only added at that pace.
• Simple state – We only need to store two numbers: the current token count and the last time we refilled.

The trade‑off is a tiny loss of precision: the refill happens lazily (only when we check), so the actual allowed rate can be slightly higher than the theoretical limit for a very short period after a long idle spell. In practice, that’s negligible and far outweighed by the gains in fairness and simplicity.

Here’s a quick ASCII picture of how the bucket works over time:

time --> 
|<--- refill rate (r) --->|
+------------------------+   <-- bucket capacity (B)
|                        |
|  tokens   * * * *      |   * = token present
|  --------->            |
|  consume   (request)   |
+------------------------+

When a request arrives, we:

1. Add tokens based on elapsed time since the last check (capped at B).
2. If tokens >= 1, consume one and allow the request.
3. Otherwise, reject or delay.

Wielding the Power (Code & Examples)

Let’s look at the before and after. First, the painful fixed‑window version (in Python‑like pseudocode):

# BEFORE: Fixed window counter – bursts break everything
class FixedWindowLimiter:
    def __init__(self, max_per_window, window_sec):
        self.max = max_per_window
        self.window = window_sec
        self.count = 0
        self.reset_time = time.time() + window_sec

    def allow(self):
        now = time.time()
        if now >= self.reset_time:          # window expired
            self.count = 0
            self.reset_time = now + self.window
        if self.count < self.max:
            self.count += 1
            return True
        return False                        # reject

The problem? If 100 requests hit in the first second of a 60‑second window with max_per_window=60, they all get through, then the next 59 seconds see zero allowed traffic — total chaos.

Now the token bucket implementation — our Jedi‑level lightsaber:

# AFTER: Token bucket – smooth, burst‑friendly
class TokenBucket:
    def __init__(self, rate, capacity):
        """
        rate    : tokens added per second (float)
        capacity: max tokens the bucket can hold (int/float)
        """
        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 time passed, but don't overflow
        self.tokens = min(self.capacity,
                          self.tokens + elapsed * self.rate)
        self.last_refill = now

    def allow(self, cost=1):
        self._refill()
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False

Why this feels like a win:

• Only two floats and a timestamp — minimal memory.
• The _refill method is called on every check, so we never need a background thread or a cron job.
• Bursts up to capacity are instantly allowed; after that, the outflow matches the refill rate.

Common traps to avoid (the “traps on the quest”):

1. Using int for tokens when your rate isn’t an integer divisor of a second — you’ll lose precision and either under‑ or over‑limit. Keep everything as floats (or use a fixed‑point library if you need deterministic behavior).
2. Forgetting to cap the token count after refilling. Without min(self.capacity, ...) the bucket can grow beyond its intended burst size, effectively disabling the limit during idle periods.

Why This New Power Matters

With the token bucket in place, our API went from “feast or famine” to a steady diet that still lets users indulge when they need to. Clients reported fewer 429 errors during traffic spikes, and our backend saw a smoother request distribution — CPU usage flattened, and we could right‑size our instances without over‑provisioning for worst‑case bursts.

The beauty of this design is its portability. Drop the same class into a Go microservice, a Node.js endpoint, or even a Lua script inside an NGINX access_by_lua_block. The core idea — track a leaking bucket of permissions — stays identical, and you only need to tweak the rate and capacity to match your SLA.

Imagine you’re building a gaming leaderboard API that must handle bursts when a new season drops, but also protect your database from a sudden surge of score submissions. A token bucket lets you grant that initial burst of excitement while keeping the long‑term flow healthy — no more frantic scaling scripts at 2 a.m.

Your Turn

Now that you’ve seen the token bucket in action, I challenge you to implement it in your favorite language and experiment with two knobs:

• Rate – how many requests per second you want to sustain.
• Capacity – how big a burst you’re willing to absorb.

Try logging the denied requests over a minute of synthetic traffic (e.g., a Poisson process) and watch how the bucket smooths things out. Share your results, tweak the numbers, and see how the limiter behaves under different workloads.

May your APIs stay balanced, your users stay happy, and your code feel as elegant as a lightsaber swing. Happy hacking! 🚀