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

1. Warum der konkrete Algorithmus tatsächlich einen Unterschied macht

Auf den ersten Blick lösen alle Rate-Limiting-Algorithmen dasselbe Problem: verhindern, dass ein Client mehr als eine festgelegte Anzahl Requests in einem Zeitraum absetzt. Bei genauerem Hinsehen unterscheiden sich die Algorithmen aber erheblich darin, wie sie mit Lastspitzen an Fenstergrenzen umgehen, wie viel Speicher sie pro Client benötigen und wie präzise sie das theoretische Limit tatsächlich durchsetzen. Ein naiv implementierter Algorithmus kann in der Praxis doppelt so viele Requests durchlassen wie das konfigurierte Limit vermuten lässt.

Für ein Symfony-Team, das Rate-Limiting über die eingebaute RateLimiter-Komponente oder eine eigene Redis-basierte Lösung umsetzt, lohnt sich deshalb ein genauer Blick auf die zugrundeliegende Strategie, statt sich blind auf die Standardkonfiguration einer Bibliothek zu verlassen. Die folgenden Abschnitte ordnen die vier verbreitetsten Algorithmen konkret ein und zeigen, wo jeweils die praktischen Fallstricke liegen.

2. Fixed Window: einfach, aber mit Burst-Problem an Fenstergrenzen

Fixed Window ist der einfachste Algorithmus: Für ein festes Zeitfenster, etwa jede volle Minute, wird ein Zähler geführt, der bei Überschreiten des Limits weitere Requests ablehnt und beim Fensterwechsel auf null zurückgesetzt wird. Die Implementierung ist trivial und speichereffizient, weil nur ein einzelner Zähler pro Client und Fenster benötigt wird, ohne dass einzelne Request-Zeitstempel gespeichert werden müssen.

Das strukturelle Problem zeigt sich an der Fenstergrenze: Ein Client kann kurz vor Ende eines Fensters das volle Limit ausschöpfen und direkt nach Fensterbeginn erneut das volle Limit, wodurch in einem sehr kurzen Zeitraum um die Fenstergrenze herum effektiv das Doppelte des konfigurierten Limits durchgesetzt werden kann. Für Systeme, die vor echten Lastspitzen schützen sollen, ist das eine gefährliche Lücke, die bei naiver Fixed-Window-Implementierung häufig übersehen wird.

<?php
// Fixed-Window-Rate-Limiting mit Redis (vereinfacht)
final class FixedWindowRateLimiter
{
    public function __construct(private readonly \Redis $redis) {}

    public function isAllowed(string $clientId, int $limit, int $windowSeconds): bool
    {
        $windowKey = sprintf('rl:%s:%d', $clientId, intdiv(time(), $windowSeconds));
        $count = $this->redis->incr($windowKey);

        if ($count === 1) {
            $this->redis->expire($windowKey, $windowSeconds);
        }

        return $count <= $limit;
    }
}

3. Sliding Window: das Fenstergrenzen-Problem entschärfen

Sliding Window Counter kombiniert zwei benachbarte Fixed-Window-Zähler gewichtet nach der verstrichenen Zeit im aktuellen Fenster, um eine glattere Annäherung an ein echtes gleitendes Fenster zu erreichen, ohne den vollen Speicheraufwand eines Sliding Logs zu benötigen. Die Formel gewichtet den Zähler des vorherigen Fensters mit dem Anteil, der noch in das aktuelle gleitende Fenster hineinreicht, plus den vollen Zähler des aktuellen Fensters.

Diese Näherung reduziert das Burst-Problem an Fenstergrenzen erheblich, ohne perfekt zu sein: In seltenen Randfällen kann die Gewichtung noch immer leicht abweichende Ergebnisse gegenüber einem exakten gleitenden Fenster liefern. Für die überwiegende Mehrheit praktischer API-Rate-Limiting-Anwendungsfälle ist diese Näherung aber genau genug, bei deutlich geringerem Speicherbedarf als ein vollständiges Sliding Log.

4. Sliding Log: exakte Präzision zum Preis des Speicherbedarfs

Sliding Log speichert den Zeitstempel jedes einzelnen Requests eines Clients und zählt bei jeder neuen Anfrage, wie viele Zeitstempel innerhalb des gleitenden Zeitfensters liegen, wobei ältere Zeitstempel außerhalb des Fensters kontinuierlich entfernt werden. Dieser Ansatz liefert absolut exakte Ergebnisse ohne jede Näherung, weil kein Rundungs- oder Gewichtungsfehler entsteht.

Der Preis dieser Präzision ist Speicherverbrauch, der linear mit der Anzahl erlaubter Requests pro Fenster wächst, statt eines einzelnen konstanten Zählers. Bei sehr hohen Limits (tausende Requests pro Minute und Client) wird dieser Speicheraufwand in Redis spürbar, weshalb Sliding Log meist nur bei niedrigen bis mittleren Limits oder bei Anwendungsfällen mit besonders hohen Präzisionsanforderungen eingesetzt wird.

<?php
// Sliding-Log-Rate-Limiting mit Redis Sorted Sets
final class SlidingLogRateLimiter
{
    public function __construct(private readonly \Redis $redis) {}

    public function isAllowed(string $clientId, int $limit, int $windowSeconds): bool
    {
        $key = "rl:log:{$clientId}";
        $now = microtime(true);
        $windowStart = $now - $windowSeconds;

        // Alte Eintraege ausserhalb des Fensters entfernen
        $this->redis->zRemRangeByScore($key, '-inf', (string) $windowStart);

        $count = $this->redis->zCard($key);
        if ($count >= $limit) {
            return false;
        }

        $this->redis->zAdd($key, $now, (string) $now);
        $this->redis->expire($key, $windowSeconds);
        return true;
    }
}

5. Token Bucket: kontrollierte Bursts statt starrer Fenster

Token Bucket funktioniert konzeptionell anders als die Fenster-basierten Algorithmen: Ein Eimer mit fester Kapazität wird kontinuierlich mit einer festen Rate an Tokens befüllt, jeder Request verbraucht ein Token, und ein Request wird nur abgelehnt, wenn der Eimer leer ist. Das erlaubt kontrollierte Bursts bis zur Eimerkapazität, gefolgt von einer gleichmäßigen, durch die Auffüllrate begrenzten Nutzung, statt einer starren Obergrenze pro festem Zeitfenster.

Dieses Verhalten passt besser zu realem Nutzerverhalten, bei dem kurze Anfragebündel (etwa beim Laden einer Seite mit mehreren parallelen API-Calls) normal und legitim sind, aber eine dauerhaft hohe Anfragerate verhindert werden soll. Token Bucket ist deshalb der Standardalgorithmus in vielen produktionsreifen API-Gateways und wird auch von Symfonys eingebauter RateLimiter-Komponente als Strategie unterstützt.

6. Rate-Limiting über mehrere Server-Instanzen hinweg

In-Memory-Rate-Limiting funktioniert nur, solange alle Requests eines Clients dieselbe Server-Instanz erreichen, was bei einer horizontal skalierten Symfony-Anwendung hinter einem Load Balancer praktisch nie garantiert ist. Ein zentraler Datenspeicher wie Redis ist deshalb für verteiltes Rate-Limiting praktisch unverzichtbar, da alle Instanzen gegen denselben, gemeinsamen Zählerstand prüfen müssen.

Diese Zentralisierung bringt eigene Herausforderungen mit: Race Conditions bei gleichzeitigen Zugriffen mehrerer Instanzen müssen durch atomare Redis-Operationen (INCR, Lua-Skripte) verhindert werden, und die Latenz des zentralen Speichers wird zum limitierenden Faktor für die Geschwindigkeit der Rate-Limit-Prüfung selbst, was bei sehr hohem Request-Volumen relevant werden kann.

7. Wie die Algorithmus-Wahl das Nutzererlebnis konkret beeinflusst

Ein zu starrer Algorithmus wie ein naives Fixed Window frustriert legitime Nutzer, die kurzzeitig mehr Anfragen brauchen (etwa beim initialen Laden eines Dashboards mit mehreren API-Calls), aber sonst weit unter dem Durchschnittslimit bleiben. Token Bucket mit ausreichender Eimerkapazität erlaubt genau diese Art von legitimen Bursts, ohne das Grundschutzniveau gegen dauerhaften Missbrauch zu senken.

Umgekehrt kann ein zu großzügig konfigurierter Token-Bucket-Eimer echten Missbrauch durch kurzzeitige, sehr hochfrequente Anfrageserien nicht mehr verhindern. Die richtige Balance zwischen Eimerkapazität und Auffüllrate erfordert deshalb, reales Nutzungsverhalten zu beobachten, statt Werte willkürlich zu wählen, idealerweise mit Monitoring, das die tatsächliche Verteilung von Request-Bursts sichtbar macht.

8. Rate-Limit-Status transparent über HTTP-Header kommunizieren

Unabhängig vom gewählten Algorithmus sollte ein API-Client über Standard-Header wie X-RateLimit-Limit, X-RateLimit-Remaining und X-RateLimit-Reset erfahren, wie viele Anfragen noch übrig sind und wann sich das Limit zurücksetzt, statt das Limit nur durch plötzliche 429-Fehler zu erfahren. Diese Transparenz erlaubt es gut implementierten Clients, ihre eigene Anfragerate proaktiv zu drosseln, statt wiederholt gegen das Limit zu laufen.

Bei Token Bucket ist X-RateLimit-Remaining direkt die aktuelle Eimerfüllung, bei Fenster-basierten Algorithmen die Differenz zwischen Limit und aktuellem Zählerstand im Fenster. Diese Werte konsistent und korrekt zu berechnen ist Teil einer gut gestalteten Rate-Limiting-Implementierung, nicht nur ein optionales Detail für besonders sorgfältige APIs.

9. Die vier Algorithmen im direkten Vergleich

Die folgende Tabelle fasst die wichtigsten Eigenschaften der vier Algorithmen zusammen, um die Wahl für den eigenen Anwendungsfall zu erleichtern.

10. Zusammenfassung

11. FAQ: Rate-Limiting-Algorithmen: Das Wichtigste auf einen Blick