Rate-Limiting-Algorithmen: Token Bucket vs. Sliding Window

#backend#api-design#performance

Jede öffentliche API braucht irgendwann Rate Limiting, und der gewählte Algorithmus entscheidet, ob „100 Anfragen pro Minute" tatsächlich das bedeutet, wonach es klingt. Zwei Ansätze dominieren in der Praxis – Token Bucket und Sliding Window –, und sie verhalten sich an den Rändern auf eine Weise unterschiedlich, die relevant wird, sobald echter Traffic darauf trifft.

Warum „Anfragen pro Minute" kniffliger ist, als es klingt

Der naive Ansatz ist ein festes Fenster: Anfragen in der aktuellen Kalenderminute zählen, den Zähler zurücksetzen, wenn die Minute umspringt. Das ist einfach zu implementieren und leicht nachzuvollziehen – bis ein Client um 0:59 100 Anfragen und um 1:00 noch einmal 100 sendet. Dein Limiter hat 100/Minute erlaubt, aber der Server hat gerade 200 Anfragen in zwei Sekunden bekommen. Feste Fenster lecken an der Grenze.

Token Bucket und Sliding Window existieren beide, um diese Lücke zu schließen, zu unterschiedlichen Kosten bei Speicher und Präzision.

Token Bucket: aus einem sich auffüllenden Vorrat ausgeben

Ein Token Bucket hält eine maximale Anzahl Tokens. Jede Anfrage verbraucht ein Token; Tokens füllen sich kontinuierlich mit fester Rate nach. Ist der Bucket leer, wird die Anfrage abgelehnt (oder in eine Warteschlange gestellt). Die entscheidende Eigenschaft: Bursts sind bis zur Bucket-Größe erlaubt, aber der durchschnittliche Durchsatz wird durch die Nachfüllrate begrenzt.

class TokenBucket {
  constructor(capacity, refillPerSecond) {
    this.capacity = capacity;
    this.tokens = capacity;
    this.refillPerSecond = refillPerSecond;
    this.lastRefill = Date.now();
  }

  #refill() {
    const now = Date.now();
    const elapsedSeconds = (now - this.lastRefill) / 1000;
    this.tokens = Math.min(this.capacity, this.tokens + elapsedSeconds * this.refillPerSecond);
    this.lastRefill = now;
  }

  tryConsume(count = 1) {
    this.#refill();
    if (this.tokens >= count) {
      this.tokens -= count;
      return true;
    }
    return false;
  }
}

const bucket = new TokenBucket(20, 5); // burst of 20, refills at 5/sec
if (bucket.tryConsume()) {
  handleRequest();
} else {
  respondWithTooManyRequests();
}

Beachte, dass im Hintergrund kein Timer läuft – #refill() berechnet nur, wie viele Tokens sich seit der letzten Prüfung angesammelt hätten, anhand der vergangenen Zeit. Dadurch ist das Ganze zwischen Anfragen zustandslos bis auf tokens und lastRefill, was genau das ist, was man will, wenn dieser Zustand in Redis hinter einer verteilten API liegt.

Sliding Window: zählen, was kürzlich tatsächlich passiert ist

Das Sliding-Window-Log verfolgt die tatsächlichen Zeitstempel der letzten Anfragen und zählt, wie viele davon jetzt in das nachlaufende Fenster fallen – nicht in einen festen Kalender-Bucket. Es ist der genaueste Ansatz, weil er direkt „wie viele Anfragen gab es in den letzten 60 Sekunden" beantwortet, ohne Leck an der Grenze.

class SlidingWindowLog {
  constructor(limit, windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
    this.timestamps = [];
  }

  tryConsume() {
    const now = Date.now();
    const cutoff = now - this.windowMs;
    this.timestamps = this.timestamps.filter((t) => t > cutoff);

    if (this.timestamps.length < this.limit) {
      this.timestamps.push(now);
      return true;
    }
    return false;
  }
}

const limiter = new SlidingWindowLog(100, 60_000); // 100 requests per rolling 60s

Der Preis ist Speicher: Man speichert pro Anfrage im Fenster einen Zeitstempel, pro Client. Bei hohem Anfragevolumen summiert sich das, weshalb Produktivsysteme häufiger Sliding-Window-Zähler verwenden – einen Hybrid, der zwei Zähler fester Fenster (aktuell und vorheriges) hält und eine gewichtete Schätzung der gleitenden Anzahl berechnet, statt jeden Zeitstempel zu speichern:

function slidingWindowCount(currentCount, previousCount, elapsedInCurrentWindowMs, windowMs) {
  const weightOfPrevious = 1 - elapsedInCurrentWindowMs / windowMs;
  return currentCount + previousCount * weightOfPrevious;
}

Das tauscht ein wenig Präzision gegen O(1) Speicher pro Client statt O(Anfragen).

Zwischen ihnen wählen

Token Bucket, wenn Bursts in Ordnung sind und es eigentlich um den durchschnittlichen Durchsatz geht – z. B. beim Schutz eines nachgelagerten Dienstes, der kurze Spitzen verkraftet, aber keine dauerhafte Last.
Sliding-Window-Log, wenn exakte Durchsetzung nötig ist und die Client-Anzahl niedrig genug, dass Zeitstempel-Speicherung billig ist – z. B. bei wenigen hochwertigen API-Keys.
Sliding-Window-Zähler, wenn man Genauigkeit eines gleitenden Fensters im großen Maßstab braucht und einen kleinen Näherungsfehler an den Fenstergrenzen verkraften kann.

Ein festes Fenster ist allein selten die richtige Produktionswahl – greife nur dazu, wenn dir Bursts an der Grenze wirklich egal sind, etwa bei groben Tageskontingenten.

Wo der Zustand tatsächlich lebt

Keiner dieser Algorithmen ist interessant, bevor man bedenkt, dass deine API mit ziemlicher Sicherheit auf mehr als einem Server läuft. Ein Token Bucket oder Zeitstempel-Log im Speicher eines einzelnen Prozesses begrenzt nur Anfragen an diesen einen Prozess – ein Client kann das N-Fache deines beabsichtigten Limits erreichen, indem er Anfragen auf N Instanzen verteilt.

Die Standardlösung ist, den Zähler in Redis zu zentralisieren, mit INCR samt PEXPIRE für einen Zähler mit festem/gleitendem Fenster oder einem Lua-Skript für eine atomare Token-Bucket-Prüfung und -Verringerung:

// Atomic fixed-window counter in Redis
async function isAllowed(redisClient, key, limit, windowSeconds) {
  const count = await redisClient.incr(key);
  if (count === 1) {
    await redisClient.expire(key, windowSeconds);
  }
  return count <= limit;
}

Die Prüfung count === 1 setzt das Ablaufdatum nur bei der ersten Anfrage in einem neuen Fenster – jedes weitere INCR erhöht nur den bestehenden Zähler, bis er abläuft und der Zyklus von vorn beginnt.

Vergiss nicht, es dem Client zu sagen

Welchen Algorithmus du auch wählst: Gib Standard-Header zurück, damit sich wohlerzogene Clients selbst zurückhalten können, statt dich zu bombardieren, bis sie ein 429 bekommen:

X-RateLimit-Limit – die Obergrenze.
X-RateLimit-Remaining – wie viel im aktuellen Fenster übrig ist.
Retry-After – Sekunden, bis sich ein neuer Versuch lohnt, zusammen mit der 429-Antwort gesendet.

Fazit

Feste Fenster sind einfach und lecken an der Grenze. Token Bucket erlaubt kontrollierte Bursts gegen eine Durchschnittsrate. Das Sliding-Window-Log ist exakt, aber speicherhungrig; Sliding-Window-Zähler nähern es im großen Maßstab billig an. Wähle danach, ob Bursts akzeptabel sind und wie präzise die Durchsetzung sein muss – und sorge dann dafür, dass der Zähler dort lebt, wo ihn alle deine Server sehen können.