Algorithmen zur Ratenbegrenzung: Token Bucket und mehr

Detaillierter Einblick in Algorithmen zur Ratenbegrenzung mit Implementierungen, Abwägungen und der Wahl des richtigen Ansatzes für deine API.

Veröffentlicht am 19. Januar 2021Aktualisiert am 9. September 20264 Min. Lesezeit

rate-limiting algorithms api-design backend distributed-systems

Ratenbegrenzung schützt dein System vor Missbrauch und Überlastung, aber welcher Algorithmus dahintersteckt, entscheidet darüber, wie sie sich für legitime Nutzer anfühlt. Ein schlecht gewählter Begrenzer lässt entweder Burst-Traffic durch, wenn er das nicht sollte, oder drosselt normale Nutzungsmuster unnötig.

Die meisten Entwickler greifen zu einem einfachen Zähler — "100 Anfragen pro Minute" — ohne zu bedenken, wie dieser Zähler zurückgesetzt wird, ob Bursts akzeptabel sind und wie er sich über verteilte Server hinweg verhält. Die Wahl des Algorithmus wirkt sich direkt auf die Nutzererfahrung aus.

Fixed-Window-Zähler

Der einfachste Ansatz: Die Zeit wird in feste Fenster unterteilt, und die Anfragen werden pro Fenster gezählt.

tstypescript

class FixedWindowLimiter {
  private windows = new Map<string, { count: number; expiry: number }>();
 
  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.expiry) {
      this.windows.set(windowKey, {
        count: 1,
        expiry: windowStart + this.windowMs,
      });
      return true;
    }
 
    if (window.count >= this.maxRequests) return false;
    window.count++;
    return true;
  }
}

Das Problem: Bursts an der Fenstergrenze. Ein Client kann um 11:59:59 Uhr 100 Anfragen senden und um 12:00:00 Uhr weitere 100 — 200 Anfragen in 2 Sekunden, während er formal unter dem Limit von "100 pro Minute" bleibt.

tstypescript

// ❌ Fixed window boundary problem
// Window 1 (11:59:00-11:59:59): 100 requests at 11:59:58 ✅
// Window 2 (12:00:00-12:00:59): 100 requests at 12:00:01 ✅
// Result: 200 requests in 3 seconds — limit is effectively doubled

Fixed Window eignet sich für einfache Anwendungsfälle, bei denen gelegentliche Bursts akzeptabel sind. Für eine strengere Durchsetzung verwende Sliding Window.

Sliding-Window-Log

Erfasse den Zeitstempel jeder Anfrage und zähle, wie viele davon innerhalb des Fensters liegen. Genau, aber speicherintensiv.

tstypescript

class SlidingWindowLog {
  private logs = new Map<string, number[]>();
 
  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) {
      this.logs.set(key, timestamps);
      return false;
    }
 
    timestamps.push(now);
    this.logs.set(key, timestamps);
    return true;
  }
}

Dieser Ansatz ist absolut präzise — keine Bursts an der Fenstergrenze. Aber jeden Zeitstempel zu speichern ist teuer. Bei 1000 Anfragen pro Minute und Nutzer speicherst du 1000 Zeitstempel pro Nutzer im Arbeitsspeicher.

Sliding-Window-Zähler

Ein Hybrid, der die Effizienz von Fixed Window mit der Genauigkeit von Sliding Window verbindet. Er interpoliert zwischen zwei benachbarten festen Fenstern, je nachdem, wie weit du dich bereits im aktuellen Fenster befindest.

tstypescript

class SlidingWindowCounter {
  private windows = new Map<string, number>();
 
  constructor(
    private maxRequests: number,
    private windowMs: number
  ) {}
 
  isAllowed(key: string): boolean {
    const now = Date.now();
    const currentWindow = Math.floor(now / this.windowMs);
    const previousWindow = currentWindow - 1;
    const elapsed = (now % this.windowMs) / this.windowMs;
 
    const currentKey = `${key}:${currentWindow}`;
    const previousKey = `${key}:${previousWindow}`;
 
    const currentCount = this.windows.get(currentKey) ?? 0;
    const previousCount = this.windows.get(previousKey) ?? 0;
 
    // Weighted sum: full current + proportional previous
    const estimatedCount = currentCount + previousCount * (1 - elapsed);
 
    if (estimatedCount >= this.maxRequests) return false;
 
    this.windows.set(currentKey, currentCount + 1);
    return true;
  }
}

Das ist der Sweet Spot für die meisten APIs: O(1) Speicher pro Nutzer (zwei Zähler), kein Burst-Problem an der Fenstergrenze und eine nahezu exakte Zählung.

Token Bucket

Token Bucket erlaubt kontrollierte Bursts und erzwingt gleichzeitig eine durchschnittliche Rate. Tokens werden mit einer konstanten Rate hinzugefügt. Jede Anfrage verbraucht ein Token. Keine Tokens, keine Anfrage. Der Bucket kann Tokens bis zu einem Maximum ansammeln, wodurch kurze Bursts möglich werden.

tstypescript

class TokenBucket {
  private tokens: number;
  private lastRefill: number;
 
  constructor(
    private capacity: number,
    private refillRate: number, // tokens per second
  ) {
    this.tokens = capacity;
    this.lastRefill = Date.now();
  }
 
  isAllowed(cost: number = 1): boolean {
    this.refill();
 
    if (this.tokens >= cost) {
      this.tokens -= cost;
      return true;
    }
    return false;
  }
 
  private refill(): void {
    const now = Date.now();
    const elapsed = (now - this.lastRefill) / 1000;
    this.tokens = Math.min(
      this.capacity,
      this.tokens + elapsed * this.refillRate
    );
    this.lastRefill = now;
  }
}
 
// Example: 10 tokens max, refills at 2/sec
// Burst of 10 requests: allowed immediately
// Then: 2 requests per second sustained
const limiter = new TokenBucket(10, 2);

Token Bucket eignet sich ideal, wenn du Bursts zulassen willst (etwa Seitenaufrufe, die mehrere API-Aufrufe auslösen), aber den dauerhaften Durchsatz begrenzen möchtest. AWS und die meisten Cloud-Anbieter setzen auf diesen Ansatz.

Verteilte Ratenbegrenzung mit Redis

Begrenzer im Arbeitsspeicher versagen, sobald deine Anwendung auf mehreren Servern läuft. Redis bietet atomare Operationen für gemeinsam genutzten Zustand.

tstypescript

import { Redis } from 'ioredis';
 
class RedisRateLimiter {
  constructor(
    private redis: Redis,
    private maxRequests: number,
    private windowSec: number
  ) {}
 
  async isAllowed(key: string): Promise<{ allowed: boolean; remaining: number }> {
    const redisKey = `ratelimit:${key}`;
 
    // Atomic increment + expire using a Lua script
    const result = await this.redis.eval(
      `
      local current = redis.call('INCR', KEYS[1])
      if current == 1 then
        redis.call('EXPIRE', KEYS[1], ARGV[1])
      end
      return current
      `,
      1,
      redisKey,
      this.windowSec
    ) as number;
 
    return {
      allowed: result <= this.maxRequests,
      remaining: Math.max(0, this.maxRequests - result),
    };
  }
}

Das Lua-Skript läuft in Redis atomar ab — es gibt keine Race Conditions zwischen den Aufrufen von INCR und EXPIRE. Das ist entscheidend, wenn sich mehrere Anwendungsserver denselben Begrenzer teilen.

Antwort-Header

Clients müssen ihren Ratenlimit-Status kennen. Gib bei jeder Antwort die Standard-Header zurück.

tstypescript

// ❌ No rate limit headers — client has no idea why requests fail
app.use((req, res, next) => {
  if (!limiter.isAllowed(req.ip)) {
    return res.status(429).json({ error: 'Too many requests' });
  }
  next();
});
 
// ✅ Informative headers — client can adapt behavior
app.use(async (req, res, next) => {
  const result = await limiter.isAllowed(req.ip);
 
  res.set({
    'X-RateLimit-Limit': String(limiter.maxRequests),
    'X-RateLimit-Remaining': String(result.remaining),
    'X-RateLimit-Reset': String(result.resetAt),
    'Retry-After': result.allowed ? undefined : String(result.retryAfter),
  });
 
  if (!result.allowed) {
    return res.status(429).json({
      error: 'Rate limit exceeded',
      retryAfter: result.retryAfter,
    });
  }
  next();
});

Der Retry-After-Header teilt wohlerzogenen Clients genau mit, wann sie es erneut versuchen sollten. Ohne ihn bestürmen Clients den Server entweder mit Wiederholungsversuchen oder warten unnötig lange.

Den richtigen Algorithmus wählen

Algorithmus	Umgang mit Bursts	Speicher	Genauigkeit	Am besten für
Fixed Window	Erlaubt das Doppelte	O(1)	Niedrig	Einfache Fälle, interne APIs
Sliding Window Log	Exakt	O(n)	Perfekt	Kleine Anfragevolumen
Sliding Window Counter	Gut	O(1)	Sehr gut	Die meisten API-Ratenbegrenzungen
Token Bucket	Explizit	O(1)	Gut	Burst-tolerante öffentliche APIs

Für die meisten Web-APIs bietet der Sliding-Window-Zähler die beste Balance. Bei APIs, bei denen Burst-Toleranz ein gewünschtes Merkmal ist (Datei-Uploads, Batch-Operationen), verwende Token Bucket.

Die wichtigsten Erkenntnisse

Fixed Window hat ein Problem mit Bursts an der Fenstergrenze — der Traffic kann sich an Fenstergrenzen verdoppeln
Der Sliding-Window-Zähler ist die beste Standardwahl — O(1) Speicher bei nahezu perfekter Genauigkeit
Token Bucket eignet sich ideal für Burst-tolerante APIs — er steuert Burst-Größe und dauerhafte Rate explizit
Nutze Redis für verteilte Ratenbegrenzung — Lua-Skripte sichern Atomarität über mehrere Server hinweg
Gib immer Ratenlimit-Header zurück — X-RateLimit-Remaining und Retry-After ermöglichen wohlerzogene Clients

Algorithmen zur Ratenbegrenzung: Token Bucket und mehr

Fixed-Window-Zähler

Sliding-Window-Log

Sliding-Window-Zähler

Token Bucket

Verteilte Ratenbegrenzung mit Redis

Antwort-Header

Den richtigen Algorithmus wählen

Die wichtigsten Erkenntnisse

Ähnliche Beiträge

API-Ratenbegrenzung: Algorithmen und Implementierung

Idempotente APIs: Anfragen sicher wiederholen

Idempotenz im API-Design: Sichere Wiederholungen