Neueste Aufgaben und Diskussionen

Ratenbegrenzer mit gleitendem Fenster und Burst-Zulassung

Entwerfen und implementieren Sie einen threadsicheren Ratenbegrenzer in einer Sprache Ihrer Wahl (Python, Go, Java, TypeScript oder Rust), der die folgenden Anforderungen unterstützt: 1. **API-Oberfläche**: Stellen Sie mindestens diese Operationen bereit: - `allow(client_id: str, cost: int = 1) -> bool` — gibt zurück, ob die Anfrage gerade jetzt erlaubt ist. - `retry_after(client_id: str) -> float` — gibt Sekunden zurück, bis mindestens 1 Einheit Kapazität verfügbar ist (0, wenn aktuell erlaubt). - Ein Konstruktor, der eine pro-Client-Konfiguration akzeptiert: `rate` (Einheiten pro Sekunde), `burst` (maximale gespeicherte Einheiten) und ein optionales `window_seconds` für die Gleitfenster-Abrechnung. 2. **Algorithmus**: Implementieren Sie eine Hybridlösung, die einen **Token Bucket** (für Burst-Toleranz) mit einem **Gleitfenster-Log oder -Zähler** kombiniert (um die Gesamtzahl der innerhalb von `window_seconds` erlaubten Anfragen zu begrenzen und so anhaltenden Missbrauch zu verhindern, den ein reiner Token Bucket nach Auffüllungen erlauben würde). Eine Anfrage ist nur dann erlaubt, wenn beide Prüfungen bestehen. Begründen Sie Ihre Wahl der Datenstruktur für das Gleitfenster (exakter Log vs. gewichtete Zwei-Bucket-Approximation) und diskutieren Sie Speichergenauigkeits-Abwägungen in einem kurzen Kommentarfeld oder einer Begleitnotiz. 3. **Nebenläufigkeit**: Der Limiter wird von vielen Threads/Goroutines gleichzeitig für dieselben und verschiedene `client_id`s getroffen. Vermeiden Sie, dass ein einzelner globaler Lock zum Flaschenhals wird (z. B. per-Client-Locks oder Lock-Striping). Dokumentieren Sie, warum Ihr Ansatz unter konkurrierenden `allow`-Aufrufen korrekt ist (kein Doppelverbrauch von Tokens, keine verlorenen Updates). 4. **Zeitquelle**: Machen Sie die Uhr injizierbar, damit Tests deterministisch sind. Verwenden Sie standardmäßig eine monotonische Uhr. 5. **Randfälle, die explizit behandelt werden müssen**: - `cost` größer als `burst` (muss abgelehnt werden, darf niemals ewig blockieren). - Uhr geht rückwärts oder große Pausen (z. B. angehaltene VM): clampen statt abstürzen, und keine unbegrenzten Tokens gewähren. - Erste Anfrage für einen neuen Client (Lazy-Initialisierung). - Aufräumen veralteter Clients (Speicher darf nicht unbegrenzt wachsen, wenn Clients aufhören zu rufen). - Bruchteilige Tokens / sub-millisekunden Timing. 6. **Tests**: Stellen Sie mindestens 6 Unit-Tests mit der injizierbaren Uhr bereit, die abdecken: grundlegendes Allow/Deny, Burst-Entleerung und Auffüllung, gleitende Fenster-Grenze unabhängig von Bucket-Auffüllung, `cost > burst`, gleichzeitige Kontention auf einem Client (deterministische Eigenschaft: insgesamt erlaubte Anfragen in T Sekunden ≤ rate*T + burst), und Eviktion veralteter Clients. 7. **Komplexität**: Geben Sie die amortisierte Zeitkomplexität von `allow` und die Speicherkomplexität pro Client an. Liefern Sie: vollständigen ausführbaren Code (eine einzelne Datei ist in Ordnung, Sie können Dateien aufteilen, wenn Sie sie deutlich kennzeichnen), die Tests und eine kurze Designnotiz (max. ~250 Wörter), die Ihre Entscheidungen und die präzisen Semantiken erklärt, wenn die beiden Algorithmen uneinig sind.