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

Requisitos não funcionais

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.

GrandezaCálculoResultado
Leituras do feed100 M × 10 por dia ÷ 86 400 scerca de 11 600 por segundo em média, talvez 35 000 no pico (3× a média)
Posts novos100 M × 0,5 ÷ 86 400 scerca de 580 por segundo
Escritas em timelines se cada post é copiado para os seguidores (push)580/s × 40 seguidorescerca de 23 000 por segundo
Escritas em timelines para uma conta com 50 M de seguidoresum post50 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:

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çãoResultado
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 entradas81 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 trimo tamanho continua 800, as entradas mais antigas são descartadas
Paginação por cursor com (idpá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:

EntradasSorted set (ZADD)Lista de ids (RPUSH)Uma string binária (8 bytes por id)
1283 120 B (24 por entrada, listpack compacto)1 664 B (13 por entrada)1 328 B (10 por entrada)
12915 216 B (118 por entrada, skiplist)1 664 B1 328 B
20025 560 B (128 por entrada)2 176 B (11 por entrada)1 840 B (9 por entrada)
80087 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?

LayoutO que dáO que custa
Sorted setAdicionar 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
ListaCerca de 10 bytes por entrada; push na cabeça e trim (LPUSH + LTRIM) são baratosUm 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áriaA menor; uma leitura traz tudoToda 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 conta39,6
Mediana de seguidores9
Maior conta500 000 seguidores
Parcela de todas as relações de seguir mantida pelo 1% de contas do topo54%
Escritas diárias em timelines com push purocerca de 19,8 milhões
Leituras diárias de listas de seguidos com pull purocerca de 396 milhões
Um post da maior conta, com push500 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 deContas em pullEscritas diárias de push (contra o push total)Listas de celebridades mescladas por abertura de feed
1 000 seguidores2 92611,1 M (56%)cerca de 17
10 000 seguidores23914,4 M (73%)cerca de 10,8
100 000 seguidores1917,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:

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áginaOFFSETCursor keyset
10,26 ms0,26 ms
1000,47 ms0,16 ms
1 0003,52 ms0,17 ms
10 00031,88 ms0,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:

  1. 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.
  2. 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).
  3. 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:

  1. 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.
  2. 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:

8. Sharding e cache

9. Atualizações em tempo real

Como um feed mostra posts novos sem recarregar?

10. Exclusões, edições e privacidade

11. Confiabilidade e operação

12. Erros comuns

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

Resumo rápido

  1. Um feed é uma visão derivada dos posts e do grafo de seguidores; pode ser reconstruído.
  2. 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.
  3. 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.
  4. 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).
  5. Use paginação keyset (por cursor): tempo constante em qualquer profundidade e estável enquanto chegam posts novos.
  6. Faça o fan-out de forma assíncrona a partir de uma fila com escritas idempotentes e pule os usuários inativos.
  7. Aplique exclusões, bloqueios e privacidade na hora da leitura.
  8. 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

  1. Markus Winand, Use The Index, Luke: paging through results without OFFSET (the seek method). Por que o OFFSET fica mais lento e como a paginação keyset o evita.
  2. 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.
  3. Documentação do Redis, Sorted sets e os comandos ZADD, ZREVRANGEBYSCORE, ZREMRANGEBYRANK.
  4. 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.
  5. Documentação do PostgreSQL, LIMIT and OFFSET e row-wise comparison (usada pela consulta keyset).
  6. 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.
  7. 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

Mais guias