Feed de notícias

01 · CONTEXTO

O feed é uma fila de leitura

O feed de notícias mostra a cada usuário os posts recentes de quem ele segue. O trabalho difícil está em montar, para cada leitor, a lista certa em poucos instantes. Segundo o resumo do High Scalability sobre a arquitetura do Twitter em 2013, quase todo o tráfego era de leitura: cerca de 300 mil requisições por segundo liam timelines e só cerca de 6 mil por segundo eram escritas.

Essa assimetria organiza o caso inteiro. A pergunta de projeto é em que momento o trabalho de montar o feed acontece: quando o post é criado ou quando o leitor abre o aplicativo. As duas respostas têm custos diferentes, e o sistema real quase nunca escolhe só uma. O desenho precisa de balanceamento de carga na entrada, de dados particionados para o grafo de seguidores e para os posts, e de um cache que absorva as leituras repetidas.

02 · FAN-OUT NA LEITURA

Montar o feed quando o leitor pede

No modelo de fan-out na leitura (também chamado de modelo pull), nada é pré-computado. Quando o usuário abre o feed, o serviço consulta o grafo de seguidores para saber quem ele segue, busca os posts recentes de cada um e ordena o resultado. A fonte de entrevista de sistemas chama isso de fan-out na leitura: uma única requisição de leitura se desdobra em muitas outras.

1. O leitor abre o aplicativo. O balanceador escolhe uma instância do serviço de feed, que não guarda nenhum feed pronto e precisa montá-lo agora.

2. O serviço pergunta ao grafo de seguidores quais contas esse usuário segue. Quanto mais contas, mais consultas virão a seguir.

3. Para cada conta seguida, o serviço procura os posts recentes no cache e, no que faltar, vai ao banco de posts. É aqui que uma leitura vira muitas, e o banco sente o peso.

4. O serviço junta tudo, ordena por tempo e devolve ao leitor. A latência da resposta depende de quantas contas o usuário segue, e não do tamanho do post.

A vantagem, segundo a fonte do ByteByteGo, é que os dados não são empurrados para os amigos, então não existe o problema da chave quente. A desvantagem é que buscar o feed é lento porque ele não foi pré-computado.

03 · FAN-OUT NA ESCRITA

Montar o feed quando o post nasce

O modelo oposto, de fan-out na escrita (modelo push), troca o momento do trabalho. Em vez de montar o feed quando o leitor pede, o sistema pré-computa os feeds quando os posts são criados. O leitor passa a ler uma lista já pronta, e o custo vai para a publicação, que acontece fora do caminho da requisição, por trabalhadores assíncronos.

1. A autora publica um post. O gateway valida a chamada e a entrega ao serviço de posts, que cuida de persistir o conteúdo.

2. O serviço grava o post no banco e publica um evento na fila. A resposta à autora não espera a distribuição aos seguidores.

3. Um trabalhador de fan-out consome o evento e consulta o grafo de seguidores para descobrir a quem o post deve chegar.

4. O trabalhador insere o identificador do post no feed pré-computado de cada seguidor. É o ponto caro: o número de escritas cresce com o número de seguidores.

5. Mais tarde, um seguidor abre o feed. O serviço de feed lê a lista pronta no cache, sem consultar o grafo de seguidores nem varrer contas.

6. A lista guarda só identificadores. O serviço busca o conteúdo desses posts no banco de posts e devolve a página ao leitor.

A fonte do ByteByteGo descreve o serviço de fan-out como o que empurra o conteúdo novo para o feed dos amigos, guardado no cache para leitura rápida. O custo aparece com muitos seguidores: buscar a lista de amigos e gerar os feeds de todos é lento e demorado.

04 · CELEBRIDADES

Quando um post tem milhões de leitores

O fan-out na escrita quebra nos extremos. Para contas enormes, os trabalhadores de fan-out têm muito trabalho a fazer por post, e a fonte do Hello Interview cita um exemplo de dezenas de milhões de seguidores numa única conta. A fonte do ByteByteGo dá nome ao problema: chave quente.

A saída comum é o modelo híbrido. A fonte do Hello Interview descreve marcar a conta grande com um indicador na tabela de seguidores, em vez de escrever o post para cada seguidor, o que permite escolher fan-out na leitura ou na escrita conta a conta. O ByteByteGo faz o mesmo: para quem tem muitos seguidores, os seguidores puxam o conteúdo sob demanda. O resumo do High Scalability sobre o Twitter registra a mesma ideia: para contas muito grandes, não fazer fan-out e mesclar o conteúdo delas na hora da leitura.

1. Para uma conta comum, o caminho é o de fan-out na escrita: o trabalhador consome o evento e insere o post no feed pré-computado de cada seguidor.

2. Para uma conta grande, o indicador na tabela de seguidores faz o trabalhador pular a distribuição. O post fica só no armazenamento de posts, e o feed dos seguidores não recebe nada.

3. O seguidor abre o feed. O serviço começa pela parte pré-computada, lida do cache de feeds.

4. Em seguida, o serviço usa o grafo de seguidores para descobrir quais contas marcadas esse leitor segue.

5. O serviço busca os posts recentes dessas contas no cache de posts e, se faltar, no banco. Esse cache recebe a leitura de todos os seguidores, então a chave quente se desloca para ele.

6. O serviço mescla a parte pré-computada com os posts das contas grandes, ordena por tempo e devolve a página ao leitor.

O híbrido não elimina a chave quente; ele a muda de lugar. A fonte do Hello Interview aponta que o maior desafio do cache de posts é ter o mesmo problema de chave quente que a tabela de posts.

05 · CACHE E TRADE-OFFS

O que guardar no feed pré-computado

O feed pré-computado é um cache por usuário com identificadores, não posts inteiros. Na fonte do Hello Interview, cada entrada da tabela de feeds pré-computados é indexada pelo usuário e guarda uma lista de identificadores de posts. No Twitter de 2013, segundo o High Scalability, a timeline ficava num cluster Redis com no máximo 800 entradas por usuário (valor da época).

A paginação acompanha esse desenho. Segundo o Hello Interview, um único timestamp indica onde o leitor parou e serve de cursor para o próximo conjunto de posts.