CS Fundamentals Trainer · Guias
Projetar um rate limiter
Onde ele vive, os algoritmos e seus trade-offs, código funcional, Redis em escala e os números.
30 min de leitura
Um rate limiter limita quantas requisições um cliente pode fazer em um período de tempo. Ele protege contra abuso, impede que um cliente barulhento faça os outros passarem fome e evita que uma tempestade de retries transforme um problema pequeno em uma indisponibilidade. É uma das perguntas de design de sistemas mais comuns em entrevistas, e uma peça que você vai construir de verdade mais cedo ou mais tarde.
1. Delimite o problema
Antes de desenhar caixas, pergunte o que está sendo limitado e por quê. As respostas mudam o design.
- Quem é limitado? Um endereço IP, um usuário, uma chave de API, um tenant, ou todos eles com regras diferentes.
- O que acontece no limite? Rejeitar com
429 Too Many Requests, desacelerar a requisição ou colocá-la em fila. - Quão estrito precisa ser? Um limitador de abuso pode errar por alguns por cento. Uma cota paga, cobrada dos clientes, não pode.
- Quanto tráfego? Milhares de requisições por segundo significam que o armazenamento dos contadores está no caminho quente de toda chamada. A seção 6 coloca números nisso.
- Um servidor ou vários? A maioria dos problemas interessantes começa com "vários".
O limitador precisa adicionar muito pouca latência, usar pouca memória e continuar funcionando se o próprio armazenamento falhar. Decida de antemão se ele falha aberto (deixa o tráfego passar) ou falha fechado (bloqueia). Aberto é o padrão certo para uma API pública: uma indisponibilidade do limitador não deve virar uma indisponibilidade da API. Limites de segurança falham fechados: se o armazenamento por trás de "5 tentativas de login por conta" estiver fora do ar, deixar todo mundo tentar senhas sem limite anula o propósito. Muitas vezes a resposta é por regra, não por sistema.
2. Onde ele vive?
Há três lugares para colocar a verificação, e a escolha depende principalmente de quem controla o código.
Diagram: Three places to enforce a limit
- No API gateway é a resposta usual. Um único lugar, nenhum código em cada serviço, e as requisições rejeitadas nunca chegam aos seus servidores. Gateways de nuvem e proxies reversos como Nginx e Envoy já trazem isso embutido.
- No serviço dá regras que o gateway não consegue expressar, como "5 tentativas de senha por conta", ao preço de repetir a lógica.
- No cliente é uma cortesia, não uma defesa. Qualquer um pode pulá-lo.
3. Quatro algoritmos
Cada algoritmo responde à mesma pergunta, "esta requisição pode passar?", com um trade-off diferente de memória e precisão.
Token bucket
Um balde guarda até capacity tokens e é reabastecido a rate tokens por segundo. Cada requisição retira um token. Com o balde vazio, a requisição é rejeitada.
Diagram: Token bucket decision for one request
Ele permite rajadas curtas (até a capacidade) enquanto mantém a média de longo prazo na taxa de reabastecimento, e precisa de apenas dois números por cliente: a contagem de tokens e o horário do último reabastecimento. Não existe um timer que adicione tokens: o reabastecimento é preguiçoso, calculado a partir do tempo decorrido quando a próxima requisição chega. A Stripe descreve o uso de um token bucket em produção [1], e o próprio algoritmo é um clássico da modelagem de tráfego de rede [13].
Leaky bucket
"Leaky bucket" significa duas coisas diferentes, e confundi-las é um deslize comum em entrevistas.
- Como fila. As requisições entram em uma fila de tamanho fixo e saem a uma taxa constante. Ele suaviza rajadas em um fluxo uniforme, o que serve a um backend que precisa de carga estável. Adiciona latência (as requisições esperam na fila) e, quando a fila está cheia, novas requisições são descartadas.
- Como medidor. Um contador enche a cada requisição e esvazia a uma taxa constante; uma requisição que o faria transbordar é rejeitada. Não há fila nem espera. É o mesmo comportamento de um token bucket visto de cabeça para baixo (espaço livre em vez de tokens).
Este guia usa a versão em fila quando diz "leaky bucket". Se você só precisa limitar a taxa e não precisa suavizar o tráfego, a versão medidor não acrescenta nada em relação a um token bucket. As duas leituras são descritas lado a lado em [12].
Fixed window counter
Conte as requisições em cada janela de relógio (por exemplo, por minuto) e rejeite acima do limite. É a opção mais simples, com um inteiro por cliente e janela. Sua falha é a fronteira: um cliente pode enviar o limite inteiro às 12:00:59 e de novo às 12:01:00, o dobro do limite em dois segundos.
Diagram: Fixed windows allow 200 requests in 20 seconds
Cada janela vê apenas 100 requisições, então nenhuma rejeita nada, e ainda assim qualquer intervalo de 60 segundos que cubra as duas rajadas contém 200.
Sliding window
Uma janela deslizante remove esse pico olhando os últimos N segundos em vez do minuto atual do relógio. Existem duas versões, e elas não são igualmente precisas.
- Um sliding log guarda um timestamp por requisição e conta os que estão dentro da janela. É o único exato [2]. A memória cresce com o limite, mas para uma regra como "100 por hora" são apenas 100 timestamps por chave, o que é aceitável. Para limites assim pequenos, prefira o log.
- Um sliding window counter mantém duas contagens de janela fixa e estima o total deslizante como
previous × overlap + current, ondeoverlapé a fração da janela anterior que ainda está dentro da janela deslizante. É uma aproximação: supõe que as requisições da janela anterior estavam distribuídas uniformemente, o que nem sempre é verdade. Em troca, precisa de dois inteiros por cliente, qualquer que seja o limite, e por isso vence para limites muito grandes e clientes muito numerosos. A Cloudflare o mediu em tráfego real e o encontrou errado em apenas uma fração minúscula das requisições [2].
Diagram: The sliding window counter weights the previous window by its overlap
Às 12:01:30 a janela deslizante alcança 12:00:30, então metade da janela anterior ainda está dentro: a estimativa é 80 × 0.5 + 40 = 80.
| Algoritmo | Memória por cliente | Rajadas | Precisão |
|---|---|---|---|
| Token bucket | 2 números | Permitidas até a capacidade | Exata para a própria regra |
| Leaky bucket (fila) | Fila de tamanho fixo | Suavizadas | Exata, adiciona latência |
| Fixed window | 1 contador | Até 2x na fronteira | Aproximada |
| Sliding log | Um timestamp por requisição | Impedidas | Exata |
| Sliding window counter | 2 contadores | Quase sempre impedidas | Aproximada (distribuição uniforme) |
Para a maioria das APIs, comece com um token bucket. Escolha um sliding log quando a regra precisa ser estrita e o limite é pequeno ("100 por hora"), e um sliding window counter quando ele precisa ser barato em escala enorme.
4. Código funcional
Os diagramas escondem os detalhes que as pessoas esquecem: o reabastecimento preguiçoso, a fórmula de ponderação, o que exatamente é descartado. Aqui estão os quatro algoritmos para um único processo, em quatro linguagens (escolha uma linguagem nas abas; sua escolha é lembrada para todos os exemplos). Cada um guarda seu estado em memória e o protege, porque duas threads poderiam, de outro modo, ler o mesmo estado e as duas passarem.
Fixed window counter
import threading
import time
class FixedWindowCounter:
def __init__(self, limit, window): # window in seconds
self.limit, self.window = limit, window
self.start, self.count = 0.0, 0
self.lock = threading.Lock()
def allow(self):
with self.lock:
now = time.time()
start = now - now % self.window # start of the current window
if start != self.start: # a new window: the count starts again
self.start, self.count = start, 0
if self.count >= self.limit:
return False
self.count += 1
return True
type FixedWindowCounter struct {
mu sync.Mutex
limit int
window time.Duration
start time.Time
count int
}
func (f *FixedWindowCounter) Allow() bool {
f.mu.Lock()
defer f.mu.Unlock()
start := time.Now().Truncate(f.window) // start of the current window
if !start.Equal(f.start) { // a new window: the count starts again
f.start, f.count = start, 0
}
if f.count >= f.limit {
return false
}
f.count++
return true
}
class FixedWindowCounter {
constructor(limit, windowMs) {
this.limit = limit;
this.windowMs = windowMs;
this.start = 0;
this.count = 0;
}
allow() {
const now = Date.now();
const start = now - (now % this.windowMs); // start of the current window
if (start !== this.start) { // a new window: the count starts again
this.start = start;
this.count = 0;
}
if (this.count >= this.limit) return false;
this.count += 1;
return true;
}
}
public sealed class FixedWindowCounter
{
private readonly object _lock = new();
private readonly int _limit;
private readonly long _windowMs;
private long _start;
private int _count;
public FixedWindowCounter(int limit, TimeSpan window)
{
_limit = limit;
_windowMs = (long)window.TotalMilliseconds;
}
public bool Allow()
{
lock (_lock)
{
long now = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
long start = now - now % _windowMs; // start of the current window
if (start != _start) // a new window: the count starts again
{
_start = start;
_count = 0;
}
if (_count >= _limit) return false;
_count++;
return true;
}
}
}
Sliding log
from collections import deque
class SlidingLog:
def __init__(self, limit, window): # window in seconds
self.limit, self.window = limit, window
self.log = deque() # accepted requests, oldest first
self.lock = threading.Lock()
def allow(self):
with self.lock:
now = time.monotonic()
while self.log and self.log[0] <= now - self.window:
self.log.popleft() # this one left the window
if len(self.log) >= self.limit:
return False
self.log.append(now)
return True
type SlidingLog struct {
mu sync.Mutex
limit int
window time.Duration
log []time.Time // accepted requests, oldest first
}
func (s *SlidingLog) Allow() bool {
s.mu.Lock()
defer s.mu.Unlock()
now := time.Now()
i := 0
for i < len(s.log) && !s.log[i].After(now.Add(-s.window)) {
i++ // this one left the window
}
s.log = s.log[i:]
if len(s.log) >= s.limit {
return false
}
s.log = append(s.log, now)
return true
}
class SlidingLog {
constructor(limit, windowMs) {
this.limit = limit;
this.windowMs = windowMs;
this.log = []; // accepted requests, oldest first
}
allow() {
const now = performance.now();
while (this.log.length && this.log[0] <= now - this.windowMs) {
this.log.shift(); // this one left the window
}
if (this.log.length >= this.limit) return false;
this.log.push(now);
return true;
}
}
using System.Diagnostics;
public sealed class SlidingLog
{
private readonly object _lock = new();
private readonly int _limit;
private readonly long _windowTicks;
private readonly Queue<long> _log = new(); // accepted requests, oldest first
public SlidingLog(int limit, TimeSpan window)
{
_limit = limit;
_windowTicks = (long)(window.TotalSeconds * Stopwatch.Frequency);
}
public bool Allow()
{
lock (_lock)
{
long now = Stopwatch.GetTimestamp();
while (_log.Count > 0 && _log.Peek() <= now - _windowTicks)
_log.Dequeue(); // this one left the window
if (_log.Count >= _limit) return false;
_log.Enqueue(now);
return true;
}
}
}
Token bucket
import threading
import time
class TokenBucket:
def __init__(self, capacity, rate): # rate = tokens added per second
self.capacity, self.rate = capacity, rate
self.tokens, self.last = capacity, time.monotonic()
self.lock = threading.Lock()
def allow(self, cost=1):
with self.lock:
now = time.monotonic()
# lazy refill: add what was earned since the last call, up to capacity
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
self.last = now
if self.tokens < cost:
return False
self.tokens -= cost
return True
type TokenBucket struct {
mu sync.Mutex
capacity float64
rate float64 // tokens added per second
tokens float64
last time.Time
}
func NewTokenBucket(capacity, rate float64) *TokenBucket {
return &TokenBucket{capacity: capacity, rate: rate, tokens: capacity, last: time.Now()}
}
func (b *TokenBucket) Allow(cost float64) bool {
b.mu.Lock()
defer b.mu.Unlock()
now := time.Now() // carries a monotonic reading, so Sub ignores clock changes
// lazy refill: add what was earned since the last call, up to capacity
b.tokens = math.Min(b.capacity, b.tokens+now.Sub(b.last).Seconds()*b.rate)
b.last = now
if b.tokens < cost {
return false
}
b.tokens -= cost
return true
}
class TokenBucket {
constructor(capacity, rate) { // rate = tokens added per second
this.capacity = capacity;
this.rate = rate;
this.tokens = capacity;
this.last = performance.now(); // monotonic, in milliseconds
}
allow(cost = 1) {
const now = performance.now();
// lazy refill: add what was earned since the last call, up to capacity
this.tokens = Math.min(this.capacity, this.tokens + ((now - this.last) / 1000) * this.rate);
this.last = now;
if (this.tokens < cost) return false;
this.tokens -= cost;
return true;
}
}
using System.Diagnostics;
public sealed class TokenBucket
{
private readonly object _lock = new();
private readonly double _capacity, _rate; // rate = tokens added per second
private double _tokens;
private long _last = Stopwatch.GetTimestamp();
public TokenBucket(double capacity, double rate)
{
_capacity = capacity;
_rate = rate;
_tokens = capacity;
}
public bool Allow(double cost = 1)
{
lock (_lock)
{
long now = Stopwatch.GetTimestamp(); // monotonic
double elapsed = Stopwatch.GetElapsedTime(_last, now).TotalSeconds;
// lazy refill: add what was earned since the last call, up to capacity
_tokens = Math.Min(_capacity, _tokens + elapsed * _rate);
_last = now;
if (_tokens < cost) return false;
_tokens -= cost;
return true;
}
}
}
Sliding window counter
class SlidingWindowCounter:
def __init__(self, limit, window): # window in seconds
self.limit, self.window = limit, window
self.start, self.current, self.previous = 0.0, 0, 0
self.lock = threading.Lock()
def allow(self):
with self.lock:
now = time.time()
start = now - now % self.window # start of the current fixed window
if start != self.start:
# exactly one window later: current becomes previous; longer: nothing to carry
self.previous = self.current if start - self.start == self.window else 0
self.current, self.start = 0, start
overlap = 1 - (now - start) / self.window
if self.previous * overlap + self.current + 1 > self.limit:
return False
self.current += 1
return True
// Create it with &SlidingWindowCounter{limit: 100, window: time.Minute}.
type SlidingWindowCounter struct {
mu sync.Mutex
limit float64
window time.Duration
start time.Time // start of the current fixed window
current float64
previous float64
}
func (s *SlidingWindowCounter) Allow() bool {
s.mu.Lock()
defer s.mu.Unlock()
now := time.Now()
start := now.Truncate(s.window) // start of the current fixed window
if !start.Equal(s.start) {
// exactly one window later: current becomes previous; longer: nothing to carry
if start.Sub(s.start) == s.window {
s.previous = s.current
} else {
s.previous = 0
}
s.current, s.start = 0, start
}
overlap := 1 - float64(now.Sub(start))/float64(s.window)
if s.previous*overlap+s.current+1 > s.limit {
return false
}
s.current++
return true
}
class SlidingWindowCounter {
constructor(limit, windowMs) {
this.limit = limit;
this.windowMs = windowMs;
this.start = 0;
this.current = 0;
this.previous = 0;
}
allow() {
const now = Date.now();
const start = now - (now % this.windowMs); // start of the current fixed window
if (start !== this.start) {
// exactly one window later: current becomes previous; longer: nothing to carry
this.previous = start - this.start === this.windowMs ? this.current : 0;
this.current = 0;
this.start = start;
}
const overlap = 1 - (now - start) / this.windowMs;
if (this.previous * overlap + this.current + 1 > this.limit) return false;
this.current += 1;
return true;
}
}
public sealed class SlidingWindowCounter
{
private readonly object _lock = new();
private readonly double _limit;
private readonly long _windowMs;
private long _start;
private double _current, _previous;
public SlidingWindowCounter(double limit, TimeSpan window)
{
_limit = limit;
_windowMs = (long)window.TotalMilliseconds;
}
public bool Allow()
{
lock (_lock)
{
long now = DateTimeOffset.UtcNow.ToUnixTimeMilliseconds();
long start = now - now % _windowMs; // start of the current fixed window
if (start != _start)
{
// exactly one window later: current becomes previous; longer: nothing to carry
_previous = start - _start == _windowMs ? _current : 0;
_current = 0;
_start = start;
}
double overlap = 1 - (double)(now - start) / _windowMs;
if (_previous * overlap + _current + 1 > _limit) return false;
_current++;
return true;
}
}
}
Leaky bucket (a versão em fila)
As requisições esperam em uma fila limitada e um worker retira uma a uma a uma taxa fixa. Uma requisição que encontra a fila cheia é descartada. (A versão medidor é o token bucket acima.)
import queue
class LeakyBucket:
def __init__(self, capacity, rate, handle): # rate = requests processed per second
self.q = queue.Queue(maxsize=capacity)
self.handle = handle # the function that does the real work
threading.Thread(target=self._drain, args=(1 / rate,), daemon=True).start()
def submit(self, request):
try:
self.q.put_nowait(request) # wait in line...
return True
except queue.Full:
return False # ...or be dropped: the bucket is full
def _drain(self, interval):
while True:
self.handle(self.q.get()) # one request leaks out
time.sleep(interval)
type LeakyBucket struct{ queue chan func() }
func NewLeakyBucket(capacity int, rate float64) *LeakyBucket {
b := &LeakyBucket{queue: make(chan func(), capacity)}
go func() {
tick := time.NewTicker(time.Duration(float64(time.Second) / rate))
defer tick.Stop()
for job := range b.queue {
<-tick.C // one request leaks out per tick
job()
}
}()
return b
}
func (b *LeakyBucket) Submit(job func()) bool {
select {
case b.queue <- job: // wait in line...
return true
default: // ...or be dropped: the bucket is full
return false
}
}
class LeakyBucket {
constructor(capacity, rate) { // rate = requests processed per second
this.capacity = capacity;
this.queue = [];
// one request leaks out per tick
setInterval(() => this.queue.shift()?.(), 1000 / rate).unref();
}
submit(job) {
if (this.queue.length >= this.capacity) return false; // the bucket is full: drop
this.queue.push(job); // wait in line
return true;
}
}
using System.Threading.Channels;
public sealed class LeakyBucket
{
private readonly Channel<Func<Task>> _queue;
public LeakyBucket(int capacity, double rate) // rate = requests processed per second
{
_queue = Channel.CreateBounded<Func<Task>>(capacity);
_ = Task.Run(async () =>
{
var tick = new PeriodicTimer(TimeSpan.FromSeconds(1 / rate));
await foreach (var job in _queue.Reader.ReadAllAsync())
{
await tick.WaitForNextTickAsync(); // one request leaks out per tick
await job();
}
});
}
// false when the bucket is full: the request is dropped
public bool Submit(Func<Task> job) => _queue.Writer.TryWrite(job);
}
Algumas observações:
- Use um relógio monotônico para o bucket (
time.monotonic, otime.Nowdo Go comSub,performance.now,Stopwatch), para que uma mudança no relógio do sistema não crie nem destrua tokens. O contador de janela precisa do horário de parede para alinhar as janelas; entre servidores, esse é um motivo para obter o horário do armazenamento (seção 5). - Thread safety. Python, Go e C# podem executar requisições em várias threads, então cada limitador usa um lock. O JavaScript executa uma função por vez em sua única thread, então o código acima não precisa de nenhum; mas no momento em que você roda vários processos Node ou worker threads, cada um tem sua própria memória e você volta ao armazenamento compartilhado da seção 5.
- Um lock por limitador serve para uma demonstração. O código real mantém um objeto por chave em um mapa e trava por chave, para que clientes diferentes não esperem uns pelos outros, e remove as chaves ociosas.
- Por exemplo, com
limit=100,window=60, 30 segundos dentro do minuto, 80 requisições na janela anterior e 40 nesta: a estimativa é80 × 0.5 + 40 = 80, então (se o tempo parasse) há espaço para mais 20: a 20ª leva a estimativa a 100, o que ainda está dentro do limite, e a 21ª a levaria a 101 e seria rejeitada.
5. Fazendo funcionar em muitos servidores
Com um servidor, os contadores são um hash map em memória. Com dez servidores atrás de um load balancer, cada um contaria apenas a sua parte, e um cliente poderia obter dez vezes o limite.
A correção padrão é um armazenamento compartilhado e rápido, geralmente o Redis, para que todos os servidores verifiquem o mesmo contador.
Diagram: Two servers share one counter in Redis
Torne a verificação atômica
"Ler o contador e depois gravá-lo de volta" não é seguro quando dois servidores fazem isso ao mesmo tempo: ambos podem ver espaço para mais uma requisição. A verificação e a atualização precisam ser um único passo, o que no Redis significa um único comando ou um script Lua (um script executa sem que nenhum outro comando se intercale) [6].
Para uma janela fixa, INCR é atômico por si só, mas INCR seguido de um EXPIRE separado não é. Se o servidor cair entre as duas chamadas, a chave existe sem TTL e nunca expira, e esse cliente fica bloqueado para sempre. Coloque os dois em um script:
-- KEYS[1] = counter key, ARGV[1] = window in seconds
local n = redis.call('INCR', KEYS[1])
if n == 1 then
redis.call('EXPIRE', KEYS[1], ARGV[1])
end
return n
Para um token bucket, todo o ciclo de ler, reabastecer, decidir e gravar vai para um único script:
-- KEYS[1] = bucket key
-- ARGV[1] = capacity, ARGV[2] = refill rate (tokens per second), ARGV[3] = cost
local t = redis.call('TIME') -- the clock of Redis, not of the caller
local now = tonumber(t[1]) + tonumber(t[2]) / 1e6
local capacity, rate, cost = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
local bucket = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(bucket[1]) or capacity -- a new client starts with a full bucket
local ts = tonumber(bucket[2]) or now
tokens = math.min(capacity, tokens + (now - ts) * rate) -- lazy refill
local allowed = tokens >= cost
local retry_after = 0
if allowed then
tokens = tokens - cost
else
retry_after = (cost - tokens) / rate
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) + 1) -- idle keys clean themselves up
return {allowed and 1 or 0, tostring(tokens), tostring(retry_after)}
Por que cada linha está lá:
TIMEdentro do script. Se cada servidor de aplicação usasse seu próprio relógio, pequenas diferenças entre eles fariam tokens aparecerem ou sumirem. O Redis mantém um único relógio para todos [7]. (Em versões do Redis anteriores à 5, chameredis.replicate_commands()antes, para que um script que lê o horário ainda possa ser replicado.)- O
EXPIRE. Depois que um bucket ficou ocioso porcapacity / ratesegundos, ele volta a ficar cheio, o que equivale a um bucket novo, então apagar a chave não perde nada. Sem um TTL, um milhão de visitantes únicos encheria sua memória para sempre. tostringna saída. O Lua converte números com fração em inteiros quando os devolve ao Redis, então as frações são retornadas como strings.retry_afteré exatamente o tempo até os tokens que faltam serem ganhos, que é o que você coloca no headerRetry-After.
Os outros três algoritmos no Redis
As mesmas regras valem para todo algoritmo: um script, o horário vindo de TIME e um TTL. O script da janela fixa é o mostrado acima.
Sliding log usa um sorted set cujas pontuações são os horários das requisições:
-- KEYS[1] = sorted set of requests, scored by time
-- ARGV[1] = limit, ARGV[2] = window in seconds, ARGV[3] = a unique id for this request
local t = redis.call('TIME')
local now = tonumber(t[1]) + tonumber(t[2]) / 1e6
local limit, window = tonumber(ARGV[1]), tonumber(ARGV[2])
redis.call('ZREMRANGEBYSCORE', KEYS[1], '-inf', now - window) -- drop what left the window
if redis.call('ZCARD', KEYS[1]) >= limit then
local oldest = redis.call('ZRANGE', KEYS[1], 0, 0, 'WITHSCORES')
return {0, tostring(tonumber(oldest[2]) + window - now)} -- seconds until a slot frees up
end
redis.call('ZADD', KEYS[1], now, ARGV[3]) -- the id keeps two requests of the same instant apart
redis.call('EXPIRE', KEYS[1], math.ceil(window))
return {1, '0'}
Sliding window counter mantém um contador por janela fixa e pondera o anterior:
-- KEYS[1] = key prefix, ARGV[1] = limit, ARGV[2] = window in seconds
local t = redis.call('TIME')
local now = tonumber(t[1]) + tonumber(t[2]) / 1e6
local limit, window = tonumber(ARGV[1]), tonumber(ARGV[2])
local index = math.floor(now / window) -- which fixed window we are in
local current_key = KEYS[1] .. ':' .. index
local previous_key = KEYS[1] .. ':' .. (index - 1)
local current = tonumber(redis.call('GET', current_key) or '0')
local previous = tonumber(redis.call('GET', previous_key) or '0')
local overlap = 1 - (now - index * window) / window
if previous * overlap + current + 1 > limit then
return 0
end
redis.call('INCR', current_key)
redis.call('EXPIRE', current_key, window * 2) -- still needed as "previous" next window
return 1
O Redis Cluster espera que um script receba todas as chaves que ele toca. Este constrói os nomes das chaves dentro do script, o que funciona em um único nó; em um cluster, calcule o índice da janela no cliente e passe as duas chaves (com a mesma {hash tag}) em KEYS.
Leaky bucket (fila) não é um contador, então o Redis guarda a própria fila, uma lista, e um worker a esvazia na taxa fixa:
-- KEYS[1] = queue (a list), ARGV[1] = maximum queue length, ARGV[2] = the request
if redis.call('LLEN', KEYS[1]) >= tonumber(ARGV[1]) then
return 0 -- the bucket is full: drop
end
redis.call('RPUSH', KEYS[1], ARGV[2]) -- wait in line
return 1
Um worker então executa LPOP uma vez por intervalo e trata o que receber. Como o trabalho acontece no worker, esta versão se encaixa melhor em filas de jobs do que em uma chamada síncrona de API. Para simplesmente limitar uma taxa, use o token bucket.
Outras coisas que dão errado
- Hot keys. Uma chave muito ocupada (um grande cliente, ou um IP compartilhado) cai em um único shard do Redis e pode saturá-lo. Faça sharding por chave e, para os poucos gigantes, deixe cada servidor de aplicação manter uma parcela local do orçamento e sincronizar com o Redis em lotes, aceitando um pequeno erro.
- Failover e lag de replicação. A replicação do Redis é assíncrona. Se o primário morre e uma réplica um pouco atrasada assume, ela esqueceu as últimas atualizações de contadores, então os clientes brevemente recebem mais que o limite. Para limites de abuso isso é aceitável. Para cotas cobradas, mantenha a contagem autoritativa em um armazenamento durável e trate o Redis como um portão rápido e aproximado na frente dele.
- Latência extra e uma nova dependência. Toda requisição agora espera uma chamada de rede. Mantenha o Redis na mesma zona, defina um timeout curto (poucos milissegundos) e aplique a escolha entre falhar aberto ou fechado da seção 1 quando ele expirar. Você também pode deixar cada servidor pegar um lote de tokens e reabastecê-lo a partir do Redis só de vez em quando.
- Regiões. Se o limitador precisa funcionar entre regiões, normalmente dê a cada região seu próprio orçamento em vez de sincronizar um contador através de oceanos.
6. Números
Vale fazer uma estimativa aproximada em voz alta em uma entrevista. Estas são suposições, a serem substituídas pelas suas.
- Tráfego. 20 milhões de clientes ativos, com um pico de 200.000 requisições por segundo em toda a API. Cada requisição faz uma verificação do limitador.
- Vazão. Um único nó do Redis atende cerca de 100.000 comandos simples por segundo em hardware comum (a ferramenta
redis-benchmarkpermite medir o seu [8]), e um script Lua custa um pouco mais. A 200.000 verificações por segundo isso dá 2 a 3 nós em carga total, então planeje 4 a 8 shards, divididos por hash da chave, para deixar folga e sobreviver a uma falha. - Memória por chave. Um token bucket guarda um hash de dois campos. Com o nome da chave e o overhead próprio do Redis por chave, suponha cerca de 100 a 150 bytes.
- Total. 20 milhões de chaves × cerca de 120 bytes ≈ 2,4 GB para toda a frota, o que cabe com folga. Só clientes vistos recentemente têm uma chave, graças ao TTL, então o valor real costuma ficar bem abaixo disso.
Como isso muda com o algoritmo, para a regra "100 por hora" e os mesmos 20 milhões de clientes (tudo estimativas; meça as suas com MEMORY USAGE <key> em uma chave real [9]):
| Algoritmo | Guardado por cliente | Aprox. por chave | Aprox. total |
|---|---|---|---|
| Fixed window | 1 contador | ~70 bytes | ~1,4 GB |
| Sliding window counter | 2 contadores | ~100 bytes | ~2 GB |
| Token bucket | tokens e timestamp | ~120 bytes | ~2,4 GB |
| Sliding log | até 100 timestamps | ~3 a 5 KB | ~60 a 100 GB |
O sliding log é de 25 a 50 vezes maior, e é por isso que só é escolhido quando a exatidão compensa esse custo. A lição para uma entrevista: a memória raramente é o problema em contadores; as requisições por segundo ao armazenamento são. É isso que decide o número de shards.
7. Avisando o cliente
Um cliente rejeitado não deveria ter que adivinhar.
- Retorne
429 Too Many Requests, não 403 nem 500. O código de status é padronizado na RFC 6585 [3]. - Adicione
Retry-Aftercom os segundos a esperar (ou uma data). Ele é definido no próprio HTTP, na RFC 9110 [4], então clientes e proxies genéricos o entendem. - Muitas APIs também enviam
X-RateLimit-Limit,X-RateLimit-RemainingeX-RateLimit-Reset. Isso é uma convenção, não um padrão: os nomes e o significado de "reset" (segundos restantes ou um timestamp) diferem entre provedores. Um draft do IETF propõe headersRateLimit-*padronizados [5]. Documente o que você usar.
Diagram: A client that respects Retry-After
O jitter importa. Se mil clientes tentarem de novo exatamente três segundos depois, chegam todos juntos e estouram o limite outra vez.
8. Perguntas que entrevistadores gostam de acrescentar
Requisições que custam mais de uma
Nem toda chamada é igual: uma busca pode custar 10 vezes uma consulta simples. Em um token bucket isso é natural: uma requisição retira cost tokens em vez de um (o argumento cost nos dois exemplos de código acima). Ela é rejeitada se restarem menos que cost tokens. Decida se uma requisição cara rejeitada deve ainda consumir os tokens que encontrou (normalmente não), e dê às chamadas muito caras um cost não maior que a capacidade, ou elas nunca terão sucesso.
Um limite de rajada e um limite sustentado
APIs reais costumam ter duas regras ao mesmo tempo, como 10 por segundo e 1.000 por hora. A primeira protege contra picos, a segunda contra o uso pesado contínuo. Mantenha um bucket para cada uma e deixe a requisição passar somente se ambos permitirem.
A armadilha é consumir do primeiro bucket e depois ser recusado pelo segundo: o cliente pagou por uma requisição que nunca rodou. Verifique os dois antes de gastar qualquer um, ou faça os dois dentro de um único script Lua, que é atômico, então não há nada para desfazer. Retorne o Retry-After da regra que está rejeitando.
Retries e idempotência
Limitadores e retries interagem nos dois sentidos.
- Clientes que tentam de novo após um
429precisam esperar oRetry-Aftere usar backoff exponencial com jitter, ou seus retries viram o tráfego que os mantém bloqueados. - Uma requisição rejeitada deve contar contra o limite? Normalmente sim, senão um cliente que martela você nunca é desacelerado. Alguns sistemas contam apenas as requisições aceitas; diga qual você escolheu.
- Uma requisição que deu timeout no cliente ainda pode ter sido processada. Repetir uma chamada não idempotente como "criar um pagamento" então a executa duas vezes. Use uma idempotency key (o cliente envia um ID único, e o servidor devolve o resultado guardado para uma repetição; a API da Stripe é o exemplo conhecido [10], e há um draft do IETF para um header
Idempotency-Keypadrão [11]). O limitador e a verificação de idempotência são camadas separadas: uma requisição repetida não deve ser cobrada duas vezes por um trabalho que foi feito uma só vez.
Testando um limitador
Um limitador que passa em testes de uma requisição por vez ainda pode estar errado sob carga. Teste-o em três níveis.
- Lógica com um relógio falso. Injete o relógio para que um teste possa avançar o tempo sem dormir: depois de 5 requisições a sexta falha, depois de
1 / ratesegundos mais uma passa, um bucket ocioso nunca guarda mais quecapacity. Teste também a fronteira de uma janela. - Concorrência. Dispare, digamos, 1.000 requisições simultâneas de muitas threads ou processos contra um limite de 100, e verifique que passam exatamente 100 (token bucket: a capacidade mais o que foi reabastecido durante a execução). Uma race de ler e depois gravar aparece aqui como 101 ou mais.
- Distribuído. Execute várias instâncias da aplicação contra um Redis real, repita o teste e depois mate o primário ou adicione latência para verificar o comportamento de falhar aberto ou fechado e o que o cliente vê.
9. Coisas a mencionar em uma entrevista
- Regras como dados. Guarde os limites por rota e por plano em uma configuração ou banco de dados, com cache em memória, para que mudar um limite não exija um deploy.
- Limites rígidos e flexíveis. Um limite flexível permite um pequeno excesso ou apenas registra em log, o que é útil enquanto você ainda está ajustando.
- Chaves diferentes. Limite por IP antes do login, por usuário depois, e por chave de API para parceiros. Cuidado com muitos usuários atrás de um mesmo endereço IP corporativo.
- Monitoramento. Acompanhe quantas requisições são rejeitadas por regra. Um aumento repentino é um ataque ou uma regra apertada demais.
- Não é cura para sobrecarga. Um limitador protege contra um cliente. Quando o sistema inteiro está sobrecarregado, você também precisa de load shedding e backpressure.
Resumo rápido
- Esclareça quem e o que é limitado, e quão estrito precisa ser. Decida falhar aberto ou fechado por regra.
- Aplique no gateway.
- Token bucket por padrão, sliding log para limites pequenos e estritos, sliding window counter para escala enorme.
- Compartilhe o contador no Redis, torne a atualização atômica (um script Lua), obtenha o horário do Redis e dê um TTL a toda chave.
- Faça a aritmética: as requisições por segundo ao armazenamento decidem o número de shards, não a memória.
- Responda com 429 e
Retry-After, e faça os clientes tentarem de novo com jitter e idempotency keys. - Teste com um relógio falso, sob concorrência e contra um Redis real.
Fontes
- Stripe, Scaling your API with rate limiters. Token bucket, e por que eles usam vários limitadores juntos.
- Cloudflare, How we built rate limiting capable of scaling to millions of domains. O sliding window counter e sua precisão medida.
- IETF, RFC 6585, section 4: 429 Too Many Requests.
- IETF, RFC 9110, section 10.2.3: Retry-After.
- IETF HTTPAPI working group, RateLimit header fields for HTTP (draft).
- Documentação do Redis, Scripting with Lua. Por que um script é atômico.
- Documentação do Redis,
TIME. O relógio do servidor. - Documentação do Redis, Benchmarks. Medindo requisições por segundo com
redis-benchmark. - Documentação do Redis,
MEMORY USAGE. Medindo bytes por chave. - Stripe, Idempotent requests.
- IETF HTTPAPI working group, The Idempotency-Key HTTP header field (draft).
- Wikipedia, Leaky bucket. As versões fila e medidor.
- Wikipedia, Token bucket.
Pratique este tema: System Design System Design › Case studies