Seau à jetons, seau percé et fenêtre glissante : en quoi diffèrent les algorithmes de limitation de débit

Ce que c'est

Le volet politique (quelle clé, quels en-têtes, quel statut) est couvert ailleurs ; cet article compare les algorithmes de comptage.

• Fenêtre fixe : un compteur par clé et par intervalle, réinitialisé à la frontière. La moins coûteuse, mais un client peut dépenser une limite complète en fin de fenêtre et une autre en début de la suivante : le double du taux nominal sur un court intervalle.
• Journal glissant : conserver l'horodatage de chaque requête et compter celles situées dans l'intervalle glissant. Exact ; la mémoire croît avec le volume.
• Compteur à fenêtre glissante : conserver les comptes de la fenêtre actuelle et de la précédente, et estimer l'intervalle glissant par previous * (1 - elapsed / window) + current. Approximatif, mémoire constante, pas de rafale de frontière.
• Seau à jetons : un seau contient jusqu'à un nombre maximal de jetons et se remplit à un taux fixe ; chaque requête prend un jeton et est rejetée lorsqu'il n'en reste plus. La configuration TokenBucket d'Envoy nomme exactement ces paramètres : max_tokens, tokens_per_fill et fill_interval, et le seau démarre plein.
• Seau percé : les requêtes entrent dans une file qui se vide à un taux fixe ; la file a une capacité au-delà de laquelle les requêtes sont rejetées. Le limit_req de nginx documente cela comme sa méthode, avec rate, une taille de burst, et nodelay ou delay pour choisir si les requêtes excédentaires à l'intérieur de la rafale sont retardées au taux nominal ou servies immédiatement.

Pourquoi c'est important

L'algorithme détermine la tolérance aux rafales, la mémoire par clé et si les clients voient un rejet ou une latence ajoutée. Les clients qui retentent à la réinitialisation d'une fenêtre fixe arrivent ensemble ; un seau à jetons absorbe une courte rafale puis impose la moyenne ; un seau percé à retardement lisse la charge du backend au prix d'un temps de mise en file.

Comment l'appliquer

• Adopter par défaut un seau à jetons par clé : stocker le nombre de jetons et la dernière heure de remplissage, remplir paresseusement à chaque requête, et rendre la mise à jour atomique (un script Redis, ou un verrou en mémoire de processus).
• Fixer la taille du seau à la rafale acceptée et le taux de remplissage à la limite soutenue ; documenter les deux valeurs.
• Utiliser un compteur à fenêtre glissante lorsque la promesse est un simple « N requêtes par minute » et que les rafales de frontière sont inacceptables.
• Utiliser un seau percé à retardement devant un backend, pas en périphérie, où les clients interactifs préfèrent un 429 rapide avec Retry-After.
• Dans un déploiement distribué, centraliser l'état par clé, ou accepter que les limites par instance se multiplient par le nombre d'instances ; utiliser une horloge monotone pour l'arithmétique de remplissage.

Pièges

Les sauts d'horloge murale corrompent l'arithmétique de remplissage. Un seau qui démarre vide bloque chaque nouvelle clé jusqu'à ce qu'il se remplisse. Les journaux glissants constituent une surface d'attaque mémoire. Indexer par IP client derrière un NAT ou un CDN limite la mauvaise population. Des règles de rafale non documentées obligent les clients bien élevés à deviner.