Veröffentlicht · wird verbessert
Algorithm
Rate Limiting begrenzt, wie viele Anfragen ein Nutzer oder eine IP pro Zeitfenster stellen darf: Token Bucket, Sliding Window, Leaky Bucket und Redis.
Ein Rate Limiter begrenzt, wie viele Anfragen innerhalb eines Zeitraums angenommen werden. Man legt einen Schlüssel, ein Limit und ein Zeitfenster fest, etwa "100 Anfragen pro Minute und Nutzer", und weist darüber hinausgehende Anfragen ab oder verzögert sie. Die klassischen Verfahren sind Fixed Window, Sliding Window Log, Sliding Window Counter, Token Bucket und Leaky Bucket; sie unterscheiden sich in Genauigkeit, Speicherbedarf und im Umgang mit Lastspitzen.
Fast jede nach außen offene Funktion, von öffentlichen APIs über Login und Zahlungen bis zum Nachrichtenversand, steht hinter einem Rate Limiter. Er schützt Server vor Lastspitzen und außer Kontrolle geratenen Retry-Schleifen, verhindert, dass ein einzelner Nutzer die Kapazität monopolisiert, und bremst Brute-Force-Angriffe. Außerdem ist er ein Standardthema in System-Design-Interviews.
Schreiben Sie zuerst einen Fixed-Window-Zähler und beobachten Sie, wie er an der Fenstergrenze das doppelte Limit durchlässt; beheben Sie das dann mit Sliding Window und Token Bucket. Danach lohnt es sich, mit injizierter Uhr zu testen, HTTP 429 mit Retry-After zu senden und ein Limit mit Redis INCR, EXPIRE und Lua-Skripten über mehrere Server zu teilen.
Tokens werden mit fester Rate nachgefüllt und jede Anfrage verbraucht eines; so gilt eine Durchschnittsrate, und Bursts bis zur Kapazität sind erlaubt.
Ein Zeitstempel-Log oder eine gewichtete Mischung zweier Fensterzähler zählt aktuelle Anfragen ohne die Spitze an der Fenstergrenze.
Getrennte Limits pro Nutzer-ID, API-Schlüssel, IP-Adresse oder Endpunkt verhindern, dass ein Client die Ressourcen monopolisiert.
Das atomare INCR von Redis und Lua-Skripte erlauben vielen Servern, ein Limit ohne Race Conditions zu teilen.
TokenBucket füllt rate Tokens pro Sekunde nach und fasst höchstens capacity Tokens. allow() schreibt alle seit dem letzten Aufruf verdienten Tokens in einem Schritt gut (Lazy Refill) und verbraucht eines, wenn genug vorhanden sind. Beim Ausführen passieren die ersten 5 Aufrufe als Burst, die nächsten 3 werden abgewiesen; nach 1,1 Sekunden Pause kommen wieder zwei durch. Gemessen wird mit time.monotonic(), das nie rückwärts läuft.
token_bucket.py
import time
class TokenBucket:
"""Allow bursts of up to `capacity` requests, refilled at `rate` tokens per second."""
def __init__(self, rate: float, capacity: float) -> None:
self.rate = rate
self.capacity = capacity
self.tokens = capacity
self.updated = time.monotonic()
def allow(self, cost: float = 1.0) -> bool:
now = time.monotonic()
self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.rate)
self.updated = now
if self.tokens >= cost:
self.tokens -= cost
return True
return False
if __name__ == "__main__":
bucket = TokenBucket(rate=2, capacity=5) # 2 requests per second, bursts of 5
print([bucket.allow() for _ in range(8)]) # 5 x True, then 3 x False
time.sleep(1.1) # about 2.2 tokens come back
print(bucket.allow(), bucket.allow(), bucket.allow()) # True True False
python token_bucket.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Rate Limiting.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Rate Limiting aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.