Qu’est-ce que le rate limiting ?

Le rate limiting est un mécanisme essentiel pour garantir, d’une part, la stabilité et, d’autre part, la sécurité des applications en ligne. Il permet de contrôler, côté client, le flux de données envoyées à un serveur ou, côté application, le trafic entrant afin d’éviter la surcharge et les abus.

Dans cet article, nous allons aborder les points suivants :

L’importance du rate limiting
Les différentes approches et algorithmes disponibles (Fixed Window, Leaky Bucket, etc.) avec des exemples en Python
Une approche alternative auto-adaptative

Table of Contents

Pourquoi le rate limiting / throttling est-il important ?

Le rate limiting (ou limitation du débit) est utile, à minima, dès lors qu’un service est destiné à être utilisé de manière intensive, que ce soit de manière continue ou très éphémère. Il est important de noter qu’un service accessible au public doit nécessairement être considéré comme utilisé de manière intensive. En effet, n’ayant pas la main mise sur les clients, il est impossible de garantir que ces derniers en auront un usage “raisonnable”. Que ce dernier soit volontairement déraisonnable ou que celui-ci soit un résultat tout à fait involontaire, le résultat est, dans ce cas, identique.

Ceci étant dit, même dans le cas d’un service utilisé au sein d’une architecture complètement maîtrisée, il est parfois très difficile de garantir que l’usage client restera maîtrisé dans le temps. En effet, côté client, il est également important de gérer correctement la reprise sur erreur, l’interruption partielle de service, …. ; autant de cas d’usage qui nécessitent le renvoi de requêtes et qui constituent un usage exceptionnel du service. Autrement dit, il est recommandé de toujours mettre en place un système de limitation de trafic, même basique, lors du développement de services et/ou de leurs clients.

Quelque soit le type de service, un envoi massif simultané de requêtes peut :

Ralentir considérablement le système
Provoquer des interruptions de service
Faciliter l’exploitation du service par des robots

Le rate limiting permet de limiter ces risques en appliquant des restrictions/limitations sur le nombre de requêtes qu’un utilisateur peut envoyer dans un laps de temps donné (côté client) ou sur le nombre de requêtes qui peuvent être traité de manière simultanée (côté service). Il permet également de contrôler les accès d’un client à une API ou une application donnée afin d’en assurer un usage homogène et équitable.

Distributed Denial-of-Service (DDoS)

Le rate limiting permet, en d’autres termes, de limiter l’impact d’une attaque de type “Distributed Denial-of-Service (DDoS)” qui consiste à envoyer de manière massive des requêtes à un serveur depuis plusieurs IPs différentes. Bien, qu’en réalité, une attaque de ce type soit particulièrement difficile à contrer, ce dernier permet d’y résister potentiellement suffisamment longtemps pour mettre en place une stratégie plus ciblée et plus efficace.

En combinant celui-ci avec d’autres mécanismes de protection comme le challenge-response (CAPTCHA), le filtrage IP ou encore des services spécialisés comme Cloudflare, il devient possible d’atténuer ces attaques. Certains systèmes adoptent également des approches comportementales qui analysent le trafic en temps réel afin de détecter des schémas suspects (ex. : pic soudain de requêtes, provenance inhabituelle, etc.).

Dans les infrastructures modernes, les services de protection DDoS utilisent des algorithmes de machine learning afin d’adapter dynamiquement les règles de filtrage et ainsi maximiser la résilience face à ce type de menace.

Approches du rate limiting / throttling

Ces techniques peuvent être mis en place à deux niveaux :

Côté serveur

Le principal objectif de la mise en place de limites côté serveur est de garantir la stabilité du service en empêchant qu’un trop grand nombre de requêtes, ou, d’une manière plus générale, le traffic entrant, ne sature les ressources disponibles. Chaque serveur possède une quantité limitée de mémoire, de threads et de puissance de calcul. Sans mécanisme de limitation, un afflux massif de données pourrait rapidement provoquer une dégradation des performances, voire une panne complète.

Le rate limiting peut être appliqué à différents niveaux de l’infrastructure :

Au niveau du système d’exploitation, où des restrictions sur le nombre de connexions simultanées par adresse IP peuvent être mises en place.
Dans les middlewares et proxys, tels que NGINX ou des API gateways, qui peuvent filtrer les requêtes avant qu’elles n’atteignent l’application.
Directement dans l’application, où un suivi précis des requêtes par utilisateur ou par clé API permet un contrôle plus fin.

L’une des stratégies les plus efficaces consiste à rejeter les requêtes excessives le plus tôt possible dans la chaîne de traitement, limitant ainsi leur impact sur les ressources critiques du serveur.

Côté client

Le rate limiting ou l’api throttling ne concernent pas uniquement les serveurs. Côté client, il s’agit d’une stratégie proactive visant à:

éviter d’être bloqué par un service
optimiser l’utilisation des ressources réseau (diminution de la bande passante)

Les clients d’API bénéficient également du rate limiting. En effet, de nombreuses plateformes imposent des quotas sur les appels API (par exemple, 1000 requêtes par heure). Implémenter un mécanisme de limitation côté client permet d’éviter de dépasser ces quotas et d’assurer une utilisation fluide des services.

Enfin, limiter l’envoi de données côté client permet de réduire la charge inutile côté serveur, améliorant ainsi la réactivité du service et l’expérience utilisateur globale. On pourrait parler d’attitude “responsable” à adopter lorsque l’on utilise un service ouvert à d’autres utilisateurs.

Dans un autre registre, moins “responsable”, c’est la meilleure solution pour faire du web scraping où un script automatisé collecte des données depuis un site web. Si les requêtes sont envoyées trop rapidement, le serveur cible peut détecter une activité anormale et bloquer l’accès. En régulant la fréquence des requêtes, un client peut s’assurer de rester en dessous des seuils de détection tout en poursuivant sa tâche efficacement. Dans ce cas de figure, l’idéal étant très souvent de reproduire l’activité d’un utilisateur “lambda” du service. En fonction du service, cela peut se traduire par un envoi de requêtes limitées dans le temps, par plages horaires, avec une plus ou moins grosse part d’aléatoire, des interruptions parfois longues, … On modifiera alors ici la manière dont sont utilisés les stratégies de rate limiting que nous allons introduire dans la section suivante.

Stratégies de rate limiting

Il existe plusieurs approches pour mettre en place une limitation du taux d’envoi/réception. Nous détaillerons rapidement chacune d’entre elles:

Fixed window counter

Cette méthode autorise un nombre fixe de requêtes par intervalle de temps défini (ex. : 100 requêtes par minute).

Python

from abc import abstractmethod

class FixedWindowCounterBase:
    def __init__(self, capacity: int = 100):
        self.capacity = capacity
        self.request_count = 0
        self.last_window = None

    @abstractmethod
    def current_window(self):
        raise NotImplementedError
    
    def acquire(self) -> bool:
        current_window = self.current_window()
        if self.last_window is None or current_window != self.last_window:
            self.last_window = current_window 
            self.request_count = 1
            return True
        if self.request_count >= self.capacity:
            return False
        self.request_count += 1
        return True

Avantages:

Facile à implémenter et à comprendre.
Permet d’avoir un compteur facile à interpréter pour chaque fenêtre de temps.

Inconvénients:

Permet l’envoi simultané de la capacité maximale de la fenêtre courante.
Permet également l‘envoi de deux fois la capacité maximale d’une fenêtre dans une plage de temps assez réduite (à la fin d’une fenêtre + au début de la fenêtre suivante).

Sliding window log

Cette variante permet d’ajuster dynamiquement la limite en fonction d’une fenêtre temporelle glissante, assurant une meilleure répartition des requêtes dans le temps.

Python

import time

from abc import abstractmethod
from collections import deque

class SlidingWindowLogBase:
    def __init__(self, capacity: int = 100):
        self.capacity = capacity
        self.requests = deque()

    @abstractmethod
    def window_start(self):
        raise NotImplementedError
    
    def acquire(self) -> bool:
        window_start = self.window_start()
        while self.requests and self.requests[0] = self.capacity:
            return False
        self.requests.append(time.monotonic())
        return True

Avantages:

Facile à implémenter et à comprendre.
Précis, respecte toujours la capacité souhaité pour une fenêtre de temps donnée.

Inconvénients:

Permet l’envoi simultané de la capacité maximale de la fenêtre courante.
Nécessite de conserver l’ensemble des timestamps en mémoire (peu adapté aux gros volumes de requêtes).

Sliding window counter

Cette approche combine les deux stratégies précédentes dans le but de supprimer la nécessité de stocker l’ensemble des timestamps en mémoire.

Python

import time

from abc import abstractmethod

class SlidingWindowCounterBase:
    def __init__(self, capacity: int = 100):
        self.capacity = capacity
        self.last_window = None
        self.last_request_count = 0
        self.prev_window = None
        self.prev_request_count = 0
                
    @abstractmethod
    def current_window(self):
        raise NotImplementedError

    def acquire(self) -> bool:
        current_window = self.current_window()
        if self.last_window is None or current_window != self.last_window:
            self.prev_window = self.last_window
            self.last_window = current_window
            self.prev_request_count = self.last_request_count
            self.last_request_count = 0
        
        if self.prev_window is not None:
            now = time.monotonic()
            elapsed = (now – self.last_window) / (self.last_window – self.prev_window)
            wgth_request_count = self.prev_request_count * (1 – elapsed) + self.last_request_count
        else:
            wgth_request_count = self.last_request_count

        if wgth_request_count >= self.capacity:
                return False
        self.last_request_count += 1
        return True

Avantages:

Précis, respecte toujours la capacité souhaité pour une fenêtre de temps donnée.

Inconvénients:

Permet l’envoi simultané de la capacité maximale de la fenêtre courante.

Token Bucket

Plutôt que d’imposer des limitations strictes, cette approche attribue un stock de « jetons » aux utilisateurs que chaque requête consomme. Ces jetons sont régénérés au fil du temps.

Cette méthode est adaptée aux systèmes nécessitant une certaine flexibilité (ex. : API autorisant des pics de requêtes avant d’imposer une restriction).

Python

import time

class TokenBucket:
    def __init__(self, capacity, fill_rate):
        self.capacity = capacity
        self.fill_rate = fill_rate
        self.last_token = time.monotonic()
        self.token_count = capacity
    
    def acquire(self) -> bool:
        now = time.monotonic()
        elapsed = now – self.last_token
        new_tokens = elapsed * self.fill_rate
        self.token_count = min(self.capacity, self.token_count + new_tokens)
        self.last_token = now

        if self.token_count < 1:
            return False		
        self.token_count -= 1
        return True

Avantages:

Facile à implémenter et à comprendre.
Permet de contraindre l’envoi de requêtes sur des petits intervalles de temps.

Inconvénients:

Ne garantit pas un taux de transfert constant.

Leaky Bucket

Cette approche utilise un concept similaire à la méthode précédente mais l’exploite différemment. En occurrence, l’approche est ici fondamentalement asynchrone puisque les requêtes sont placées dans une file d’attente et sont traitées à un débit constant. Si la file d’attente est pleine, les requêtes excédentaires sont rejetées.

Python

import anyio

from contextlib import AsyncExitStack

class LeakyBucket:
    def __init__(self, capacity: int, leak_rate: float):
        self.capacity = capacity
        self.leak_rate = leak_rate
        self.snd, self.rcv = anyio.create_memory_object_stream[anyio.Event](capacity)
        self.exit_stack = AsyncExitStack()

    async def __aenter__(self):
        stack = await self.exit_stack.__aenter__()
        task_group = await stack.enter_async_context(anyio.create_task_group())
        stack.enter_context(self.snd)
        task_group.start_soon(self._leak)
        return self

    async def __aexit__(self, *args):
        return await self.exit_stack.__aexit__(*args)

    async def _leak(self) -> None:
        period = 1 / self.leak_rate
        with self.rcv:
            async for event in self.rcv:
                event.set()
                await anyio.sleep(period)

    async def acquire(self) -> bool:
        try:
            event = anyio.Event()
            self.snd.send_nowait(event)
            await event.wait()
            return True
        except anyio.WouldBlock:
            return False

# Usage
async with LeakyBucket(10, 1) as rl:
    for k in range(5):
        if await rl.acquire():
            print(f"tic {k}: accepted: {anyio.current_time()}")
        else:
            print(f"tic {k}: rejected: could not happen here :/")

Avantages:

Permet de traiter les requêtes à un débit constant, le rendant complètement prévisible.

Inconvénients:

Plus complexe à implémenter.
Ne permet pas de gérer les “bursts” de requêtes, elles sont rapidement rejetées.

Variantes

Combinaisons Il est tout a fait envisageable de combiner certaines de ces techniques. Il peut alors être nécessaire d’implémenter un moyen d’annuler l’acquisition d’un token auprès d’un rate limiter. Dans un tel cas, on peut alors imaginer tenter d’acquérir un token auprès de plusieurs entités avec des approches différentes pour valider le tout. Certains algorithmes s’y prêtent mieux que d’autres. On peut par exemple ajouter un support limité des bursts à l’approche “Leaky bucket” en considérant que chaque requête rejetée doit être rediriger vers une autre méthode capable de les supporter.
Token variable Autre méthode potentiellement simple à implémenter, en tout cas pour les approches basées sur des capacités, il suffit de moduler la quantité de “tokens” acquises en fonction du temps (ie. considérer que l’on obtient n tokens au lieu d’un seul nécessairement, n pouvant être une valeur flottante). On peut, par exemple, avec cette technique, passer simplement d’un débit linéaire à un débit plus complexe, type sinusoïdale ou semi-aléatoire, …

L’approche concurrente auto-adaptative: le cas Netflix

Pour respecter les contraintes des requêtes API externes ou imposer ces mêmes limites aux requêtes entrantes, les approches citées précédemment sont bien souvent suffisantes. Néanmoins, dans certains cas de figures, il peut être intéressant d’aller au delà de ce type d’approche. En effet, imaginez qu’il vous est possible d’ajuster de manière automatique la quantité de requêtes concurrentes à exécuter tout en maximisant l’utilisation de vos ressources. C’est ce qu’a tenté d’implémenter l’équipe Netflix au travers d’une bibliothèque Java disponible ici: https://github.com/Netflix/concurrency-limits.

Le principe est relativement simple et se base uniquement sur le temps de réponse des requêtes.

Si ce dernier augmente, cela indique une surcharge, donc la limite de requêtes est réduite.
Si les performances restent stables, la limite est progressivement augmentée.

Il existe en réalité plusieurs algorithmes disponibles dans cette bibliothèque permettant de configurer, à votre souhait, la méthode et la rapidité de convergence de l’algorithme.

Les avantages de cette méthode sont multiples:

Inutile de tester manuellement votre système pour trouver la limite idéale.
Ne nécessite aucune centralisation/coordination.
Aucune connaissance préalable requise quant à la topologie/architecture.
S’adapte automatiquement à un changement de topologie/architecture.
Simple à mettre en place.

Nous vous conseillons fortement d’utiliser cette approche, aussi bien côté client que côté serveur, s’il correspond à votre cas d’usage.

Conclusion

Le rate limiting est un élément essentiel pour assurer la disponibilité et la fiabilité d’un système. Différentes stratégies existent en fonction des besoins spécifiques. Pour aller plus loin, des solutions comme NGINX rate limiting, Redis ou des middlewares spécialisés peuvent être explorées. La mise en place d’un rate limiter efficace est une nécessité pour protéger les infrastructures et garantir une expérience utilisateur optimale.

Pour vos besoins en interne, à l’heure ou les architectures micro-services sont dominantes, pensez à utiliser des solutions alternatives ou à développer vous même une solution sur mesure qui répondra à vos besoins.

Bien que les approches que nous décrivons dans cet article soient relativement simples, elles peuvent tout à fait suffire à petite échelle ou pour vos projets en interne. Elles seront, par contre, surement trop limitées pour un usage externe.

Qu’est-ce que le rate limiting ?

Pourquoi le rate limiting / throttling est-il important ?

Distributed Denial-of-Service (DDoS)

Approches du rate limiting / throttling

Côté serveur

Côté client

Stratégies de rate limiting

Fixed window counter

Sliding window log

Sliding window counter

Token Bucket

Leaky Bucket

Variantes

L’approche concurrente auto-adaptative: le cas Netflix

Conclusion

You may like to read:

Help & Info