Rate limiter com token bucket
A missão
Problema
Um API gateway limita cada cliente com um token bucket. O bucket guarda no máximo capacity tokens e começa cheio no instante 0. Os tokens voltam a pingar continuamente, a per_second tokens por segundo, nunca além da capacidade, e cada requisição gasta um token inteiro ou é rejeitada. Dados os instantes das requisições em milissegundos, em ordem, retorne para cada uma se ela é permitida. As recargas são fracionárias, então um quarto de segundo a 4 tokens por segundo é exatamente um token; evite ponto flutuante para que uma requisição exatamente no limite nunca seja rejeitada por um erro de arredondamento.
Exemplos
Input: capacity = 2, per_second = 1, times_ms = [0, 0, 0, 500, 1000, 3000]
Output: [True, True, False, False, True, True]
Por quê: a rajada de três recebe dois; meio token em 500 não basta; depois, o bucket se recarrega
Input: capacity = 1, per_second = 4, times_ms = [0, 100, 250, 260]
Output: [True, False, True, False]
Por quê: exatamente um token está de volta em 250 ms
Input: capacity = 3, per_second = 1, times_ms = []
Output: []
Por quê: edge case: sem tráfego
Dicas
0 / 3
Você nunca precisa de um timer. O nível do bucket pode ser atualizado sob demanda, no momento em que uma requisição chega, a partir do tempo desde a última requisição.
Ponto flutuante deixa o caso de limite frágil. Conte em milésimos de token: assim, cada milissegundo soma exatamente per_second milésimos, um número inteiro.
Guarde o nível em milésimos e o instante da última requisição. Para cada requisição, some (t - last) × per_second, limite o total a capacity × 1000 e permita a requisição se restarem pelo menos 1000, subtraindo 1000.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Restrições
- request times are in milliseconds, in order
Solução
Um token bucket não precisa de uma tarefa de recarga em segundo plano: o nível pode ser recalculado quando uma requisição chega, a partir de quanto tempo se passou desde a anterior, o que dá a mesma resposta que um timer contando daria. Contar em milésimos de token torna cada recarga um inteiro, porque um milissegundo a per_second tokens por segundo é exatamente per_second milésimos, então uma requisição que chega bem no momento em que um token se completa é sempre permitida. O teto modela o tamanho do bucket, que é o que limita uma rajada depois de um período de silêncio. Cada requisição é O(1), então a execução inteira é O(n), com estado O(1) por cliente.
def token_bucket(capacity, per_second, times_ms):
# count in thousandths of a token so every refill is exact integer maths
full, tokens, last, out = capacity * 1000, capacity * 1000, 0, []
for t in times_ms:
tokens = min(full, tokens + (t - last) * per_second) # refill since last
last = t
if tokens >= 1000:
tokens -= 1000 # spend one whole token
out.append(True)
else:
out.append(False)
return out
print(token_bucket(2, 1, [0, 0, 0, 500, 1000, 3000])) # -> [True, True, False, False, True, True]
print(token_bucket(1, 4, [0, 100, 250, 260])) # -> [True, False, True, False]
print(token_bucket(3, 1, [])) # -> []Travou na ideia, e não no código? Rate limiting explica isso.