Rate limiter con token bucket
La misión
Problema
Un API gateway limita a cada cliente con un token bucket. El bucket guarda como máximo capacity tokens y empieza lleno en el instante 0. Los tokens vuelven a entrar de forma continua a razón de per_second tokens por segundo, nunca por encima de la capacidad, y cada solicitud gasta un token entero o se rechaza. Dados los instantes de las solicitudes en milisegundos, en orden, devuelve para cada una si se permite. Las recargas son fraccionarias, así que un cuarto de segundo a 4 tokens por segundo es exactamente un token; evita el punto flotante para que una solicitud que cae justo en el límite nunca se rechace por un error de redondeo.
Ejemplos
Input: capacity = 2, per_second = 1, times_ms = [0, 0, 0, 500, 1000, 3000]
Output: [True, True, False, False, True, True]
Por qué: la ráfaga de tres obtiene dos; medio token en 500 no alcanza; después el bucket se recarga
Input: capacity = 1, per_second = 4, times_ms = [0, 100, 250, 260]
Output: [True, False, True, False]
Por qué: exactamente un token está de vuelta a los 250 ms
Input: capacity = 3, per_second = 1, times_ms = []
Output: []
Por qué: caso límite: no hay tráfico
Pistas
0 / 3
Nunca necesitas un temporizador. El nivel del bucket se puede poner al día de forma perezosa, en el momento en que llega una solicitud, a partir del tiempo transcurrido desde la solicitud anterior.
El punto flotante vuelve frágil el caso en el límite exacto. Cuenta en milésimas de token: así cada milisegundo agrega exactamente per_second milésimas, un número entero.
Guarda el nivel en milésimas y el instante de la última solicitud. Para cada solicitud, suma (t - last) × per_second, limita el resultado a capacity × 1000 y permite la solicitud si quedan al menos 1000, restando 1000.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Restricciones
- request times are in milliseconds, in order
Solución
Un token bucket no necesita un proceso de recarga en segundo plano: el nivel se puede recalcular cuando llega una solicitud a partir del tiempo transcurrido desde la anterior, que es la misma respuesta que daría un temporizador en marcha. Contar en milésimas de token hace que cada recarga sea un entero, porque un milisegundo a per_second tokens por segundo es exactamente per_second milésimas, así que una solicitud que llega justo cuando se completa un token siempre se permite. El tope modela el tamaño del bucket, que es lo que limita una ráfaga después de un periodo tranquilo. Cada solicitud es O(1), así que toda la ejecución es O(n), con O(1) de estado 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, [])) # -> []¿Lo que te frena es la idea y no el código? Rate limiting lo explica.