Top-K e trending em janela de tempo

01 · CONTEXTO E REQUISITOS

O que significa pedir os mais vistos

O Top-K é um problema clássico de design de sistemas, com muitas variantes. Este caso segue o roteiro do Hello Interview, que usa as visualizações do YouTube: entra um fluxo enorme de eventos, cada um identificando um vídeo, e a consulta pede os K vídeos mais vistos na última hora, no último dia, no último mês e em todo o período.

O roteiro distingue dois tipos de janela. Na janela deslizante, a última hora é o intervalo entre o instante atual menos uma hora e o instante atual. Na janela fixa (tumbling), é a última hora cheia, que começa e termina nos limites da hora. O roteiro propõe usar janelas fixas, que são mais fáceis de tratar que as deslizantes.

Os requisitos centrais: consultar o Top-K com no máximo mil resultados; tolerar no máximo um minuto de atraso entre a visualização e a contagem; entregar resultados precisos, sem aproximar; e responder em dezenas de milissegundos. Essa última exigência elimina muitas soluções e leva a favorecer o pré-cálculo.

02 · ESTIMATIVA DE ESCALA

Por que um banco só não aguenta

Como ordem de grandeza, o guia cita 70 bilhões de visualizações por dia do YouTube Shorts. Dividindo por 100 mil segundos por dia, a conta dá 700 mil escritas por segundo. O guia lembra que RDBMSs modernos conseguem mais de 10 mil escritas por segundo por nó sob as circunstâncias certas, e conclui que a carga fica bem além disso.

Para o armazenamento, o guia estima um contador ingênuo por vídeo: 4 bilhões de vídeos, 8 bytes por ID e 8 bytes por contador somam 64 GB. Sempre que for preciso manter as visualizações de todos os vídeos, serão necessários ao menos 64 GB.

03 · PRIMEIRA VERSÃO

Um consumidor e um Postgres

O guia prefere partir de um sistema que funciona e otimizá-lo, em vez de começar por um sistema ótimo e tentar fazê-lo funcionar. Ele assume que existe um fluxo Kafka de eventos de visualização, alimentado por outro sistema (o que mostra os vídeos aos usuários), e que o tópico é particionado pelo ID do vídeo. Um consumidor simples lê os eventos e atualiza um banco Postgres.

1. Os eventos de visualização chegam a um tópico particionado pelo ID do vídeo, e um consumidor simples os lê.

2. O consumidor atualiza o contador do vídeo no Postgres.

3. Para consultar, o serviço pega os K primeiros da lista, o índice de contagem, que é basicamente uma lista ordenada dos vídeos por visualizações; a consulta pode ser muito eficiente.

4. O custo está na escrita: cada atualização também precisa atualizar o índice, e o guia reconhece que são muitas escritas numa única instância Postgres.

Para suportar janelas, a tabela ganha uma coluna de timestamp e passa a haver uma linha por vídeo visto ao menos uma vez em cada hora. O número de escritas não muda, pois continua uma escrita por evento, mas o número de linhas armazenadas explode. A consulta por janela fica bem menos eficiente: varreduras (scans) são quando o banco precisa ler todas as linhas de um segmento para atender a consulta, e o guia avisa que não será possível evitar algumas.

04 · ESCRITA E LEITURA

Particionar, agregar e pré-calcular

A primeira alavanca é particionar o banco pelo mesmo esquema do tópico, de modo que cada partição tenha só um subconjunto dos vídeos. Para baixar a carga do banco a cerca de 10 mil escritas por segundo, o guia precisaria de 70 instâncias. Com o banco particionado, é preciso consultar cada partição e juntar os resultados; pegando o Top-K de cada partição, o guia diz que o Top-K global fica matematicamente garantido na lista final, e o cron passa a fazer uma chamada por partição.

Muitas visualizações recaem sobre poucos vídeos. Por isso, em vez de uma escrita por visualização, agrupam-se as escritas de cada vídeo e descarregam-se os lotes periodicamente no banco. O guia usa o Flink com uma janela fixa de uma hora para agregar as visualizações de cada vídeo e com espera de eventos atrasados de cerca de trinta segundos, menos de um minuto. Como o Flink lê do Kafka, se uma máquina falha ou cai ele volta ao offset do checkpoint no tópico e retoma dali. O guia espera que as escritas caiam de 2 a 100 vezes e que as partições fiquem na faixa de 5 a 10.

1. O Flink lê o tópico e soma as visualizações de cada vídeo numa janela fixa de uma hora, esperando um pouco por eventos atrasados.

2. Em vez de uma escrita por visualização, o Flink descarrega lotes periodicamente no banco, que está particionado: cada partição guarda um subconjunto dos vídeos.

3. O job de pré-cálculo faz uma chamada por partição e junta os resultados, e o Top-K global está garantido na lista final.

4. Em intervalos fixos, o job calcula o Top-K de cada janela e aquece o cache.

5. O serviço de Top-K só lê do cache e nunca consulta o banco.

6. Se uma máquina do Flink falha ou cai, ele volta ao offset do checkpoint no tópico e retoma dali.

Na leitura, um cache devolve a resposta imediatamente quando a entrada existe. O problema é a expiração: de repente chega uma enxurrada de requisições ao banco. A alternativa é o job periódico descrito acima, que pré-calcula o Top-K de cada janela em intervalos fixos; assim o serviço só lê do cache e nunca consulta o banco. Reter as entradas por algumas horas cobre o caso de o job atrasar, e o serviço pode servir dados defasados por pouco tempo em vez de nada.

Para as janelas, o guia propõe manter agregados para cada janela, em vez de agregados por partições arbitrárias de tempo, e o cron só precisa ler o Top-K direto do índice. A abordagem move complexidade da leitura para a escrita: passa-se a escrever em 4 tabelas em vez de 1.

05 · APROXIMAR COM SKETCH

Count-Min Sketch e lista ordenada

Se os usuários aceitam algum risco de imprecisão, a eficiência melhora drasticamente, e o guia observa que os vídeos do topo provavelmente diferem por um fator grande. A estrutura proposta é o Count-Min Sketch (CMS), que usa várias funções de hash para mapear itens a uma matriz de contadores. Ele esquece os itens reais, mas lembra quantas vezes foram vistos por meio do hash, e estima contagens com bem menos memória que a tabela hash completa, na ordem de centenas de megabytes.

O CMS não tem operação de listar: ao adicionar, perde-se o ID do item. Por isso o guia o emparelha com uma lista ordenada ou heap. Quando uma visualização chega, ela é somada ao CMS; logo depois estima-se a contagem do item, o que dá um limite superior do número de visualizações e uma boa aproximação; a contagem é então somada à lista, que é truncada periodicamente para não usar memória em excesso. Para obter o Top-K, pegam-se os K primeiros itens da lista. Como os usuários nunca consultam além do topo de mil, a lista de todo o período pode ter mil entradas. Para janelas fixas, basta manter um sketch e uma lista para cada janela consultada.

1. Cada visualização lida do tópico é somada ao CMS, que atualiza o sketch.

2. Logo depois o consumidor estima a contagem do item; o resultado é um limite superior das visualizações do item e uma boa aproximação.

3. A contagem do item é somada a uma lista ordenada (um conjunto ordenado no Redis), truncada periodicamente para não usar memória em excesso; no Redis, o conjunto ordenado é mantido aparado em mil entradas.

4. Para consultar, o serviço pega os K primeiros itens da lista ordenada.

5. O risco é a durabilidade: a abordagem com Redis traz essa preocupação, e há risco de perder dados se uma visualização entra no sketch mas não é atualizada na lista ordenada.

O artigo original do CMS descreve uma nova estrutura de dados de espaço sublinear. Cada item é mapeado a uma célula em cada linha da matriz de contadores, e a estimativa do item é o mínimo entre essas células. O artigo afirma que os CM sketches nunca subestimam contagens e, para encontrar itens frequentes (aqueles com multiplicidade acima de uma fração do total) no modelo em que todas as atualizações são positivas, atualiza o sketch, consulta a estimativa e coloca em um heap o item cuja estimativa passa do limiar, mantendo o heap pequeno por verificação. Pela garantia de erro unilateral, todo item frequente entra na saída, mas pode haver itens não frequentes incluídos.

06 · JANELAS DESLIZANTES E LIMITES

Onde o desenho aperta

As abordagens com sketch funcionam bem em janelas fixas, em que só se adiciona ao sketch durante a janela, mas ficam aquém em janelas deslizantes. Remover itens do sketch não pode ser feito com a abordagem com Redis. Em tabelas, a janela deslizante é ainda mais complexa que a fixa: a cada minuto, o contador da janela de uma hora aumenta pelas visualizações que chegaram nesse minuto e diminui pelas ocorridas sessenta minutos antes, e é preciso manter dados em granularidade de minuto por um mês inteiro.