Visto
Programação
OpenAI
GPT-5.5
VS
Google
Gemini 2.5 Flash
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.
