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.

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

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.

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.

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.

AlgoritmoMemória por clienteRajadasPrecisão
Token bucket2 númerosPermitidas até a capacidadeExata para a própria regra
Leaky bucket (fila)Fila de tamanho fixoSuavizadasExata, adiciona latência
Fixed window1 contadorAté 2x na fronteiraAproximada
Sliding logUm timestamp por requisiçãoImpedidasExata
Sliding window counter2 contadoresQuase sempre impedidasAproximada (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:

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á:

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

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.

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]):

AlgoritmoGuardado por clienteAprox. por chaveAprox. total
Fixed window1 contador~70 bytes~1,4 GB
Sliding window counter2 contadores~100 bytes~2 GB
Token buckettokens e timestamp~120 bytes~2,4 GB
Sliding logaté 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.

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.

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.

  1. 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 / rate segundos mais uma passa, um bucket ocioso nunca guarda mais que capacity. Teste também a fronteira de uma janela.
  2. 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.
  3. 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

Resumo rápido

  1. Esclareça quem e o que é limitado, e quão estrito precisa ser. Decida falhar aberto ou fechado por regra.
  2. Aplique no gateway.
  3. Token bucket por padrão, sliding log para limites pequenos e estritos, sliding window counter para escala enorme.
  4. 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.
  5. Faça a aritmética: as requisições por segundo ao armazenamento decidem o número de shards, não a memória.
  6. Responda com 429 e Retry-After, e faça os clientes tentarem de novo com jitter e idempotency keys.
  7. Teste com um relógio falso, sob concorrência e contra um Redis real.

Fontes

  1. Stripe, Scaling your API with rate limiters. Token bucket, e por que eles usam vários limitadores juntos.
  2. Cloudflare, How we built rate limiting capable of scaling to millions of domains. O sliding window counter e sua precisão medida.
  3. IETF, RFC 6585, section 4: 429 Too Many Requests.
  4. IETF, RFC 9110, section 10.2.3: Retry-After.
  5. IETF HTTPAPI working group, RateLimit header fields for HTTP (draft).
  6. Documentação do Redis, Scripting with Lua. Por que um script é atômico.
  7. Documentação do Redis, TIME. O relógio do servidor.
  8. Documentação do Redis, Benchmarks. Medindo requisições por segundo com redis-benchmark.
  9. Documentação do Redis, MEMORY USAGE. Medindo bytes por chave.
  10. Stripe, Idempotent requests.
  11. IETF HTTPAPI working group, The Idempotency-Key HTTP header field (draft).
  12. Wikipedia, Leaky bucket. As versões fila e medidor.
  13. Wikipedia, Token bucket.

Pratique este tema: System Design System Design › Case studies

Mais guias