Building a Rate Limiter From Scratch

A step-by-step tutorial for rate limiters using token bucket, sliding window and fixed window — with TypeScript, Redis integration and production patterns.

Published on September 16, 2022Updated on September 9, 20264 min read

rate-limiting redis typescript backend api-design tutorials

Rate limiters protect APIs from abuse and ensure fair resource distribution. Whether you are preventing brute-force login attempts, throttling expensive operations, or enforcing plan-based quotas, understanding how rate limiters work under the hood makes you better at configuring and debugging them.

This tutorial builds three rate limiting algorithms from scratch, then shows how to deploy them in production with Redis for distributed systems.

Fixed Window Rate Limiter

The fixed window algorithm divides time into fixed intervals and counts requests per interval. It is the simplest approach but has a burst problem at window boundaries — a client can send double the limit by timing requests at the end of one window and the start of the next.

tstypescript

class FixedWindowRateLimiter {
  private windows: Map<string, { count: number; expiresAt: number }> =
    new Map();
 
  constructor(
    private maxRequests: number,
    private windowMs: number
  ) {}
 
  isAllowed(key: string): boolean {
    const now = Date.now();
    const windowStart =
      Math.floor(now / this.windowMs) * this.windowMs;
    const windowKey = `${key}:${windowStart}`;
 
    const window = this.windows.get(windowKey);
 
    if (!window || now >= window.expiresAt) {
      // New window
      this.windows.set(windowKey, {
        count: 1,
        expiresAt: windowStart + this.windowMs,
      });
      return true;
    }
 
    if (window.count < this.maxRequests) {
      window.count++;
      return true;
    }
 
    return false;
  }
}
 
// Usage: 100 requests per minute
const limiter = new FixedWindowRateLimiter(100, 60_000);
 
// Problem: At 11:00:59, send 100 requests (allowed)
// At 11:01:00, send 100 more (new window, allowed)
// Result: 200 requests in 2 seconds — double the intended rate

Sliding Window Log Rate Limiter

The sliding window log keeps a sorted list of request timestamps. It counts requests within the last N seconds from the current time, eliminating the boundary burst problem.

tstypescript

class SlidingWindowLogLimiter {
  private logs: Map<string, number[]> = new Map();
 
  constructor(
    private maxRequests: number,
    private windowMs: number
  ) {}
 
  isAllowed(key: string): boolean {
    const now = Date.now();
    const windowStart = now - this.windowMs;
 
    let timestamps = this.logs.get(key) ?? [];
 
    // Remove expired entries
    timestamps = timestamps.filter((t) => t > windowStart);
 
    if (timestamps.length < this.maxRequests) {
      timestamps.push(now);
      this.logs.set(key, timestamps);
      return true;
    }
 
    this.logs.set(key, timestamps);
    return false;
  }
 
  // Returns milliseconds until next allowed request
  retryAfter(key: string): number {
    const now = Date.now();
    const timestamps = this.logs.get(key) ?? [];
    if (timestamps.length < this.maxRequests) return 0;
 
    const oldest = timestamps[timestamps.length - this.maxRequests];
    return Math.max(0, oldest + this.windowMs - now);
  }
}
 
// ❌ Memory problem: stores every timestamp
// 10,000 users × 100 requests/min = 1M timestamps in memory
// Not practical for high-traffic APIs
 
// ✅ Solution: use sliding window counter (next section)

Token Bucket Algorithm

The token bucket allows bursts while enforcing an average rate. Tokens are added at a fixed rate. Each request consumes one token. When the bucket is empty, requests are rejected.

tstypescript

class TokenBucketLimiter {
  private buckets: Map<
    string,
    { tokens: number; lastRefill: number }
  > = new Map();
 
  constructor(
    private capacity: number,
    private refillRate: number, // tokens per second
  ) {}
 
  isAllowed(key: string, tokensRequired: number = 1): boolean {
    const now = Date.now();
    let bucket = this.buckets.get(key);
 
    if (!bucket) {
      bucket = { tokens: this.capacity, lastRefill: now };
      this.buckets.set(key, bucket);
    }
 
    // Refill tokens based on elapsed time
    const elapsed = (now - bucket.lastRefill) / 1000;
    bucket.tokens = Math.min(
      this.capacity,
      bucket.tokens + elapsed * this.refillRate
    );
    bucket.lastRefill = now;
 
    if (bucket.tokens >= tokensRequired) {
      bucket.tokens -= tokensRequired;
      return true;
    }
 
    return false;
  }
}
 
// 10 requests/second with burst capacity of 20
const bucket = new TokenBucketLimiter(20, 10);
 
// Burst: 20 requests immediately (empties bucket)
// Then: 10 requests/second sustained
// If idle for 2 seconds: bucket refills to 20

Distributed Rate Limiting with Redis

In-memory rate limiters fail when you have multiple server instances. Redis provides atomic operations for distributed rate limiting.

tstypescript

import Redis from "ioredis";
 
class RedisSlidingWindowLimiter {
  constructor(
    private redis: Redis,
    private maxRequests: number,
    private windowMs: number,
    private prefix: string = "ratelimit"
  ) {}
 
  async isAllowed(
    key: string
  ): Promise<{ allowed: boolean; remaining: number; retryAfter: number }> {
    const now = Date.now();
    const windowStart = now - this.windowMs;
    const redisKey = `${this.prefix}:${key}`;
 
    // Use a Lua script for atomicity
    const result = await this.redis.eval(
      `
      -- Remove expired entries
      redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', ARGV[1])
 
      -- Count current entries
      local count = redis.call('ZCARD', KEYS[1])
 
      if count < tonumber(ARGV[2]) then
        -- Add new entry with timestamp as score
        redis.call('ZADD', KEYS[1], ARGV[3], ARGV[3] .. ':' .. math.random())
        redis.call('PEXPIRE', KEYS[1], ARGV[4])
        return {1, tonumber(ARGV[2]) - count - 1, 0}
      else
        -- Get oldest entry to calculate retry-after
        local oldest = redis.call('ZRANGE', KEYS[1], 0, 0, 'WITHSCORES')
        local retryAfter = tonumber(oldest[2]) + tonumber(ARGV[4]) - tonumber(ARGV[3])
        return {0, 0, retryAfter}
      end
      `,
      1,
      redisKey,
      windowStart.toString(),
      this.maxRequests.toString(),
      now.toString(),
      this.windowMs.toString()
    ) as [number, number, number];
 
    return {
      allowed: result[0] === 1,
      remaining: result[1],
      retryAfter: Math.max(0, result[2]),
    };
  }
}

tstypescript

// Express middleware using the Redis rate limiter
import { Request, Response, NextFunction } from "express";
 
function rateLimitMiddleware(limiter: RedisSlidingWindowLimiter) {
  return async (req: Request, res: Response, next: NextFunction) => {
    // Rate limit by IP, or by user ID if authenticated
    const key = req.user?.id ?? req.ip ?? "anonymous";
    const result = await limiter.isAllowed(key);
 
    // Always set rate limit headers
    res.set("X-RateLimit-Limit", "100");
    res.set("X-RateLimit-Remaining", result.remaining.toString());
 
    if (!result.allowed) {
      res.set(
        "Retry-After",
        Math.ceil(result.retryAfter / 1000).toString()
      );
      res.status(429).json({
        error: "Too Many Requests",
        retryAfter: Math.ceil(result.retryAfter / 1000),
      });
      return;
    }
 
    next();
  };
}
 
// ❌ Same rate limit for all endpoints
// app.use(rateLimitMiddleware(globalLimiter));
 
// ✅ Different limits for different endpoints
// app.use("/api/auth/login", rateLimitMiddleware(strictLimiter));   // 5/min
// app.use("/api/search", rateLimitMiddleware(searchLimiter));       // 30/min
// app.use("/api", rateLimitMiddleware(defaultLimiter));             // 100/min

Choosing the Right Algorithm

tstypescript

const algorithmComparison = {
  fixedWindow: {
    accuracy: "Low — boundary burst problem",
    memory: "O(1) per key",
    complexity: "Simple",
    bestFor: "Non-critical rate limiting, analytics quotas",
  },
  slidingWindowLog: {
    accuracy: "High — no boundary issues",
    memory: "O(n) per key (stores all timestamps)",
    complexity: "Moderate",
    bestFor: "Low-volume, high-accuracy needs",
  },
  slidingWindowCounter: {
    accuracy: "Good — weighted average eliminates most bursts",
    memory: "O(1) per key",
    complexity: "Moderate",
    bestFor: "General purpose API rate limiting",
  },
  tokenBucket: {
    accuracy: "Good — controlled bursts by design",
    memory: "O(1) per key",
    complexity: "Moderate",
    bestFor: "APIs where bursts are acceptable (CDN, uploads)",
  },
};

Key Takeaways

Fixed window is simple but allows boundary bursts — use it when approximate limiting is acceptable; for strict enforcement, use sliding window or token bucket
Token bucket allows controlled bursts — it naturally supports bursty traffic patterns while enforcing a sustained average rate
Use Redis for distributed rate limiting — in-memory limiters fail with multiple server instances; Lua scripts in Redis provide atomic operations
Always return rate limit headers — X-RateLimit-Limit, X-RateLimit-Remaining, and Retry-After help clients self-regulate without hitting limits
Apply different limits to different endpoints — login endpoints need strict limits (5/min), search might need 30/min, and general API endpoints 100/min

Building a Rate Limiter From Scratch

Fixed Window Rate Limiter

Sliding Window Log Rate Limiter

Token Bucket Algorithm

Distributed Rate Limiting with Redis

Choosing the Right Algorithm

Key Takeaways

Related Posts

Building a GraphQL Server From Scratch

Building a URL Shortener from Scratch

Building a Full-Stack Type-Safe API with tRPC and Next.js