Feed de Notícias

"Projete o feed inicial de uma rede social como o Instagram ou o X: usuários seguem outros usuários e, ao abrir o app, veem as publicações mais recentes de quem seguem."

O news feed é o problema clássico de leitura intensa com fan-out. Uma escrita (uma publicação) precisa ficar visível nos feeds de todos que seguem o autor — duas pessoas para a maioria dos usuários, cinquenta milhões para um astro pop. A entrevista gira em torno de uma decisão — fazer o trabalho quando a publicação é escrita, ou quando o feed é lido? — e do que acontece nos extremos dessa decisão: celebridades, usuários inativos, publicações apagadas e ranqueamento.

O BoxOffice tem o mesmo formato: fãs seguem artistas e locais, e a aba "Seguindo" mostra anúncios de turnês, novas datas e códigos de pré-venda. Quando um artista de estádio com milhões de seguidores anuncia uma turnê, o BoxOffice enfrenta exatamente o problema das celebridades desta página — no pior momento, porque todo mundo vai abrir o app ao mesmo tempo.

1. Esclarecer os requisitos

(roteiro de entrevista)

Requisitos funcionais

1. Um usuário publica um post (texto, imagens/vídeo opcionais).
2. Um usuário segue / deixa de seguir outros usuários (assimétrico: seguir não é amizade).
3. Um usuário abre o feed inicial: posts de quem ele segue, os mais novos primeiro (ou ranqueados), paginados com rolagem infinita.
4. Os posts mostram autor, contadores (curtidas, comentários) e mídia.

Requisitos não funcionais

Fora do escopo (diga explicitamente)

Comentários e curtidas como funcionalidades (só mostramos os contadores), busca, notificações, ranqueamento de anúncios, mensagens diretas. Cada um é seu próprio problema de design.

2. Estimativas de guardanapo (back-of-the-envelope)

# News feed: assumptions (illustrative)
dau            = 100_000_000
posts_per_dau  = 0.2          # most users read, few post
reads_per_dau  = 10           # feed opens / refreshes per day
peak_factor    = 3
avg_followers  = 200          # average fan-out per post (the tail is much larger)
timeline_len   = 800          # post IDs kept per cached feed
id_b           = 8            # one post ID (64-bit)
cache_overhead = 2            # data-structure overhead in the cache
post_b         = 1_000        # text + metadata
media_share    = 0.1          # posts with an image
image_b        = 500_000

posts_day      = dau * posts_per_dau
write_qps      = posts_day / 86_400
read_qps       = dau * reads_per_dau / 86_400
peak_read_qps  = read_qps * peak_factor
fanout_qps     = write_qps * avg_followers          # timeline inserts per second (push)
timeline_gb    = dau * timeline_len * id_b * cache_overhead / 1e9
posts_tb_year  = posts_day * post_b * 365 / 1e12
media_tb_day   = posts_day * media_share * image_b / 1e12

rows = [
    ("posts_day", posts_day, "posts"), ("write_qps", write_qps, "posts/s"),
    ("read_qps", read_qps, "req/s"), ("peak_read_qps", peak_read_qps, "req/s"),
    ("fanout_qps", fanout_qps, "inserts/s"), ("timeline_gb", timeline_gb, "GB"),
    ("posts_tb_year", posts_tb_year, "TB"), ("media_tb_day", media_tb_day, "TB/day"),
]
print("| quantity | value | unit |\n|---|---:|---|")
for name, value, unit in rows:
    v = f"{value:,.0f}" if abs(value) >= 100 else f"{value:,.2f}"
    print(f"| `{name}` | {v} | {unit} |")

O que os números dizem:

• As leituras (~12 mil/s, ~35 mil/s no pico) superam os posts (~230/s) em 50:1. ⇒ torne as leituras baratas, mesmo ao custo de mais trabalho nas escritas.
• Mas o fan-out por push transforma 230 posts/s em ~46 mil inserções de timeline/s em média — e a média esconde a cauda: um post de uma conta com 50 M de seguidores são 50 M de inserções sozinho. ⇒ o caminho de escrita precisa ser assíncrono (fila + workers), e celebridades precisam de tratamento especial.
• Timelines em cache de 800 IDs para cada usuário diário ocupam ~1,3 TB de RAM — um cluster de cache grande, mas comum (dezenas de nós). Guardar só IDs, não os posts, é o que torna isso viável; guardar só para usuários ativos reduz ainda mais.
• Os posts somam ~7 TB/ano (um armazenamento particionado), a mídia ~1 TB/dia (object storage + CDN — nunca no banco).

3. API

POST /v1/posts                               → 201 {postId, createdAt}
     {"text": "Tour announced! Presale Friday 10:00", "mediaIds": ["m_81f…"]}
POST /v1/media                               → 201 {mediaId, uploadUrl}   (pre-signed PUT to object store)

GET  /v1/feed?limit=20&cursor=eyJ0cyI6…      → 200 {items: [Post…], nextCursor}
GET  /v1/users/{id}/posts?cursor=…           → 200 {items: [Post…], nextCursor}   (profile timeline)

PUT    /v1/users/{id}/followers/me           → 204   (follow)
DELETE /v1/users/{id}/followers/me           → 204   (unfollow)

• Cursor, não número de página: cursor codifica (score ou timestamp, postId) do último item visto. Posts novos chegando no topo não deslocam as páginas (sem duplicatas, sem buracos) e a consulta é um seek no índice, não um OFFSET 4000.
• A mídia é enviada diretamente ao object storage com uma URL pré-assinada; o post só referencia o mediaId.

4. Modelo de dados

-- Posts: partitioned by author, newest first (wide-column, e.g. Cassandra)
CREATE TABLE posts_by_author (
    author_id  BIGINT,
    post_id    BIGINT,          -- Snowflake-style: time-ordered, unique
    text       TEXT,
    media      LIST<TEXT>,
    visibility TEXT,
    PRIMARY KEY ((author_id), post_id)
) WITH CLUSTERING ORDER BY (post_id DESC);

-- Social graph, stored in both directions
CREATE TABLE followers (user_id BIGINT, follower_id BIGINT, PRIMARY KEY ((user_id), follower_id));
CREATE TABLE following (user_id BIGINT, followee_id BIGINT, PRIMARY KEY ((user_id), followee_id));

# Timeline cache (Redis sorted set, score = post timestamp), trimmed to 800 entries
feed:{user_id}   →  { (1767261600123, 918273645), (1767261598001, 918273511), ... }

# Post cache for hydration (hash per post) and counters
post:{post_id}   →  { author_id, text, media, created_at }
likes:{post_id}  →  1532

5. Design de alto nível

flowchart LR
    u([App]) --> lb["Balanceador de carga"]
    lb --> ps["Serviço de posts"]
    ps --> pdb[("Armazenamento de posts<br/>por autor")]
    ps --> k[["Kafka<br/>post-created"]]
    k --> fw["Workers de fan-out"]
    fw --> g[("Grafo social<br/>seguidores")]
    fw --> tl[("Cache de timelines<br/>feed:{user} → IDs")]
    lb --> fs["Serviço de feed"]
    fs --> tl
    fs --> pc[("Cache de posts")]
    pc --> pdb
    fs --> rk["Ranqueamento"]
    u -. imagens .-> cdn["CDN"] --> obj[("Object store")]

Caminho de escrita: o serviço de posts grava o post e publica post-created; ele devolve 201 na hora. Os workers de fan-out leem os seguidores do autor em páginas e empurram o ID do post na timeline de cada seguidor ativo (ZADD + ZREMRANGEBYRANK para aparar).

Caminho de leitura:

sequenceDiagram
    autonumber
    participant A as App
    participant F as Serviço de feed
    participant T as Cache de timelines
    participant C as Posts de celebridades
    participant P as Cache de posts
    participant R as Ranqueamento
    A->>F: GET /v1/feed?limit=20
    F->>T: ZREVRANGE feed:42 0 199
    T-->>F: 200 IDs de posts (empurrados)
    F->>C: posts recentes das celebridades seguidas (pull)
    C-->>F: 30 IDs de posts
    F->>F: mescla, descarta apagados / bloqueados
    F->>P: multi-get de 230 posts (em lote)
    P-->>F: objetos de post
    F->>R: pontua os candidatos
    R-->>F: top 20
    F-->>A: 20 posts + nextCursor

6. Aprofundamentos (deep dives)

6.1 Fan-out na escrita, na leitura ou os dois

Quanto trabalho um limiar economiza? Com uma distribuição de seguidores de cauda pesada, uma fatia minúscula dos autores produz a maior parte do fan-out:

# Who pays for push fan-out? Synthetic heavy-tailed follower counts (illustrative)
import random

random.seed(42)
authors = 200_000
followers = [min(50_000_000, int(60 / (1 - random.random()) ** 1.25)) for _ in range(authors)]
total = sum(followers)                  # timeline inserts if every author posts once
followers.sort()

print(f"median followers: {followers[authors // 2]:,}  ·  max: {followers[-1]:,}\n")
print("| threshold | celebrities | celebrities_pct | writes_avoided_pct |\n|---:|---:|---:|---:|")
for threshold in (10_000, 100_000, 1_000_000):
    celeb = [f for f in followers if f >= threshold]
    print(f"| {threshold:,} | {len(celeb):,} | {len(celeb) / authors:.2%} | {sum(celeb) / total:.1%} |")

Puxar os posts de uma fração de um por cento dos autores elimina a maior parte das escritas de fan-out. O limiar é um botão de ajuste: abaixe-o e as leituras ficam um pouco mais caras (mais celebridades para mesclar por usuário), suba-o e os posts de celebridades demoram mais para se espalhar.

6.2 O cache de timelines e a hidratação

• Guarde IDs, não posts. Um post pode ser editado, apagado ou ter os contadores alterados; copiá-lo em 200 timelines faria de cada mudança um fan-out. Uma timeline é uma lista de (score, post_id); o conteúdo é hidratado na leitura com um único multi-get em lote no cache de posts.
• Apare cada timeline para algumas centenas de entradas (ZREMRANGEBYRANK). Ninguém rola 5 000 posts para trás no feed inicial; o histórico mais antigo vem do caminho de pull.
• Só usuários ativos. Os workers de fan-out pulam usuários que não abrem o app há, digamos, 30 dias. Quando um deles volta, o serviço de feed reconstrói a timeline com um pull (lento uma vez, depois em cache) — um caminho clássico de falta no cache (padrões de cache).
• Filtre na leitura. Posts apagados, autores bloqueados e posts que viraram privados são removidos durante a hidratação (o cache de posts diz deleted), então a timeline em si nunca precisa ser limpa de forma síncrona.
• Particione o cache de timelines por user_id (hash consistente); o feed de um usuário mora num shard, então a leitura é uma única ida e volta.

6.3 Ranqueamento

Um feed cronológico é "ordenar por tempo". Um feed ranqueado é um pequeno pipeline que precisa caber no orçamento de latência:

flowchart LR
    cand["Candidatos<br/>~500 IDs<br/>(empurrados + puxados)"] --> feat["Features<br/>afinidade com o autor, idade,<br/>engajamento, tipo de mídia"]
    feat --> score["Modelo de pontuação<br/>(leve)"]
    score --> rerank["Reordenação<br/>diversidade, deduplicação,<br/>regras de negócio"]
    rerank --> page["Top 20"]

• A geração de candidatos é a timeline (push + pull); as features vêm de armazenamentos pré-computados (a afinidade entre usuário e autor é calculada offline), nunca de consultas caras ao vivo.
• Pré-compute quando possível: ranqueie a primeira página quando é provável que o usuário abra o app (ou logo após o fan-out) e guarde em cache por alguns minutos.
• Mantenha um fallback: se o serviço de ranqueamento estiver lento, devolva a ordem cronológica. Um feed menos esperto mas no prazo é melhor do que um spinner (padrões de confiabilidade).

6.4 Paginação e atualidade

• Paginação por cursor: o cursor é (score, post_id) do último item; a próxima página é ZREVRANGEBYSCORE feed:42 (score -inf LIMIT 0 20. Posts novos chegando no topo não deslocam a próxima página, ao contrário do OFFSET.
• Posts novos durante a rolagem aparecem num aviso "novos posts" que recarrega do topo (uma requisição separada com since=), e não são inseridos embaixo do dedo do usuário.
• Ler as próprias escritas: depois de publicar, o autor precisa ver o post no próprio feed na hora, mesmo que o fan-out leve segundos — insira-o de forma síncrona na timeline do próprio autor, ou mescle os posts mais recentes do autor na leitura (modelos de consistência).

7. Gargalos, modos de falha e trade-offs

Os trade-offs para dizer em voz alta: amplificação de escrita vs. latência de leitura (o push paga na escrita para as leituras serem baratas), atualidade vs. custo (fan-out assíncrono significa segundos de atraso), e relevância vs. latência (o ranqueamento precisa cair para o cronológico quando está lento).

8. Experimente no playground

O cenário news-feed contém o serviço de posts, um caminho de fan-out por uma fila e workers, um cache de timelines e o serviço de feed.

Abrir o playground completo

9. Perguntas de follow-up que o entrevistador faz

10. Rubrica de autoavaliação

Relacionados: Mensageria, Padrões de cache, Particionamento, Hands-on 7 (processamento assíncrono com Kafka), Hands-on 5 (cache).

Como se conecta

Quais aulas este caso testa? Cada ramo é uma aula cujas ideias o design usa (azul), com os componentes da paleta em que elas aparecem (verde):

flowchart LR
    CASE(["News feed"]) --> EST["Estimation<br/>fan-out write amplification"]:::tech
    CASE --> MSG["Messaging<br/>post events, fan-out workers"]:::tech
    CASE --> CAC["Caching<br/>timeline cache, hydration"]:::tech
    CASE --> DB["Databases<br/>partition posts and timelines"]:::tech
    CASE --> DIS["Distributed<br/>read-your-writes for the author"]:::tech
    CASE --> REL["Reliability<br/>fallback to chronological order"]:::tech
    MSG -.-> k1["kafka · worker"]:::comp
    CAC -.-> k2["cache"]:::comp
    DB -.-> k3["nosql · objstore · cdn"]:::comp
    REL -.-> k4["app · lb"]:::comp
    classDef comp fill:#1e9e5a22,stroke:#1e9e5a
    classDef tech fill:#2f6fed22,stroke:#2f6fed

Aulas que ele testa: Mensageria — Kafka · Caching — padrões · Bancos de dados — particionamento · Distribuídos — consistência · Confiabilidade — padrões · Hands-on 5 e Hands-on 7. Componentes da paleta: lb · app · cache · nosql · kafka · worker · objstore · cdn. Cenários: news-feed.

Referências

• XU, A. System Design Interview — An Insider's Guide, vol. 1, cap. 11 "Design a News Feed System"¹.
• KLEPPMANN, M.; RICCOMINI, C. Designing Data-Intensive Applications, 2ª ed. — o exemplo da timeline inicial (fan-out na escrita vs. na leitura) no capítulo sobre descrever a carga².
• KRIKORIAN, R. Timelines at Scale — como o Twitter combinou push e pull³.
• BRONSON, N. et al. TAO: Facebook's Distributed Data Store for the Social Graph⁴.