Twitter Timeline — fan-out, celebridades e consistência eventual

Em 2012, o Twitter tinha um problema chamado internamente de "Bieber problem". Justin Bieber tinha 30 milhões de seguidores na época, e cada tweet seu disparava 30 milhões de writes simultâneos nos sistemas de timeline — travando o serviço. A solução encontrada foi um dos exemplos mais didáticos de como a escala transforma um problema simples num problema de distributed systems: não dá para tratar um usuário com 30 milhões de seguidores da mesma forma que um com 300.

O Twitter timeline — a lista de tweets das pessoas que você segue, em ordem cronológica reversa — parece simples à primeira vista. Mas ele encapsula o trade-off central de sistemas de feed em qualquer escala: o custo do trabalho deve ser pago no momento da escrita (quando o tweet é criado) ou no momento da leitura (quando o feed é carregado)? A resposta correta é: depende de quem está escrevendo.

Requisitos e estimation

Requisitos funcionais:

• Home timeline: tweets de contas que o usuário segue, em ordem cronológica reversa, carregados em páginas
• User timeline: tweets de uma conta específica, paginados
• Postar tweet: texto (280 chars), mídia opcional, reply/retweet
• Follow/unfollow: resultado deve se refletir na timeline

# Estimation para escala do Twitter (2023)
# DAU: 250M | MAU: 500M
# Tweets por dia: 500M (~5.800 tweets/s | pico: ~15k tweets/s)
# Leituras de timeline: 250M DAU × 10 checks/dia = 2,5B leituras/dia
#                       → ~29.000 reads/s | pico: ~80k reads/s

# Razão read:write ≈ 5:1 (2,5B leituras ÷ 500M escritas)
# Mas o custo por operação é muito diferente:
#   - Write de tweet: O(1) — inserir 1 registro
#   - Read de timeline sem cache: O(seguidores médios) = O(~200) queries
# Custo efetivo: reads dominam o sistema por uma margem enorme

# Storage de tweets:
# 500M tweets/dia × 500 bytes (texto + metadados) = 250 GB/dia
# Em 5 anos: ~456 TB (só tweets)
# Com replicação 3×: ~1,4 PB — requer armazenamento distribuído

Fan-out on read (pull model)

A abordagem mais intuitiva: quando o usuário abre o timeline, buscar tweets de todos que ele segue e montar o feed na hora.

-- Naive fan-out on read
SELECT t.*
FROM tweets t
JOIN follows f ON t.user_id = f.followee_id
WHERE f.follower_id = :user_id
  AND t.created_at > :cursor
ORDER BY t.created_at DESC
LIMIT 50;

-- Problema: essa query faz um join entre duas tabelas grandes
-- follows: 500M usuários × média de 200 follows = 100B linhas
-- tweets:  500M/dia × 365 × 5 = ~912B tweets
-- Essa query em produção, sem cache agressivo, é proibitiva

Mesmo com índices e otimizações, o problema fundamental permanece: se você segue 1.000 contas, a query precisa considerar 1.000 fontes de tweets e fazer o merge/sort. Em 80k reads/s no pico, isso se multiplica para uma carga insuportável no banco.

Quando fan-out on read faz sentido: para user timelines (tweets de uma única conta) — aí é uma query simples por user_id, com índice e cache por usuário. O problema é específico ao home timeline, onde múltiplas fontes precisam ser combinadas.

Fan-out on write (push model)

A abordagem inversa: quando um tweet é criado, imediatamente inserir uma referência a ele no feed pré-computado de cada seguidor. A leitura do timeline vira uma operação trivial — só buscar do feed pré-computado.

# Estrutura do timeline feed no Redis (Sorted Set por usuário)
# Score = timestamp do tweet (permite ordenação cronológica eficiente)
# Member = tweet_id (referência, não o conteúdo)

ZADD timeline:{follower_id} {tweet_timestamp} {tweet_id}

# Leitura do timeline: busca paginada em O(log N) + O(K)
ZREVRANGE timeline:{user_id} 0 49  # 50 tweets mais recentes
# → retorna lista de tweet_ids

# Busca de conteúdo: batch fetch dos tweets
GET tweet:{tweet_id_1}
GET tweet:{tweet_id_2}
... (pipeline Redis, ~1ms para 50 tweets)

# Fluxo completo de leitura:
# 1. ZREVRANGE timeline:{user_id} → lista de tweet_ids    (~0.5ms)
# 2. MGET tweet:{id1} tweet:{id2} ...                     (~1ms)
# 3. Merge com tweets de celebridades (explicado abaixo)  (~0.5ms)
# Total: ~2ms — latência excelente

A manutenção da timeline como sorted set resolve elegantemente vários problemas: inserção de tweet de quem você segue é um ZADD, remoção de tweet é um ZREM, follow de uma conta é um backfill dos tweets recentes dela, unfollow é um ZREM de todos os tweets dela.

O problema: ao criar um tweet, é necessário executar um ZADD para cada seguidor. Para um usuário comum com 300 seguidores, isso é 300 writes — aceitável. Para Katy Perry com 100M seguidores, isso é 100M writes por tweet. Com o Redis rodando a 100k ops/s, fan-out de um único tweet de celebridade levaria 1.000 segundos — claramente inviável.

O celebrity problem — análise quantitativa

# Distribuição de seguidores no Twitter (lei de potência / long tail):
# ~99% dos usuários têm < 10.000 seguidores
# ~0.9% têm entre 10k e 1M seguidores
# ~0.1% têm mais de 1M seguidores (celebridades)

# Custo de fan-out por tweet:
# Usuário comum (300 seguidores):    300 ZADD = ~3ms de trabalho do fan-out service
# Usuário médio (10k seguidores):  10.000 ZADD = ~100ms
# Influencer (1M seguidores):    1.000.000 ZADD = ~10 segundos
# Celebridade (100M seguidores):100.000.000 ZADD = ~17 minutos

# Se múltiplas celebridades postam simultaneamente (evento ao vivo):
# 10 celebridades × 50M seguidores = 500M writes simultâneos
# → impossível de executar em tempo real

# Conclusão: fan-out on write puro não é viável para celebridades.
# A solução precisa de um tratamento assimétrico baseado no número de seguidores.

A solução híbrida — o que o Twitter realmente fez

O Twitter introduziu um threshold de celebridade (internamente chamado de "heavy hitter threshold") em torno de 1 milhão de seguidores. Abaixo do threshold: fan-out on write. Acima: fan-out on read. O timeline de um usuário é então a combinação das duas fontes:

# Ao carregar o home timeline do usuário U:

# Fonte 1: feed pré-computado (fan-out on write)
# Contém tweets de todas as contas regulares que U segue
timeline_ids = ZREVRANGE timeline:{U} 0 199  # últimas 200 entradas

# Fonte 2: tweets recentes de celebridades seguidas por U
# (fan-out on read — só para celebridades)
celebrity_follows = GET celebrity_follows:{U}  # lista de celeb_ids seguidos por U
# Para cada celeb:
for celeb_id in celebrity_follows:
    celeb_tweets = ZREVRANGE user_tweets:{celeb_id} 0 19  # últimos 20 tweets da celeb
    timeline_ids.extend(celeb_tweets)

# Merge e sort por timestamp (feito no application layer)
# Os tweet_ids carregam o timestamp no Snowflake ID → sort sem fetch do conteúdo
all_ids = sorted(set(timeline_ids), key=lambda id: extract_timestamp(id), reverse=True)
final_ids = all_ids[:50]  # primeiros 50 para a primeira página

# Batch fetch do conteúdo dos tweets selecionados
tweets = MGET [f"tweet:{id}" for id in final_ids]

O merge no application layer é barato: os tweet IDs do Twitter (Snowflake) carregam o timestamp nos bits mais significativos, então ordenar por ID é equivalente a ordenar por tempo — sem necessidade de buscar o conteúdo dos tweets só para fazer o merge.

O serviço de fan-out

# Quando um tweet é criado:
# 1. Persistir o tweet no store de tweets (fonte de verdade)
tweet_id = tweets_db.insert(user_id, content, created_at)
# Cachear o conteúdo do tweet no Redis
SETEX tweet:{tweet_id} 86400 {serialized_tweet_content}

# 2. Publicar evento no fan-out queue (Kafka/SQS)
fan_out_queue.publish({
    "tweet_id": tweet_id,
    "author_id": user_id,
    "follower_count": user.follower_count,
    "created_at": created_at
})

# 3. Fan-out service consome o evento:
def process_fan_out(event):
    if event.follower_count > CELEBRITY_THRESHOLD:
        # Celebridade: não fazer fan-out
        # O tweet aparecerá via fan-out on read no momento de leitura do timeline
        mark_as_celebrity_tweet(event.tweet_id)
        return

    # Usuário regular: buscar todos os seguidores e fazer ZADD
    followers = follow_service.get_followers(event.author_id)
    # Processar em batches para eficiência
    pipeline = redis.pipeline()
    for follower_id in followers:
        pipeline.zadd(f"timeline:{follower_id}", {event.tweet_id: event.created_at})
        # Manter o timeline capped para não crescer indefinidamente
        pipeline.zremrangebyrank(f"timeline:{follower_id}", 0, -801)  # manter top 800
    pipeline.execute()  # batch de writes Redis em uma única round-trip

Follow graph: o problema da escala

O follow graph — quem segue quem — é uma das estruturas de dados mais consultadas no sistema. Fan-out service precisa de "todos os seguidores do usuário X"; timeline read precisa de "todas as celebridades que o usuário Y segue".

# Modelo relacional simples (adequado até ~10B arestas):
CREATE TABLE follows (
    follower_id BIGINT NOT NULL,
    followee_id BIGINT NOT NULL,
    created_at  TIMESTAMPTZ NOT NULL,
    PRIMARY KEY (follower_id, followee_id),
    INDEX idx_followee (followee_id, follower_id)  -- para buscar seguidores de X
);

# Consultas críticas:
# "Quem segue X?" (para fan-out)
SELECT follower_id FROM follows WHERE followee_id = :x;
# Com 100M seguidores, essa query retorna 100M linhas → não é feita em tempo real
# O fan-out service mantém essa lista pré-computada em shards do follow graph

# "A quem Y segue?" (para montar o timeline)
SELECT followee_id FROM follows WHERE follower_id = :y;
# Com Y seguindo em média 200 contas: 200 linhas — query rápida

# "Quais celebridades Y segue?" (para o merge do timeline)
SELECT followee_id FROM follows f
JOIN users u ON f.followee_id = u.id
WHERE f.follower_id = :y AND u.follower_count > CELEBRITY_THRESHOLD;
# Cacheável por usuário com TTL de 5 minutos (follows de celebridades mudam raramente)

Sharding do follow graph

Para usuários com 100M seguidores, a lista de seguidores não cabe num único shard. O Twitter usa um serviço dedicado de follow graph particionado por followee_id: todos os seguidores do usuário X estão no shard hash(X) % N. O fan-out service consulta esse shard para obter a lista de seguidores em pages (não toda de uma vez) e processa em batches paralelos.

Backfill ao fazer follow

Quando o usuário A começa a seguir o usuário B, o timeline de A deve imediatamente incluir tweets recentes de B — não só tweets futuros. Esse backfill precisa ser tratado com cuidado:

# Ao fazer follow:
def handle_follow(follower_id, followee_id):
    # 1. Persiste a aresta no follow graph
    follows_db.insert(follower_id, followee_id)

    # 2. Se followee é celebridade: sem backfill (tweets aparecerão via fan-out on read)
    if users[followee_id].follower_count > CELEBRITY_THRESHOLD:
        return

    # 3. Backfill: pegar os últimos N tweets do followee e inserir no timeline do follower
    recent_tweets = ZREVRANGE f"user_tweets:{followee_id}" 0 19  # últimos 20 tweets
    if recent_tweets:
        pipeline = redis.pipeline()
        for tweet_id in recent_tweets:
            tweet = get_tweet(tweet_id)
            pipeline.zadd(f"timeline:{follower_id}", {tweet_id: tweet.created_at})
        pipeline.execute()

# Ao fazer unfollow:
def handle_unfollow(follower_id, followee_id):
    # 1. Remove aresta do follow graph
    follows_db.delete(follower_id, followee_id)

    # 2. Remover tweets do followee do timeline do follower
    # Opção A: scan e remoção (cara para contas com muitos tweets no timeline do follower)
    followee_tweets = ZREVRANGE f"user_tweets:{followee_id}" 0 -1
    ZREM f"timeline:{follower_id}" *followee_tweets

    # Opção B: filtrar na leitura (mais simples, eventual consistency)
    # Marcar o unfollow e filtrar tweets do followee ao montar o timeline
    # Trade-off: tweets do followee ainda aparecem até o próximo refresh do timeline

Tweets deletados e edições

# Tweet deletado:
# 1. Soft delete no tweet store (deleted_at = NOW())
# 2. Não é necessário remover do timeline cache imediatamente
#    → ao fazer fetch do tweet_id, retornar null se deleted_at != null
#    → filtrar nulls ao montar o timeline para o usuário
# 3. Benefício: sem necessidade de scan do timeline de 100M seguidores ao deletar

# Tweet editado (feature introduzida em 2022):
# O tweet_id não muda (referências no timeline continuam válidas)
# O conteúdo no tweet store é atualizado com version_history
# Timeline cache armazena apenas o tweet_id → sempre busca a versão atual
# → a "edição" é transparente para o cache de timeline sem invalidação

Timeline cache: tamanho, eviction e cold start

# Tamanho do timeline cache:
# 250M usuários ativos × 800 tweet_ids × 8 bytes = 1,6 TB de memória
# → Redis Cluster com múltiplos shards (ex: 20 shards × 100 GB = 2 TB)
# O tweet_id ocupa 8 bytes (int64 Snowflake) → cache é muito eficiente em memória

# Capping da timeline:
# Manter apenas os 800 tweets mais recentes por usuário
# ZREMRANGEBYRANK timeline:{user_id} 0 -801  # remove o mais antigo quando > 800
# 800 tweets é suficiente para scrolling normal; leituras mais antigas vão ao banco

# Cold start (usuário que não acessa há muitos dias):
# O Redis pode ter evicted o timeline do usuário por pressão de memória
# → ao detectar cache miss de timeline, reconstruir do banco:
def rebuild_timeline(user_id):
    followees = follows_db.get_followees(user_id)
    # Query no banco de tweets para montar o timeline inicial
    recent_tweets = tweets_db.query("""
        SELECT tweet_id, created_at FROM tweets
        WHERE user_id = ANY(:followees)
        ORDER BY created_at DESC LIMIT 800
    """, followees=followees)
    # Populäre o cache Redis
    pipeline = redis.pipeline()
    for tweet in recent_tweets:
        pipeline.zadd(f"timeline:{user_id}", {tweet.tweet_id: tweet.created_at})
    pipeline.execute()
# Cold start tem latência alta (query no banco) mas acontece raramente
# Usuários inativos por > 30 dias: timeline reconstruído sob demanda

Do cronológico ao rankeado

O Twitter original servia tweets em ordem cronológica reversa pura. Em 2016, introduziram o "algorithmic timeline" — tweets rankeados por relevância (engajamento, relação com o usuário, diversidade de conteúdo) em vez de ordem cronológica.

Isso muda o problema de design de forma significativa:

• Timeline cronológica: o sorted set por timestamp é suficiente. Merge é trivial (sort por score).
• Timeline rankeada: é necessário um score de relevância para cada tweet em cada timeline — que depende do usuário específico. Um tweet pode ter score alto no timeline de A e score baixo no de B, dependendo de sua relação com o autor e histórico de engajamento.

# Para timeline rankeada:
# O fan-out service não pode pré-computar o score por usuário de forma eficiente
# Approach do Twitter (2016+): candidatos + ranking em duas etapas

# Etapa 1 — Geração de candidatos (retrieval):
# Buscar os últimos 800 tweets do feed pré-computado (fan-out on write/read híbrido)
# Este conjunto é a lista de candidatos

# Etapa 2 — Ranking (scoring):
# Para cada candidato, calcular um score usando ML model:
#   features: engagement_rate_of_tweet, relation_strength(user, author),
#             recency, topic_affinity, ...
# Ordenar por score descendente → timeline rankeado

# Custo adicional: 80k reads/s × 800 candidatos × ML inference ≈ enorme
# Solução: modelo de ML leve (linear model ou shallow tree) para o ranking inicial
#          + heavy model só para os top candidatos (reranking)
# Caching do scoring: scores de tweets populares são pré-computados e cacheados

Arquitetura completa

Usuário → API Gateway → Tweet Service
                              ↓
                        Tweet Store (persistência)
                        ├── Cassandra / Manhattan (tweets, particionado por user_id)
                        └── Redis (tweet content cache, tweet_id → serialized tweet)

                              ↓ evento publicado
                        Fan-out Queue (Kafka)
                              ↓
                        Fan-out Service
                        ├── Consulta Follow Graph Service → lista de seguidores
                        ├── Filtra celebridades (acima do threshold)
                        └── ZADD em Redis Cluster (timeline:{follower_id})

Timeline Read (home timeline):
  App Server:
  ├── ZREVRANGE timeline:{user_id} → tweet_ids (fan-out on write)
  ├── Para cada celeb seguida: ZREVRANGE user_tweets:{celeb_id} → tweet_ids
  ├── Merge + sort por Snowflake ID (≈ timestamp sort)
  ├── MGET tweet:{id} para os top-50 tweet_ids selecionados
  └── [opcional] Ranking ML nos candidatos antes de selecionar top-50

Follow Graph Service:
  ├── Storage: banco dedicado particionado por followee_id
  ├── Cache Redis: followees(user_id), celebrity_follows(user_id)
  └── API: get_followers(user_id), get_followees(user_id), is_celebrity(user_id)

Decisões de engenharia

Perguntas de entrevista

Exercícios práticos