Ultimas tarefas e discussoes

Limitador de Taxa com Janela Deslizante e Tolerância a Rajada

Desenhe e implemente um limitador de taxa thread-safe numa linguagem à sua escolha (Python, Go, Java, TypeScript, ou Rust) que suporte os seguintes requisitos: 1. **API surface**: Exponha pelo menos estas operações: - `allow(client_id: str, cost: int = 1) -> bool` — retorna se a requisição é permitida neste momento. - `retry_after(client_id: str) -> float` — retorna segundos até que pelo menos 1 unidade de capacidade esteja disponível (0 se atualmente permitido). - Um construtor que aceite configuração por cliente: `rate` (unidades por segundo), `burst` (máx. unidades armazenadas), e um opcional `window_seconds` para contabilização por janela deslizante. 2. **Algorithm**: Implemente um híbrido que combine um **token bucket** (para tolerância a rajadas) com um **log ou contador de janela deslizante** (para limitar o total de pedidos permitidos dentro de `window_seconds`, prevenindo abuso sustentado que um token bucket puro permitiria após reabastecimentos). Uma requisição é permitida somente se ambas as verificações passarem. Justifique sua escolha de estrutura de dados para a janela deslizante (log exato vs. aproximação ponderada de dois "buckets") e discuta trade-offs de memória/precisão num bloco curto de comentário ou nota acompanhante. 3. **Concurrency**: O limitador será atingido por muitas threads/goroutines concorrentes para o mesmo e diferentes `client_id`s. Evite que um único lock global se torne um gargalo (por exemplo, locks por cliente ou lock striping). Documente por que sua abordagem está correta sob chamadas concorrentes a `allow` (nenhum duplo gasto de tokens, sem atualizações perdidas). 4. **Time source**: Torne o relógio injetável para que os testes sejam determinísticos. Use um relógio monotônico por padrão. 5. **Edge cases to handle explicitly**: - `cost` maior que `burst` (deve rejeitar, nunca bloquear para sempre). - Relógio retrocedendo ou pausas longas (ex.: VM suspensa): amarre (clamp) em vez de explodir, e não conceda tokens ilimitados. - Primeiro pedido de um novo cliente (inicialização preguiçosa). - Limpeza de clientes obsoletos (a memória não deve crescer indefinidamente se clientes pararem de chamar). - Tokens fraccionários / temporização sub-milisegundo. 6. **Tests**: Forneça pelo menos 6 testes unitários usando o relógio injetável que cubram: permitir/negar básico, drenagem e reabastecimento de rajada, cota de janela deslizante independente do reabastecimento do balde, `cost > burst`, contenção concorrente num cliente (propriedade determinística: total permitido em T segundos ≤ rate*T + burst), e evasão de cliente obsoleto. 7. **Complexity**: Declare a complexidade amortizada de tempo de `allow` e a complexidade de memória por cliente. Entregue: código completo executável (um único ficheiro é aceitável, mas pode separar ficheiros se os identificar claramente), os testes, e uma breve nota de design (máx. ~250 palavras) explicando as suas escolhas e a semântica precisa quando os dois algoritmos discordarem.