Dernieres taches et discussions

Limiteur de débit avec fenêtre glissante et tolérance de rafale

Concevez et implémentez un limiteur de débit sûr pour les threads dans un langage de votre choix (Python, Go, Java, TypeScript ou Rust) qui prend en charge les exigences suivantes : 1. **Surface de l'API** : Exposez au moins ces opérations : - `allow(client_id: str, cost: int = 1) -> bool` — retourne si la requête est autorisée immédiatement. - `retry_after(client_id: str) -> float` — retourne le nombre de secondes avant qu'au moins 1 unité de capacité soit disponible (0 si autorisé actuellement). - Un constructeur qui accepte une configuration par client : `rate` (unités par seconde), `burst` (unités max stockées), et un `window_seconds` optionnel pour la comptabilité par fenêtre glissante. 2. **Algorithme** : Implémentez un hybride qui combine un **token bucket** (pour la tolérance aux rafales) avec un **journal de fenêtre glissante ou un compteur** (pour borner le total des requêtes permises dans `window_seconds`, évitant les abus soutenus qu’un simple token bucket permettrait après recharges). Une requête n’est autorisée que si les deux contrôles passent. Justifiez votre choix de structure de données pour la fenêtre glissante (journal exact vs approximation à deux seaux pondérés) et discutez des compromis mémoire/précision dans un court bloc de commentaire ou une note jointe. 3. **Concurrence** : Le limiteur sera sollicité par de nombreux threads/goroutines concurrentement pour le même `client_id` et pour des `client_id` différents. Évitez qu’un verrou global unique devienne un goulot d’étranglement (par ex. verrous par client ou lock striping). Documentez pourquoi votre approche est correcte sous des appels `allow` concurrents (pas de double-dépense de jetons, pas de mises à jour perdues). 4. **Source de temps** : R rendez l’horloge injectable pour que les tests soient déterministes. Utilisez par défaut une horloge monotone. 5. **Cas limites à traiter explicitement** : - `cost` plus grand que `burst` (doit être rejeté, ne jamais bloquer indéfiniment). - Horloge reculant ou pauses longues (par ex. VM suspendue) : plafonner plutôt que planter, et ne pas accorder de jetons illimités. - Première requête pour un client nouveau (initialisation paresseuse). - Nettoyage des clients obsolètes (la mémoire ne doit pas croître indéfiniment si des clients arrêtent d’appeler). - Jetons fractionnaires / timing sous-millisecondes. 6. **Tests** : Fournissez au moins 6 tests unitaires utilisant l’horloge injectable qui couvrent : autorisation/refus de base, vidage de rafale et recharge, plafond de la fenêtre glissante indépendant de la recharge du seau, `cost > burst`, contention concurrente sur un seul client (propriété déterministe : total permis en T secondes ≤ rate*T + burst), et éviction des clients obsolètes. 7. **Complexité** : Indiquez la complexité en temps amortie de `allow` et la complexité mémoire par client. Livrables : code exécutable complet (un seul fichier convient, mais vous pouvez scinder si vous les étiquetez clairement), les tests, et une brève note de conception (max ~250 mots) expliquant vos choix et la sémantique précise lorsque les deux algorithmes sont en désaccord.