Zum Inhalt springen
Tutorials

Einen Rate Limiter von Grund auf selbst bauen

Schritt-für-Schritt zu Rate Limitern mit Token Bucket, Sliding Window und Fixed Window — mit TypeScript, Redis-Integration und Produktionsmustern.

4 Min. Lesezeit
Diagramm des Token-Bucket-Algorithmus: Tokens werden mit fester Rate hinzugefügt und von eingehenden Anfragen verbraucht

Rate Limiter schützen APIs vor Missbrauch und sorgen für eine faire Verteilung der Ressourcen. Ob du Brute-Force-Angriffe auf Logins verhinderst, teure Operationen drosselst oder planbasierte Kontingente durchsetzt — wenn du verstehst, wie Rate Limiter intern funktionieren, kannst du sie besser konfigurieren und debuggen.

Dieses Tutorial baut drei Rate-Limiting-Algorithmen von Grund auf und zeigt anschließend, wie man sie mit Redis für verteilte Systeme in der Produktion einsetzt.

Rate Limiter mit festem Fenster (Fixed Window)

Der Fixed-Window-Algorithmus teilt die Zeit in feste Intervalle und zählt die Anfragen pro Intervall. Er ist der einfachste Ansatz, hat aber ein Burst-Problem an den Fenstergrenzen — ein Client kann das Doppelte des Limits senden, indem er Anfragen am Ende eines Fensters und am Anfang des nächsten zeitlich geschickt platziert.

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

Rate Limiter mit Sliding-Window-Log

Das Sliding-Window-Log führt eine sortierte Liste der Zeitstempel von Anfragen. Es zählt die Anfragen innerhalb der letzten N Sekunden ab dem aktuellen Zeitpunkt und beseitigt damit das Burst-Problem an den Fenstergrenzen.

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)

Der Token-Bucket-Algorithmus

Der Token Bucket erlaubt Bursts und setzt gleichzeitig eine durchschnittliche Rate durch. Tokens werden mit einer festen Rate hinzugefügt. Jede Anfrage verbraucht einen Token. Wenn der Bucket leer ist, werden Anfragen abgelehnt.

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

Verteiltes Rate Limiting mit Redis

In-Memory-Rate-Limiter versagen, sobald mehrere Server-Instanzen im Spiel sind. Redis stellt atomare Operationen für verteiltes Rate Limiting bereit.

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

Den richtigen Algorithmus auswählen

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)",
  },
};

Die wichtigsten Erkenntnisse

  1. Fixed Window ist einfach, erlaubt aber Bursts an den Fenstergrenzen — verwende es, wenn eine ungefähre Begrenzung ausreicht; für eine strikte Durchsetzung nutze Sliding Window oder Token Bucket
  2. Der Token Bucket erlaubt kontrollierte Bursts — er unterstützt auf natürliche Weise stoßartige Verkehrsmuster und hält dabei eine nachhaltige Durchschnittsrate ein
  3. Verwende Redis für verteiltes Rate Limiting — In-Memory-Limiter versagen bei mehreren Server-Instanzen; Lua-Skripte in Redis stellen atomare Operationen bereit
  4. Gib immer Rate-Limit-Header zurück — X-RateLimit-Limit, X-RateLimit-Remaining und Retry-After helfen Clients, sich selbst zu regulieren, ohne gegen Limits zu laufen
  5. Wende unterschiedliche Limits auf unterschiedliche Endpunkte an — Login-Endpunkte brauchen strikte Limits (5/min), die Suche eventuell 30/min und allgemeine API-Endpunkte 100/min
Wilfredo Rujel

Wilfredo Rujel

Full-Stack-Softwareentwickler

Diesen Beitrag teilenX

Ähnliche Beiträge