API-Rate-Limiting: Token-Bucket, Sliding Window und Redis

Veröffentlicht

12. Oktober 2026

Autor

Faizan Nadeem

Die Grundlagen

Was ein Rate Limiter tatsächlich entscheidet

Im Kern beantwortet jeder Rate-Limiting-Algorithmus für jede eingehende Anfrage eine Frage: Wie viele Anfragen hat dieser Client in letzter Zeit bereits gemacht – sollte diese durchgelassen oder mit einem 429 Too Many Requests abgelehnt werden? Jeder Algorithmus in diesem Beitrag beantwortet diese Frage unterschiedlich – einige verfolgen eine harte Anzahl in einem festen Zeitslot, einige verfolgen eine kontinuierlich auffüllende Zulage, einige verfolgen einen glatt gewichteten Durchschnitt über zwei benachbarte Fenster – aber die Schnittstelle, die jeder von ihnen deiner Anwendung bietet, ist dieselbe: erlauben oder ablehnen, und normalerweise auch wann der Client es erneut versuchen sollte.

Warum die Algorithmenwahl tatsächlich wichtig ist

Grenzverhalten unterscheidet sich stark. Ein Client, der unter einem angegebenen Limit bei einem Algorithmus liegt, kann bei einem anderen weit darüber bursten, nur aufgrund dessen, wie jeder Algorithmus die Kante eines Zeitfensters behandelt.
Burst-Toleranz ist eine Produktentscheidung, nicht nur eine technische. Einige APIs wollen, dass ein Client sein gesamtes Kontingent für eine Minute in einem schnellen Burst aufbrauchen kann und dann still ist; andere wollen den Traffic gleichmäßig verteilt. Das ist eine Algorithmenwahl, keine Konfigurationsanpassung.
Fehler zu machen ist unsichtbar, bis es nicht mehr so ist. Ein Rate-Limiter, der nur „meistens" funktioniert, sieht bei normalem Traffic identisch aus wie ein korrekter – der Unterschied zeigt sich nur unter gleichzeitiger Last oder direkt bei Missbrauchsschwellen, genau dann, wenn er tatsächlich halten soll.

Die vollständige Architektur

        client request
              │
              ▼
   ┌─────────────────────┐
   │  rate limit middleware │──── ask: allowed?
   └─────────┬───────────┘
              │
              ▼
   ┌─────────────────────┐
   │   Redis (shared state) │  ← atomic INCR / Lua script
   │   key: user:123:bucket │     so every API replica
   └─────────────────────┘     agrees on the same count
              │
      allow ──┴── deny (429)

Das Leitprinzip: Der Algorithmus definiert die Mathematik davon, wann eine Anfrage erlaubt wird, aber die Storage-Schicht definiert, ob diese Mathematik tatsächlich korrekt ist, sobald mehr als ein Prozess sie gleichzeitig auswertet. Macht man die Storage-Schicht falsch, verliert der beste Algorithmus der Welt trotzdem.

Erläuterung der Core-Layer

1. Fixed Window Counter

Was es ist: Teile die Zeit in feste Slots auf (z.B. jeden 00:00–00:59 jeder Minute) und zähle Anfragen gegen den Slot, in den die aktuelle Zeit fällt. Wenn die Slot-Anzahl das Limit überschreitet, ablehnen; wenn die Uhr in einen neuen Slot tickt, wird der Zähler auf null zurückgesetzt.

Warum es wichtig ist: Es ist der einfachste Algorithmus zu implementieren – ein einzelner Zähler mit einem TTL – und aus diesem Grund immer noch der häufigste in der freien Wildbahn. Aber er hat einen bekannten Grenzfehler: Ein Client kann sein volles Limit in der letzten Sekunde eines Fensters senden, dann sein volles Limit in der ersten Sekunde des nächsten senden, und erhält effektiv das Doppelte der vorgesehenen Rate über die zwei Sekunden, die die Grenze überspannen.

Produktionstipp: Fixed Window ist für grobe, großzügige Limits in Ordnung (10.000 Anfragen/Stunde auf einem Free Tier), bei denen ein 2x-Grenz-Burst nicht wesentlich schadet. Es ist die falsche Wahl für enge Limits, bei denen dieser Burst tatsächlich wichtig ist, wie einem Login-Versuch-Limiter.

2. Sliding Window Log

Was es ist: Speichere einen Zeitstempel für jede Anfrage, die ein Client macht, und zähle bei jeder neuen Anfrage, wie viele gespeicherte Zeitstempel in das hintere Fenster fallen (z.B. die letzten 60 Sekunden von jetzt, nicht eine feste Uhruhrzeit), und verwerfe alles Ältere.

Warum es wichtig ist: Das ist der genaueste Algorithmus – überhaupt kein Grenzfehler, da das Fenster immer relativ zum aktuellen Moment ist. Die Kosten sind der Speicher: eine wachsende Liste von Zeitstempeln pro Client statt einer einzelnen Ganzzahl, was bei Scale schwerer ist.

Produktionstipp: Redis’s Sorted Sets (ZADD, ZREMRANGEBYSCORE, ZCARD) implementieren das sauber – score jeden Eintrag nach seinem Zeitstempel, trimme alles außerhalb des Fensters und zähle, was übrig ist. Es ist präzise, aber kalkuliere extra Speicher pro verfolgtem Client im Vergleich zu einem einzelnen Zähler ein.

3. Sliding Window Counter

Was es ist: Ein praktischer Kompromiss: Halte zwei Fixed-Window-Counter (das aktuelle Fenster und das vorherige) und schätze den Sliding-Count als gewichtete Mischung beider, basierend darauf, wie weit du im aktuellen Fenster bist.

Warum es wichtig ist: Das gibt dir den Großteil der Genauigkeit eines vollen Sliding Logs – der Grenz-Burst-Fehler ist dramatisch reduziert, nicht vollständig eliminiert – bei niedrigen Speicherkosten auf zwei Ganzzahlen pro Client statt einer wachsenden Zeitstempelliste. Es ist der Algorithmus, den die meisten Rate-Limiting-Bibliotheken (einschließlich den Standard-Implementierungen von Cloudflare und Kong) tatsächlich liefern, weil es das beste Genauigkeits-zu-Kosten-Verhältnis für die meisten APIs ist.

Produktionstipp: Das ist ein vernünftiger Standard, wenn man keinen spezifischen Grund hat, zu Token Bucket oder einem vollen Sliding Log zu greifen – es ist günstig, nah genug an genau und einfach zu verstehen.

4. Token Bucket

Was es ist: Jeder Client hat einen Eimer mit bis zu einer maximalen Anzahl von Tokens. Tokens füllen sich mit einer gleichmäßigen Rate auf (sagen wir, einer alle 100ms für ein 10 Req/s-Limit), und jede Anfrage verbraucht einen. Ein leerer Eimer lehnt die Anfrage ab; ein voller lässt einen Client den ganzen Eimer in einem schnellen Burst ausgeben.

Warum es wichtig ist: Token Bucket ist der einzige Algorithmus in dieser Liste, der absichtlich kontrollierten Bursting erlaubt – ein Client, der untätig war, kann sofort die volle Anzahl Requests eines vollen Eimers abfeuern, dann muss er warten, bis Tokens wieder aufgefüllt werden. Das ist ein Feature, kein Bug, für APIs, bei denen legitime Clients genuinlich bursten (eine mobile App, die nach dem Offline-Sein synchronisiert, ein Dashboard, das mehrere Widgets auf einmal lädt), du aber trotzdem eine harte Grenze für die nachhaltige Rate brauchst.

Produktionstipp: Stimme Bucket-Kapazität und Auffüllrate als zwei separate Knöpfe ab – Kapazität kontrolliert, wie viel Burst du tolerierst, Auffüllrate kontrolliert die langfristige nachhaltige Rate. Sie in eine einzige „Anfragen pro Minute"-Zahl zu kollabieren verliert diese Flexibilität.

5. Leaky Bucket

Was es ist: Das Gegenteil von Token Bucket – Anfragen treten in eine Warteschlange (den „Eimer") ein und werden mit einer streng konstanten Rate verarbeitet (sie „lecken aus"), unabhängig davon, wie burstig die Ankünfte waren. Ein voller Eimer lässt neue Anfragen fallen.

Warum es wichtig ist: Leaky Bucket erzwingt eine genuinlich glatte Ausgaberate, was wichtig ist, wenn man der ist, der eine Rate-limitierte nachgelagerte API aufruft und garantieren muss, deren Limit nie zu überschreiten, statt nur eingehenden Traffic zu begrenzen. Es ist seltener für API-seitiges Rate-Limiting, weil es Request-Queuing und Latenz hinzufügt statt einer schnellen Ablehnung.

Produktionstipp: Greife speziell auf Leaky Bucket zurück, wenn du ausgehenden Traffic zu einer Drittanbieter-API mit einem strengen Limit formst, nicht wenn du die eingehende Kante deiner eigenen API schützt – Token Bucket oder Sliding Window Counter passen für diesen Fall besser.

Durchgehende Erklärung

Verfolge einen Burst von Anfragen durch einen Token-Bucket-Rate-Limiter, der von Redis unterstützt wird, über zwei API-Replikas:

Client sendet 5 Anfragen in schneller Folge bei einem Limit von „10 Anfragen, Auffüllung mit 1/Sekunde." Beide Anfragen könnten auf einem der beiden API-Replikas hinter einem Load Balancer landen.
Replikas A erhält Anfrage 1. Es führt ein Lua-Script gegen Redis aus: aktuellen Token-Count lesen, seit dem letzten Auffüll-Zeitstempel hinzugefügte Tokens berechnen, eines für diese Anfrage abziehen, den neuen Count und Zeitstempel zurückschreiben – alles innerhalb einer atomaren Redis-Operation.
Replika B erhält Anfrage 2 ein paar Millisekunden später, bevor Replika As Schreibvorgang für ihn überhaupt relevant ist, weil beide Replikas gegen denselben Redis-Key arbeiten, nicht gegen ihren eigenen lokalen Speicher. Die Lua-Script-Ausführung von Replika B wird in die Warteschlange gestellt und ist atomar relativ zur von Replika A – Redis führt Befehls- (und Script-)Ausführung single-threaded aus, sodass es keine Race zwischen den beiden gibt.
Anfragen 3–5 setzen sich auf dieselbe Weise fort, jede dekrementiert denselben geteilten Counter unabhängig davon, welches Replikas sie verarbeitet.
Client sendet Anfrage 11 sofort danach. Der Eimer ist leer (10 Tokens verbraucht, Auffüllrate ist nur 1/Sekunde, und weniger als eine Sekunde ist vergangen) – das Lua-Script gibt „deny" zurück, und die API antwortet mit 429 und einem Retry-After-Header, der aus der Auffüllrate berechnet wird.
Eine Sekunde später kommt eine neue Anfrage an. Das Lua-Script berechnet die seit dem letzten Schreibvorgang vergangene Zeit, fügt einen aufgefüllten Token hinzu und erlaubt die Anfrage.

Sonderfälle

Per-User vs. Per-IP-Limiting. Authentifizierte Endpunkte sollten den Limiter nach Benutzer-ID, nicht nach IP, als Key verwenden – NAT und Unternehmens-Proxies stellen viele legitime Benutzer hinter einer IP, und ein Shared-IP-Limit bestraft alle für den Traffic eines Benutzers. Nicht-authentifizierte Endpunkte (Login, Registrierung, Passwort-Reset) fallen auf IP-basiertes Limiting zurück, weshalb Brute-Force-Login-Schutz seinen eigenen strengeren Limiter braucht, separat vom allgemeinen API-Limit.

Verteiltes Rate-Limiting über Replikas. Das ist der Kerngrund für Redis (oder einen anderen gemeinsamen Speicher) statt In-Memory-Countern: Jedes Replikas muss denselben Count beobachten, oder das effektive Limit skaliert mit deiner Replikas-Anzahl statt fest zu bleiben. Ein dict-basierter In-Memory-Limiter ist für einen Single-Prozess-Entwicklungsserver in Ordnung und aktiv falsch für alles horizontal Skalierte.

Burst-Erlaubnis für legitime spiky Clients. Eine mobile App, die Anfragen nach dem Wiederverbinden bündelt, oder ein Dashboard, das mehrere parallele Aufrufe beim Seitenladen abfeuert, braucht etwas Burst-Toleranz oder wird bei vollkommen legitimem Gebrauch rate-limited. Die separaten Kapazitäts-/Auffüllknöpfe von Token Bucket passen hier natürlich; ein strenges Sliding Window nicht.

Rate-Limiting innerhalb der Request-Verarbeitung selbst. Wenn deine API eine Anfrage akzeptiert und dann schwerere Arbeit an einen Hintergrundarbeiter übergibt – einen Bericht erstellen, eine Charge von E-Mails senden – gehört das Limit normalerweise auf den eingehenden Endpunkt, nicht den Hintergrundjob, da das der Punkt ist, an dem du tatsächlich die Zulassung kontrollierst.

Skalierung & Produktionsherausforderungen

Die Check-then-Increment-Race-Condition. Der einzige häufigste Bug in einem selbstgebauten Rate-Limiter: den aktuellen Count lesen, ihn gegen das Limit im Anwendungscode prüfen und erst dann ein separates Increment ausgeben – als zwei Round-Trips zu Redis statt einer atomaren Operation. Unter gleichzeitigen Anfragen können zwei Anfragen beide einen Count von 9 lesen (unter einem Limit von 10), beide entscheiden zu erlauben und beide inkrementieren – und lassen 11 statt 10 durch. Der Fix besteht darin, Lesen, Berechnen und Schreiben innerhalb eines einzigen Lua-Scripts (oder MULTI/EXEC-Transaktion oder Redis 7s OBJECT-Befehlserweiterungen) durchzuführen, sodass Redis’s Single-Threaded-Ausführungsmodell die gesamte Operation atomar macht.

Clock Drift über Replikas. Algorithmen, die auf Wanduhr-Zeitstempeln beruhen (Token Buckets Auffüllung, Sliding Windows Trimm-Grenze), sollten verstrichene Zeit mit Redis’s eigenem TIME-Befehl innerhalb des Lua-Scripts berechnen, nicht mit der lokalen Uhr jedes Replikas – ein paar Hundert Millisekunden Drift reichen aus, um die Auffüllmathe subtil falsch zu machen, wenn jedes Replikas seiner eigenen vertraut.

Redis als Single Point of Failure. Ein Limiter, der hart geschlossen scheitert, wenn Redis nicht erreichbar ist, verwandelt einen Redis-Ausfall in einen vollständigen API-Ausfall. Die meisten Produktions-Setups scheitern stattdessen offen – wenn Redis ausfällt, Anfragen durchlassen statt alles abzulehnen – da die Aufgabe eines Limiters die Verhinderung von Missbrauch ist, nicht ein zweiter Fehlerpunkt zu sein. Logge den Fehler in jedem Fall laut.

Key-Ablauf und Speicherwachstum. Jeder Client-Key braucht einen TTL leicht länger als sein Fenster, oder Redis akkumuliert einen Zähler für jeden Client, der jemals eine Anfrage gemacht hat und lässt ihn nie ablaufen. Setze ihn explizit (EXPIRE nach dem Schreibvorgang des Lua-Scripts) und überprüfe ihn immer dann, wenn du die Datenstruktur des Keys änderst – es ist einfach, bei einem späteren Refactor still zu vergessen.

Code-Beispiele

Ein Redis-backed Token Bucket als atomares Lua-Script, aufgerufen aus Python:

import time
import redis

r = redis.Redis(host="localhost", port=6379, decode_responses=True)

# KEYS[1] = bucket key
# ARGV[1] = capacity (max tokens)
# ARGV[2] = refill_rate (tokens per second)
# ARGV[3] = now (unix timestamp, float)
# ARGV[4] = requested tokens (usually 1)
TOKEN_BUCKET_SCRIPT = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

local bucket = redis.call("HMGET", key, "tokens", "last_refill")
local tokens = tonumber(bucket[1])
local last_refill = tonumber(bucket[2])

if tokens == nil then
    tokens = capacity
    last_refill = now
end

local elapsed = math.max(0, now - last_refill)
tokens = math.min(capacity, tokens + elapsed * refill_rate)

local allowed = 0
if tokens >= requested then
    tokens = tokens - requested
    allowed = 1
end

redis.call("HMSET", key, "tokens", tokens, "last_refill", now)
redis.call("EXPIRE", key, math.ceil(capacity / refill_rate) + 1)

return {allowed, tokens}
"""

_script = r.register_script(TOKEN_BUCKET_SCRIPT)


def is_allowed(client_id: str, capacity: int = 10, refill_rate: float = 1.0) -> tuple[bool, float]:
    now = time.time()
    allowed, remaining = _script(
        keys=[f"ratelimit:{client_id}"],
        args=[capacity, refill_rate, now, 1],
    )
    return bool(allowed), float(remaining)

Als FastAPI-Middleware eingebunden:

from fastapi import FastAPI, Request
from fastapi.responses import JSONResponse

app = FastAPI()


@app.middleware("http")
async def rate_limit_middleware(request: Request, call_next):
    client_id = request.headers.get("x-api-key", request.client.host)
    allowed, remaining = is_allowed(client_id, capacity=10, refill_rate=1.0)

    if not allowed:
        return JSONResponse(
            status_code=429,
            content={"detail": "rate limit exceeded"},
            headers={"Retry-After": "1"},
        )

    response = await call_next(request)
    response.headers["X-RateLimit-Remaining"] = str(int(remaining))
    return response

Eine schnelle Gleichzeitigkeitsprüfung:

seq 1 20 | xargs -P 20 -I {} curl -s -o /dev/null -w "%{http_code}\n" \
    -H "x-api-key: test-client" http://localhost:8000/ping

Mit Kapazität 10 erwarte genau 10 200s und 10 429s, unabhängig davon, wie viele Replikas hinter dem Load Balancer sitzen – das Lua-Script, nicht der Speicher irgendeines einzelnen Replikas, ist die Source of Truth.

Häufige Fallstricke

Fehler: Rate-Limiting mit einem In-Memory-Counter hinter einem Multi-Replikas-Deployment. Jedes Replikas verfolgt seinen eigenen Count, sodass das effektive Limit mit der Replikas-Anzahl multipliziert wird. Lösung: Backe den Limiter mit Redis (oder einem anderen gemeinsamen Speicher), sobald du mehr als einen Prozess betreibst.

Fehler: Separate Read-then-Write-Aufrufe statt einer atomaren Operation. Das ist die oben beschriebene Check-then-Increment-Race. Lösung: Erledige das gesamte Lesen/Berechnen/Schreiben innerhalb eines einzelnen Lua-Scripts oder einer Redis-Transaktion.

Fehler: Fixed Window für ein enges, sicherheitsempfindliches Limit verwenden. Login-Versuch-Limiting mit Fixed Window ermöglicht es einem Angreifer, seine effektiven Versuche zu verdoppeln, indem er Anfragen rund um die Fenstergrenze timed. Lösung: Verwende Sliding Window oder Token Bucket für alles, bei dem das Grenz-Burst-Verhalten tatsächlich ausnutzbar ist.

Fehler: Vergessen, einen TTL auf Rate-Limit-Keys zu setzen. Redis-Speicher wächst unbegrenzt, da jeder Client, der jemals eine Anfrage gemacht hat, einen permanenten Key erhält. Lösung: Setze immer einen Ablauf, der leicht länger ist als das Fenster oder der Auffüllzeitraum.

Fehler: Offen scheitern, wenn Redis nicht verfügbar ist. Ein Redis-Ausfall wird zu einem vollständigen API-Ausfall statt zu einer Rate-Limiting-Lücke. Lösung: Standardmäßig offen scheitern für Rate-Limiting, mit lauter Protokollierung/Alarmierung beim Fehler selbst.

Best Practices für die Produktion

Wähle Sliding Window Counter als Standard und greife speziell auf Token Bucket zurück, wenn du untätigen Clients Burst-Kapazität belohnen willst.
Implementiere das Check-and-Decrement immer als eine atomare Redis-Operation, über ein Lua-Script – niemals zwei Round-Trips.
Schlüssel nach authentifizierter Benutzer-ID wenn möglich, und falle nur für nicht-authentifizierte Endpunkte auf IP zurück.
Setze einen TTL auf jeden Rate-Limit-Key und berechne ihn aus den Fenster-/Auffüllparametern, nicht als fest codierter Schätzung.
Entscheide dein Redis-Down-Verhalten explizit – offen scheitern für allgemeine API-Limits, und behandle diese Entscheidung als bewussten Kompromiss, kein nie untersuchtes Standard.

Fazit

Der Algorithmus, den du wählst, ändert, wie sich dein Rate-Limiter an den Rändern verhält – wie er einen Burst, eine Fenstergrenze, einen untätig-dann-aktiven Client behandelt – und einer zu wählen, der nicht deinem tatsächlichen Traffic-Muster entspricht, ist ein echter, behebbarer Designfehler. Aber der häufigere Produktionsvorfall ist überhaupt kein Algorithmus-Mismatch; es ist ein Limiter, der nur jemals auf einem Prozess korrekt war und still sein effektives Limit multiplizierte, sobald ein zweites Replikas der Flotte beitrat. Mach die Atomizität zuerst richtig – mit einer einzelnen Redis-Operation, die Lesen-Prüfen-Schreiben als einen unteilbaren Schritt macht – und die Algorithmenwahl wird eine Abstimmungsentscheidung statt einer Korrektheitsentscheidung.

Wenn dein aktueller Rate-Limiter ein In-Memory-Dictionary ist und du mehr als ein Replikas betreibst, ist das die Lücke, die es zuerst wert ist zu schließen, bevor alles andere in diesem Beitrag.