Pourquoi le rate limiting (limitation d’usage) est-il nécessaire ?
- Dans un chat Twitch avec de nombreux participants, s’il y a un spammeur et qu’aucune limitation d’usage n’est en place, il peut monopoliser la conversation.
- La limitation d’usage permet à chaque utilisateur d’avoir une chance équitable de participer.
- Un rate limiter (limiteur de débit) contrôle le trafic d’un service en bloquant les requêtes qui dépassent une limite définie sur une période donnée. Cela est utile au-delà de la régulation du spam dans un chat.
- Par exemple, sur un formulaire de connexion, la limitation d’usage peut freiner les attaques par force brute tout en autorisant un petit nombre de tentatives erronées.
- Les endpoints d’API sont eux aussi souvent soumis à une limitation d’usage afin d’éviter qu’un seul utilisateur ne monopolise les ressources.
- Si un utilisateur ne peut appeler un endpoint d’API coûteux que 100 fois par minute, on peut utiliser un compteur pour suivre 100 accès par minute, puis bloquer les requêtes suivantes.
- C’est l’un des algorithmes de limitation d’usage les plus simples : le Fixed Window Limiter.
- C’est une méthode courante pour contrôler le trafic d’un service.
Algorithme des fixed windows
- Le nombre de requêtes est limité dans une fenêtre temporelle fixe (
window).
- Au début de chaque fenêtre temporelle, le compteur de requêtes est réinitialisé à 0.
- Avantages
- Facile à implémenter et à comprendre
- Prévisible pour l’utilisateur
- Inconvénients
- Si les requêtes commencent vers la fin d’une fenêtre, cela peut autoriser une rafale (
burst) allant jusqu’à 2 fois la limite.
- Cas réel : l’API GitHub utilise un limiteur de débit à fenêtre fixe autorisant 5 000 requêtes par heure.
- Au lieu de fixer le début des fenêtres à intervalles réguliers, chaque fenêtre peut aussi être créée au moment de la première requête de l’utilisateur dans cette fenêtre.
- Avec cette approche, il est particulièrement important d’indiquer à l’utilisateur le temps restant avant la fenêtre suivante.
Algorithme des sliding windows
- Au lieu de recharger toute la capacité d’un coup, une sliding window reconstitue la capacité requête par requête.
- Avantages
- Rend la distribution du trafic de requêtes plus fluide
- Convient bien aux charges élevées
- Inconvénients
- Moins prévisible pour l’utilisateur qu’une fenêtre fixe
- Stocker le timestamp de chaque requête consomme beaucoup de ressources
- Comme les sliding windows sont surtout utiles dans des scénarios à fort trafic, le fait que l’algorithme de base soit gourmand en ressources devient contre-productif.
- C’est pourquoi la plupart des limiteurs de débit à sliding window utilisés en pratique emploient une approximation.
- Cette approximation calcule le nombre de requêtes autorisées dans la fenêtre fixe précédente et dans la fenêtre fixe actuelle, puis applique aux requêtes autorisées dans la fenêtre précédente un poids proportionnel à leur chevauchement avec une fenêtre glissante se terminant à l’instant présent.
- Cette méthode limite les requêtes à un rythme presque identique, tout en étant bien plus efficace.
- Cas réel : le rate limiter configurable de Cloudflare utilise une sliding window approximative.
Algorithme des token buckets
- Au lieu de raisonner en durée de fenêtre temporelle, on imagine un seau rempli de « jetons » à un rythme constant.
- Chaque requête retire un jeton de ce seau, et si le seau est vide, la requête suivante est bloquée.
- La capacité du seau représente le nombre maximal de requêtes qu’une rafale peut supporter.
- L’intervalle de recharge représente l’intervalle moyen autorisé entre les requêtes sur le long terme.
- L’un des principaux avantages de cet algorithme est qu’il permet d’avoir séparément une capacité de rafale et une capacité moyenne, sans multiplier les rate limiters.
- Avantages
- Autorise des rafales de trafic importantes tout en imposant un débit moyen à long terme
- Plus flexible pour l’utilisateur, en autorisant des pics de trafic dans les limites acceptables
- Inconvénients
- Plus difficile que les fenêtres fixes pour communiquer à l’utilisateur les contraintes et le temps de recharge
- Cas réels
- Stripe utilise un token bucket avec une limite de 500 et un intervalle de recharge de 0,01 seconde par utilisateur, ce qui permet 100 requêtes par seconde en continu, avec des rafales allant jusqu’à 500 requêtes.
- Le palier gratuit de GPT-3.5 d’OpenAI utilise un token bucket avec une limite de 200 et un intervalle de recharge de
86400/200 secondes, ce qui le limite à 200 requêtes par jour.
Points à considérer lors de la mise en place d’un rate limit
- Il faut prévoir un stockage persistant pour le rate limiter.
- Si la connexion du serveur à ce stockage persistant échoue, il faut laisser passer toutes les requêtes plutôt que de les bloquer.
- Il est possible, de façon optionnelle, de réguler le trafic en rafale.
- Il faut choisir une clé appropriée (ID utilisateur, clé API, etc.).
- Il faut afficher des erreurs de limitation de débit utiles (temps d’attente avant la prochaine requête, code HTTP 429, en-têtes de réponse
x-ratelimit-*, etc.).
2 commentaires
J’ai lu l’article résumé en coréen en me disant : « OK, je vois l’idée, mais au fond, ce n’est pas toujours la même chose ? » Puis j’ai lu l’article du lien original, et il est vraiment très bien expliqué, avec des visualisations vraiment très réussies ! 👍👍👍
Avis Hacker News
Résumé des commentaires Hacker News
Considérations supplémentaires tirées d’une longue expérience :
Dans un environnement multi-tenant, le fair queuing est l’approche optimale pour prévenir les attaques DoS : chaque client se voit attribuer sa propre file, et une routine d’arrière-plan parcourt chaque file en boucle pour traiter les requêtes. Un client qui envoie des requêtes spam ne congestionne ainsi que sa propre file.
Expérience d’implémentation de code côté client : je me suis toujours demandé quelle était la meilleure stratégie de backoff lorsqu’on atteint une rate limit. Il était intéressant de lire les compromis du point de vue du service.
Message de félicitations : c’est le meilleur exemple de visualisation pour un contenu court, très informatif et allant droit à l’essentiel.
Algorithme GCRA : je pense que c’est un meilleur algorithme pour le rate limiting. J’aimerais qu’il soit mieux connu et davantage utilisé.
Excellent travail : on sent que beaucoup de temps et d’efforts ont été investis dans ce billet. Bravo.
Problème de rate-limiting sur AWS Lambda : quelqu’un a essayé d’implémenter du rate-limiting en NodeJS, mais sur AWS Lambda, les timers se comportaient bizarrement et dépassaient l’objectif. Les tests en local passaient, mais échouaient sur Lambda. Il n’est pas clair si cela vient des timers ou de la bibliothèque.
Que faire lorsque la couche de rate limiting est saturée : quelqu’un se demande s’il existe d’autres options que CF. Il se demande aussi dans quelle mesure des règles nftable sont efficaces pour se défendre contre des attaques DoS sur un petit VPS.
Le genre de ressource dont on a eu besoin à plusieurs moments : c’est une ressource qui aurait été utile plusieurs fois au cours d’une carrière. Ravi qu’elle existe désormais.
Fan de visualisation de données : quelqu’un se demande si cela utilise D3.