Escolha de estrutura de dados e complexidade em consultas de log
Um serviço registra eventos com timestamp (inteiro, em milissegundos), identificador de usuário (inteiro de 64 bits) e tipo de evento (enumeração com 8 valores). Em horário de pico chegam 50.000 eventos por segundo, e o sistema precisa responder, em menos de 50 ms, a consultas do tipo: "quantos eventos do tipo X ocorreram para o usuário U entre t1 e t2?". O volume diário é de cerca de 4 bilhões de eventos. A equipe propõe manter tudo em memória em uma única lista encadeada ordenada por timestamp, com busca linear por usuário e tipo, alegando que "a lista é simples e a memória é barata". Um servidor tem 256 GB de RAM. Cada evento ocupa, na estrutura proposta, cerca de 48 bytes (incluindo ponteiros).
1. Avalie a viabilidade da proposta em termos de memória e de complexidade das consultas.
Read the worked answer
Memória: 4×10⁹ eventos × 48 bytes = 1,92×10¹¹ bytes ≈ 192 GB por dia, o que já consome 75% dos 256 GB e não cresce de forma sustentável (no segundo dia, estoura). Complexidade: busca linear é O(n) - com 4 bilhões de nós, cada consulta percorreria bilhões de elementos; mesmo a 10⁹ operações/s, isso é da ordem de segundos por consulta, muito acima de 50 ms. Além disso, a lista encadeada tem péssima localidade de cache, agravando o custo real. Veredito: inviável em memória e em tempo. A alegação de que "memória é barata" ignora que o crescimento é diário e que a estrutura não suporta o padrão de consulta.
2. Proponha uma estrutura/estratégia alternativa e justifique com a ordem de complexidade esperada.
Read the worked answer
Consultas filtram por (usuário, tipo, intervalo de tempo) e pedem contagem. Estratégia em camadas: (1) particionamento por tempo (ex.: por hora) com índice hash por (usuário, tipo) dentro de cada partição, mapeando para uma lista/array de timestamps ordenada; a contagem no intervalo vira duas buscas binárias: O(log k) para localizar as bordas + O(1) para a diferença de índices, onde k é o número de eventos daquele usuário/tipo na partição. (2) Alternativa: árvore de Fenwick/segment tree sobre timestamps discretizados, dando O(log k) por consulta e permitindo atualização incremental. (3) Para consultas muito frequentes, contadores agregados por janelas pré-computadas. Memória: guardar apenas timestamps compactos por chave reduz muito o custo; eventos antigos vão para armazenamento em disco com índice. Com isso, a consulta de 50 ms é folgada, e a ingestão de 50 mil/s é absorvida por inserções O(log k) ou O(1) amortizado.
3. O que muda se as consultas passarem a pedir também a série temporal (contagem por minuto) para gráficos?
Read the worked answer
A consulta deixa de ser apenas uma contagem total e passa a exigir agregação em janelas. Duas abordagens: (a) pré-agregar na ingestão - manter, por (usuário, tipo, minuto), um contador incremental; a consulta vira leitura de O(número de minutos no intervalo), tipicamente pequeno (ex.: 60 leituras para 1 hora), mas com custo de memória proporcional a usuários × tipos × minutos ativos; (b) calcular sob demanda a partir dos timestamps ordenados, fazendo varredura do intervalo - O(m) no número de eventos do intervalo, aceitável se m for pequeno, arriscado se o usuário for muito ativo. Em geral, pré-agregar compensa quando o padrão de acesso é repetido e o número de séries é limitado; sob demanda compensa quando as consultas são esparsas e ad-hoc. A escolha deve considerar que 8 tipos × muitos usuários pode explodir o número de séries - nesse caso, pré-agregar apenas para usuários/tipos mais consultados (cache quente) e calcular o resto sob demanda.