Pourquoi le rate limiting sur Redis casse à grande échelle (et ce que fait Uber à la place)

Le rate limiting sur une seule machine est un problème résolu. Vous gardez un compteur, vous le rechargez sur un timer, vous rejetez les requêtes quand il tombe à zéro. Vingt lignes de code et c'est terminé.

Les ennuis commencent dès que vous avez plus d'une machine. « 100 requêtes par seconde » devient une affirmation sur toute la flotte, pas sur un seul processus. Chaque nœud ne voit que la part du trafic qui l'a atteint, mais la limite est globale. D'un coup il vous faut de la coordination, et la coordination à grande échelle, c'est là que la plupart des conceptions s'effondrent en silence.

Cet article suit le même chemin qu'un vrai système : on démarre avec le token bucket en mémoire, on le met derrière Redis pour qu'il fonctionne entre plusieurs nœuds, on regarde ce modèle casser sous la charge, puis on observe ce qu'Uber a construit pour son Global Rate Limiter à la place. L'objectif, c'est le raisonnement, pas une bibliothèque à copier-coller, pour que vous puissiez faire le bon choix pour vos propres services.

Étape un : le token bucket sur un seul nœud

Le token bucket est le classique. Un seau contient jusqu'à capacity jetons. Chaque requête prend un jeton. Les jetons se rechargent à un rythme constant. Si le seau est vide, la requête est rejetée. La capacité est ce qui vous permet d'absorber les pics courts ; le rythme de recharge, c'est votre limite en régime permanent.

type TokenBucket struct {
    mu         sync.Mutex
    tokens     float64
    capacity   float64
    refillRate float64 // jetons par seconde
    lastRefill time.Time
}

func (b *TokenBucket) Allow() bool {
    b.mu.Lock()
    defer b.mu.Unlock()

    now := time.Now()
    elapsed := now.Sub(b.lastRefill).Seconds()
    b.tokens = math.Min(b.capacity, b.tokens+elapsed*b.refillRate)
    b.lastRefill = now

    if b.tokens >= 1 {
        b.tokens--
        return true
    }
    return false
}

C'est correct, rapide, et le verrou est local. Pas de réseau, pas de dépendance, des décisions en nanosecondes. Il a exactement un défaut : le compteur vit dans la mémoire de ce processus. Lancez dix réplicas derrière un load balancer et vous avez dix seaux indépendants, chacun appliquant la limite entière. Votre vraie limite globale est maintenant 10 × capacity. Personne n'a demandé ça.

Étape deux : déplacer l'état dans Redis

La correction évidente, c'est de sortir le compteur du processus et de le mettre dans un store que chaque nœud peut voir. Redis est le choix par défaut : rapide, atomique, et tout le monde en fait déjà tourner.

La version naïve, c'est un compteur par fenêtre avec un TTL :

func Allow(ctx context.Context, rdb *redis.Client, key string, limit int, window time.Duration) (bool, error) {
    // clé du type "rl:user:42:1720512000", bucketée par fenêtre fixe
    count, err := rdb.Incr(ctx, key).Result()
    if err != nil {
        return false, err
    }
    if count == 1 {
        rdb.Expire(ctx, key, window)
    }
    return count <= int64(limit), nil
}

Les fenêtres fixes ont un bord bien connu : un appelant peut envoyer limit requêtes à la fin d'une fenêtre et limit de plus au début de la suivante, soit 2 × limit en un peu plus d'une seconde. La réponse habituelle est une fenêtre glissante dans un script Lua, exécuté atomiquement à l'intérieur de Redis :

-- KEYS[1] = clé du bucket, ARGV = now (ms), window (ms), limit
local now    = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit  = tonumber(ARGV[3])

redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)
local count = redis.call('ZCARD', KEYS[1])
if count < limit then
  redis.call('ZADD', KEYS[1], now, now)
  redis.call('PEXPIRE', KEYS[1], window)
  return 1
end
return 0

C'est précis. Chaque nœud voit le même état, la limite est vraiment globale, et la fenêtre glissante ferme le trou aux frontières. Pour beaucoup de systèmes, c'est la bonne réponse et vous pouvez vous arrêter là.

Étape trois : là où le modèle Redis casse

Le design Redis a une propriété qui semble inoffensive et devient fatale : chaque requête, sans exception, fait un aller-retour réseau avant que vous sachiez s'il faut l'autoriser.

Suivez ce que ça coûte à mesure que vous grandissez.

• De la latence dans le chemin critique. Chaque requête attend maintenant Redis avant de continuer. Un aller-retour, c'est une milliseconde ou deux un bon jour. Vous venez de l'ajouter au p50 de chaque endpoint, et la queue est pire quand Redis est chargé.
• Une dépendance partagée dans le chemin critique. Si Redis est lent, chaque service rate-limité est lent. Si Redis est en panne, soit vous échouez en mode ouvert (plus de limitation), soit en mode fermé (tout rejeter). Vous avez couplé la disponibilité de chaque service à un seul store.
• Les clés chaudes (hot keys). Un appelant populaire ou un endpoint chaud dirige tout son trafic vers une seule clé, donc un seul shard Redis. Vous ne pouvez pas vous en sortir en shardant ; le sharding découpe les clés, pas la charge sur une clé unique.
• La taxe de l'état global. Maintenir un compteur global exact et en temps réel signifie que chaque nœud parle en permanence au même état de référence. L'équipe d'Uber a constaté qu'à leur volume ce n'était tout simplement pas viable, estimant que « des centaines de clusters Redis seraient nécessaires pour maintenir un état global exact en temps réel ».

Les chiffres qui font casser ça ne sont pas subtils. Uber tourne à l'ordre de 80 millions de requêtes par seconde, sur plus de 1 100 services et des centaines de milliers de hôtes. À cette échelle, un aller-retour par requête vers un store partagé n'est pas une taxe que vous pouvez vous offrir. Le store est le goulot d'étranglement.

Le problème racine, c'est l'exigence elle-même : un état global parfaitement exact, de façon synchrone, à chaque requête. Si vous y tenez, vous êtes coincé à le payer. Alors remettez l'exigence en question.

Le virage : appliquer localement, coordonner globalement

Voici l'idée qui débloque l'échelle. Vous n'avez pas besoin du compte global exact à chaque requête. Vous avez besoin que chaque nœud prenne une bonne décision locale, en s'appuyant sur une image globale légèrement périmée. Un rate limit est une soupape de sécurité, pas un grand livre comptable. Si l'application retarde le trafic réel d'une seconde ou deux, presque rien ne casse.

Séparez donc les deux tâches que Redis faisait en même temps :

1. L'application se fait localement, dans le chemin critique, sans aucun appel réseau. Rapide.
2. La coordination se fait hors bande, de façon asynchrone. Les nœuds rapportent ce qu'ils voient ; un control plane agrège et leur dit à quel point ils doivent freiner.

Le Global Rate Limiter d'Uber est une boucle de rétroaction à trois niveaux bâtie exactement sur cette séparation :

                                        ┌───────────────────────┐
                                        │  Contrôleur global /  │  agrège l'usage des zones,
                                        │  régional             │  calcule les drop ratios,
                                        └───────────▲───────────┘  pousse les directives vers le bas
                                            usage   │   drop ratio
                                                    │
                                        ┌───────────┴───────────┐
                                        │  Agrégateurs de zone  │  somment les comptes par hôte
                                        └───────────▲───────────┘  en usage de zone
                                            comptes │   drop ratio
                                                    │
                            ┌───────────────┬───────┴───────┬───────────────┐
                            │ Data plane    │ Data plane    │ Data plane    │  applique localement,
                            │ (proxy mesh)  │ (proxy mesh)  │ (proxy mesh)  │  rapporte les comptes
                            └───────────────┴───────────────┴───────────────┘
                                ▲ décision dans le chemin critique, sans saut réseau

Les proxies décident chaque requête localement. En arrière-plan ils rapportent les comptes par hôte vers les agrégateurs de zone, qui remontent vers les contrôleurs, qui calculent à quel point chaque bucket est en surcharge et repoussent un seul nombre vers le bas : le drop ratio. Toute la boucle se referme en quelques secondes.

L'algorithme : le rejet probabiliste

Une fois qu'un nœud a un drop ratio du control plane, l'application devient presque triviale, et c'est la partie à bien intégrer. Au lieu de compter vers une limite dure, chaque nœud rejette un pourcentage de requêtes. Le pourcentage est calculé à partir de l'écart entre la flotte et sa limite :

dropRatio = (actualRPS - limitRPS) / actualRPS

Si la flotte tourne à 1,5× sa limite, c'est (150 - 100) / 150 ≈ 0,33, donc chaque nœud rejette environ un tiers de ses requêtes. Additionnez les survivants sur tous les nœuds et vous retombez près de la limite, sans qu'aucun nœud ne compte jamais l'état global.

type Limiter struct {
    dropRatio atomic.Value // float64, mis à jour par lz boucle du control plane
}

// Allow est appelé dans le chemin critique. Pas de réseau, pas de verrou sur le chemin rapide.
func (l *Limiter) Allow() bool {
    ratio, _ := l.dropRatio.Load().(float64)
    if ratio <= 0 {
        return true // la flotte est sous sa limite, on laisse tout passer
    }
    // rejette chaque requête indépendamment avec la probabilité = ratio
    return rand.Float64() >= ratio
}

// mis à jour de façon asynchrone, hors du chemin des requêtes, chaque ~seconde
func (l *Limiter) SetDropRatio(actualRPS, limitRPS float64) {
    ratio := 0.0
    if actualRPS > limitRPS {
        ratio = (actualRPS - limitRPS) / actualRPS
    }
    l.dropRatio.Store(ratio)
}

Regardez ce que ça nous rapporte. Allow() est un seul load atomique et un nombre aléatoire : pas de contention de verrou, pas de Redis, pas de clé chaude. La partie coûteuse, le calcul du ratio, a quitté le chemin des requêtes entièrement et tourne une fois par seconde sur des données agrégées. Le passage d'Uber à ce modèle a réduit drastiquement les latences de queue, avec un p99.5 qui chute jusqu'à 90 % une fois l'aller-retour Redis disparu.

Le piège est honnête et mérite d'être dit : comme le drop ratio repose sur des données agrégées chaque seconde, l'application peut retarder le trafic réel de 2 à 3 secondes. Pour un pic soudain et extrêmement bref, le système réagit avec un temps de retard. En pratique cette fenêtre importe rarement, et l'échanger est précisément ce qui fait tenir l'échelle.

Les compromis, côte à côte

Il n'y a pas de repas gratuit ici, seulement un échange : vous abandonnez la précision exacte en temps réel et vous gagnez la capacité d'appliquer des limites à une échelle où le modèle exact ne peut physiquement pas tourner.

Deux détails qui rendent le système prêt pour la production

L'algorithme central est le titre, mais deux pièces opérationnelles sont ce qui permet à une équipe de vraiment lui faire confiance.

Échouer en mode ouvert. Si le control plane devient silencieux, les nœuds continuent de servir le trafic avec le dernier ratio qu'ils tenaient, ou aucun. Un rate limiter qui met tout le système à terre quand lui tombe est pire que pas de rate limiter du tout. L'application locale est ce qui rend ça sûr : un nœud n'a besoin de rien d'externe pour continuer à répondre.

Le mode shadow. Avant qu'une nouvelle limite n'applique quoi que ce soit, faites-la tourner en shadow : calculez ce qui aurait été rejeté et émettez-le comme métrique, ne rejetez rien. Les équipes regardent le graphe, confirment que la limite est saine face au trafic réel, et seulement ensuite basculent en mode application. Uber couple ça à un réglage automatisé qui dérive les limites de plusieurs semaines de pics observés plus une marge, pour que les limites suivent le trafic au lieu de pourrir dans un YAML que quelqu'un a réglé il y a deux ans.

Ce qu'il faut retenir

• Le rate limiting sur un seul nœud est facile ; tout le problème est la coordination. Chaque décision de conception est en réalité une décision sur la quantité de précision dans cette coordination que vous acceptez d'échanger contre l'échelle.
• Un store partagé dans le chemin critique est un plafond de scalabilité. Ça marche à merveille jusqu'à ce que l'aller-retour par requête, et le store lui-même, deviennent le goulot. Sachez où se trouve ce plafond pour votre trafic.
• Relâcher « exact et temps réel » vers « approximatif et légèrement périmé » change tout le design. Un retard de 1 à 3 secondes vous permet de déplacer l'application en local et de supprimer la dépendance partagée entièrement.
• Le rejet probabiliste transforme un compte global difficile en une décision locale triviale : rejeter avec la probabilité (actual − limit) / actual, calculée hors bande.
• La limitation au niveau infrastructure bat celle au niveau applicatif en haut de la courbe d'échelle, parce qu'elle applique uniformément à travers chaque service sans que chacun ne réimplémente le même compteur.

Si vous tournez à des milliers de requêtes par seconde, la fenêtre glissante Redis est probablement le bon outil et vous ne devriez pas sur-concevoir. Mais si vous fixez le point où un aller-retour par requête cesse d'être abordable, la réponse n'est pas un Redis plus gros. C'est d'arrêter de demander un compte globalement exact à chaque requête, et de laisser chaque nœud décider par lui-même avec un nombre qui est assez bon.