Rate Limiting

Rate limiting é o mecanismo pelo qual um sistema controla a taxa de requisições que aceita de um cliente ou de um conjunto de clientes. Sem rate limiting, um único cliente mal-comportado — intencional ou acidentalmente — pode consumir todos os recursos disponíveis e derrubar o serviço para todos os outros. Com rate limiting mal projetado, clientes legítimos são bloqueados desnecessariamente e a API se torna não confiável. A diferença está nos algoritmos escolhidos, na granularidade da identidade do cliente, e em como o sistema comunica os limites.

Rate limiting não é apenas proteção contra ataques — é também um mecanismo de modelagem de tráfego (traffic shaping) para garantir que a capacidade do sistema seja distribuída de forma previsível entre os clientes, e um sinal de qualidade de API para clientes legítimos que precisam saber com antecedência o que esperar.

Os quatro algoritmos principais

Fixed Window Counter

O algoritmo mais simples: conta as requisições em janelas de tempo fixas (ex: 1 minuto). Quando a contagem ultrapassa o limite, requisições adicionais são rejeitadas até a próxima janela começar.

-- Redis: contador por janela fixa
-- Chave: "ratelimit:{client_id}:{window_start}"
-- window_start = floor(now / window_size) * window_size

local key = "ratelimit:" .. client_id .. ":" .. window_start
local count = redis.call("INCR", key)
if count == 1 then
    redis.call("EXPIRE", key, window_size_seconds)
end
return count <= limit  -- true = permitido

Problema crítico do fixed window: boundary burst. Um cliente pode enviar 100 requisições no final de uma janela e mais 100 no início da próxima — 200 requisições em poucos segundos, mesmo com limite de 100/minuto. Esse comportamento é determinístico e exploitável.

Janela 1: [... ... ... 100 req nos últimos 2s]
Janela 2: [100 req nos primeiros 2s ...]
Total: 200 req em 4 segundos — limite violado na prática

Sliding Window Log

Mantém um log de timestamps de cada requisição. Para verificar o limite, conta quantas requisições ocorreram nos últimos N segundos (janela deslizante). Elimina o boundary burst — a janela é sempre relativa ao momento atual.

-- Redis Sorted Set: timestamps como score, request_id como member
-- Permite contar eficientemente quantas requisições ocorreram em [now-window, now]

local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])  -- ex: 60000 ms
local limit = tonumber(ARGV[3])
local key = KEYS[1]

-- Remove timestamps fora da janela
redis.call("ZREMRANGEBYSCORE", key, 0, now - window)

-- Conta requisições na janela atual
local count = redis.call("ZCARD", key)

if count < limit then
    -- Adiciona a requisição atual
    redis.call("ZADD", key, now, now .. "-" .. math.random())
    redis.call("EXPIRE", key, math.ceil(window / 1000) + 1)
    return 1  -- permitido
end
return 0  -- bloqueado

Precisão perfeita, mas o armazenamento cresce proporcionalmente ao número de requisições — para limites altos (ex: 10.000/hora), o sorted set fica grande. Adequado para limites baixos ou quando a precisão é crítica (ex: APIs de pagamento).

Sliding Window Counter

Compromisso entre fixed window e sliding window log: mantém contadores de duas janelas fixas adjacentes e calcula o valor interpolado, estimando o rate da janela deslizante sem armazenar timestamps individuais.

-- Fórmula de aproximação
-- current_window_count: requisições na janela atual
-- previous_window_count: requisições na janela anterior
-- elapsed: fração da janela atual já transcorrida (0.0 a 1.0)

estimated_count = previous_window_count * (1 - elapsed) + current_window_count

-- Exemplo:
-- Janela anterior: 80 req
-- Janela atual: 30 req
-- elapsed: 0.4 (40% da janela atual passou)
-- estimated: 80 * 0.6 + 30 = 78 req estimados na janela deslizante

A aproximação tem erro máximo de ~0.003% em distribuições uniformes — na prática, imperceptível. É o algoritmo usado pelo Cloudflare em seus sistemas de rate limiting distribuído. Armazenamento constante (dois inteiros por cliente por janela), sem crescimento proporcional ao tráfego.

Token Bucket

Um balde contém tokens. Cada requisição consome um token. Tokens são adicionados a uma taxa constante (ex: 10 tokens/segundo). Se o balde está vazio, a requisição é rejeitada. O balde tem capacidade máxima — tokens não acumulam além do limite.

-- Token Bucket com Redis (implementação atômica via Lua)
local key = KEYS[1]
local capacity = tonumber(ARGV[1])   -- capacidade máxima do balde
local rate = tonumber(ARGV[2])       -- tokens adicionados por segundo
local now = tonumber(ARGV[3])        -- timestamp atual em ms
local requested = tonumber(ARGV[4])  -- tokens necessários (geralmente 1)

local data = redis.call("HMGET", key, "tokens", "last_refill")
local tokens = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now

-- Calcular tokens adicionados desde o último acesso
local elapsed = (now - last_refill) / 1000  -- em segundos
local new_tokens = math.min(capacity, tokens + elapsed * rate)

if new_tokens >= requested then
    -- Permitido: consumir tokens
    redis.call("HMSET", key, "tokens", new_tokens - requested, "last_refill", now)
    redis.call("EXPIRE", key, math.ceil(capacity / rate) + 10)
    return {1, math.floor(new_tokens - requested)}  -- {permitido, tokens_restantes}
else
    redis.call("HMSET", key, "tokens", new_tokens, "last_refill", now)
    return {0, math.floor(new_tokens)}  -- {bloqueado, tokens_disponíveis}
end

O token bucket permite bursts controlados: se o cliente ficou inativo, acumula tokens até o limite de capacidade e pode usá-los em burst. É o algoritmo ideal quando você quer suavizar picos mas permitir aceleração temporária legítima (ex: uma pipeline que processa um lote grande ocasionalmente).

Leaky Bucket

Requisições entram em uma fila (o balde) e saem a uma taxa constante. Se o balde transborda (fila cheia), a requisição é rejeitada. Garante saída uniforme — não importa como as requisições chegam, o sistema downstream as recebe sempre na mesma taxa.

-- Leaky Bucket: implementado como fila com rate de dequeue fixo
-- Menos comum em APIs HTTP; mais usado em traffic shaping de rede
-- Em APIs, token bucket é preferido por ser mais simples e igualmente efetivo

-- Diferença fundamental:
-- Token bucket: permite burst até a capacidade, suaviza a média
-- Leaky bucket: garante taxa constante de saída, sem burst downstream

Dimensões de identidade do cliente

Rate limiting por IP é o mínimo, mas é insuficiente em produção. Múltiplos clientes podem compartilhar um IP (NAT corporativo, VPN), e atacantes usam proxies. As dimensões mais úteis:

Em produção, aplique múltiplos limites em camadas: limite global por IP (proteção contra ataques de força bruta), limite por API key ou usuário (fair use), e limite por endpoint para operações custosas (ex: busca full-text = 10/min, leitura de item = 1000/min).

Headers de resposta — RFC 6585 e convenções

Clientes precisam saber o estado do rate limiting para implementar backoff correto. Os headers padrão:

HTTP/1.1 200 OK
RateLimit-Limit: 1000          # limite total na janela
RateLimit-Remaining: 876       # requisições restantes na janela atual
RateLimit-Reset: 1715299200    # Unix timestamp quando a janela reseta
Retry-After: 45                # segundos a aguardar (em respostas 429)

# Quando bloqueado:
HTTP/1.1 429 Too Many Requests
Content-Type: application/json
RateLimit-Limit: 1000
RateLimit-Remaining: 0
RateLimit-Reset: 1715299200
Retry-After: 45

{
  "error": "rate_limit_exceeded",
  "message": "Limite de 1000 req/hora atingido",
  "retry_after": 45
}

A IETF padronizou o formato em RFC 9110 e draft-ietf-httpapi-ratelimit-headers. Evite headers proprietários como X-RateLimit-* em APIs novas — os headers sem prefixo X- são o padrão atual. Inclua Retry-After em todas as respostas 429 — sem ele, clientes fazem backoff arbitrário ou continuam tentando.

Rate limiting distribuído

Em um sistema com múltiplas instâncias do serviço, o rate limiting local (em memória) conta apenas as requisições que chegam a uma instância específica — clientes podem bypass rotando entre instâncias. Rate limiting distribuído centraliza o estado no Redis.

O trade-off é latência: cada verificação de rate limit requer uma round-trip ao Redis. Em endpoints de alta frequência, isso pode ser significativo. Otimizações:

Script Lua no Redis: execute a lógica de verificação + incremento atomicamente no Redis via script Lua — evita race conditions e reduz o número de round-trips para um único comando.

Cache local com TTL curto: mantenha um cache local do estado do rate limit por 100-500ms. Cada instância confirma com Redis periodicamente, não em cada requisição. Aceita pequeno overshoot (cliente pode exceder em ~tráfego de 500ms) em troca de latência de verificação de microsegundos.

Redis Cluster: para sistemas com milhões de clientes simultâneos, distribua as chaves de rate limit em um cluster Redis usando hash slots. Cada chave vai para um nó específico — sem coordenação entre nós para a operação de rate limit.

Throttling vs rate limiting

Rate limiting rejeita requisições que excedem o limite com 429. O cliente deve esperar e tentar novamente. Throttling (ou traffic shaping) atrasa requisições em vez de rejeitar — enfileira e processa mais devagar. Throttling preserva mais requisições mas pode causar timeouts se a fila crescer além da capacidade.

Em APIs HTTP públicas, rate limiting (rejeição com 429) é o padrão — dá feedback imediato ao cliente e não consome memória com filas longas. Throttling é mais comum em sistemas internos ou pipelines de processamento onde descartar trabalho é inaceitável.

Comparativo entre linguagens — middleware de rate limiting

// C# — Rate limiting com ASP.NET Core RateLimiter (built-in, .NET 7+)
// e Redis para estado distribuído via AspNetCoreRateLimit

// Program.cs — configuração built-in (in-process, sem Redis)
builder.Services.AddRateLimiter(options => {
    // Limite global por IP — sliding window
    options.AddPolicy("per-ip", httpContext =>
        RateLimitPartition.GetSlidingWindowLimiter(
            partitionKey: httpContext.Connection.RemoteIpAddress?.ToString() ?? "anonymous",
            factory: _ => new SlidingWindowRateLimiterOptions {
                PermitLimit = 100,
                Window = TimeSpan.FromMinutes(1),
                SegmentsPerWindow = 6,          // janela dividida em 6 segmentos de 10s
                QueueProcessingOrder = QueueProcessingOrder.OldestFirst,
                QueueLimit = 0,                 // sem fila — rejeição imediata
            }
        )
    );

    // Limite por API key — token bucket
    options.AddPolicy("per-apikey", httpContext => {
        var apiKey = httpContext.Request.Headers["X-API-Key"].ToString();
        return string.IsNullOrEmpty(apiKey)
            ? RateLimitPartition.GetNoLimiter("anonymous")
            : RateLimitPartition.GetTokenBucketLimiter(
                partitionKey: $"apikey:{apiKey}",
                factory: _ => new TokenBucketRateLimiterOptions {
                    TokenLimit = 1000,
                    ReplenishmentPeriod = TimeSpan.FromHours(1),
                    TokensPerPeriod = 1000,
                    AutoReplenishment = true,
                }
            );
    });

    // Resposta 429 customizada com headers corretos
    options.OnRejected = async (context, token) => {
        context.HttpContext.Response.StatusCode = StatusCodes.Status429TooManyRequests;

        if (context.Lease.TryGetMetadata(MetadataName.RetryAfter, out var retryAfter)) {
            context.HttpContext.Response.Headers["Retry-After"] =
                ((int)retryAfter.TotalSeconds).ToString();
        }

        context.HttpContext.Response.Headers["RateLimit-Limit"] = "100";
        await context.HttpContext.Response.WriteAsJsonAsync(new {
            error = "rate_limit_exceeded",
            retry_after = (int?)retryAfter.TotalSeconds
        }, token);
    };
});

// Aplicação por endpoint
app.MapGet("/api/search", SearchHandler)
    .RequireRateLimiting("per-apikey");

app.MapPost("/api/orders", OrderHandler)
    .RequireRateLimiting("per-ip");

# Python — Rate limiting com FastAPI e Redis (token bucket via Lua script)

import time
import hashlib
from typing import Callable
from fastapi import FastAPI, Request, Response, HTTPException
from fastapi.routing import APIRoute
import redis.asyncio as aioredis

app = FastAPI()
redis_client: aioredis.Redis = None

# Script Lua para token bucket — executado atomicamente no Redis
TOKEN_BUCKET_SCRIPT = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now

local elapsed = (now - last_refill) / 1000
local new_tokens = math.min(capacity, tokens + elapsed * rate)

if new_tokens >= 1 then
    redis.call('HMSET', key, 'tokens', new_tokens - 1, 'last_refill', now)
    redis.call('EXPIRE', key, math.ceil(capacity / rate) + 10)
    return {1, math.floor(new_tokens - 1), math.ceil((1 - new_tokens + 1) / rate * 1000)}
else
    redis.call('HMSET', key, 'tokens', new_tokens, 'last_refill', now)
    local wait_ms = math.ceil((1 - new_tokens) / rate * 1000)
    return {0, 0, wait_ms}
end
"""

def rate_limit(capacity: int = 100, rate: float = 100/3600):
    """Decorator de rate limit por IP usando token bucket."""
    script = None

    def decorator(func: Callable):
        async def wrapper(request: Request, *args, **kwargs):
            nonlocal script
            if script is None:
                script = redis_client.register_script(TOKEN_BUCKET_SCRIPT)

            client_ip = request.client.host
            key = f"rl:ip:{client_ip}"
            now_ms = int(time.time() * 1000)

            allowed, remaining, wait_ms = await script(
                keys=[key],
                args=[capacity, rate, now_ms]
            )

            # Adiciona headers de rate limit sempre
            headers = {
                "RateLimit-Limit": str(capacity),
                "RateLimit-Remaining": str(remaining),
            }

            if not allowed:
                retry_after = max(1, wait_ms // 1000)
                raise HTTPException(
                    status_code=429,
                    detail={
                        "error": "rate_limit_exceeded",
                        "retry_after": retry_after,
                    },
                    headers={**headers, "Retry-After": str(retry_after)},
                )

            response = await func(request, *args, **kwargs)
            for k, v in headers.items():
                response.headers[k] = v
            return response

        return wrapper
    return decorator


@app.get("/api/search")
@rate_limit(capacity=10, rate=10/60)  # 10 req/minuto
async def search(request: Request, q: str):
    return {"results": [], "query": q}

// Go — middleware de rate limiting com golang.org/x/time/rate (in-process)
// e Redis para distribuído

package middleware

import (
    "context"
    "encoding/json"
    "net/http"
    "strconv"
    "sync"
    "time"

    "golang.org/x/time/rate"
    "github.com/redis/go-redis/v9"
)

// In-process: limiter por IP com cleanup de entradas inativas
type IPRateLimiter struct {
    limiters sync.Map
    rate     rate.Limit  // tokens por segundo
    burst    int         // capacidade máxima
}

func NewIPRateLimiter(r rate.Limit, burst int) *IPRateLimiter {
    l := &IPRateLimiter{rate: r, burst: burst}
    go l.cleanup()  // goroutine de limpeza de limiters inativos
    return l
}

func (l *IPRateLimiter) getLimiter(ip string) *rate.Limiter {
    v, _ := l.limiters.LoadOrStore(ip, rate.NewLimiter(l.rate, l.burst))
    return v.(*rate.Limiter)
}

func (l *IPRateLimiter) cleanup() {
    ticker := time.NewTicker(10 * time.Minute)
    for range ticker.C {
        l.limiters.Range(func(k, _ any) bool {
            l.limiters.Delete(k)
            return true
        })
    }
}

func (l *IPRateLimiter) Middleware(next http.Handler) http.Handler {
    return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        ip := r.RemoteAddr
        limiter := l.getLimiter(ip)

        reservation := limiter.Reserve()
        if !reservation.OK() {
            w.Header().Set("RateLimit-Limit", strconv.Itoa(l.burst))
            w.Header().Set("RateLimit-Remaining", "0")
            w.Header().Set("Retry-After", "1")
            w.WriteHeader(http.StatusTooManyRequests)
            json.NewEncoder(w).Encode(map[string]any{
                "error":       "rate_limit_exceeded",
                "retry_after": 1,
            })
            return
        }

        delay := reservation.Delay()
        if delay > 100*time.Millisecond {
            // Delay muito longo — cancelar e rejeitar
            reservation.Cancel()
            retryAfter := int(delay.Seconds()) + 1
            w.Header().Set("Retry-After", strconv.Itoa(retryAfter))
            w.WriteHeader(http.StatusTooManyRequests)
            json.NewEncoder(w).Encode(map[string]any{
                "error":       "rate_limit_exceeded",
                "retry_after": retryAfter,
            })
            return
        }

        // Pequeno delay aceitável — throttle ao invés de rejeitar
        if delay > 0 {
            time.Sleep(delay)
        }

        w.Header().Set("RateLimit-Limit", strconv.Itoa(l.burst))
        next.ServeHTTP(w, r)
    })
}

// Distributed: Redis token bucket via Lua script
var tokenBucketScript = redis.NewScript(`
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local data = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(data[1]) or capacity
local ts = tonumber(data[2]) or now
local new_tokens = math.min(capacity, tokens + (now - ts) * rate / 1000)
if new_tokens >= 1 then
    redis.call('HMSET', key, 'tokens', new_tokens - 1, 'ts', now)
    redis.call('EXPIRE', key, math.ceil(capacity / rate) + 5)
    return 1
end
redis.call('HMSET', key, 'tokens', new_tokens, 'ts', now)
return 0
`)

func RedisRateLimit(rdb *redis.Client, capacity int, ratePerSec float64) func(http.Handler) http.Handler {
    return func(next http.Handler) http.Handler {
        return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
            key := "rl:ip:" + r.RemoteAddr
            nowMs := time.Now().UnixMilli()

            allowed, err := tokenBucketScript.Run(r.Context(), rdb,
                []string{key}, capacity, ratePerSec, nowMs,
            ).Int()

            if err != nil {
                // Fail-open: Redis indisponível → permitir requisição
                next.ServeHTTP(w, r)
                return
            }

            if allowed == 0 {
                w.Header().Set("Retry-After", "1")
                w.WriteHeader(http.StatusTooManyRequests)
                return
            }

            next.ServeHTTP(w, r)
        })
    }
}

1. Demonstre o boundary burst do fixed window: implemente um contador simples e escreva um script que envia 100 requisições nos últimos 2 segundos de uma janela e mais 100 nos primeiros 2 segundos da próxima. Meça quantas passam. Em seguida, substitua por sliding window counter com interpolação linear e repita o experimento.
   Critério: com fixed window: até 200 requisições passam em 4s; com sliding window: no máximo 100 + margem de interpolação passam; diferença documentada com números reais.
2. Implemente token bucket com Redis usando script Lua. Valide atomicidade: inicie 20 goroutines/threads simultâneas, todas tentando consumir o último token ao mesmo tempo. Verifique que apenas uma consegue e as outras recebem 429. Adicione logging para mostrar a ordem de execução.
   Critério: com 1 token restante e 20 goroutines simultâneas, exatamente 1 é aceita e 19 recebem 429; nenhuma condição de corrida detectada em 1000 repetições do teste.
3. Configure rate limiting em camadas para uma API FastAPI ou ASP.NET Core: 1000/hora por API key (Redis), 100/minuto por IP (in-process), e 10/minuto para o endpoint POST /orders especificamente. Implemente os headers RateLimit-Limit, RateLimit-Remaining e Retry-After em todas as respostas.
   Critério: os três limites funcionam independentemente; ao exceder qualquer um, o response inclui headers corretos com valores precisos; testes automatizados verificam cada camada isoladamente.
4. Implemente o retry client correto: um cliente que lê o header Retry-After de respostas 429 e aguarda exatamente o tempo indicado antes de tentar novamente, com jitter de ±10%. Com 20 clientes simultâneos todos recebendo 429 ao mesmo tempo, demonstre que o jitter distribui os retries ao longo do tempo em vez de criar thundering herd.
   Critério: histograma dos tempos de retry mostra distribuição uniforme de ±10% em torno do Retry-After; sem jitter, todos os 20 clientes retentam exatamente no mesmo segundo.
5. Meça o overhead de latência do rate limiting distribuído vs in-process: com um benchmark de 10.000 req/s usando k6 ou wrk, compare o P50, P95 e P99 de latência de uma rota com rate limit in-process (token bucket em memória) vs distribuído (Redis Lua script). Identifique quando o overhead do Redis se torna significativo.
   Critério: benchmark com resultados tabulados para P50/P95/P99; análise do ponto de inflexão onde latência do Redis impacta P99 significativamente; recomendação de quando usar cada abordagem baseada nos dados.