Designing a Distributed Rate Limiter: A Token Bucket Approach

The Necessity of Rate Limiting in System Design

Rate limiting is a fundamental architectural pattern for ensuring the stability and availability of services, especially those exposed to unpredictable external traffic. Without it, even simple services like a URL shortener can easily succumb to accidental spikes, malicious attacks, or even a runaway script, leading to resource exhaustion, increased latency, and outright service downtime. The core problem isn't always the application logic or storage, but the inability to control the ingress rate of requests.

Protecting Resources with API-Layer Throttling

A key insight in designing an effective rate limiter is to protect the underlying resources (like databases or computation services) by throttling requests at the API layer, _before_ they consume significant downstream resources. This approach allows the system to gracefully reject requests with a `429 Too Many Requests` status, preventing cascading failures and ensuring the core services remain operational. The trade-off is introducing a small amount of state at the API gateway or service entry point.

Token Bucket Algorithm for Flexible Rate Limiting

The token bucket algorithm is a popular choice for rate limiting due to its ability to handle bursts while maintaining a steady average rate. Each client (identified by IP or API key) is allocated a virtual 'bucket' of tokens. Requests consume tokens, and tokens are refilled at a constant rate up to a maximum bucket size. If a client's bucket is empty, new requests are rejected. This contrasts with fixed-window counters (which can allow double the limit at window edges) and leaky buckets (which can be too aggressive in smoothing bursts).

class TokenBucket {
  constructor(size, rate) {
    this.size = size;
    this.rate = rate;
    this.buckets = new Map(); // key => { tokens, lastRefill }
  }

  consume(key) {
    const now = Date.now() / 1000; // seconds
    let bucket = this.buckets.get(key);

    if (!bucket) {
      bucket = { tokens: this.size, lastRefill: now };
      this.buckets.set(key, bucket);
    }

    // refill based on elapsed time
    const elapsed = now - bucket.lastRefill;
    bucket.tokens = Math.min(this.size, bucket.tokens + elapsed * this.rate);
    bucket.lastRefill = now;

    if (bucket.tokens < 1) {
      return false; // not allowed
    }

    bucket.tokens -= 1;
    return true; // allowed
  }
}

const limiter = new TokenBucket(10, 5); // 10 max burst, 5 tokens per second

function rateLimit(req, res, next) {
  const key = req.ip; // or req.headers['x-api-key']
  if (!limiter.consume(key)) {
    return res.status(429).json({ error: 'Too many requests, please slow down.' });
  }
  next();
}