Rate limiting : quatre algorithmes, quatre façons d'échouer

« 100 requêtes par minute » ne suffit pas comme spécification. Selon l'algorithme qui l'applique, cette phrase autorise 200 requêtes en deux secondes, ou en interdit 10 à un client qui n'a rien fait depuis une heure, ou ajoute trente secondes de latence sans jamais refuser personne. L'algorithme décide de ce que votre limite laisse passer quand le cas réel l'attaque, et chacun a sa faiblesse.

Avant de choisir, il faut savoir ce que la limite protège. L'équité entre clients, la capacité du serveur et la facturation d'un usage sont des objectifs différents, et un seul mécanisme les sert mal tous à la fois.

Ce que chaque algorithme laisse passer

Fenêtre fixe. Un compteur par client et par minute calendaire, remis à zéro à chaque changement de minute. C'est simple, avec une seule valeur à stocker. La faille se trouve à la frontière, puisque 100 requêtes à 12:00:59 et 100 à 12:01:00 sont toutes acceptées. Le débit réel toléré est le double de la limite annoncée, concentré sur une seconde. Et un client qui se synchronise sur la remise à zéro (tout script le fait sans le vouloir en relançant « à la prochaine minute ») produit un pic à chaque frontière, aligné avec celui de tous les autres.

Fenêtre glissante. Elle prend deux formes. La première tient un log de l'horodatage de chaque requête, exact mais dont la mémoire croît avec la limite ; la seconde est une approximation qui pondère le compteur de la fenêtre précédente par la part qui recouvre encore la fenêtre courante. Cette approximation est le bon compromis pour une limite d'équité, mais elle suppose un trafic uniforme dans la fenêtre précédente. Une rafale en fin de fenêtre est sous-estimée, une rafale en début est surestimée. L'erreur reste bornée, elle existe pourtant, et un client à la limite recevra des refus qu'il ne peut pas prévoir.