Limitador de Taxa

"Projete um rate limiter para uma API pública. Ele precisa funcionar entre muitas réplicas do API gateway, acrescentar quase nenhuma latência e permitir limites diferentes por usuário, por IP e por parceiro."

Toda API pública precisa de um, e todo sistema grande tem vários: na borda contra inundações, no gateway por cliente, dentro dos serviços para proteger uma dependência frágil. O problema é pequeno o bastante para ser projetado de ponta a ponta em 45 minutos e profundo o bastante para separar níveis: um candidato júnior diz "token bucket"; um sênior explica por que um contador de janela deslizante é preciso o suficiente, como tornar a verificação atômica entre 20 réplicas do gateway, o que acontece quando o armazenamento dos contadores cai, e por que só rate limiting não impede uma sobrecarga.

No BoxOffice, o rate limiter é a segunda linha de defesa da venda relâmpago: o WAF barra inundações óbvias, a sala de espera dosa as admissões e o gateway aplica "5 tentativas de reserva por minuto por conta" e as cotas dos parceiros revendedores.

1. Esclarecer os requisitos

A expressão "rate limiter" esconde vários produtos diferentes. Pergunte antes de desenhar (roteiro de entrevista).

Requisitos funcionais

1. Limitar o número de requisições que um cliente pode fazer numa janela de tempo; o cliente pode ser um ID de usuário, uma chave de API, um endereço IP ou uma combinação.
2. Várias regras por requisição, ex.: 10 req/s por usuário e 1 000 req/min por chave de API e 100 req/s por IP em /login.
3. Requisições rejeitadas recebem HTTP 429 Too Many Requests com uma indicação de quando tentar de novo.
4. Regras configuráveis sem novo deploy (por endpoint, por plano: gratuito, parceiro, interno).
5. Expor métricas: permitidas vs. rejeitadas por regra e cliente.

Requisitos não funcionais

Fora do escopo (diga explicitamente)

Proteção contra DDoS na camada de rede (é trabalho do WAF/CDN), cobrança por uso, detecção de abuso com aprendizado de máquina. Mencione que existem nas camadas em volta do limitador.

2. Estimativas de guardanapo (back-of-the-envelope)

# Rate limiter: assumptions (illustrative)
peak_rps       = 50_000      # API requests per second at peak
gateways       = 20          # gateway replicas
active_clients = 1_000_000   # distinct keys active in a window
rules_per_req  = 2           # e.g. per-user + per-IP
bucket_b       = 100         # one counter in Redis: key + 2 numbers + overhead, bytes
user_limit_min = 600         # per-user limit: 600 requests per minute
log_entry_b    = 50          # one timestamp in a sorted set, with overhead
redis_ops_node = 100_000     # simple ops/s one Redis node sustains (order of magnitude)
rtt_ms         = 0.5         # gateway → Redis round trip in the same zone

counter_ops    = peak_rps * rules_per_req           # one atomic op per rule (or 1 script)
script_calls   = peak_rps                            # all rules in one Lua call
counters_mb    = active_clients * rules_per_req * bucket_b / 1e6
log_gb         = active_clients * user_limit_min * log_entry_b / 1e9
redis_nodes    = script_calls * 3 / redis_ops_node   # a script costs ~3 simple ops
local_error    = gateways                             # per-replica limits: worst-case factor
added_ms       = rtt_ms

rows = [
    ("counter_ops", counter_ops, "ops/s"), ("script_calls", script_calls, "calls/s"),
    ("counters_mb", counters_mb, "MB"), ("log_gb", log_gb, "GB"),
    ("redis_nodes", redis_nodes, "nodes"), ("local_error", local_error, "x limit"),
    ("added_ms", added_ms, "ms"),
]
print("| quantity | value | unit |\n|---|---:|---|")
for name, value, unit in rows:
    v = f"{value:,.0f}" if abs(value) >= 100 else f"{value:,.2f}"
    print(f"| `{name}` | {v} | {unit} |")

O que os números dizem:

• Contadores para um milhão de clientes ocupam ~200 MB — um nó Redis guarda com folga. Um log de janela deslizante (um timestamp por requisição) precisaria de ~30 GB para os mesmos clientes: por isso o log raramente é usado em escala.
• 50 mil chamadas de script/s com ~3 operações cada dão ~1,5 nó Redis de trabalho ⇒ um pequeno Redis Cluster (3 primários + réplicas), fragmentado pela chave do cliente, com folga.
• Uma ida e volta na mesma zona acrescenta ~0,5 ms — dentro do orçamento, desde que o gateway fale com o Redis por conexões persistentes com pipelining e que todas as regras vão numa única chamada de script.
• Aplicar limit de forma independente em cada uma das 20 réplicas deixa um cliente obter até 20× o limite quando o balanceador espalha suas requisições. ⇒ ou um contador compartilhado, ou um limite local de limit / N com roteamento fixo, ou um híbrido (veja 6.3).

3. API

O limitador normalmente não é uma API pública, e sim um filtro dentro do gateway; mesmo assim, defina seu contrato — interno e externo.

# Internal (gateway → limiter library or sidecar)
check(rules=[("user:42", 10, 1s), ("ip:203.0.113.7", 100, 1s)], cost=1)
    → {allowed: true|false, remaining: 7, resetMs: 380, retryAfterMs: 0}

# External: what the API client sees
HTTP/1.1 429 Too Many Requests
Retry-After: 2
RateLimit-Policy: "per-user";q=10;w=1
RateLimit: "per-user";r=0;t=2
Content-Type: application/problem+json

{"type": "https://bx.example/problems/rate-limited", "title": "Too many requests",
 "detail": "Limit of 10 requests per second per user exceeded", "retryAfterSeconds": 2}

• 429 (RFC 6585) mais Retry-After (segundos ou uma data) é o contrato. Clientes bem-comportados tentam de novo depois desse tempo, com backoff exponencial e jitter.
• Os campos de cabeçalho RateLimit / RateLimit-Policy estão sendo padronizados pelo grupo de trabalho HTTPAPI do IETF; muitas APIs ainda usam os antigos X-RateLimit-Limit/Remaining/Reset. De qualquer forma: informe aos clientes o orçamento deles antes de baterem na parede.
• Regras são dados, não código, ex.: guardadas num serviço de configuração e em cache em todo gateway:

rules:
  - match: { path: "/v1/events/*/holds", method: POST }
    key: user
    limit: { requests: 5, per: 60s }          # 5 hold attempts per minute per account
  - match: { path: "/v1/*" }
    key: api_key
    limit: { requests: 1000, per: 60s, burst: 200 }
    plans: { partner: 10000, internal: unlimited }
  - match: { path: "/v1/auth/login" }
    key: ip
    limit: { requests: 10, per: 60s }
    on_store_failure: closed                   # security-sensitive: fail closed

4. Modelo de dados

O estado é minúsculo e de vida curta: por (regra, cliente) um contador ou uma quantidade de tokens com um timestamp, expirando automaticamente.

# Token bucket (Redis hash)              key TTL = time to refill completely × 2
rl:tb:user:42          → { tokens: 7.4, ts: 1767261600123 }

# Fixed window counter (Redis string)    key TTL = window
rl:fw:user:42:29454360 → 9            (window id = floor(now / 60 s))

# Sliding window counter: two fixed windows, current and previous
rl:sw:user:42:29454360 → 4
rl:sw:user:42:29454359 → 9

# Sliding window log (Redis sorted set)  score = timestamp
rl:log:user:42         → { 1767261600123, 1767261600201, ... }

5. Design de alto nível

flowchart LR
    c([Clientes]) --> waf["WAF / CDN<br/>limites grossos por IP"]
    waf --> lb["Balanceador de carga"]
    lb --> gw1["API gateway #1<br/>filtro de rate limit"]
    lb --> gw2["API gateway #N<br/>filtro de rate limit"]
    gw1 --> r[("Redis Cluster<br/>contadores, Lua")]
    gw2 --> r
    cfg["Serviço de configuração<br/>das regras"] -. enviado / em cache .-> gw1
    cfg -. enviado / em cache .-> gw2
    gw1 --> svc["Serviços de backend"]
    gw2 --> svc
    gw1 -. permitido / 429 .-> m["Métricas"]

Uma requisição passando pelo filtro:

sequenceDiagram
    autonumber
    participant C as Cliente
    participant G as API gateway
    participant R as Redis
    participant S as Serviço
    C->>G: POST /v1/events/42/holds (usuário 42)
    G->>G: casa as regras (cache local)
    G->>R: EVALSHA token_bucket {user:42, ip:…} now cost=1
    R-->>G: allowed=1, remaining=4
    G->>S: encaminha a requisição
    S-->>G: 201 Created
    G-->>C: 201 + RateLimit: r=4
    C->>G: 6ª tentativa no mesmo minuto
    G->>R: EVALSHA token_bucket …
    R-->>G: allowed=0, tentar de novo em 9 s
    G-->>C: 429 Too Many Requests, Retry-After: 9

6. Aprofundamentos (deep dives)

6.1 Os algoritmos

O problema de fronteira das janelas fixas é mais fácil de ver com um traço. Limite: 10 requisições por segundo; um cliente envia 10 requisições em t = 0,99 s e mais 10 em t = 1,01 s:

# How many of 20 requests (10 at t=0.99 s, 10 at t=1.01 s) does each algorithm allow?
limit, window = 10, 1.0
trace = [0.99] * 10 + [1.01] * 10

def fixed_window(ts):
    counts, ok = {}, 0
    for t in ts:
        w = int(t // window)
        if counts.get(w, 0) < limit:
            counts[w] = counts.get(w, 0) + 1
            ok += 1
    return ok

def sliding_log(ts):
    log, ok = [], 0
    for t in ts:
        log = [x for x in log if x > t - window]
        if len(log) < limit:
            log.append(t)
            ok += 1
    return ok

def sliding_counter(ts):
    counts, ok = {}, 0
    for t in ts:
        w = int(t // window)
        overlap = 1 - (t % window) / window
        estimate = counts.get(w - 1, 0) * overlap + counts.get(w, 0)
        if estimate < limit:
            counts[w] = counts.get(w, 0) + 1
            ok += 1
    return ok

def token_bucket(ts, capacity=limit, rate=limit / window):
    tokens, last, ok = capacity, 0.0, 0
    for t in ts:
        tokens = min(capacity, tokens + (t - last) * rate)
        last = t
        if tokens >= 1:
            tokens -= 1
            ok += 1
    return ok

print("| algorithm | allowed of 20 |\n|---|---:|")
for f in (fixed_window, sliding_log, sliding_counter, token_bucket):
    print(f"| `{f.__name__}` | {f(trace)} |")

A janela fixa deixa passar 20 requisições em 20 ms — o dobro do limite — porque elas caem em duas janelas diferentes. O log e o token bucket permitem exatamente 10. O contador de janela deslizante permite 11: ele supõe que as requisições da janela anterior foram distribuídas de forma uniforme, enquanto aqui todas chegaram bem no final dela — um erro pequeno e limitado em troca de dois números de estado. Por isso limitadores de produção usam token bucket ou contador de janela deslizante.

6.2 Tornando atômico entre réplicas

A implementação ingênua tem uma condição de corrida:

gateway A: GET rl:user:42      → 9          gateway B: GET rl:user:42 → 9
gateway A: 9 < 10 → allow, SET 10           gateway B: 9 < 10 → allow, SET 10
                       → 11 requests allowed, counter says 10

Ler-verificar-escrever precisa ser uma operação atômica no armazenamento. No Redis, use INCR (atômico) para contadores, ou um script Lua, que roda atomicamente no shard dono da chave:

-- token_bucket.lua   KEYS[1] = bucket key   ARGV: capacity, refill per second, cost
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])
local t        = redis.call('TIME')                       -- server clock: no skew between gateways
local now      = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

local b      = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or capacity
local ts     = tonumber(b[2]) or now
tokens = math.min(capacity, tokens + (now - ts) / 1000 * rate)

local allowed = 0
if tokens >= cost then
  tokens  = tokens - cost
  allowed = 1
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) * 2)
local retry_ms = 0
if allowed == 0 then retry_ms = math.ceil((cost - tokens) / rate * 1000) end
return { allowed, tostring(tokens), retry_ms }               -- floats → string (Redis truncates numbers)

Detalhes que mostram senioridade:

• Uma chamada por requisição para todas as regras (passe várias chaves) — mas no Redis Cluster todas as chaves de um script precisam cair no mesmo slot: use uma hash tag, ex.: rl:{user:42}:tb e rl:{user:42}:fw; regras com chaves de entidades diferentes (usuário e IP) precisam de chamadas separadas, em pipeline.
• Use o relógio do servidor (TIME) em vez do de cada gateway: 20 gateways com relógios 50 ms fora de sincronia reabasteceriam o balde de forma inconsistente.
• TTL em toda chave: clientes ociosos somem sozinhos; a memória fica proporcional aos clientes ativos.
• Carregue o script uma vez (SCRIPT LOAD) e chame-o com EVALSHA para não enviar o código-fonte a cada requisição.

6.3 Onde aplicar, e local vs. global

flowchart LR
    cl["SDK do cliente<br/>limite de cortesia"] --> edge["Borda / WAF<br/>por IP, grosso"]
    edge --> gw["API gateway<br/>por usuário / chave / plano"]
    gw --> mesh["Service mesh<br/>por serviço chamador"]
    mesh --> svc["Serviço<br/>limite de concorrência<br/>para seu banco / provedor"]

Global vs. local. Um Redis compartilhado dá um limite global exato ao custo de um salto de rede. Alternativas quando esse salto é caro demais (multirregião, taxas muito altas):

• Buckets locais com limit / N: sem rede, mas errado quando o tráfego está mal distribuído; aceitável com roteamento por hash consistente de cada cliente para um gateway.
• Local + sincronização periódica: cada gateway conta localmente e envia os deltas ao armazenamento compartilhado a cada 100 ms, lendo de volta o total global — aproximado (passa do limite em no máximo um intervalo de sincronização de tráfego), muito rápido. É mais ou menos assim que grandes CDNs fazem.
• Limites por região: limite por região e aceite que um cliente usando duas regiões obtenha até 2× — normalmente tudo bem.

# rate limiting per API key: 20 req/s per key, bursts of up to 40.
# Requests WITHOUT an X-Api-Key header have an empty key and are not limited
# (in production you would also limit them per client IP).
limit_req_zone  $http_x_api_key  zone=per_key:10m  rate=20r/s;
limit_req_status  429;
    location /catalog/ {
        limit_req  zone=per_key  burst=40  nodelay;

6.4 Quando o próprio limitador falha

• Fail-open (permitir quando o Redis está inacessível) mantém a API disponível — o padrão certo para limites comuns, porque o limitador existe para proteger o backend, e um curto período sem limites raramente é pior do que uma queda total. Combine com um bucket local de reserva para a proteção degradar em vez de sumir.
• Fail-closed (rejeitar) para limites que guardam segurança: tentativas de login, redefinição de senha, verificação de OTP — senão um atacante capaz de sobrecarregar o Redis também desliga a proteção contra força bruta.
• Coloque um timeout apertado (poucos ms) na chamada ao Redis e um circuit breaker em volta: um limitador lento é pior que nenhum, porque acrescenta latência a toda requisição (padrões de confiabilidade).

7. Gargalos, modos de falha e trade-offs

Os trade-offs para dizer em voz alta: precisão vs. latência (contadores globais exatos custam um salto de rede; locais aproximados são de graça), disponibilidade vs. proteção (fail-open vs. fail-closed, escolhido por regra), e justiça vs. simplicidade (limites por IP são fáceis, mas punem usuários atrás de um NAT compartilhado).

8. Experimente no playground

O cenário rate-limiter coloca um API gateway com rate limiting na frente de um backend de capacidade fixa.

Abrir o playground completo

9. Perguntas de follow-up que o entrevistador faz

10. Rubrica de autoavaliação

Relacionados: API gateway, Hands-on 3 (rate limiting no Nginx), Hands-on 4 (gateway e identidade), Redis, Padrões de confiabilidade.

Como se conecta

Quais aulas este caso testa? Cada ramo é uma aula cujas ideias o design usa (azul), com os componentes da paleta em que elas aparecem (verde):

flowchart LR
    CASE(["Rate limiter"]) --> EDG["Edge<br/>where limits live: WAF, gateway"]:::tech
    CASE --> CAC["Caching<br/>Redis counters, Lua atomicity"]:::tech
    CASE --> REL["Reliability<br/>fail-open vs fail-closed, load shedding"]:::tech
    CASE --> CLI["client contract<br/>429, Retry-After, jitter"]:::tech
    CASE --> PERF["Performance<br/>k6 at a known arrival rate"]:::tech
    EDG -.-> k1["waf · cdn · lb · apigw"]:::comp
    CAC -.-> k2["cache"]:::comp
    REL -.-> k3["metrics"]:::comp
    classDef comp fill:#1e9e5a22,stroke:#1e9e5a
    classDef tech fill:#2f6fed22,stroke:#2f6fed

Aulas que ele testa: Borda — API gateway · Caching — Redis · Confiabilidade — padrões (load shedding, backoff com jitter) · Desempenho · Hands-on 3 e Hands-on 4. Componentes da paleta: waf · cdn · lb · apigw · cache · metrics. Cenários: rate-limiter.

Referências

• XU, A. System Design Interview — An Insider's Guide, vol. 1, cap. 4 "Design a Rate Limiter"¹.
• Os quatro tipos de limitadores da Stripe (taxa de requisições, concorrência, descarte de carga da frota, utilização de workers)².
• O contador de janela deslizante da Cloudflare na borda³.
• O status HTTP 429⁴ e o tratamento de sobrecarga no Google⁵.