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

#backend#api-design#performance

Jede öffentliche API braucht irgendwann Rate Limiting, und der Algorithmus, den du nimmst, entscheidet, ob "100 Requests pro Minute" tatsächlich bedeutet, wia's klingt. Zwoa Ansätze dominieren in da Praxis - Token Bucket und Sliding Window - und sie verhoitn si an den Rändern unterschiedlich, auf eine Art, de zählt, sobois echter Traffic sie trifft.

Warum "Requests pro Minute" kniffliger is, ois es klingt

Der naive Ansatz is a Fixed Window: Requests in da aktuellen Kalenderminute zähln, den Zähler zruckstelln, wenn die Minute umschlägt. Es is einfach zum Implementiern und leicht zum Durchdenkn - bis a Client um 0:59 100 Requests schickt und um 1:00 nochamoi 100. Dein Limiter hot 100/Minute erlaubt, aber da Server hot grod 200 Requests in zwoa Sekunden kriagt. Fixed Windows leckn an der Grenze.

Token Bucket und Sliding Window gibt's beide, um die Lücke zu schließn, zu unterschiedlichen Kosten bei Speicher und Präzision.

Token Bucket: Aus ana sich auffüllenden Reserve ausgebn

A Token Bucket hoit a maximale Anzoi an Tokens. Jeder Request verbraucht oan Token; Tokens füllen si kontinuierlich mit fester Rate auf. Wenn der Bucket leer is, wird der Request abglehnt (oda in a Queue gstöt). Die zentrale Eigenschaft: Bursts sand bis zur Bucket-Größe erlaubt, aber der durchschnittliche Durchsatz wird durch die Auffü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 ka Timer lauft - #refill() berechnet einfach, wie vül Tokens sich seit der letztn Prüfung angesammelt hättn, auf Basis der verstrichenen Zeit. Das mocht das Ganze zustandslos zwischn Requests, außer tokens und lastRefill, was genau des is, wos du willst, wenn dieser State in Redis hinter ana verteilten API lebt.

Sliding Window: Zähln, wos tatsächlich kürzlich passiert is

Das Sliding Window Log trackt die tatsächlichen Zeitstempel von kürzlichen Requests und zählt, wie vül davon ins nachlaufende Fenster fallen, genau jetzt - ned in an festen Kalender-Bucket. Es is der genaueste Ansatz, weil er direkt "wie vül Requests sand in den letztn 60 Sekunden passiert" beantwortet, ohne Grenzleck.

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

Die Kosten sand Speicher: Du speicherst pro Request im Fenster an Zeitstempel, pro Client. Bei hohem Request-Volumen summiert sich des, drum nutzen Produktivsysteme öfter Sliding Window Counter - a Hybrid, der zwoa Fixed-Window-Zähler (aktuell und vorherig) hoitet und a gewichtete Schätzung vom gleitenden Zählstand berechnet, statt jeden Zeitstempel zu speichern:

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

Des tauscht a klans Stückl Präzision gegn O(1)-Speicher pro Client statt O(Requests).

Zwischen ihnen wählen

Token Bucket, wenn Bursts in Ordnung sand und es dir eigentlich um den durchschnittlichen Durchsatz geht - z. B. um an nachgelagerten Service zu schützn, der kurze Spitzen verträgt, aber ka Dauerlast.
Sliding Window Log, wennst exakte Durchsetzung brauchst und die Client-Zoi niedrig gnua is, dass Speichern pro Zeitstempel billig is - z. B. a klane Zoi an hochwertigen API-Keys.
Sliding Window Counter, wennst Genauigkeit wia beim gleitenden Fenster im großen Stil brauchst und a klane Näherungsabweichung an den Fenstergrenzen verträgst.

A Fixed Window is allein selten die richtige Produktivwahl - greif nur dazu, wenn dir Boundary-Bursts wirklich wurscht sand, wia bei groben Tagesquoten.

Wo der State tatsächlich lebt

Koaner dieser Algorithmen is interessant, bevor du bedenkst, dass deine API fast sicher auf mehr als oam Server lauft. A Token Bucket oda Zeitstempel-Log im Speicher von oam einzelnen Prozess begrenzt nur Requests, de diesen oan Prozess treffen - a Client kann N mal dei beabsichtigtes Limit kriagn, indem er Requests auf N Instanzen verteilt.

Die Standardlösung is, den Zähler in Redis zu zentralisiern, mit INCR und PEXPIRE für an Fixed-/Sliding-Window-Zähler, oda mit am Lua-Skript für a atomares Token-Bucket-Check-and-Decrement:

// 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;
}

Der count === 1-Check setzt das Ablaufdatum nur beim ersten Request in am neichn Fenster - jeder weitere INCR erhöht einfach den bestehenden Zähler, bis er abläuft und der Zyklus neu startet.

Vergiss ned, es dem Client zum sogn

Egal, wöchan Algorithmus du nimmst, gib Standard-Header zruck, damit brave Clients von söba abbremsn kinnan, statt auf dich einzuhämmern, bis's a 429 kriagn:

X-RateLimit-Limit - die Obergrenze.
X-RateLimit-Remaining - wia vül im aktuellen Fenster no übrig is.
Retry-After - Sekunden, bis sich a neicher Versuch lohnt, mitgschickt mit der 429-Antwort.

Fazit

Fixed Windows sand einfach und leckn an der Grenze. Token Bucket erlaubt kontrollierte Bursts gegenüber ana Durchschnittsrate. Sliding Window Log is exakt, aber speicherhungrig; Sliding Window Counter nähern es billig im großen Stil an. Wähl danach, ob Bursts akzeptabel sand und wia präzise die Durchsetzung sei muass - und stell dann sicher, dass der Zähler irgendwo lebt, wo olle deine Server ihn sehn.