Ultimas tareas y discusiones

Limitador de tasa con ventana deslizante y tolerancia a ráfagas

Diseña e implementa un limitador de tasa seguro para hilos en un lenguaje de tu elección (Python, Go, Java, TypeScript o Rust) que admita los siguientes requisitos: 1. **Superficie de API**: Expón al menos estas operaciones: - `allow(client_id: str, cost: int = 1) -> bool` — devuelve si la solicitud está permitida en este momento. - `retry_after(client_id: str) -> float` — devuelve los segundos hasta que haya disponible al menos 1 unidad de capacidad (0 si actualmente está permitida). - Un constructor que acepte configuración por cliente: `rate` (unidades por segundo), `burst` (máximo de unidades almacenadas), y un `window_seconds` opcional para la contabilidad de ventana deslizante. 2. **Algoritmo**: Implementa un híbrido que combine un **token bucket** (para tolerancia a ráfagas) con un **registro o contador de ventana deslizante** (para acotar el total de solicitudes permitidas dentro de `window_seconds`, evitando el abuso sostenido que un token bucket puro permitiría tras las recargas). Una solicitud se permite solo si ambas comprobaciones se superan. Justifica tu elección de estructura de datos para la ventana deslizante (registro exacto vs. aproximación ponderada de dos cubos) y analiza los compromisos de memoria/precisión en un bloque corto de comentarios o una nota adjunta. 3. **Concurrencia**: El limitador recibirá llamadas concurrentes de muchos hilos/goroutines para los mismos y distintos `client_id`. Evita que un único bloqueo global se convierta en un cuello de botella (p. ej., bloqueos por cliente o lock striping). Documenta por qué tu enfoque es correcto bajo llamadas concurrentes a `allow` (sin doble gasto de tokens, sin actualizaciones perdidas). 4. **Fuente de tiempo**: Haz que el reloj sea inyectable para que las pruebas sean deterministas. Usa por defecto un reloj monotónico. 5. **Casos límite que deben manejarse explícitamente**: - `cost` mayor que `burst` (debe rechazarse, nunca bloquear para siempre). - El reloj retrocede o hay pausas largas (p. ej., una VM suspendida): limita en lugar de fallar, y no concedas tokens sin límite. - Primera solicitud de un cliente nuevo (inicialización diferida). - Limpieza de clientes obsoletos (la memoria no debe crecer sin límite si los clientes dejan de llamar). - Tokens fraccionales / temporización por debajo del milisegundo. 6. **Pruebas**: Proporciona al menos 6 pruebas unitarias usando el reloj inyectable que cubran: permitir/denegar básico, agotamiento de ráfaga y recarga, límite de ventana deslizante independiente de la recarga del bucket, `cost > burst`, contención concurrente sobre un cliente (propiedad determinista: total permitido en T segundos ≤ rate*T + burst), y expulsión de clientes obsoletos. 7. **Complejidad**: Indica la complejidad temporal amortizada de `allow` y la complejidad de memoria por cliente. Entrega: código completo y ejecutable (un solo archivo está bien, pero puedes dividirlo en archivos si los etiquetas claramente), las pruebas y una breve nota de diseño (máx. ~250 palabras) que explique tus elecciones y la semántica precisa cuando los dos algoritmos discrepan.