Publié · en amélioration
Algorithm
La limitation de débit plafonne les requêtes par utilisateur ou par IP sur une fenêtre de temps : token bucket, fenêtre glissante, leaky bucket, Redis.
Un limiteur de débit (rate limiter) contrôle le nombre de requêtes acceptées sur une période donnée. On fixe une clé, une limite et une fenêtre, par exemple « 100 requêtes par minute et par utilisateur », et les requêtes au-delà sont refusées ou retardées. Les algorithmes classiques sont la fenêtre fixe, le journal à fenêtre glissante, le compteur à fenêtre glissante, le token bucket et le leaky bucket ; ils diffèrent par leur précision, leur consommation mémoire et leur gestion des rafales.
Presque toute fonctionnalité exposée à l'extérieur, des API publiques à la connexion, aux paiements et à l'envoi de messages, se trouve derrière un limiteur de débit. Il protège les serveurs des pics de trafic et des boucles de relance incontrôlées, empêche un utilisateur d'accaparer la capacité partagée et ralentit les attaques par force brute. C'est aussi un grand classique des entretiens de conception de systèmes.
Commencez par écrire un compteur à fenêtre fixe et observez-le laisser passer le double de la limite à la frontière d'une fenêtre, puis corrigez cela avec une fenêtre glissante et un token bucket. Apprenez ensuite à tester avec une horloge injectée, à répondre HTTP 429 avec Retry-After et à partager une limite entre serveurs avec INCR, EXPIRE et les scripts Lua de Redis.
Les jetons se remplissent à un rythme constant et chaque requête en consomme un : le débit moyen est respecté et les rafales sont admises jusqu'à la capacité du seau.
Un journal d'horodatages, ou un mélange pondéré de deux compteurs, compte les requêtes récentes sans le pic à la frontière de la fenêtre fixe.
Des limites séparées par identifiant d'utilisateur, clé d'API, adresse IP ou endpoint empêchent un client unique d'accaparer les ressources.
L'INCR atomique de Redis et les scripts Lua permettent à de nombreux serveurs de partager une limite sans condition de concurrence.
TokenBucket ajoute rate jetons par seconde et en contient au plus capacity. allow() crédite en une fois tous les jetons gagnés depuis le dernier appel (remplissage paresseux), puis en consomme un s'il y en a assez. À l'exécution, les 5 premiers appels passent en rafale et les 3 suivants sont refusés ; après une pause de 1,1 seconde, deux autres passent. Le temps est mesuré avec time.monotonic(), qui ne recule jamais.
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.pySix chapitres pour aller de l'installation aux notions essentielles de Limitation de débit.
Posez vos questions, partagez votre expérience et échangez vos avis sur Limitation de débit.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.