How to Design a Rate Limiter: Algorithms, Distributed Coordination, and Production Pitfalls

Rate limiting is one of those topics where the interview answer and the production answer diverge significantly. Most system design guides stop at “use a token bucket with Redis.” That’s not wrong, but it skips everything that actually matters: why your distributed limiter has race conditions under concurrent load, what happens when Redis goes down, how clock skew breaks your sliding window, and why naive client backoff turns a partial outage into a full one.

This guide covers all four mainstream algorithms with TypeScript implementations, then gets into the distributed coordination problems that make rate limiting genuinely hard, and ends with a decision framework for choosing the right algorithm for your traffic shape.

The Four Algorithms

Fixed Window Counter

The simplest approach. Divide time into fixed buckets (one per minute, one per hour), increment a counter per request, and reject when the counter exceeds the limit.

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

  constructor(
    private readonly limit: number,
    private readonly windowMs: number
  ) {}

  isAllowed(key: string): boolean {
    const now = Date.now();
    const windowStart = Math.floor(now / this.windowMs) * this.windowMs;
    const entry = this.counts.get(key);

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

    if (entry.count >= this.limit) return false;

    entry.count++;
    return true;
  }
}

The problem is the boundary. A client can make limit requests at 00:59 and limit requests at 01:01, and you’ve served 2 * limit requests in a two-second window. For most APIs this is acceptable. For security-sensitive endpoints it is not.

Sliding Window Log

Keep a log of every request timestamp. On each request, remove timestamps older than the window and check the log length against the limit.

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

  constructor(
    private readonly limit: number,
    private readonly windowMs: number
  ) {}

  isAllowed(key: string): boolean {
    const now = Date.now();
    const windowStart = now - this.windowMs;
    const log = this.logs.get(key) ?? [];

    // Remove expired entries
    const trimmed = log.filter((ts) => ts > windowStart);

    if (trimmed.length >= this.limit) {
      this.logs.set(key, trimmed);
      return false;
    }

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

This gives exact fairness: the window truly slides. The cost is memory. A user who hits the limit stores one timestamp per request for the full window duration. At scale with many unique keys, the memory pressure is real. At 1000 requests per user per minute, with 10,000 active users, you’re holding 10 million timestamps.

Sliding Window Counter

A hybrid. Divide time into fixed buckets but approximate the sliding window by weighting the previous bucket’s count based on how far into the current bucket you are.

class SlidingWindowCounterLimiter {
  private buckets = new Map<string, { current: number; previous: number; windowStart: number }>();

  constructor(
    private readonly limit: number,
    private readonly windowMs: number
  ) {}

  isAllowed(key: string): boolean {
    const now = Date.now();
    const windowStart = Math.floor(now / this.windowMs) * this.windowMs;
    const elapsed = now - windowStart;
    const previousWeight = 1 - elapsed / this.windowMs;

    const entry = this.buckets.get(key);

    let current: number;
    let previous: number;

    if (!entry) {
      current = 0;
      previous = 0;
    } else if (entry.windowStart === windowStart) {
      current = entry.current;
      previous = entry.previous;
    } else if (entry.windowStart === windowStart - this.windowMs) {
      // Rolled into a new window
      current = 0;
      previous = entry.current;
    } else {
      // More than one window has passed
      current = 0;
      previous = 0;
    }

    const estimated = previous * previousWeight + current;

    if (estimated >= this.limit) return false;

    this.buckets.set(key, {
      current: current + 1,
      previous,
      windowStart,
    });

    return true;
  }
}

The approximation error is at most limit / window_size requests, which is negligible for most use cases. This approach uses O(1) memory per key and avoids the boundary problem of fixed windows. It is the algorithm most production systems should default to.

Token Bucket

Tokens accumulate at a fixed rate up to a configured maximum. Each request consumes one token. Requests that arrive when no tokens are available are rejected.

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

  constructor(
    private readonly capacity: number,
    private readonly refillRatePerMs: number // tokens per millisecond
  ) {}

  isAllowed(key: string): boolean {
    const now = Date.now();
    const bucket = this.buckets.get(key) ?? { tokens: this.capacity, lastRefill: now };

    // Refill based on elapsed time
    const elapsed = now - bucket.lastRefill;
    const refilled = Math.min(this.capacity, bucket.tokens + elapsed * this.refillRatePerMs);

    if (refilled < 1) {
      this.buckets.set(key, { tokens: refilled, lastRefill: now });
      return false;
    }

    this.buckets.set(key, { tokens: refilled - 1, lastRefill: now });
    return true;
  }
}

Token bucket excels when you want to allow short bursts while enforcing a long-term average rate. A client can hammer an endpoint briefly and succeed as long as they’ve built up enough tokens. The tradeoff: it is harder to reason about fairness because the effective rate depends on historical usage patterns, not just the current window.

Tradeoffs at a Glance

Algorithm	Memory	Accuracy	Burst Handling	Fairness	Complexity
Fixed Window	O(1) per key	Low (boundary spikes)	Allows 2x at boundary	Simple	Low
Sliding Window Log	O(limit) per key	Exact	Accurate	Strong	Medium
Sliding Window Counter	O(1) per key	~1% error	Accurate	Strong	Medium
Token Bucket	O(1) per key	Exact	Configurable burst	Depends on config	Medium

For API endpoints where you care about per-user fairness and want simple operations: sliding window counter. For endpoints where burst traffic is legitimate (uploads, batch processing): token bucket. For simple per-IP DoS protection where you own the tradeoffs: fixed window.

Distributed Rate Limiting

All four implementations above break the moment you add a second server. Each instance has its own in-memory state. A client round-robining across three servers gets three times the limit.

The standard solution is centralizing state in Redis. But centralizing state introduces new problems.

Atomic Operations with Redis

The naive approach: GET counter, check against limit, INCR counter. This has a race condition. Two concurrent requests can both read the same counter value, both conclude they are under the limit, and both increment.

Fix this with a Lua script, which Redis executes atomically:

import { createClient } from "redis";

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

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

  -- Remove expired entries
  redis.call('ZREMRANGEBYSCORE', key, '-inf', windowStart)

  -- Count remaining
  local count = redis.call('ZCARD', key)

  if count >= limit then
    return 0
  end

  -- Add current request
  redis.call('ZADD', key, now, now .. '-' .. math.random(100000))
  redis.call('PEXPIRE', key, windowMs)

  return 1
`;

async function isAllowed(key: string, limit: number, windowMs: number): Promise<boolean> {
  const now = Date.now();
  const result = await client.eval(slidingWindowScript, {
    keys: [key],
    arguments: [String(limit), String(windowMs), String(now)],
  });
  return result === 1;
}

This uses a sorted set where the score is the request timestamp. The Lua script removes expired entries, checks the count, and adds the new entry atomically. No race condition.

For the sliding window counter approach in Redis, you need two keys (current and previous bucket) and atomic increment logic:

const slidingCounterScript = `
  local currentKey = KEYS[1]
  local previousKey = KEYS[2]
  local limit = tonumber(ARGV[1])
  local windowMs = tonumber(ARGV[2])
  local now = tonumber(ARGV[3])
  local windowStart = math.floor(now / windowMs) * windowMs
  local elapsed = now - windowStart
  local previousWeight = 1 - (elapsed / windowMs)

  local current = tonumber(redis.call('GET', currentKey)) or 0
  local previous = tonumber(redis.call('GET', previousKey)) or 0

  local estimated = previous * previousWeight + current

  if estimated >= limit then
    return 0
  end

  redis.call('INCR', currentKey)
  redis.call('PEXPIRE', currentKey, windowMs * 2)

  return 1
`;

Rate Limiter Middleware Pattern

Wrapping this in Express middleware keeps the logic out of your route handlers:

import { Request, Response, NextFunction } from "express";

interface RateLimitOptions {
  limit: number;
  windowMs: number;
  keyFn?: (req: Request) => string;
  onRejected?: (req: Request, res: Response) => void;
}

function rateLimitMiddleware(options: RateLimitOptions) {
  const keyFn = options.keyFn ?? ((req) => req.ip ?? "unknown");

  return async (req: Request, res: Response, next: NextFunction) => {
    const key = `rl:${keyFn(req)}`;

    try {
      const allowed = await isAllowed(key, options.limit, options.windowMs);

      if (!allowed) {
        if (options.onRejected) {
          return options.onRejected(req, res);
        }
        res.setHeader("Retry-After", Math.ceil(options.windowMs / 1000));
        return res.status(429).json({ error: "rate_limit_exceeded" });
      }

      next();
    } catch (err) {
      // Redis failure: decide your failopen vs failclosed policy here
      console.error("Rate limiter error:", err);
      next(); // fail open
    }
  };
}

The catch block is load-bearing. It encodes your failover policy.

Production Pitfalls

Clock Skew in Distributed Systems

When you have multiple Redis replicas or compute nodes with slightly different clocks, time-based windows drift. A request that arrives at 00:999 on one node is assigned to window N. The same request on a node 10ms ahead is assigned to window N+1. In most cases the drift is small enough to ignore. But if you’re using Redis Cluster and your Lua scripts read redis.call('TIME') instead of accepting the timestamp as an argument, you’re relying on each shard’s clock. Shards can diverge.

The fix: always generate timestamps on the application layer and pass them into Redis scripts. This makes the timestamp authoritative from a single source (your application server’s NTP-synchronized clock), not Redis’s own clock.

Failover Behavior

Every distributed rate limiter has an implicit policy when the state store is unavailable. Two options:

Fail open: allow all requests when Redis is down. This prevents a cache outage from becoming an API outage, but briefly removes rate limiting entirely. Accept this if your default traffic is mostly legitimate and you have other DoS protections (WAF, CDN limits).

Fail closed: reject all requests when Redis is down. This is safer for security-sensitive endpoints but converts a partial infrastructure failure into a user-visible outage.

Document this decision explicitly in your codebase. The default in many libraries is fail open without being explicit about it, which means you discover the policy during an incident.

Client-Side Backoff

When your rate limiter starts rejecting requests at scale, what clients do next determines whether you recover or spiral. A naive client that retries immediately after a 429 generates exactly the same load as before, except now it also has to process the rejection overhead.

Good rate limiting requires cooperation: set Retry-After headers with realistic values, and clients should implement exponential backoff with jitter. Without jitter, all clients retry at the same time (the thundering herd), and each retry wave hits the limit again.

async function fetchWithBackoff(url: string, maxRetries = 3): Promise<Response> {
  for (let attempt = 0; attempt <= maxRetries; attempt++) {
    const response = await fetch(url);

    if (response.status !== 429) return response;

    const retryAfter = response.headers.get("Retry-After");
    const baseDelay = retryAfter ? parseInt(retryAfter) * 1000 : 1000 * Math.pow(2, attempt);
    const jitter = Math.random() * baseDelay * 0.2;

    await new Promise((resolve) => setTimeout(resolve, baseDelay + jitter));
  }

  throw new Error("Max retries exceeded");
}

Redis Key Expiration and Memory

Rate limit keys that never expire accumulate indefinitely. Always set a TTL on your keys. For sliding window log (sorted set approach), set the TTL to windowMs. For fixed/sliding counter approaches, set it to 2 * windowMs to allow the previous bucket to still be readable.

If you’re using Redis Cluster, be aware that all keys involved in a single Lua script must hash to the same slot. If you have currentKey and previousKey as separate keys, prefix them with a hash tag to force co-location: {user:123}:rl:current and {user:123}:rl:previous.

Choosing a Granularity for Your Key

Most rate limiters key by user ID or API key. Consider whether you also want to key by endpoint. A user who abuses one expensive endpoint (say, a report export) should not have that counted against their limit for your lightweight read endpoints. Multi-dimensional rate limiting (per user, per endpoint, per global resource budget) is more complex but necessary for APIs where endpoint costs vary significantly.

Algorithm Decision Framework

Traffic Pattern	Recommended Algorithm
Simple per-IP DoS prevention	Fixed window (easy to implement and reason about)
Per-user API quotas	Sliding window counter
Burst-tolerant APIs (uploads, webhooks)	Token bucket with configured capacity
Security-sensitive endpoints (auth, payments)	Sliding window log (exact counts worth the memory cost)
Mixed traffic with SLAs	Token bucket per tier with separate limits

One thing worth noting: in most production systems, the right rate limiter is the one already in your infrastructure. If you’re behind a CDN or API gateway, it almost certainly has a rate limiting module. Use it before building your own. Own the complexity only when you need rate limiting logic that is specific to your application: per-user quotas, per-resource limits, or behavior that depends on request content.

Closing

The algorithm choice matters less than the operational choices around it. Fixed window is not wrong, and sliding window log is not always better. What breaks production rate limiters is the gap between the in-process prototype and the distributed reality: no atomicity, no failover policy, clients that retry without backoff, and keys that accumulate without expiry. Get those right and any of the four algorithms will hold up under load.