Designing a Distributed Rate Limiter from Scratch: Token Bucket vs Leaky Bucket & Redis Implementation

Rate limiting is one of the most critical defensive primitives in modern distributed systems. Whether defending against Denial-of-Service (DoS) attacks, mitigating brute-force password attempts, throttling noisy API tenants, or preventing cascading database overloads, a well-architected rate limiter safeguards system reliability and infrastructure budgets.

However, moving from a naive single-server in-memory limiter to a high-throughput, horizontally scalable distributed rate limiter introduces complex engineering trade-offs: race conditions, concurrency bottlenecks, network latency, and multi-region data synchronization.

This comprehensive guide breaks down the core mathematical algorithms (Token Bucket, Leaky Bucket, Fixed Window, and Sliding Window Log/Counter), provides production-ready Redis Lua scripts, and walks through the multi-region architectural blueprints expected in high-scale systems.

1. Core Rate Limiting Algorithms Compared#

Choosing the right rate-limiting algorithm depends on your API traffic characteristics, memory constraints, and tolerance for burstiness.

Algorithm Comparison Matrix#

2. Deep Dive: Token Bucket vs. Leaky Bucket Mechanics#

The Token Bucket Algorithm#

The Token Bucket algorithm models a bucket of fixed capacity C that is continuously refilled with tokens at a constant rate of R tokens per second.

1. When a request arrives, the limiter checks if at least 1 token is available.
2. If tokens are greater than or equal to 1, 1 token is removed, and the request proceeds.
3. If tokens are less than 1, the request is rejected with HTTP 429 Too Many Requests.

Key Advantage: Instead of running a background cron job to increment tokens every second, we calculate tokens dynamically on read using timestamp deltas:

Current Tokens = min(Capacity, Stored Tokens + (Now - Last Updated) * Refill Rate)

The Leaky Bucket (Traffic Shaping) Algorithm#

While the Token Bucket allows bursts up to capacity C, the Leaky Bucket acts as a FIFO queue with a constant leak rate.

• Incoming requests enter the queue.
• If the queue is full, incoming packets are dropped.
• Requests are drained and processed at a strictly uniform rate R.

Best For: Systems feeding databases or legacy downstream services that cannot tolerate sudden spikes in concurrency.

3. Production Distributed Implementation: Redis + Lua Scripting#

In a distributed environment with dozens of API gateway instances, keeping local counters causes state drift. Storing counts in a shared Redis cluster is standard practice.

However, a naive implementation with separate GET and INCR commands introduces severe race conditions:

Client A -> GET user:101 -> Returns 99 (Limit 100)
Client B -> GET user:101 -> Returns 99
Client A -> INCR user:101 -> Sets 100 (Passes)
Client B -> INCR user:101 -> Sets 101 (Passes -> Bug!)

Atomic Token Bucket Implementation in Redis Lua#

By executing the logic inside an atomic Lua script, Redis guarantees that no other operation can interleave during calculation:

-- KEYS[1]: Rate limit key (e.g., "ratelimit:user:1042")
-- ARGV[1]: Bucket Capacity (e.g., 10)
-- ARGV[2]: Refill Rate per second (e.g., 2.0)
-- ARGV[3]: Current Unix Timestamp in seconds
-- ARGV[4]: Requested Tokens (usually 1)

local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

-- Retrieve current state [last_tokens, last_updated]
local data = redis.call("HMGET", key, "tokens", "last_updated")
local tokens = tonumber(data[1])
local last_updated = tonumber(data[2])

if tokens == nil then
    tokens = capacity
    last_updated = now
else
    -- Compute generated tokens since last request
    local delta = math.max(0, now - last_updated)
    tokens = math.min(capacity, tokens + delta * refill_rate)
    last_updated = now
end

if tokens >= requested then
    tokens = tokens - requested
    redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
    redis.call("EXPIRE", key, math.ceil(capacity / refill_rate) * 2)
    return { 1, math.floor(tokens) } -- 1 = Allowed, remaining tokens
else
    redis.call("HMSET", key, "tokens", tokens, "last_updated", last_updated)
    return { 0, math.floor(tokens) } -- 0 = Blocked, remaining tokens
end

Node.js / TypeScript Gateway Middleware Integration#

import { createClient } from 'redis';
import fs from 'fs';

const redis = createClient({ url: process.env.REDIS_URL });
const tokenBucketScript = fs.readFileSync('./scripts/tokenBucket.lua', 'utf-8');

export async function rateLimiterMiddleware(req: any, res: any, next: any) {
  const identifier = req.headers['x-api-key'] || req.ip;
  const key = `ratelimit:${identifier}`;
  
  const capacity = 50;       // Max burst: 50 requests
  const refillRate = 10;     // Refill: 10 requests per second
  const now = Date.now() / 1000;

  try {
    const result = await redis.eval(tokenBucketScript, {
      keys: [key],
      arguments: [capacity.toString(), refillRate.toString(), now.toString(), '1'],
    }) as [number, number];

    const [allowed, remainingTokens] = result;

    res.setHeader('X-RateLimit-Limit', capacity);
    res.setHeader('X-RateLimit-Remaining', remainingTokens);

    if (allowed === 1) {
      return next();
    } else {
      res.setHeader('Retry-After', Math.ceil(1 / refillRate));
      return res.status(429).json({
        error: 'Too Many Requests',
        message: 'Rate limit exceeded. Please throttle your requests.',
      });
    }
  } catch (err) {
    console.error('Rate limiter evaluation error:', err);
    // Fail-open strategy to avoid taking down APIs during Redis blips
    return next();
  }
}

4. Multi-Region Architectural Patterns#

When deploying systems across North America, Europe, and Asia, a single centralized Redis cluster incurs a 100ms–200ms latency penalty on every API request.

Architectural Trade-offs in Multi-Region Setups#

1. Local-First Rate Limiting (Recommended for 99% of APIs):
   • Divide global quotas across regions based on historical traffic weight (e.g., 50% US, 30% EU, 20% AP).
   • Each region limits independently against its local Redis cluster with under 2ms latency.
2. Centralized Global Redis with Read Replicas:
   • High read throughput, but token writes still experience cross-region latency.
3. CRDTs (Conflict-Free Replicated Data Types):
   • Redis Enterprise active-active replication utilizes PN-Counters (Positive-Negative Counters) to asynchronously converge token allocations across global clusters.

5. Defensive Best Practices: Headers, Fail-Open, & Client Guidance#

Building an enterprise-grade rate limiter requires clear client communication and disaster resilience:

1. Standard RFC 6585 & IETF Headers: Always return standard HTTP rate-limiting headers:
   • RateLimit-Limit: Maximum quota allowed in the period.
   • RateLimit-Remaining: Remaining units available.
   • RateLimit-Reset: Unix timestamp when quota resets.
   • Retry-After: Number of seconds to wait before retrying (on 429 status).
2. Fail-Open Policy: If your Redis cluster suffers an outage, your rate limiter should log the failure and allow traffic through rather than causing a complete API outage.
3. Layered Throttling: Apply rate limits at multiple layers—by IP address at the Edge/CDN layer (preventing DDoS), by User ID at the Gateway layer, and by tenant organization at the database layer.

Frequently Asked Questions#

Why not use memory counters in application instances?#

If you scale your application horizontally to 10 instances behind a load balancer, an in-memory counter is partitioned across all 10 processes. A client sending 100 requests will have their traffic split across instances, allowing up to 10 times their intended quota unless sticky routing is used (which creates hot spots).

What is the difference between Sliding Window Log and Sliding Window Counter?#

Sliding Window Log stores every single timestamp in a sorted set (ZSET), providing mathematically exact rate limiting at the cost of high memory usage. Sliding Window Counter stores two counters (previous window and current window) and computes a weighted average, using constant O(1) memory with approximately 99% accuracy.

What should client applications do when receiving a 429 response?#

Clients should implement Exponential Backoff with Jitter. Instead of retrying immediately, clients wait a calculated exponential delay with randomized jitter while respecting the Retry-After header.