Designing a Rate Limiter: Lessons from The Matrix

#systemdesign #architecture #backend #programming

The Quest Begins (The "Why")

Honestly, I was staring at a production alert at 2 a.m. that screamed “Too many requests!” – our shiny new API was getting hammered by a rogue script, and the whole service started to lag like a character stuck in loading screen. I’d thrown together a quick fix: every incoming request dropped its timestamp into an in‑memory array, and we’d just prune entries older than a minute. It seemed to work on my laptop, but in the real world the array grew without bound, ate up RAM, and eventually caused the node to crash. I felt like Neo dodging bullets, except the bullets were my own bad code, and I was definitely not in slow‑motion.

That night I asked myself: What’s the minimal, correct way to protect a service without turning my server into a memory hog? The answer led me down the rabbit hole of rate limiting algorithms, and the one that clicked was the token bucket. It’s simple, bounded, and gives you that sweet spot between strictness and flexibility that most naive implementations miss.

The Revelation (The Insight)

Here’s the thing: a rate limiter isn’t about counting every single request; it’s about allowing a burst of traffic up to a limit, then draining at a steady rate. Think of a bucket that leaks water at a constant pace. You can pour a burst of water in (allowing spikes), but if you pour too fast, the bucket overflows and excess water is lost (requests are rejected). The magic is that the bucket never grows beyond its capacity – memory usage stays constant.

Why does this beat the naive “store‑every‑timestamp” approach?

Approach	Memory	Burst handling	Complexity
Timestamp list	O(N) – grows with traffic	Poor (needs pruning)	High (cleanup logic)
Fixed window counter	O(1)	Poor – allows bursts at window edges	Low
Token bucket	O(1)	Excellent – native burst support	Low‑medium

The token bucket gives you a deterministic upper bound on memory (just two numbers: current tokens and last refill timestamp) while still letting you accommodate realistic traffic spikes – exactly what you need for APIs, webhooks, or any public endpoint.

Below is an ASCII diagram that shows how the bucket works over time:

time →
|<--- refill interval --->|
   +--------+   +--------+   +--------+
   |        |   |        |   |        |
---|  ● ● ● |---|  ● ●   |---|  ●     |---   (● = token)
   |        |   |        |   |        |
   +--------+   +--------+   +--------+
   ^refill   ^consume   ^refill

Every refill_interval we add refill_amount tokens (up to capacity). When a request arrives, we try to consume one token; if none are available, we reject.

Wielding the Power (Code & Examples)

The Struggle (Before)

// Naïve in‑memory timestamp array – DON’T DO THIS IN PROD
let timestamps = [];

function allowRequest() {
  const now = Date.now();
  timestamps = timestamps.filter(t => now - t < 60_000); // keep last minute
  timestamps.push(now);
  return timestamps.length <= 100; // arbitrary limit
}

Problems:

timestamps can grow to millions of entries during a spike.
Filtering on every request is O(N).
No built‑in burst handling – a sudden surge either gets all through or all blocked, depending on the filter window.

The Victory (After) – Token Bucket in Node.js

// Simple, production‑ready token bucket (single‑process)
// For distributed systems you’d back this with Redis or a similar store.
class TokenBucket {
  constructor(capacity, refillPerSec) {
    this.capacity = capacity;          // max tokens
    this.tokens = capacity;            // start full
    this.refillPerSec = refillPerSec;  // tokens added each second
    this.lastRefill = Date.now();
  }

  _refill() {
    const now = Date.now();
    const delta = (now - this.lastRefill) / 1000; // seconds passed
    const added = delta * this.refillPerSec;
    this.tokens = Math.min(this.capacity, this.tokens + added);
    this.lastRefill = now;
  }

  allow() {
    this._refill();
    if (this.tokens >= 1) {
      this.tokens -= 1;
      return true;
    }
    return false;
  }
}

// Usage
const limiter = new TokenBucket({ capacity: 10, refillPerSec: 2 }); // 10 burst, 2 req/s steady

function handler(req, res) {
  if (!limiter.allow()) {
    return res.status(429).send('Too Many Requests');
  }
  // …process request
}

Why this works:

Memory stays at two numbers (tokens, lastRefill).
_refill() is O(1) – just a time diff and a multiplication.
The bucket naturally absorbs bursts up to capacity while throttling long‑term average to refillPerSec.

Common traps to avoid:

Forgetting to cap tokens at capacity – otherwise a long idle period can overflow the bucket, letting a huge burst through later.
Using floating‑point math for token counts in high‑throughput scenarios – can cause drift; either use integers (refill in fixed‑point) or a library that handles it.
Assuming this works across multiple nodes without coordination – a single‑process bucket is great for a single instance, but for a cluster you need a shared store (Redis Lua script, etc.). The algorithm itself stays the same; only the storage changes.

Why This New Power Matters

Now you can slap a rate limiter onto any endpoint with confidence that it won’t melt your server under a flash crowd, and you’ll still let legitimate users experience those natural spikes (think of a user rapidly clicking a “like” button or a mobile app retrying after a flaky network). The trade‑off is tiny: you give up the exact‑request‑count granularity of a timestamp list for constant memory and predictable performance – a bargain any sane engineer would take.

Imagine you’re building a micro‑service gateway: each route gets its own TokenBucket tuned to its SLA. You can even expose the bucket’s state via metrics (tokens_available, refill_rate) to auto‑scale or alert when you’re constantly hitting the limit. It’s the kind of tool that turns a frantic 2 a.m. firefight into a calm, “hey, the system’s handling it” moment.

Your Turn

Grab a language you love, implement a token bucket (or adapt the snippet above), and plug it into a route you’ve been worried about. Try tweaking capacity and refillPerSec to see how the bucket absorbs bursts versus smoothing traffic. When you see those 429 responses appear exactly when you expect them, you’ll feel like you’ve just leveled up your backend wizardry.

What’s the first endpoint you’ll protect with a token bucket? Drop your experiments in the comments – I’d love to hear how it went! 🚀

DEV Community