Token Bucket, Leaky Bucket und Sliding Window: wie sich Rate-Limiter-Algorithmen unterscheiden

Worum es geht

Die Strategie-Seite (welcher Schlüssel, welche Header, welcher Status) wird an anderer Stelle behandelt; dieser Artikel vergleicht die Zählalgorithmen.

• Fixed Window: ein Zähler pro Schlüssel und Intervall, der an der Grenze zurückgesetzt wird. Am günstigsten, aber ein Client kann am Ende eines Fensters ein volles Limit ausschöpfen und am Anfang des nächsten ein weiteres: die doppelte nominelle Rate in kurzer Zeit.
• Sliding Log: den Zeitstempel jeder Anfrage aufbewahren und diejenigen innerhalb des nachlaufenden Intervalls zählen. Exakt; der Speicherbedarf wächst mit dem Volumen.
• Sliding-Window-Zähler: die Zählwerte des aktuellen und des vorherigen Fensters aufbewahren und das nachlaufende Intervall als previous * (1 - elapsed / window) + current schätzen. Näherungsweise, konstanter Speicherbedarf, kein Burst an der Fenstergrenze.
• Token Bucket: ein Bucket fasst bis zu einer Höchstzahl an Tokens und wird mit fester Rate wieder aufgefüllt; jede Anfrage entnimmt ein Token und wird zurückgewiesen, wenn keines mehr vorhanden ist. Envoys Konfiguration TokenBucket benennt genau diese Parameter: max_tokens, tokens_per_fill und fill_interval, und der Bucket startet gefüllt.
• Leaky Bucket: Anfragen gelangen in eine Warteschlange, die mit fester Rate abfliesst; die Warteschlange hat eine Kapazität, oberhalb derer Anfragen zurückgewiesen werden. nginx dokumentiert dies als Methode von limit_req, mit rate, einer burst-Grösse sowie nodelay oder delay, um zu wählen, ob überschüssige Anfragen innerhalb des Bursts auf die Rate verzögert oder sofort bedient werden.

Warum es wichtig ist

Der Algorithmus bestimmt die Burst-Toleranz, den Speicherbedarf pro Schlüssel und ob Clients eine Zurückweisung oder eine zusätzliche Latenz erleben. Clients, die bei einem Fixed-Window-Reset erneut versuchen, treffen gemeinsam ein; ein Token Bucket fängt einen kurzen Burst ab und erzwingt danach den Durchschnitt; ein verzögernder Leaky Bucket glättet die Backend-Last auf Kosten der Wartezeit in der Warteschlange.

So wird es angewendet

• Standardmässig einen Token Bucket pro Schlüssel verwenden: die Tokenanzahl und den letzten Auffüllzeitpunkt speichern, bei jeder Anfrage verzögert (lazy) auffüllen und die Aktualisierung atomar gestalten (ein Redis-Skript oder ein prozessinterner Lock).
• Die Bucket-Grösse auf den akzeptierten Burst und die Auffüllrate auf das dauerhafte Limit setzen; beide Werte dokumentieren.
• Einen Sliding-Window-Zähler verwenden, wenn die Zusage schlicht "N Anfragen pro Minute" lautet und Bursts an der Fenstergrenze nicht akzeptabel sind.
• Einen verzögernden Leaky Bucket vor einem Backend einsetzen, nicht am Edge, wo interaktive Clients ein schnelles 429 mit Retry-After bevorzugen.
• In einem verteilten Deployment den Zustand pro Schlüssel zentralisieren oder in Kauf nehmen, dass sich Limits pro Instanz mit der Anzahl Instanzen vervielfachen; für die Auffüll-Berechnung eine monotone Uhr verwenden.

Stolpersteine

Sprünge der Systemuhr verfälschen die Auffüll-Berechnung. Ein Bucket, der leer startet, blockiert jeden neuen Schlüssel, bis er sich füllt. Sliding Logs sind eine Angriffsfläche für den Speicherbedarf. Eine Schlüsselung nach Client-IP hinter NAT oder einem CDN begrenzt die falsche Gruppe. Undokumentierte Burst-Regeln zwingen wohlverhaltene Clients zum Raten.