Entrevista de código: implementar un limitador de tasa de token-bucket tolerante a ráfagas

Planteamiento y alcance

Implementa un limitador de tasa de tipo token-bucket por usuario. Cada bucket tiene un capacity máximo, una tasa de recarga refillRate por segundo y un balance actual de tokens. Una solicitud incluye un ID de usuario, una marca de tiempo y un costo. Si el balance recargado cubre el costo, consúmelo y permite la solicitud; de lo contrario, recházala. Explica la API, la complejidad, la precisión del tiempo, la concurrencia y las pruebas.

Esto encaja en entrevistas de código para backend, plataforma e infraestructura. AWS describe los token buckets como tokens que representan solicitudes, recargados a una tasa configurada, consumiendo un token por solicitud, y recomienda probar los límites antes de incrementarlos.

Qué evalúa el entrevistador

• Si deduces la recarga diferida (lazy refill) en lugar de iniciar un temporizador para cada bucket.
• Si usas tiempo monotónico para que un retroceso del reloj de pared no pueda acuñar tokens.
• Si los tokens tienen un tope y las solicitudes rechazadas dejan el balance intacto.
• Si distingues la memoria de un solo proceso del estado compartido distribuido.
• Si cubres concurrencia, precisión numérica, intervalos largos de inactividad y parámetros no válidos.

Aclaraciones que conviene hacer primero

Confirma:

1. ¿Es cost siempre un entero positivo o puede ser fraccionario?
2. ¿Se inyecta el tiempo para pruebas deterministas o lo lee el propio limitador?
3. ¿Basta con una implementación de un solo proceso o las instancias deben compartir cuotas?
4. ¿Debe el rechazo incluir los tokens restantes o un tiempo estimado de reintento?

Si no se especifica, asume un solo proceso, costos enteros no negativos, un reloj monotónico en nanosegundos y ráfagas permitidas hasta la capacidad del bucket.

Estructura de respuesta en treinta segundos

Almacena tokens y lastRefillAt por usuario. En cada solicitud, recarga de forma diferida con min(capacity, tokens + elapsed * refillRate) usando el tiempo transcurrido monotónico. Permite la solicitud solo cuando el balance recargado cubra cost; de lo contrario, preserva el estado y rechaza. En un solo proceso, un bloqueo por usuario o una sección crítica atómica hace que la lectura, la recarga, la verificación y la escritura sean indivisibles. En un despliegue distribuido, ejecuta la misma transición en un script o transacción atómica de almacenamiento compartido. Valida parámetros, comportamiento del reloj, límites y llamadas concurrentes con una prueba de modelo de reloj controlable.

Análisis detallado paso a paso

1. Estado e invariantes

Almacena tokens, lastRefillAt y, opcionalmente, una versión por usuario. El invariante es 0 <= tokens <= capacity, y lastRefillAt nunca retrocede. Valida que la capacidad y la tasa de recarga sean positivas al crearlas. El costo debe ser positivo y no mayor que la capacidad; de lo contrario, devuelve un error de parámetro sin cambiar el estado.

2. Recarga diferida (lazy refill)

Sea now el tiempo actual y elapsed = now - lastRefillAt. Suma elapsed * refillRate, luego delimita el balance con min(capacity, tokens + refill). Incluso cuando el bucket esté lleno, avanza lastRefillAt a now para que el intervalo no se vuelva a contar. Los nanosegundos enteros con aritmética racional reducen la desviación de punto flotante; si se usan flotantes, define el redondeo y prueba ejecuciones prolongadas.

3. Permitir y rechazar

Si el balance recargado es al menos cost, resta el costo y permite la solicitud. De lo contrario, no restes nada; devuelve un rechazo y, opcionalmente, retryAfter. Estima el retraso como (cost - tokens) / refillRate, redondeado hacia arriba, manejando una tasa de recarga de cero y un costo mayor que la capacidad. Un rechazo no debe parecer un éxito ni mover el cursor hacia atrás.

4. Concurrencia y almacenamiento

El código de un solo proceso debe mantener la lectura, la recarga, la decisión y la escritura en una sola sección crítica; los bloqueos fragmentados (sharded) por usuario evitan un único bloqueo global. Cuando varias instancias comparten cuotas, los bloqueos de aplicación son insuficientes. Usa Redis Lua, un bloqueo de fila de base de datos u otra transacción atómica para toda la transición de estado. Transporta un ID de solicitud en los reintentos de red para que una respuesta perdida no consuma accidentalmente tokens de negocio dos veces.

5. Expiración y cardinalidad

Expira el estado de usuarios inactivos usando lastRefillAt y una política de arrendamiento (lease policy), asegurando al mismo tiempo que una nueva solicitud se inicialice correctamente. Protégete contra usuarios de alta cardinalidad con un límite de estado, fragmentación (sharding) y una política de desalojo (eviction). Recrear un bucket desalojado a su capacidad máxima puede crear una ráfaga, por lo que la política de producción debe indicar si eso es aceptable. Nunca permitas que IDs de usuario controlados por un atacante hagan crecer un mapa sin límites.

6. Pruebas y observabilidad

Prueba un bucket inicialmente lleno, rechazos repetidos, recarga exacta, costo igual a la capacidad, sin avance de tiempo, retroceso del reloj, intervalos largos de inactividad, contención y llamadas duplicadas. Con un reloj inyectado, valida que el balance se mantenga dentro de los límites y que el costo exitoso nunca exceda la capacidad inicial más la recarga teórica. Monitorea las tasas de solicitudes permitidas y rechazadas, la distribución de tokens, la cantidad de estados, la espera de bloqueos, los errores de scripts atómicos y el uso de memoria.

Respuesta de muestra de alta calidad

Expondría allow(userId, now, cost). El estado de un usuario contiene únicamente tokens y lastRefillAt. Dentro de una sola sección crítica, calcula el tiempo transcurrido, recarga, delimita a la capacidad y toma la decisión. En caso de éxito, resta el costo y mueve el cursor a now; en caso de rechazo, mantén el balance recargado pero no consumas nada. Toda la aritmética temporal usa un reloj monotónico, por lo que el estado no puede retroceder.

Para un solo proceso, usaría bloqueos fragmentados por usuario. Para múltiples instancias, colocaría la misma transición en Redis Lua o en una transacción atómica de base de datos en lugar de realizar lecturas y escrituras de red por separado. Un ID de solicitud respalda la idempotencia de reintentos; no hace que la operación de negocio sea de ejecución única exacta por sí misma. La expiración y los controles de alta cardinalidad previenen el abuso de memoria.

Las pruebas usan un reloj controlable para tiempo transcurrido cero, recarga exacta, solicitudes de costo total, períodos largos de inactividad, retroceso de reloj y concurrencia. Una prueba de propiedades valida que cada balance permanezca entre cero y la capacidad, y que el costo permitido acumulado nunca exceda la capacidad inicial más la recarga. En producción, observaría la tasa de rechazo, la distribución de tokens, el crecimiento del estado, la espera de bloqueos y los errores de scripts de almacenamiento; la guía de AWS también exige probar un límite propuesto antes de aumentarlo.

Errores comunes

• Iniciar un temporizador para cada bucket, haciendo que el costo de programación crezca con la cantidad de usuarios.
• Usar el tiempo de reloj de pared, de modo que el retroceso por NTP cree tokens adicionales.
• Olvidar la delimitación de capacidad y permitir una acumulación ilimitada.
• Cobrar solicitudes rechazadas y consumir silenciosamente la cuota del usuario.
• Tratar un bloqueo dentro del proceso como atomicidad entre instancias.
• Aceptar cost > capacity, lo que puede causar esperas infinitas o producir un tiempo de reintento erróneo.
• Usar punto flotante sin definir el redondeo y la desviación a largo plazo.
• Probar solo llamadas secuenciales y pasar por alto condiciones de carrera concurrentes de lectura-modificación-escritura.

Preguntas de seguimiento y respuestas

¿Por qué no un contador de ventana fija?

Una ventana fija es simple pero puede permitir una doble ráfaga corta en el límite de la ventana. Un token bucket expresa la ráfaga permitida con la capacidad y la tasa sostenida con la recarga. Si no se tolera ninguna ráfaga, compara una ventana deslizante o un leaky bucket.

¿Cómo devuelves Retry-After?

Divide el balance faltante por la tasa de recarga y redondea hacia arriba. Con recarga cero o un costo superior a la capacidad, devuelve un error de configuración o un resultado no reintentable en lugar de una marca de tiempo infinita.

¿Qué pasa si Redis no está disponible?

Elige fail-closed, un presupuesto local delimitado o una degradación explícita según el riesgo del endpoint, y registra la razón. No permitas que cada instancia haga fail-open sin presupuesto ni ocultes la caída como un rechazo ordinario.

¿Cómo cambias la capacidad y la tasa de recarga?

Recarga con los parámetros anteriores hasta el momento del cambio, luego delimita o convierte el balance bajo una política explícita y registra la versión de configuración. Reducir la capacidad debe manejar de forma atómica un balance existente que supere el nuevo límite.

¿Cómo demuestras que no hay sobreventa?

Ejecuta una prueba de propiedades de máquina de estados con tiempos aleatorios y valida que el costo permitido en cada intervalo esté acotado por los tokens iniciales más la recarga teórica. Agrega pruebas de estrés concurrentes para verificar la sección crítica atómica.