CS Fundamentals Trainer · Guias
Projetando um news feed
Fan-out na escrita versus na leitura, o problema das celebridades e o híbrido, timelines em Redis com memória medida, paginação por keyset versus OFFSET cronometrada no PostgreSQL, ranqueamento, exclusões e privacidade.
34 min de leitura
"Projete um news feed" (ou "projete a timeline inicial do Twitter", ou "projete o feed do Instagram") é uma das perguntas de system design mais ricas, porque a versão simples funciona em uma tarde e a versão real é cheia de trocas: quem paga o custo, o autor ou o leitor, o que acontece quando um usuário tem cinquenta milhões de seguidores e o que sequer significa "página 2" quando a lista não para de mudar. Este guia constrói o projeto passo a passo e sustenta cada afirmação com uma medição: um modelo de fan-out sobre um grafo de seguidores assimétrico, timelines em Redis (memória e velocidade) e paginação por offset contra keyset no PostgreSQL.
1. O que estamos construindo
Um usuário abre o app e vê uma lista de posts recentes das contas que segue, do mais novo para o mais antigo (ou ranqueados), e pode continuar rolando. As pessoas publicam; os seguidores veem rápido.
Requisitos funcionais
- Publicar um post (texto, talvez referências a mídia).
- Seguir e deixar de seguir contas.
- Ler o feed inicial: posts das pessoas que sigo, do mais novo ao mais antigo, com "carregar mais".
- Ler uma timeline de perfil: os posts de um só usuário (um problema bem mais fácil).
Requisitos não funcionais
- Ler o feed precisa ser rápido (algumas centenas de milissegundos), porque é a tela principal.
- Um post novo deve aparecer nos feeds dos seguidores em segundos, não em horas.
- O sistema precisa sobreviver à assimetria: a maioria das contas tem poucos seguidores, algumas têm milhões.
- Não há problema se um feed estiver um pouco obsoleto ou perder um post por um instante (consistência eventual, veja o guia do CAP). Não é aceitável perder posts permanentemente.
- Fora do escopo aqui: o pipeline de mídia, a busca, os anúncios e o sistema de notificações.
Números de guardanapo
Anote as suas suposições; elas guiam cada decisão posterior. Suponha 100 milhões de usuários ativos por dia, cada um abrindo o feed 10 vezes por dia e publicando 0,5 post por dia em média, seguindo cerca de 40 contas.
| Grandeza | Cálculo | Resultado |
|---|---|---|
| Leituras do feed | 100 M × 10 por dia ÷ 86 400 s | cerca de 11 600 por segundo em média, talvez 35 000 no pico (3× a média) |
| Posts novos | 100 M × 0,5 ÷ 86 400 s | cerca de 580 por segundo |
| Escritas em timelines se cada post é copiado para os seguidores (push) | 580/s × 40 seguidores | cerca de 23 000 por segundo |
| Escritas em timelines para uma conta com 50 M de seguidores | um post | 50 milhões de escritas a partir de um único clique |
As leituras superam as escritas em cerca de 20 para 1, o que sugere fazer trabalho na hora da escrita para tornar as leituras baratas. A última linha é a razão de não ser tão simples.
2. O modelo de dados
Três coisas são armazenadas de forma durável (os nomes são simples, adapte-os ao seu banco de dados):
CREATE TABLE users (id bigint PRIMARY KEY, handle text UNIQUE NOT NULL, followers_count int NOT NULL DEFAULT 0);
CREATE TABLE posts (id bigint PRIMARY KEY, -- a time-sortable id, see below
author_id bigint NOT NULL REFERENCES users,
body text NOT NULL,
created_at timestamptz NOT NULL DEFAULT now(),
deleted_at timestamptz);
CREATE INDEX posts_by_author ON posts (author_id, id DESC);
CREATE TABLE follows (follower_id bigint NOT NULL, followee_id bigint NOT NULL,
created_at timestamptz NOT NULL DEFAULT now(),
PRIMARY KEY (follower_id, followee_id));
CREATE INDEX follows_by_followee ON follows (followee_id, follower_id); -- "who follows X": needed for fan-out
Notas que importam em uma entrevista:
- Ids de post ordenáveis por tempo (estilo Snowflake: bits de timestamp, bits da máquina, bits de sequência; veja o guia do encurtador de URL para a ideia) significam que "ordenar por id" é "ordenar por tempo", os empates somem e um id funciona como cursor de paginação.
- O grafo de seguidores é lido em ambas as direções: "quem eu sigo" para o pull, "quem me segue" para o push. Indexe as duas.
- Não guarde o próprio feed neste esquema relacional: um feed é uma visão derivada e reconstruível. Essa é a chave de tudo abaixo.
Diagram: The main pieces of a feed system
3. Abordagem 1: montar o feed quando ele é lido (fan-out na leitura, "pull")
Quando um usuário abre o feed, busque os posts recentes de todos os que ele segue e faça o merge:
SELECT p.id, p.author_id, p.body
FROM posts p
JOIN follows f ON f.followee_id = p.author_id
WHERE f.follower_id = $1 AND p.deleted_at IS NULL AND p.id < $2 -- $2 = the cursor
ORDER BY p.id DESC
LIMIT 20;
Publicar um post é trivial: um insert. Ler custa uma consulta por seguido: com cerca de 40 seguidos, a leitura de um feed toca 40 listas de autores e as mescla. Não parece muito, mas multiplique pela taxa de leituras. No meu modelo de um milhão de usuários (abaixo), o pull precisa de cerca de 396 milhões de leituras de listas de seguidos por dia, contra 10 milhões de aberturas de feed, e cada uma dessas leituras está no tempo de espera do usuário. O pull é simples e sempre fresco, e fica lento exatamente onde o produto é mais movimentado: o caminho de leitura.
4. Abordagem 2: montar o feed quando um post é escrito (fan-out na escrita, "push")
Inverta. Cada usuário tem uma timeline pré-calculada: uma lista de ids de post, do mais novo ao mais antigo. Quando alguém publica, workers acrescentam o id à timeline de cada seguidor. Ler um feed passa a ser uma consulta barata a uma lista.
Diagram: Fan-out on write: one post is copied into every follower's timeline
Note a ordem: o post é salvo primeiro, e o fan-out acontece de forma assíncrona a partir de uma fila. Se os workers ficam para trás, os seguidores veem o post um pouco depois, mas o autor nunca é bloqueado. A fila dá os retries; as escritas precisam ser idempotentes, porque o mesmo evento pode ser entregue duas vezes (veja filas de mensagens e garantias de entrega). Adicionar um id a um sorted set é naturalmente idempotente: adicionar o mesmo membro de novo não muda nada.
Timelines no Redis
Um sorted set do Redis por usuário se encaixa bem: membro = id do post, score = o mesmo id ordenável por tempo. Executei isto contra um Redis 7 de verdade:
ZADD tl:42 7000000000001 7000000000001 # add a post (a repeat changes nothing)
ZREMRANGEBYRANK tl:42 0 -801 # keep only the newest 800
ZREVRANGEBYSCORE tl:42 +inf -inf LIMIT 0 20 # page 1, newest first
ZREVRANGEBYSCORE tl:42 (7000000000980 -inf LIMIT 0 20 # next page: strictly below the last id seen
O que medi:
| Medição | Resultado |
|---|---|
| Fan-out de um post para 100 000 timelines (em pipeline, um cliente na mesma máquina) | 1,59 s, cerca de 63 000 escritas de timeline por segundo (um pequeno sandbox: depende do hardware, então trate como ordem de grandeza e execute de novo no seu próprio hardware) |
| Uma timeline de 800 entradas | 81 944 bytes: cerca de 102 bytes por entrada (87 064 bytes, 109 por entrada, quando a construí em um único ZADD em lote; os níveis aleatórios da skip list fazem o tamanho variar alguns por cento) |
| Depois de 1 000 inserts com o trim | o tamanho continua 800, as entradas mais antigas são descartadas |
Paginação por cursor com (id | página 1 = 1000…996, página 2 = 995…991: sem sobreposição, sem lacuna |
Dois fatos de planejamento decorrem. Primeiro, a memória: 800 entradas são cerca de 82 KB por usuário, então 100 milhões de usuários precisariam de aproximadamente 8 TB de RAM se todo usuário mantivesse uma timeline completa. Respostas de projeto: guarde apenas ids (nunca corpos de posts; busque os corpos em um cache de posts), mantenha menos entradas (200 entradas são cerca de 25 KB no teste de layout abaixo) e mantenha timelines apenas para usuários recentemente ativos. Segundo, a velocidade: uma instância de Redis tratou cerca de 63 000 escritas por segundo neste teste, em uma máquina pequena, com um cliente no mesmo host e sem rede. Um deployment real tem uma rede entre os workers e o Redis, replicação e valores maiores, então espere menos por instância e meça. Mesmo assim, as 23 000 escritas por segundo em média do projeto de 100 M de usuários cabem em um punhado de shards, e a verdadeira questão de projeto são as rajadas, não as médias.
Qual layout de memória para uma timeline?
O sorted set não é a única forma de guardar uma lista de ids. Guardei os mesmos ids (números de 8 bytes, do mais novo ao mais antigo) de três formas no Redis 7 e perguntei ao Redis a memória de cada chave:
| Entradas | Sorted set (ZADD) | Lista de ids (RPUSH) | Uma string binária (8 bytes por id) |
|---|---|---|---|
| 128 | 3 120 B (24 por entrada, listpack compacto) | 1 664 B (13 por entrada) | 1 328 B (10 por entrada) |
| 129 | 15 216 B (118 por entrada, skiplist) | 1 664 B | 1 328 B |
| 200 | 25 560 B (128 por entrada) | 2 176 B (11 por entrada) | 1 840 B (9 por entrada) |
| 800 | 87 064 B (109 por entrada) | 8 320 B (10 por entrada) | 7 216 B (9 por entrada) |
O sorted set é cerca de 10 vezes maior que os outros dois depois de passar de 128 entradas, que é onde o Redis o troca de um array compacto para uma skip list (o padrão de zset-max-listpack-entries é 128). Então por que pagar por ele?
| Layout | O que dá | O que custa |
|---|---|---|
| Sorted set | Adicionar um id duas vezes não muda nada (fan-out idempotente). O cursor por score ((id) é um comando. Trim por posição. | Cerca de 100 a 130 bytes por entrada além de 128 entradas |
| Lista | Cerca de 10 bytes por entrada; push na cabeça e trim (LPUSH + LTRIM) são baratos | Um retry acrescenta uma duplicata (você precisa deduplicar na leitura ou proteger a escrita); sem busca por id, então o cursor significa um offset ou uma varredura |
| String binária | A menor; uma leitura traz tudo | Toda escrita é um ler-modificar-escrever do valor inteiro, o que sofre corrida com workers de fan-out concorrentes, a menos que você serialize por usuário |
Decisão: o sorted set é o padrão aqui porque o fan-out é at-least-once e a idempotência vale a memória. Se a memória é a restrição, a lista, com um décimo do tamanho, é uma opção real, desde que o caminho de escrita seja protegido contra duplicatas (por exemplo, pule o push quando o id novo não for maior que a cabeça da lista: os ids são ordenáveis por tempo). Outro corte é manter pequenos os sorted sets: 128 entradas continuam compactas com 24 bytes cada, então uma timeline curta (e um fallback de pull além dela, abaixo) pode ser muito mais barata que uma de 800 entradas. Os números são os padrões do Redis 7.0.15; confira os seus com MEMORY USAGE.
Por que só o push quebra: o problema das celebridades
Construí um modelo de um milhão de usuários com uma distribuição de seguidores de cauda pesada (uma forma de Pareto, de modo que a maioria das contas tem poucos seguidores e algumas têm audiências enormes; os números exatos dependem das minhas suposições de 0,5 post e 10 aberturas de feed por usuário por dia):
| Resultado | |
|---|---|
| Média de seguidores por conta | 39,6 |
| Mediana de seguidores | 9 |
| Maior conta | 500 000 seguidores |
| Parcela de todas as relações de seguir mantida pelo 1% de contas do topo | 54% |
| Escritas diárias em timelines com push puro | cerca de 19,8 milhões |
| Leituras diárias de listas de seguidos com pull puro | cerca de 396 milhões |
| Um post da maior conta, com push | 500 000 escritas em timelines |
O push puro é muito mais barato que o pull puro no total (20 milhões de escritas contra 396 milhões de leituras), mas um post da maior conta dispara meio milhão de escritas de uma vez. Atrasa os seguidores dessa conta, inunda a fila de modo que os posts de usuários comuns esperam atrás dele, e a maioria dessas escritas vai para usuários que não abrirão o app hoje. A resposta é uma mistura.
5. O híbrido: push para a maioria, pull para poucos
Escolha um limiar (digamos, 10 000 seguidores). Contas normais recebem push; contas de celebridades não. Quando alguém abre o feed, a API lê a sua timeline pré-calculada e mescla os posts recentes das celebridades que essa pessoa segue, obtidos por pull na hora da leitura. Os posts de uma celebridade são buscados em uma lista quente e muito bem armazenada em cache, de modo que um milhão de leitores compartilham o trabalho de uma consulta.
Diagram: Reading the home feed in the hybrid design
Executei o mesmo modelo de um milhão de usuários para três limiares:
| Pull para contas com mais de | Contas em pull | Escritas diárias de push (contra o push total) | Listas de celebridades mescladas por abertura de feed |
|---|---|---|---|
| 1 000 seguidores | 2 926 | 11,1 M (56%) | cerca de 17 |
| 10 000 seguidores | 239 | 14,4 M (73%) | cerca de 10,8 |
| 100 000 seguidores | 19 | 17,2 M (87%) | cerca de 5,1 |
Leia esta tabela como um botão de ajuste. Um limiar baixo remove mais custo de escrita e as maiores rajadas, e faz cada leitura mesclar mais listas. Um limiar alto mantém as leituras simples e deixa as rajadas (as 19 contas do topo respondem por 13% de todas as escritas neste modelo, em grandes blocos). Escolher o limiar é questão de medir a sua própria distribuição de seguidores, e pode ser uma decisão por conta tomada a partir de followers_count na hora de publicar. (A coluna "listas de celebridades por abertura de feed" supõe que os seguidores se distribuem aleatoriamente; as pessoas reais seguem contas mais famosas que a média, então meça com dados reais.)
Outras escolhas em torno do híbrido:
- Não faça push para usuários inativos. Se alguém não abre o app há 30 dias, pule-o; quando voltar, reconstrua a sua timeline por pull (uma "partida a frio"). Só isso pode cortar muito o volume de escrita, porque muitas arestas de seguir apontam para contas dormentes.
- Reconstrua em caso de perda. O armazenamento de timelines é um cache de dados derivados. Se um shard morre, reconstrua as timelines a partir do grafo de seguidores e da tabela de posts, de forma preguiçosa, na próxima leitura.
- Priorize. O fan-out de contas pequenas não deve esperar atrás de uma celebridade: use filas ou prioridades separadas.
6. Lendo o feed: paginação que não quebra
O feed muda enquanto você rola: posts novos chegam no topo. Isso torna a "página 2" traiçoeira. A abordagem comum, LIMIT 20 OFFSET 20, tem dois defeitos, e medi os dois no PostgreSQL com uma tabela de timeline de um milhão de linhas (500 000 para um usuário):
Mais lenta quanto mais fundo você vai. OFFSET n faz o banco de dados passar por n linhas e jogá-las fora.
| Página | OFFSET | Cursor keyset |
|---|---|---|
| 1 | 0,26 ms | 0,26 ms |
| 100 | 0,47 ms | 0,16 ms |
| 1 000 | 3,52 ms | 0,17 ms |
| 10 000 | 31,88 ms | 0,22 ms |
Errada quando a lista muda. Carreguei a página 1, inseri 5 posts novos e depois carreguei a página 2: a página 2 por OFFSET repetiu 5 posts já vistos (tudo se deslocou cinco posições para baixo); a página por keyset repetiu 0.
A paginação keyset (cursor, "seek") pede as linhas depois da última que você viu, usando a chave de ordenação: WHERE (created_at, post_id) < (last_created_at, last_post_id) ORDER BY created_at DESC, post_id DESC LIMIT 20. O plano é uma varredura reversa somente de índice que para depois de 20 linhas, e o custo não depende de quão fundo você está [1]. O cursor é opaco para o cliente: codifique a chave de ordenação do último item (por exemplo, base64 do id do post) e devolva-a como ?cursor=….
Aqui está o núcleo do caminho de leitura: mesclar a timeline com push e os posts das celebridades depois de um cursor, e devolver uma página e o próximo cursor (escolha uma linguagem nas abas; sua escolha é lembrada):
import heapq
def feed_page(timeline_ids, celeb_lists, cursor, limit=20):
"""Each input list is sorted newest first (largest id first). cursor = the smallest id already
shown, or None for the first page. Returns (page, next_cursor)."""
def after_cursor(ids):
return (i for i in ids if cursor is None or i < cursor)
merged = heapq.merge(after_cursor(timeline_ids), *(after_cursor(l) for l in celeb_lists), reverse=True)
page, last = [], None
for i in merged:
if i == last: # the same post can come from two lists: drop duplicates
continue
page.append(i)
last = i
if len(page) == limit:
break
return page, (page[-1] if len(page) == limit else None)
// Each input slice is sorted newest first (largest id first). cursor == 0 means the first page.
func FeedPage(timeline []int64, celebs [][]int64, cursor int64, limit int) (page []int64, next int64) {
lists := append([][]int64{timeline}, celebs...)
pos := make([]int, len(lists))
for len(page) < limit {
best, from := int64(-1), -1
for i, l := range lists {
for pos[i] < len(l) && cursor != 0 && l[pos[i]] >= cursor {
pos[i]++ // skip what the cursor says was already shown
}
if pos[i] < len(l) && l[pos[i]] > best {
best, from = l[pos[i]], i
}
}
if from < 0 {
return page, 0 // everything is used up: no next page
}
for i, l := range lists { // advance every list that holds the same id (duplicates)
if pos[i] < len(l) && l[pos[i]] == best {
pos[i]++
}
}
page = append(page, best)
}
return page, page[len(page)-1]
}
// Each input array is sorted newest first (largest id first). cursor is null on the first page.
function feedPage(timeline, celebLists, cursor, limit = 20) {
const lists = [timeline, ...celebLists].map((l) => l.filter((id) => cursor === null || id < cursor));
const pos = lists.map(() => 0);
const page = [];
while (page.length < limit) {
let best = null;
lists.forEach((l, i) => {
if (pos[i] < l.length && (best === null || l[pos[i]] > best)) best = l[pos[i]];
});
if (best === null) return { page, next: null };
lists.forEach((l, i) => {
if (pos[i] < l.length && l[pos[i]] === best) pos[i]++; // drop duplicates across lists
});
page.push(best);
}
return { page, next: page[page.length - 1] };
}
// Each input list is sorted newest first (largest id first). cursor == null means the first page.
public static (List<long> Page, long? Next) FeedPage(
IReadOnlyList<long> timeline, IReadOnlyList<IReadOnlyList<long>> celebs, long? cursor, int limit = 20)
{
var lists = new List<List<long>> { timeline.Where(i => cursor is null || i < cursor).ToList() };
lists.AddRange(celebs.Select(l => l.Where(i => cursor is null || i < cursor).ToList()));
var pos = new int[lists.Count];
var page = new List<long>();
while (page.Count < limit)
{
long? best = null;
for (int i = 0; i < lists.Count; i++)
if (pos[i] < lists[i].Count && (best is null || lists[i][pos[i]] > best)) best = lists[i][pos[i]];
if (best is null) return (page, null);
for (int i = 0; i < lists.Count; i++)
if (pos[i] < lists[i].Count && lists[i][pos[i]] == best) pos[i]++;
page.Add(best.Value);
}
return (page, page[^1]);
}
Uma implementação real lê de cada lista apenas o que precisa (os próximos 20 depois do cursor, do Redis), não listas inteiras; a lógica do merge é a mesma.
Além disso: posts novos que chegam enquanto o usuário rola não deslocam as páginas seguintes (o cursor cuida disso); no topo, mostre um botão "3 posts novos" em vez de inserir itens sob os olhos do leitor (seção 9).
Rolando além do fim da timeline
A timeline guarda apenas os 800 ids mais novos, então um rolador determinado chegará ao fim, e também um usuário que volta depois de uma longa ausência. Há três opções honestas:
- Parar com um fim claro: "Você está em dia" (ou "Carregar posts mais antigos", que abre a busca ou a lista do perfil). Simples, e muitos produtos fazem isso; o custo é que usuários muito ativos encontram um limite.
- Recuar para o pull nas páginas mais antigas: quando o cursor passa abaixo do id mais antigo da timeline, leia a lista de seguidos e a tabela de posts com a mesma condição keyset (
id < cursor) e mescle, exatamente como na abordagem 1, mas uma página por vez. Isso é lento e caro por requisição, então limite a taxa e a profundidade (por exemplo, 7 dias ou alguns milhares de posts). - Manter uma cauda maior para os poucos que precisam: um limite de trim maior só para leitores intensos.
Para saber se a timeline é a história toda, registre se algo chegou a ser descartado. ZREMRANGEBYRANK devolve o número de membros que removeu (conferi: 1 quando uma quinta entrada empurrou para fora a mais antiga de quatro, 0 na chamada seguinte), então o worker pode definir uma flag por usuário quando for maior que zero. O caminho de leitura fica assim:
def older_page(user, cursor, limit=20):
ids = timeline.below(user, cursor, limit) # ZREVRANGEBYSCORE tl:user (cursor -inf LIMIT 0 limit
if len(ids) == limit or not timeline.was_trimmed(user):
return ids # a full page, or the timeline holds everything there is
last = ids[-1] if ids else cursor # continue where the timeline ran out
return ids + pull_page(user, below=last, limit=limit - len(ids)) # approach 1, one page, depth-capped
A mesma função cobre a partida a frio de um usuário que volta: uma timeline vazia ou obsoleta é simplesmente uma timeline que acabou de imediato.
7. Feeds ranqueados
Muitos produtos ranqueiam em vez de ordenar por tempo. A forma usual tem dois estágios:
- Geração de candidatos: barata e ampla. A timeline da seção 5 (algumas centenas de ids recentes), mais alguns posts recomendados de fora do grafo de seguidores.
- Ranqueamento: um modelo pontua cada candidato para este usuário, a partir de sinais como a relação do autor com o usuário (respostas, curtidas, visitas ao perfil), a idade do post e o engajamento inicial, o tipo de mídia e as ações previstas (curtir, responder, compartilhar, ocultar). Ordene pela pontuação e depois aplique regras: no máximo dois posts seguidos do mesmo autor, misture tipos de mídia, remova o que o usuário já viu.
Consequências de projeto:
- O ranqueamento acontece no caminho de leitura, sobre um pequeno conjunto de candidatos, de modo que a latência fica limitada; o trabalho pesado do modelo é feito offline (treinamento, features) ou em cache.
- A paginação por cursor fica mais difícil, porque a ordem é calculada por requisição e muda conforme as pontuações mudam. Correções típicas: calcular a lista ranqueada uma vez por sessão e guardá-la (um snapshot de vida curta), paginar pelo snapshot e lembrar os ids vistos para evitar repetições.
- Mantenha uma opção cronológica; os usuários gostam de vê-la, e é um fallback útil quando o ranqueador está fora do ar.
- Cuidado com os ciclos de realimentação (o que é mostrado recebe engajamento, o que o faz ser mostrado mais) e meça além dos cliques (ocultações, retenção de longo prazo). Isso é tanto um problema de produto quanto técnico.
8. Sharding e cache
- As timelines têm sharding por id de usuário (consistent hashing, veja o guia de consistent hashing). O feed inteiro de um usuário vive em um shard, então a leitura de um feed é uma ida e volta.
- Os posts são consultados por id e são imutáveis exceto por edições e exclusões; um cache read-through na frente do banco de posts (estratégias de cache) responde à maioria das buscas de corpo. Os posts de celebridades são as chaves mais quentes do sistema; replique-os ou guarde-os em cache na borda.
- O grafo de seguidores é lido com frequência e muda devagar. Guarde em cache o conjunto de seguidos de cada usuário; para o fan-out, percorra os seguidores de um autor em lotes (1 000 por vez) em vez de carregá-los todos.
- As réplicas fazem o próprio post novo de um usuário parecer ausente do seu feed se ele lê de uma cópia atrasada. Acrescente o post do autor à sua própria timeline imediatamente e leia as suas próprias escritas do primário (a garantia "read your writes" do guia do CAP).
9. Atualizações em tempo real
Como um feed mostra posts novos sem recarregar?
- Polling: a cada 30 a 60 segundos pergunte "algo mais novo que o id X?". Simples, desperdiçador e bom o bastante para muitos produtos.
- Long polling, Server-Sent Events, WebSockets: o servidor empurra um pequeno sinal de "há posts novos". Mantenha-o um sinal, não os próprios posts; o cliente então busca os itens novos com a API normal e mostra "N posts novos". Isso mantém um só caminho de código para a leitura e mantém leve a camada de conexões.
- As conexões são caras em escala (memória por conexão, roteamento fixo); mantenha-as apenas para usuários que estão olhando o feed agora.
10. Exclusões, edições e privacidade
- Exclusões: não persiga um post apagado por milhões de timelines. Marque o post como apagado na tabela de posts e filtre na hora da leitura ao buscar os corpos (a timeline guarda apenas ids, e é por isso que isso funciona). As timelines se arrumam sozinhas conforme as entradas antigas são aparadas.
- Edições: o id continua o mesmo, o corpo muda; o cache é invalidado pelo id.
- Bloqueios, silenciamentos, contas privadas: também filtrados na hora da leitura, usando as configurações atuais do leitor; não dependa do que era verdade quando o post foi distribuído, porque as relações mudam.
- Seguir e deixar de seguir: seguir alguém deve mostrar logo os posts recentes dessa pessoa (preencha alguns posts recentes na timeline); deixar de seguir deve ocultar os posts (filtre na hora da leitura por "ainda sigo este autor").
11. Confiabilidade e operação
- Fan-out idempotente e repetível a partir de uma fila durável, com uma dead-letter queue para eventos que continuam falhando e um alerta sobre o atraso da fila (a idade do post não processado mais antigo é o número que os usuários sentem).
- Backpressure e prioridades: filas separadas para contas normais e muito grandes; limite a taxa de fan-out para que o Redis continue saudável.
- Degrade com elegância: se o armazenamento de timelines cai, recue para o pull para um conjunto limitado de seguidos; se o ranqueador cai, sirva o feed cronológico.
- Limite a taxa de publicar e seguir (guia do rate limiter); contas de spam seguem em massa e publicam em massa.
- Métricas: latência de leitura do feed (p50, p99), atraso do fan-out, memória das timelines, taxa de acerto do cache, profundidade da fila e a parcela das requisições de feed que precisaram de um merge por pull.
- Testes: testes unitários do merge e do cursor (duplicatas, listas vazias, o fim do feed); um teste de carga com uma distribuição de seguidores assimétrica, porque um teste uniforme esconde por completo o problema das celebridades; um teste de caos que mata um shard de timeline e confere a reconstrução.
12. Erros comuns
- Copiar corpos de posts para as timelines. Guarde ids; busque os corpos em um cache. Do contrário, edições e exclusões viram um pesadelo e a memória explode.
- Push puro para todos, e um post de celebridade que derruba o sistema. Meça a cauda.
- Pull puro, e uma tela inicial lenta.
- Paginação por
OFFSETem uma lista que muda: duplicatas, lacunas e páginas profundas lentas (medido acima). - Um cursor que não é uma chave de ordenação única. Se muitos posts compartilham um timestamp, um cursor só de timestamp pula ou repete itens; use o id único (ou
(timestamp, id)). - Fan-out dentro da requisição que cria o post. Use uma fila.
- Fazer push para usuários inativos, o que desperdiça a maior parte do volume de escrita.
- Tratar o armazenamento de timelines como fonte da verdade. São dados derivados e precisam ser reconstruíveis.
- Esquecer o próprio post do leitor em uma réplica atrasada.
13. Perguntas que os entrevistadores gostam de acrescentar
"Por que não usar simplesmente uma consulta SQL com um join, como na abordagem 1?"
Funciona em pequena escala e é uma boa primeira resposta. Com os números acima, coloca um merge largo em cada leitura de feed, sem uma forma amigável ao cache. Diga isso e depois passe ao push.
"E se um usuário segue 10 000 pessoas?"
Com push a timeline dele continua sendo uma lista (ele não paga nada a mais na leitura), mas as contas que segue fazem fan-out para a lista dele como de costume. Com pull ele seria o pior caso. Os seguidores intensos são uma razão para manter o push como base.
"Como você lida com um usuário que não faz login há meses?"
Não faça push para ele; quando voltar, monte a timeline sob demanda buscando por pull os posts recentes dos seus seguidos (e mostre um spinner ou um feed um pouco mais antigo nesse meio-tempo), depois retome o push.
"Como você garante que nenhum post se perca?"
O post é escrito no banco de dados durável de posts antes de qualquer outra coisa; o evento passa por uma fila durável com retries e consumidores idempotentes. Se uma escrita de timeline se perder mesmo assim, a timeline pode ser reconstruída a partir dos posts e do grafo.
"Como você acrescentaria ranqueamento depois?"
Mantenha as timelines como o conjunto de candidatos e acrescente um estágio de ranqueamento no caminho de leitura; guarde a página ranqueada para a sessão, para que a paginação continue estável.
"O que você faria de diferente para um feed de 1 000 usuários?"
Nada sofisticado: uma consulta SQL com o índice certo (pull) é mais simples e rápida o bastante. O projeto acima é para quando isso deixa de ser verdade, e a resposta na entrevista deve dizer isso.
14. Coisas a mencionar em uma entrevista
- Comece pelos requisitos e números, e note que as leituras superam as escritas.
- Explique o pull e o push com seus custos e nomeie o problema das celebridades.
- Dê o híbrido, com um limiar, e diga que o escolheria a partir de dados.
- Guarde ids, não corpos; faça sharding das timelines por usuário; apare para os N mais novos; pule os usuários inativos.
- Use paginação keyset com um cursor único e diga por que o
OFFSETfalha. - Faça o fan-out de forma assíncrona por uma fila, com escritas idempotentes.
- Filtre exclusões, bloqueios e privacidade na hora da leitura.
- Cubra o ranqueamento como um segundo estágio e as atualizações em tempo real como um sinal de "posts novos".
- Feche com monitoramento: atraso da fila, percentis de latência, memória.
Resumo rápido
- Um feed é uma visão derivada dos posts e do grafo de seguidores; pode ser reconstruído.
- O pull (merge na hora da leitura) é simples mas deixa as leituras lentas; o push (copiar para as timelines dos seguidores) deixa as leituras rápidas, mas um post de celebridade pode significar centenas de milhares de escritas.
- O híbrido faz push das contas normais e pull das celebridades na hora da leitura; o limiar é um botão que você ajusta a partir de dados.
- As timelines guardam apenas ids, em um sorted set por usuário aparado para os N mais novos (cerca de 102 bytes por entrada no Redis aqui).
- Use paginação keyset (por cursor): tempo constante em qualquer profundidade e estável enquanto chegam posts novos.
- Faça o fan-out de forma assíncrona a partir de uma fila com escritas idempotentes e pule os usuários inativos.
- Aplique exclusões, bloqueios e privacidade na hora da leitura.
- O ranqueamento é um segundo estágio sobre um pequeno conjunto de candidatos; mantenha um fallback cronológico.
Apêndice: o código dos experimentos
O modelo de seguidores, os testes de Redis e o benchmark de paginação são todos curtos. Você precisa do Python 3, do redis-py e de um Redis na porta 6399 para os testes de Redis (redis-server --port 6399 --save "" --appendonly no), e do psycopg mais um PostgreSQL para o teste de paginação (edite a string de conexão). Todos são descartáveis: apagam o que criam.
fanout.py: o modelo de seguidores (um milhão de usuários, forma de Pareto 1,1 com mínimo de 5 seguidores, limitado à metade dos usuários; 0,5 post e 10 aberturas de feed por usuário por dia; semente 7). Imprime as tabelas das seções de celebridades e do híbrido. Mude a semente ou a forma e os números se movem; o padrão (poucas contas causam uma grande parcela das escritas) é o que se deve conferir.
import random, math, statistics
rnd=random.Random(7)
N=1_000_000 # users
# follower counts ~ Pareto (a few accounts have a huge audience)
def followers():
x=int(5*(1/(1-rnd.random()))**(1/1.1)) # shape 1.1, min 5
return min(x,N//2)
F=[followers() for _ in range(N)]
tot=sum(F); F.sort(reverse=True)
print("users",N,"mean followers %.1f"%(tot/N),"median",F[N//2],"max",F[0])
print("top 1%% of accounts hold %.0f%% of all follow edges"%(100*sum(F[:N//100])/tot))
posts_per_user_day=0.5 # assumed
reads_per_user_day=10 # assumed feed opens
following_avg=tot/N # edges / users = avg following
# push: every post is written to every follower's timeline
posts=N*posts_per_user_day
# post rate proportional to account (same for all) -> expected writes = posts * mean followers
push_writes=posts*tot/N
# pull: each feed open reads the last k posts of every followee
pull_reads_per_open=following_avg
pull_reads=N*reads_per_user_day*pull_reads_per_open
print("posts/day %.0f"%posts)
print("push: timeline writes/day %.2e, reads/day %.2e (one list per open)"%(push_writes,N*reads_per_user_day))
print("pull: reads of followee lists/day %.2e (avg %.0f followees per open)"%(pull_reads,pull_reads_per_open))
# the celebrity problem: one post by the biggest account
print("one post by the top account: push = %d timeline writes"%F[0])
for T in (1000,10000,100000):
big=[f for f in F if f>T]
# hybrid: push only for accounts with <=T followers; accounts above T are pulled at read time
pushed=sum(f for f in F if f<=T)*posts_per_user_day
celeb_count=len(big)
# each feed open must also merge in posts of the celebrities that user follows: expected celebs followed
expected_celebs=sum(big)/N
print("T=%6d: %6d accounts above T; push writes/day %.2e (%.0f%% of full push); each open merges ~%.1f celebrity lists"%(T,celeb_count,pushed,100*pushed/push_writes,expected_celebs))
feedredis.py: velocidade do fan-out, tamanho da timeline, trim e paginação por cursor:
import redis, time
r=redis.Redis(port=6399); r.flushall()
base=r.info("memory")["used_memory"]
followers=100_000; KEEP=800
post_id=7_000_000_000_001 # time-sortable id: larger = newer
t=time.perf_counter()
pipe=r.pipeline(transaction=False)
for i in range(followers):
key=f"tl:{i}"
pipe.zadd(key,{post_id:post_id}); pipe.zremrangebyrank(key,0,-(KEEP+1))
if i%1000==999: pipe.execute()
pipe.execute()
dt=time.perf_counter()-t
used=r.info("memory")["used_memory"]-base
print("fan-out of one post to %d timelines: %.2f s (%.0f timeline writes/s), %.0f bytes per one-entry timeline"%(followers,dt,followers/dt,used/followers))
# a full timeline of 800 entries
for i in range(1,801): r.zadd("full",{post_id+i:post_id+i})
m=r.memory_usage("full"); print("one timeline of 800 entries: %d bytes (%.1f bytes per entry)"%(m,m/800))
# trim keeps the newest 800
for i in range(801,1001): r.zadd("full",{post_id+i:post_id+i}); r.zremrangebyrank("full",0,-(KEEP+1))
print("after 1000 inserts with trim: length",r.zcard("full"),"oldest kept offset",int(r.zrange("full",0,0)[0])-post_id)
# cursor pagination, newest first, exclusive cursor
page1=r.zrevrangebyscore("full","+inf","-inf",start=0,num=5); cur=int(page1[-1])
page2=r.zrevrangebyscore("full",f"({cur}","-inf",start=0,num=5)
print("page1",[int(x)-post_id for x in page1],"page2",[int(x)-post_id for x in page2])
layouts.py: a comparação de layouts de memória:
import redis, struct
r=redis.Redis(port=6399); r.flushall()
base=7_000_000_000_000
def size(key): return r.memory_usage(key)
for n in (100,128,129,200,800):
ids=[base+i for i in range(n)]
r.delete("z","l","b","zs")
r.zadd("z",{str(i):i for i in ids}) # sorted set, member = id, score = id
r.rpush("l",*[str(i) for i in reversed(ids)]) # list of ids, newest first, as text
r.set("b",b"".join(struct.pack(">Q",i) for i in reversed(ids))) # one binary string, 8 bytes per id
print("%4d entries | sorted set %6d B (%5.1f/entry, %s) | list %6d B (%5.1f/entry, %s) | binary string %6d B (%4.1f/entry)"%(
n,size("z"),size("z")/n,r.object("encoding","z").decode(),size("l"),size("l")/n,r.object("encoding","l").decode(),size("b"),size("b")/n))
pag.py: OFFSET contra keyset no PostgreSQL, e o teste de duplicatas:
import psycopg, time, statistics
c=psycopg.connect("host=/tmp port=5499 user=postgres dbname=postgres",autocommit=True)
c.execute("DROP TABLE IF EXISTS timeline")
c.execute("CREATE TABLE timeline (user_id int, post_id bigint, created_at timestamptz, PRIMARY KEY (user_id, created_at, post_id))")
# one user with 500k timeline entries, ids increasing with time; plus 1000 other users x 500 entries
c.execute("""INSERT INTO timeline SELECT 1, g, timestamptz '2026-01-01' + g * interval '1 second' FROM generate_series(1,500000) g""")
c.execute("""INSERT INTO timeline SELECT 2+ (g % 1000), g, timestamptz '2026-01-01' + g * interval '1 second' FROM generate_series(1,500000) g""")
c.execute("ANALYZE timeline")
def timeit(sql,args=()):
ts=[]
for _ in range(7):
t=time.perf_counter(); c.execute(sql,args).fetchall(); ts.append((time.perf_counter()-t)*1000)
return statistics.median(ts)
print("rows",c.execute("select count(*) from timeline").fetchone()[0])
for page in (1,100,1000,10000):
off=(page-1)*20
t_off=timeit("SELECT post_id FROM timeline WHERE user_id=1 ORDER BY created_at DESC, post_id DESC LIMIT 20 OFFSET %s",(off,))
# keyset: the cursor is the last (created_at, post_id) of the previous page
cur=c.execute("SELECT created_at, post_id FROM timeline WHERE user_id=1 ORDER BY created_at DESC, post_id DESC LIMIT 1 OFFSET %s",(max(off-1,0),)).fetchone()
t_key=timeit("SELECT post_id FROM timeline WHERE user_id=1 AND (created_at,post_id) < (%s,%s) ORDER BY created_at DESC, post_id DESC LIMIT 20",cur)
print("page %5d (offset %6d): OFFSET %.2f ms keyset %.2f ms"%(page,off,t_off,t_key))
print(c.execute("EXPLAIN SELECT post_id FROM timeline WHERE user_id=1 AND (created_at,post_id) < ('2026-01-03','1') ORDER BY created_at DESC, post_id DESC LIMIT 20").fetchall()[0][0])
# duplicates with OFFSET when new items arrive between page 1 and page 2
ids1=[r[0] for r in c.execute("SELECT post_id FROM timeline WHERE user_id=1 ORDER BY created_at DESC, post_id DESC LIMIT 20")]
last=c.execute("SELECT created_at, post_id FROM timeline WHERE user_id=1 ORDER BY created_at DESC, post_id DESC LIMIT 1 OFFSET 19").fetchone()
c.execute("INSERT INTO timeline SELECT 1, g, timestamptz '2026-01-01' + g*interval '1 second' FROM generate_series(600001,600005) g") # 5 new posts
off2=[r[0] for r in c.execute("SELECT post_id FROM timeline WHERE user_id=1 ORDER BY created_at DESC, post_id DESC LIMIT 20 OFFSET 20")]
key2=[r[0] for r in c.execute("SELECT post_id FROM timeline WHERE user_id=1 AND (created_at,post_id)<(%s,%s) ORDER BY created_at DESC, post_id DESC LIMIT 20",last)]
print("5 new posts arrive between page 1 and 2:")
print(" OFFSET page 2 repeats %d posts already seen on page 1"%len(set(ids1)&set(off2)))
print(" keyset page 2 repeats %d"%len(set(ids1)&set(key2)))
Fontes
- Markus Winand, Use The Index, Luke: paging through results without OFFSET (the seek method). Por que o
OFFSETfica mais lento e como a paginação keyset o evita. - Raffi Krikorian, Timelines at Scale (QCon, 2012). O fan-out na escrita do Twitter para as timelines iniciais e como as contas de celebridades são tratadas de forma diferente.
- Documentação do Redis, Sorted sets e os comandos
ZADD,ZREVRANGEBYSCORE,ZREMRANGEBYRANK. - Nathan Bronson et al., TAO: Facebook's Distributed Data Store for the Social Graph, USENIX ATC 2013. As leituras superam em muito as escritas em um grafo social, e a camada de cache construída para isso.
- Documentação do PostgreSQL, LIMIT and OFFSET e row-wise comparison (usada pela consulta keyset).
- Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly, 2017. O exemplo da timeline do Twitter no capítulo 1 (descrevendo a carga) e os capítulos sobre replicação e processamento de streams.
- Alex Xu, System Design Interview, 2020, capítulo "Design a news feed system". O tratamento padrão de entrevista para este problema.
Pratique este tema: System Design System Design › Case studies