Designing a Rate Limiter: Token Buckets, Sliding Windows, and Distributed Rate Limiting at Scale

Rate limiting is one of those problems that looks solved until you have to run it in production. The interview answer is straightforward: pick an algorithm, back it with Redis, use atomic operations. The production reality involves clock skew across nodes, Redis unavailability at 2 AM, Lua scripts that nobody on the team understands anymore, and a burst of traffic that your “fixed window” limiter let through cleanly because the burst landed on a window boundary.

This guide covers all five mainstream algorithms, how to implement distributed rate limiting with Redis correctly, where to place the limiter in your request path, and the failure modes that will eventually bite you.

The Five Algorithms

Rate limiting algorithms differ on one primary axis: how they define “now” relative to the limit window. Some use fixed time boundaries. Some track individual request timestamps. Some model flow as a leaking or filling bucket. Each choice produces a different cost, accuracy, and burst behavior.

Fixed Window Counter

Divide time into fixed buckets aligned to the clock. One counter per user per bucket. Reject requests when the counter exceeds the limit.

class FixedWindowLimiter {
  private buckets = new Map<string, { count: number; windowStart: number }>();

  allow(key: string, limit: number, windowMs: number): boolean {
    const now = Date.now();
    const windowStart = Math.floor(now / windowMs) * windowMs;
    const bucket = this.buckets.get(key);

    if (!bucket || bucket.windowStart !== windowStart) {
      this.buckets.set(key, { count: 1, windowStart });
      return true;
    }

    if (bucket.count >= limit) return false;
    bucket.count++;
    return true;
  }
}

The critical flaw: a user who sends 100 requests at 11:59:59 and 100 at 12:00:01 has sent 200 requests in two seconds while technically respecting a 100 req/minute limit. The window boundary is an attack surface. This is not a theoretical problem; it appears in real traffic from clients that sync their request batches to wall-clock minutes.

Sliding Window Log

Track a timestamp for every request. On each new request, purge timestamps older than one window duration, then count how many remain. Reject if the count reaches the limit.

class SlidingWindowLogLimiter {
  private logs = new Map<string, number[]>();

  allow(key: string, limit: number, windowMs: number): boolean {
    const now = Date.now();
    const windowStart = now - windowMs;
    const timestamps = this.logs.get(key) ?? [];

    // Remove expired entries
    const valid = timestamps.filter(t => t > windowStart);
    if (valid.length >= limit) {
      this.logs.set(key, valid);
      return false;
    }

    valid.push(now);
    this.logs.set(key, valid);
    return true;
  }
}

This is the most accurate algorithm. There is no boundary exploit because every request is evaluated against a true rolling window. The cost is memory: storing a timestamp per request per user. At 1,000 requests per user per minute with 10,000 active users, you are tracking 10 million timestamps in memory. For most APIs this is fine. For high-throughput public APIs, it is not.

Sliding Window Counter

A practical approximation of the sliding window log. Store two counters: one for the previous window, one for the current. Weight the previous window’s count by how much of it overlaps with the current rolling window.

class SlidingWindowCounterLimiter {
  private windows = new Map<string, { prev: number; curr: number; windowStart: number }>();

  allow(key: string, limit: number, windowMs: number): boolean {
    const now = Date.now();
    const currentWindowStart = Math.floor(now / windowMs) * windowMs;
    const elapsed = now - currentWindowStart;
    const prevWeight = 1 - elapsed / windowMs;

    let state = this.windows.get(key);
    if (!state || state.windowStart !== currentWindowStart) {
      const prevCount = state?.windowStart === currentWindowStart - windowMs ? state.curr : 0;
      state = { prev: prevCount, curr: 0, windowStart: currentWindowStart };
      this.windows.set(key, state);
    }

    const estimated = Math.floor(state.prev * prevWeight) + state.curr;
    if (estimated >= limit) return false;

    state.curr++;
    return true;
  }
}

The error rate on this approximation is typically under 0.1% in practice. For most APIs, this is the right choice: O(1) memory per key, no timestamp lists, and accurate enough to matter. Cloudflare uses this approach for their edge rate limiting at scale.

Token Bucket

Each user has a bucket that holds up to capacity tokens. Tokens refill at a fixed rate. Each request consumes one token. Requests that arrive when the bucket is empty are rejected.

class TokenBucketLimiter {
  private buckets = new Map<string, { tokens: number; lastRefill: number }>();

  allow(
    key: string,
    capacity: number,
    refillRate: number, // tokens per second
  ): boolean {
    const now = Date.now();
    let bucket = this.buckets.get(key);

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

    // Add tokens based on time elapsed
    const elapsed = (now - bucket.lastRefill) / 1000;
    bucket.tokens = Math.min(capacity, bucket.tokens + elapsed * refillRate);
    bucket.lastRefill = now;

    if (bucket.tokens < 1) return false;

    bucket.tokens--;
    return true;
  }
}

Token bucket’s key property is that it allows bursting up to capacity. A user who has been idle for 30 seconds with a refill rate of 2 tokens/second and a capacity of 10 can fire 10 requests instantly. For most API use cases this is desirable behavior. For strict throughput control (billing, metering), it can be a problem.

Leaky Bucket

Requests enter a queue. A worker drains the queue at a fixed rate, processing one request per interval. Requests that arrive when the queue is full are rejected.

class LeakyBucketLimiter {
  private queues = new Map<string, { size: number; nextDrain: number }>();

  allow(
    key: string,
    capacity: number,
    drainIntervalMs: number,
  ): boolean {
    const now = Date.now();
    let bucket = this.queues.get(key);

    if (!bucket) {
      bucket = { size: 0, nextDrain: now + drainIntervalMs };
      this.queues.set(key, bucket);
    }

    // Drain slots that have elapsed
    if (now >= bucket.nextDrain) {
      const intervals = Math.floor((now - bucket.nextDrain) / drainIntervalMs) + 1;
      bucket.size = Math.max(0, bucket.size - intervals);
      bucket.nextDrain = now + drainIntervalMs;
    }

    if (bucket.size >= capacity) return false;

    bucket.size++;
    return true;
  }
}

Leaky bucket enforces a smooth output rate. This makes it useful for rate-limiting outbound requests to third-party APIs that will penalize you for bursts. It is less useful as an inbound API rate limiter because it does not communicate meaningful retry-after semantics, and the smoothing behavior can introduce artificial latency for legitimate bursty clients.

Algorithm Tradeoffs

Algorithm	Memory	Burst Allowed	Boundary Attack	Best For
Fixed window	O(1) per key	Yes (double at boundary)	Yes	Internal systems, simple throttling
Sliding window log	O(requests) per key	No	No	High-value APIs, per-second accuracy
Sliding window counter	O(1) per key	Partially	Near-zero	Public APIs, high cardinality keys
Token bucket	O(1) per key	Yes (up to capacity)	No	User-facing APIs, metered usage
Leaky bucket	O(1) per key	No	No	Outbound API calls, smooth egress

Distributed Rate Limiting with Redis

In-process implementations fall apart the moment you have more than one server. Traffic is load-balanced across nodes, so each node sees only a fraction of the requests for any given user. A 100 req/min limit becomes effectively 100 * N req/min across N nodes.

Redis solves this with a shared counter. The key implementation challenge is atomicity: a read-then-write across two separate Redis commands can let concurrent requests slip through.

Fixed Window in Redis (Atomic)

import { createClient } from "redis";

const redis = createClient({ url: process.env.REDIS_URL });

async function fixedWindowAllow(
  key: string,
  limit: number,
  windowSeconds: number,
): Promise<{ allowed: boolean; remaining: number }> {
  const windowKey = `rl:${key}:${Math.floor(Date.now() / 1000 / windowSeconds)}`;

  const result = await redis.multi()
    .incr(windowKey)
    .expire(windowKey, windowSeconds * 2) // 2x TTL for safety
    .exec();

  const count = result![0] as number;
  const allowed = count <= limit;
  return { allowed, remaining: Math.max(0, limit - count) };
}

The MULTI/EXEC block ensures the increment and TTL-set are atomic. Do not use INCR followed by a separate EXPIRE call; a process crash between the two leaves a key with no TTL that never expires.

Sliding Window Counter in Redis (Lua)

For the sliding window counter, the weighted-count calculation must happen atomically with the increment. This requires a Lua script executed via EVAL, which Redis runs as a single atomic operation:

const slidingWindowScript = `
local key = KEYS[1]
local now = tonumber(ARGV[1])
local window_ms = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])

local window_start = math.floor(now / window_ms) * window_ms
local prev_window_start = window_start - window_ms
local elapsed = now - window_start
local prev_weight = 1 - (elapsed / window_ms)

local curr_key = key .. ":" .. window_start
local prev_key = key .. ":" .. prev_window_start

local curr_count = tonumber(redis.call("GET", curr_key) or "0")
local prev_count = tonumber(redis.call("GET", prev_key) or "0")
local estimated = math.floor(prev_count * prev_weight) + curr_count

if estimated >= limit then
  return {0, limit - estimated}
end

redis.call("INCR", curr_key)
redis.call("EXPIRE", curr_key, math.ceil(window_ms / 1000) * 2)
return {1, limit - estimated - 1}
`;

async function slidingWindowAllow(
  key: string,
  limit: number,
  windowMs: number,
): Promise<{ allowed: boolean; remaining: number }> {
  const result = await redis.eval(
    slidingWindowScript,
    { keys: [`rl:${key}`], arguments: [Date.now().toString(), windowMs.toString(), limit.toString()] },
  ) as [number, number];

  return { allowed: result[0] === 1, remaining: Math.max(0, result[1]) };
}

Token Bucket in Redis (Lua)

Token bucket also requires atomic read-compute-write in Lua:

const tokenBucketScript = `
local key = KEYS[1]
local now = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local refill_rate = tonumber(ARGV[3])

local state = redis.call("HMGET", key, "tokens", "last_refill")
local tokens = tonumber(state[1]) or capacity
local last_refill = tonumber(state[2]) or now

local elapsed = (now - last_refill) / 1000
tokens = math.min(capacity, tokens + elapsed * refill_rate)

if tokens < 1 then
  redis.call("HMSET", key, "tokens", tokens, "last_refill", now)
  redis.call("EXPIRE", key, math.ceil(capacity / refill_rate) + 60)
  return {0, 0}
end

tokens = tokens - 1
redis.call("HMSET", key, "tokens", tokens, "last_refill", now)
redis.call("EXPIRE", key, math.ceil(capacity / refill_rate) + 60)
return {1, math.floor(tokens)}
`;

async function tokenBucketAllow(
  key: string,
  capacity: number,
  refillRatePerSecond: number,
): Promise<{ allowed: boolean; remaining: number }> {
  const result = await redis.eval(
    tokenBucketScript,
    {
      keys: [`rl:tb:${key}`],
      arguments: [Date.now().toString(), capacity.toString(), refillRatePerSecond.toString()],
    },
  ) as [number, number];

  return { allowed: result[0] === 1, remaining: result[1] };
}

Per-User and Per-API-Key Rate Limiting

The key space for a production rate limiter usually has at least three dimensions: the identifier (who), the resource (what), and the tier (how much).

function buildRateLimitKey(params: {
  identifier: string;      // user ID or API key hash
  identifierType: "user" | "api_key" | "ip";
  endpoint?: string;       // optional per-route limiting
  tier: "free" | "pro" | "enterprise";
}): string {
  const parts = ["rl", params.identifierType, params.identifier];
  if (params.endpoint) parts.push(params.endpoint);
  parts.push(params.tier);
  return parts.join(":");
}

const TIER_LIMITS = {
  free: { limit: 100, windowMs: 60_000 },
  pro: { limit: 1_000, windowMs: 60_000 },
  enterprise: { limit: 10_000, windowMs: 60_000 },
} as const;

For API key-based limiting, never use the raw key as a Redis key. Hash it first. If Redis is compromised, you do not want raw API keys in the keyspace.

import { createHash } from "crypto";

function hashApiKey(rawKey: string): string {
  return createHash("sha256").update(rawKey).digest("hex").slice(0, 32);
}

Returning limit headers with every response is non-optional in production. Clients need this to implement proper backoff without hammering your 429 endpoint:

function setRateLimitHeaders(
  res: Response,
  result: { allowed: boolean; remaining: number },
  limit: number,
  windowMs: number,
): void {
  res.setHeader("X-RateLimit-Limit", limit);
  res.setHeader("X-RateLimit-Remaining", result.remaining);
  res.setHeader("X-RateLimit-Reset", Math.ceil((Date.now() + windowMs) / 1000));
  if (!result.allowed) {
    res.setHeader("Retry-After", Math.ceil(windowMs / 1000));
  }
}

Placement in the Request Path

Where you place the rate limiter changes what it can enforce and what it costs.

API Gateway (Nginx, Kong, Cloudflare, AWS API Gateway): The limiter runs before traffic reaches your application servers. This is the right layer for coarse-grained limiting (IP-based DDoS mitigation, global per-user limits). The downside: gateway-level limiters often lack access to your application’s concept of identity. An unauthenticated request has no user ID, so IP becomes the fallback. IP-based limiting is easy to evade and hurts users behind NATs.

Middleware (Express, Hono, Fastify middleware layer): The limiter runs after authentication, so it can enforce per-user or per-API-key limits based on verified identity. This is the most common production approach. Cost: one Redis round-trip per request adds roughly 1-3ms of latency in typical deployments.

Application-level: The limiter is called explicitly inside specific route handlers or service methods. This gives the finest control: different limits per operation, dynamic limits based on request payload. Cost: easy to forget, easy to implement inconsistently across routes.

In practice, a layered approach works best. Gateway-level IP limiting blocks volumetric abuse before it touches your servers. Middleware-level per-identity limiting enforces your API contract. Application-level limiting handles specific expensive operations (LLM inference calls, report generation, bulk exports).

Production Considerations

Race Conditions

Even with Lua scripts, you can still have correctness problems. If you are running multiple independent Redis commands and treating their combined result as authoritative, you have a race. The rule is simple: any rate limit check that modifies state must do so inside a single Lua script or a Redis transaction.

One subtle race: you check the limit, pass, and then update the counter in two separate calls. Between the check and the update, another request could have passed the same check. Lua scripts eliminate this by making check-and-increment atomic.

Clock Drift

Sliding window algorithms that use Date.now() for window boundaries are sensitive to clock skew. If two nodes have clocks that differ by more than a few seconds, requests near a window boundary will be counted in different windows on different nodes. This can cause limit undercounting (requests that should be blocked are allowed) or overcounting (requests that should be allowed are blocked).

Fix: use Redis’s server time via TIME command rather than application server time for all timestamp calculations. This eliminates application-level clock skew.

async function getRedisTime(): Promise<number> {
  const [seconds, microseconds] = await redis.time();
  return parseInt(seconds) * 1000 + Math.floor(parseInt(microseconds) / 1000);
}

Graceful Degradation When Redis Is Down

A rate limiter that throws on Redis failure will take down your API. The default behavior for any Redis operation should be to fail open (allow the request) with a circuit breaker that stops hitting Redis once it is clearly down.

class ResilientRateLimiter {
  private redisAvailable = true;
  private failureCount = 0;
  private readonly failureThreshold = 5;
  private lastFailure = 0;
  private readonly recoveryMs = 30_000;

  async allow(key: string, limit: number, windowMs: number): Promise<boolean> {
    // Circuit breaker: stop hitting Redis if it's down
    if (!this.redisAvailable) {
      if (Date.now() - this.lastFailure > this.recoveryMs) {
        this.redisAvailable = true; // Half-open: try again
        this.failureCount = 0;
      } else {
        return true; // Fail open
      }
    }

    try {
      const result = await slidingWindowAllow(key, limit, windowMs);
      this.failureCount = 0;
      return result.allowed;
    } catch {
      this.failureCount++;
      this.lastFailure = Date.now();
      if (this.failureCount >= this.failureThreshold) {
        this.redisAvailable = false;
      }
      return true; // Fail open rather than blocking all traffic
    }
  }
}

Failing open is not always safe. If your rate limiter protects a scarce resource (LLM API calls with per-token billing, outbound SMS), you may prefer to fail closed and return 503 when Redis is unavailable. Build the decision explicitly into the limiter configuration.

Multi-Region Rate Limiting

A Redis instance in us-east-1 has no visibility into requests processed by your eu-west-1 cluster. Global rate limiting requires either:

1. A globally replicated counter store (Redis Enterprise, DynamoDB global tables) with the latency cost of cross-region writes.
2. Approximate local limiting per region with a global overage correction mechanism.
3. Accepting per-region limits (effective global limit = per-region limit * number of regions).

Most teams end up with option 3 for cost and latency reasons, and set per-region limits accordingly. For cases where global accuracy is required (billing metering, compliance enforcement), route all limit checks through a single authoritative region and accept the added latency.

The Architecture in Practice

A production rate limiting service typically looks like this:

Request
  ↓
API Gateway (IP-based DDoS, global burst limit)
  ↓
Auth Middleware (resolve identity from JWT or API key)
  ↓
Rate Limit Middleware (per-identity limit check via Redis)
  ↓
Route Handler
  ↓
Application-Level Limiter (per-operation, expensive resources only)

Each layer has a different Redis key namespace, different limits, and different failure behavior. The gateway layer fails open because blocking traffic at the gateway is a high-impact decision. The middleware layer fails open by default with monitoring. The application layer for billing-sensitive operations fails closed.

Rate limit decisions should emit structured log events at every layer. When a customer disputes a 429, you need to reconstruct exactly what the limiter saw: the key, the counter value at the time of the check, the limit, and the Redis response time. Without this, every limit dispute becomes an archaeology exercise in your logs.

Where the Design Actually Fails

Token buckets and sliding windows handle steady-state traffic correctly. They fail at edges: coordinated traffic bursts from a CDN edge pop that batches requests, clock resets after daylight saving transitions that corrupt window boundaries, Redis key eviction under memory pressure that resets counters mid-window, and Lua script timeouts during heavy load that leave the rate limit check incomplete.

None of these are hypothetical. They are failure modes that production systems encounter on the way to maturity. The difference between a rate limiter that works in demos and one that works under production load is how deliberately you have thought through each failure case and built an explicit response: fail open or fail closed, with monitoring, with retry-after headers, with a circuit breaker that stops hitting a degraded Redis before it cascades into a latency spike.

Rate limiting is simple to describe and genuinely difficult to operate correctly at scale. The algorithm is usually the easy part.