Reddit (votos, ranking "hot", comentários)

01 · CONTEXTO E REQUISITOS

O que o Reddit precisa fazer

Este caso usa o código aberto do Reddit como mapa de um sistema real. Os objetos centrais são links, comentários, contas e subreddits, e três caminhos merecem atenção: votar, ler uma listagem ordenada e comentar.

Como exercício de levantamento de requisitos, os requisitos funcionais são criar um post, votar, ver a listagem de um subreddit em ordens como hot, new e top, e comentar em forma de árvore. Entre os não funcionais, a listagem precisa responder rápido, o voto não deve fazer o usuário esperar e a contagem pode ficar um pouco atrasada, ou seja, consistência eventual.

O software descrito pelo próprio projeto é monolítico: a aplicação recebe a requisição HTTP e faz sozinha o trabalho de buscar dados e montar a resposta. Há dois armazenamentos permanentes centrais, PostgreSQL e Cassandra, e o memcached é usado intensamente para acelerar consultas.

1. O navegador chama a aplicação, que sozinha busca os dados e monta a resposta.

2. Antes de ir aos bancos, a aplicação usa o memcached para acelerar as consultas.

3. Os dados permanentes ficam em dois armazenamentos, PostgreSQL e Cassandra.

Modelo de dados: links, comentários, contas e subreddits vivem no PostgreSQL pelo mecanismo ThingDB, um key/value quase sem esquema com duas tabelas por tipo. A tabela principal reúne colunas comuns, entre elas as contagens de votos, e esse esquema fixo facilita ordenações relativamente rápidas.

O Cassandra, por sua vez, oferece sharding transparente e resiste a falhas de hardware. Parte da carga de escrita é feita fora da requisição do usuário, justamente para que lentidões de processamento não se reflitam na resposta.

02 · RANKING

Como cada ordenação é calculada

O ponto de partida é o score, a diferença entre votos positivos e negativos. A ordenação hot soma dois termos: o sinal do score multiplicado pela sua ordem de grandeza, que é o log10 do módulo do score com piso em um, e os segundos desde uma data de referência fixa divididos por uma constante.

Para a confiança, o código mantém uma tabela de valores já calculados, indexada por votos positivos e negativos, e só calcula na hora quando as contagens saem da faixa da tabela.

No banco, cada ordenação aponta para uma coluna do item: hot para a coluna de hot, new para a data, top para o score e controversial para a coluna de controvérsia. Só top e controversial aceitam filtro de tempo.

03 · O CAMINHO DO VOTO

Votar sem fazer o usuário esperar

A função cast_vote registra o voto e o coloca numa fila para processamento, e grava a marca do voto no memcached para a interface atualizar na hora. Votos em links e em comentários seguem para filas diferentes.

1. O usuário vota e a aplicação registra o voto.

2. A aplicação grava a marca do voto no memcached para a interface atualizar imediatamente.

3. O voto serializado entra na fila de votos.

4. Um consumidor cria o voto sob um lock que combina usuário e link, para manter o estado do voto e a consulta em cache consistentes.

5. Ao confirmar, o voto incrementa a contagem do item e é gravado por conta.

6. Se o voto é válido, o link vai para a fila que atualiza as listagens.

Quando o usuário troca de voto, o efeito do voto anterior é desfeito e o do novo é aplicado. O voto de cada conta fica em VotesByAccount, uma relação desnormalizada sobre o Cassandra.

O código também lida com votos ainda em fila: só consulta o memcache por votos ainda não processados se o usuário votou dentro do período de carência. Registros corrompidos na fila são ignorados.

04 · LISTAGENS PRÉ-COMPUTADAS

Ler uma página hot sem recalcular

O cache de listagens funciona assim: cada consulta tem um resultado em cache que busca a lista, sob demanda, no cache persistente. Cada item guardado traz o nome completo do item e as colunas de ordenação, e a lista tem um limite de itens, dado por uma constante.

O ponto-chave é inserir em vez de recalcular: quando é possível, um item novo é inserido na listagem em vez de reexecutar a consulta. Criar um link atualiza só a listagem new, e as listagens hot, top e controversial ficam com o caminho de votos.

1. A aplicação busca a lista da consulta, sob demanda, no cache persistente.

2. Um voto válido envia o link à fila de atualização por subreddit.

3. O consumidor lê as mensagens em lote e agrupa os links por subreddit.

4. Para cada subreddit, ele insere os links nas listagens hot, top e controversial.

5. Atualizar a lista exige ler, modificar e gravar sob lock, e fragmentar por subreddit permite vários consumidores sem contenção de lock.

05 · COMENTÁRIOS

Árvores de comentários e votos em escala

Comentários têm a própria fila de votos. O consumidor carrega o comentário votado e, quando ele já acumula muitos votos, só atualiza as pontuações de tempos em tempos: a atualização é pulada quando o número de votos passa de um limite configurável e não é múltiplo de um período, também configurável.

1. O voto em comentário entra numa fila própria, distinta da de links.

2. O consumidor carrega o comentário votado.

3. Com muitos votos, a atualização das pontuações é só periódica.

4. Se o link usa ordenações pré-computadas, o comentário vai para a fila da árvore.

5. O atualizador cuida das pontuações por link e da ordem dos comentários.

As pontuações ficam em CommentScoresByLink, uma view sobre o Cassandra cuja chave de linha combina o link e a ordenação. Há pontuações guardadas para quatro ordenações de comentário. Se faltam pontuações, o código as recalcula e limita a regravação a uma vez por minuto.

Comentários também podem ser enfileirados de formas diferentes. Os de links marcados na configuração como fastlane vão para uma fila dedicada; com a opção de sharding ligada a fila é escolhida pelo link, e sem ela há uma única fila. Para ordenar por data, o código usa o próprio id do comentário, porque os ids crescem de forma monotônica.

06 · LIÇÕES E LIMITES

Problema e mecanismo, lado a lado

Este caso descreve mecanismos, não números de tráfego. Trate-os como padrões a justificar pelos requisitos, e faça a estimativa de escala com premissas próprias.