Conception d'un limiteur de débit

Voici mes notes sur la conception d'un limiteur de débit.

Qu'est-ce qu'un limiteur de débit ?

• Dans les réseaux informatiques, la limitation du débit est utilisée pour contrôler le débit des requêtes envoyées ou reçues par un contrôleur d'interface réseau .
• Du côté HTTP, limite le nombre de requêtes client autorisées à être envoyées sur une période spécifiée.

• Les utilisateurs peuvent créer 1 ticket toutes les 5 minutes
• Les utilisateurs peuvent créer 2 comptes par jour avec la même adresse IP
• Les utilisateurs peuvent essayer 5 tentatives de connexion infructueuses par heure avec la même adresse IP en une journée

• Un limiteur de débit empêche les attaques DoS
• Arrêtez les abus du système
• Réduit le coût
• Il évite de surcharger les serveurs. Réduit également la charge du serveur
• Améliorez l'expérience utilisateur avec moins de trafic

• Le limiteur de débit ne doit pas ralentir le temps de réponse HTTP de votre système.
• Utiliser moins de mémoire
• Afficher les exceptions aux utilisateurs lorsque leurs demandes sont bloquées en raison de la limitation du débit.
• Votre limiteur de débit ne doit pas affecter l'ensemble du système. Par exemple, si votre serveur de cache tombe en panne, votre système doit être disponible.

• Il existe différentes manières d'implémenter un limiteur de débit. Ceux-ci sont; Implémentation côté client, implémentation côté serveur et une autre méthode utilisant une passerelle API tierce.
• En règle générale, le côté client n'est pas un endroit fiable pour appliquer la limitation de débit
• Une implémentation côté serveur présente certains avantages internes car vous pouvez modifier la logique de votre côté.
• L'utilisation d'une passerelle API tierce est parfois utile car elle prend du temps à mettre en place.

1- Seau à jetons

• Deux paramètres principaux ; Taille du seau et taux de remplissage.
• Taille du bucket : nombre maximal de jetons autorisés
• Taux de recharge : nombre de jetons mis dans le seau dans n'importe quel intervalle, comme toutes les secondes
• En supposant que nous ayons un compartiment, la capacité est définie comme le nombre de jetons qu'il peut contenir. Chaque fois qu'un consommateur souhaite accéder à un point de terminaison d'API, il doit obtenir un jeton du compartiment. Le jeton est supprimé du compartiment s'il est disponible et accepte la demande. Si le jeton n'est pas disponible, le serveur rejette la demande.
• À chaque intervalle fixe, nous devons faire le plein.
• Si nous devons limiter les requêtes HTTP en fonction des adresses IP, chaque adresse IP nécessite un compartiment.
• Peut provoquer des conditions de concurrence dans un environnement distribué (inconvénient)

2- Seau qui fuit

• Lorsqu'une requête HTTP arrive, le système vérifie la file d'attente. Si la file d'attente n'est pas pleine, la demande est ajoutée à la file d'attente. Sinon, la demande est bloquée.
• Les requêtes HTTP sont extraites de la file d'attente et traitées à intervalles réguliers.
• Le traitement du premier élément de la file d'attente se produit à intervalle régulier ou premier entré, premier sorti (FIFO)

• Divise la chronologie en fenêtres de temps de taille fixe
• Chaque requête incrémente le compteur.
• La fenêtre temporelle est considérée du début de l'unité de temps à la fin de l'unité de temps.
• Complexité spatiale : O(1) — Stockage du nombre de fenêtres actuelles Complexité temporelle : O(1) — Obtention et simple opération d'incrémentation atomique

• Le plus gros problème avec cela est que les consommateurs peuvent trouver le temps de réinitialisation et maximiser la demande dans un court laps de temps qu'ils peuvent bombarder.

• l'algorithme de fenêtre fixe a un problème comme je l'ai écrit. Il permet à plus de requêtes de passer aux bords d'une fenêtre. Un journal de fenêtre coulissante résout ce problème.
• conserve l'heure des requêtes triées dans un Set ou une Table (Ex: Redis)
• Chaque minute, nous recherchons les demandes plus anciennes et les filtrons. Calculez ensuite la disponibilité. Si la demande dépasse le taux de seuil, elle est retenue, sinon elle est servie.
• Consomme beaucoup de mémoire.
• Coûteux de stocker un nombre illimité de journaux pour chaque requête.
• Complexité de l'espace : O (requêtes max vues dans une fenêtre de temps) : stocke tous les horodatages des requêtes dans une fenêtre de temps.
• Complexité temporelle : O (requêtes maximales vues dans une fenêtre de temps) : suppression d'un sous-ensemble d'horodatages

1. Comptez le nombre total d'éléments dans l'ensemble trié. Rejetez la demande si ce nombre est supérieur à notre limite de limitation de "3".
2. Insérez l'heure actuelle dans l'ensemble trié et acceptez la demande.

• combine le faible coût de traitement de l'algorithme à fenêtre fixe et les conditions aux limites améliorées du journal glissant.
• Complexité spatiale : O (nombre de seaux)
• Complexité temporelle : O(1) : récupère le compartiment récent, l'incrémente et le vérifie par rapport à la somme totale des compartiments (peut être stocké dans une variable totalCount).
• Pour plus de détails sur la mise en œuvre, vous pouvez suivre cet article.
• Un autre article pour mieux comprendre.

1. Supprimez tous les compteurs de plus d'une minute.
2. incrémente le compteur si la requête arrive dans le compartiment actuel.
3. Requête bloquée si le compartiment actuel a déjà dépassé la limite de gorge.

Références

• https://www.quinbay.com/blog/rate-limiter-implementation-token-bucket-algorithm
• https://betterprogramming.pub/4-rate-limit-algorithms-every-developer-should-know-7472cb482f48
• https://codeminion.hashnode.dev/rate-limiting-algorithms
• https://goalgorithm.wordpress.com/2019/06/08/designing-an-api-rate-limiter/