Algorithmes de limitation de débit : token bucket contre fenêtre glissante

Toute API publique finit par avoir besoin d'une limitation de débit, et l'algorithme que vous choisissez détermine si « 100 requêtes par minute » signifie réellement ce que cela semble dire. Deux approches dominent en pratique, le token bucket et la fenêtre glissante, et elles se comportent différemment aux limites, d'une façon qui compte dès que le vrai trafic les atteint.

Pourquoi « requêtes par minute » est plus délicat qu'il n'y paraît

L'approche naïve est la fenêtre fixe : compter les requêtes dans la minute calendaire en cours et remettre le compteur à zéro au changement de minute. C'est simple à implémenter et facile à raisonner, jusqu'à ce qu'un client envoie 100 requêtes à 0:59 et 100 autres à 1:00. Votre limiteur a autorisé 100 par minute, mais le serveur vient de recevoir 200 requêtes en deux secondes. Les fenêtres fixes fuient à la frontière.

Le token bucket et la fenêtre glissante existent tous deux pour combler cet écart, à des coûts différents en mémoire et en précision.

Token bucket : dépenser dans une réserve qui se remplit

Un token bucket contient un nombre maximal de jetons. Chaque requête consomme un jeton ; les jetons se reconstituent en continu à un rythme fixe. Si le seau est vide, la requête est rejetée (ou mise en file). Propriété clé : les rafales sont autorisées jusqu'à la taille du seau, mais le débit moyen est plafonné par le rythme de recharge.

class TokenBucket {
  constructor(capacity, refillPerSecond) {
    this.capacity = capacity;
    this.tokens = capacity;
    this.refillPerSecond = refillPerSecond;
    this.lastRefill = Date.now();
  }

  #refill() {
    const now = Date.now();
    const elapsedSeconds = (now - this.lastRefill) / 1000;
    this.tokens = Math.min(this.capacity, this.tokens + elapsedSeconds * this.refillPerSecond);
    this.lastRefill = now;
  }

  tryConsume(count = 1) {
    this.#refill();
    if (this.tokens >= count) {
      this.tokens -= count;
      return true;
    }
    return false;
  }
}

const bucket = new TokenBucket(20, 5); // burst of 20, refills at 5/sec
if (bucket.tryConsume()) {
  handleRequest();
} else {
  respondWithTooManyRequests();
}

Remarquez qu'aucun minuteur ne tourne en arrière-plan : #refill() calcule simplement combien de jetons se seraient accumulés depuis la dernière vérification, d'après le temps écoulé. L'ensemble est ainsi sans état entre les requêtes, hormis tokens et lastRefill, ce qui est exactement ce qu'il faut si cet état vit dans Redis derrière une API distribuée.

Fenêtre glissante : compter ce qui s'est réellement passé récemment

Le journal à fenêtre glissante suit les horodatages réels des requêtes récentes et compte combien tombent dans la fenêtre qui se termine à l'instant présent, et non dans une tranche calendaire fixe. C'est l'approche la plus précise, car elle répond directement à « combien de requêtes ont eu lieu dans les 60 dernières secondes », sans fuite à la frontière.

class SlidingWindowLog {
  constructor(limit, windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
    this.timestamps = [];
  }

  tryConsume() {
    const now = Date.now();
    const cutoff = now - this.windowMs;
    this.timestamps = this.timestamps.filter((t) => t > cutoff);

    if (this.timestamps.length < this.limit) {
      this.timestamps.push(now);
      return true;
    }
    return false;
  }
}

const limiter = new SlidingWindowLog(100, 60_000); // 100 requests per rolling 60s

Le coût est la mémoire : vous stockez un horodatage par requête dans la fenêtre et par client. À fort volume, cela s'additionne, ce qui explique pourquoi les systèmes de production utilisent plus souvent des compteurs à fenêtre glissante, un hybride qui conserve deux compteurs à fenêtre fixe (courante et précédente) et calcule une estimation pondérée du compte glissant au lieu de stocker chaque horodatage :

function slidingWindowCount(currentCount, previousCount, elapsedInCurrentWindowMs, windowMs) {
  const weightOfPrevious = 1 - elapsedInCurrentWindowMs / windowMs;
  return currentCount + previousCount * weightOfPrevious;
}

Cela sacrifie un peu de précision pour obtenir une mémoire en O(1) par client au lieu de O(requêtes).

Choisir entre eux

• Token bucket quand les rafales sont acceptables et que ce qui vous importe est le débit moyen, par exemple pour protéger un service en aval qui peut absorber de brefs pics mais pas une charge soutenue.
• Journal à fenêtre glissante quand il faut une application exacte et que le nombre de clients est assez faible pour que le stockage par horodatage soit peu coûteux, par exemple un petit nombre de clés d'API à forte valeur.
• Compteur à fenêtre glissante quand il faut la précision d'une fenêtre glissante à grande échelle et que l'on tolère une petite erreur d'approximation aux limites de fenêtre.

Une fenêtre fixe est rarement le bon choix de production à elle seule : n'y recourez que si les rafales aux frontières ne vous importent vraiment pas, par exemple pour des quotas journaliers grossiers.

Où vit réellement l'état

Aucun de ces algorithmes n'est intéressant tant qu'on ne considère pas que votre API tourne presque certainement sur plus d'un serveur. Un token bucket ou un journal d'horodatages stocké dans la mémoire d'un seul processus ne limite que les requêtes qui atteignent ce processus : un client peut obtenir N fois votre limite prévue en répartissant ses requêtes sur N instances.

La solution standard consiste à centraliser le compteur dans Redis, avec INCR et PEXPIRE pour un compteur à fenêtre fixe ou glissante, ou un script Lua pour une vérification-décrémentation atomique de token bucket :

// Atomic fixed-window counter in Redis
async function isAllowed(redisClient, key, limit, windowSeconds) {
  const count = await redisClient.incr(key);
  if (count === 1) {
    await redisClient.expire(key, windowSeconds);
  }
  return count <= limit;
}

Le test count === 1 ne pose l'expiration que sur la première requête d'une nouvelle fenêtre : chaque INCR suivant incrémente simplement le compteur existant jusqu'à son expiration, puis le cycle recommence.

N'oubliez pas d'informer le client

Quel que soit l'algorithme choisi, renvoyez des en-têtes standard pour que les clients bien élevés puissent ralentir d'eux-mêmes au lieu de vous marteler jusqu'à obtenir un 429 :

• X-RateLimit-Limit : le plafond.
• X-RateLimit-Remaining : ce qu'il reste dans la fenêtre actuelle.
• Retry-After : le nombre de secondes avant qu'il vaille la peine de réessayer, envoyé avec la réponse 429.

À retenir

Les fenêtres fixes sont simples et fuient à la frontière. Le token bucket autorise des rafales contrôlées par rapport à un débit moyen. Le journal à fenêtre glissante est exact mais gourmand en mémoire ; les compteurs à fenêtre glissante l'approximent à bas coût à grande échelle. Choisissez selon que les rafales sont acceptables et selon la précision requise de l'application de la limite, puis veillez à ce que le compteur vive à un endroit que tous vos serveurs voient.