CS Fundamentals Trainer · Guias

Projetando um sistema de chat

Um projeto desenvolvido com números: conexões persistentes, números de sequência por conversa para ordenação, entrega idempotente, fan-out na escrita contra na leitura, presença, sincronização offline e grupos muito grandes.

39 min de leitura

"Projete um sistema de chat" é uma das perguntas de system design mais comuns, porque toca em quase tudo ao mesmo tempo: conexões de longa duração, ordenação em um sistema distribuído, garantias de entrega sobre redes que perdem mensagens, armazenamento com uma taxa de escrita muito alta, fan-out para grupos, presença e usuários offline. É útil praticá-la como um exemplo desenvolvido, com números. Este guia projeta um serviço de chat passo a passo e mede as partes fáceis de errar: quão ruim é ordenar pelo relógio do remetente, quanto custa armazenar os dois projetos de fan-out e quanta memória é preciso para manter uma conexão aberta. Os scripts estão no apêndice.

É um estudo de caso no estilo de projetando um news feed, e usa ideias de outros guias, incluindo filas de mensagens e consistent hashing: balanceamento de carga e DNS e HTTP para a frente, replicação e sharding e motores de armazenamento para o armazenamento, consenso e tempo para a ordenação, resiliência para os retries e cargas de séries temporais para o caminho de escrita.

Leia isto primeiro: a criptografia de ponta a ponta muda o projeto, e tem limites. Este guia projeta um serviço de chat em que o servidor pode ler as mensagens (elas são criptografadas em trânsito e em repouso, mas o serviço guarda as chaves). É isso que torna simples a busca no servidor, as verificações de spam e abuso, o histórico em um dispositivo novo e a recuperação de mensagens. Com a criptografia de ponta a ponta (E2EE), os servidores guardam apenas texto cifrado que não conseguem ler, e cada um desses recursos fica mais difícil ou impossível; a seção 9.1 mostra as consequências com um modelo pequeno. A E2EE também não esconde os metadados (quem fala com quem, quando, quanto), não protege um celular comprometido e depende de os usuários verificarem as chaves uns dos outros. Se o seu produto promete privacidade, decida isto antes do resto, porque muda armazenamento, busca, sincronização, backup e moderação.

1. Requisitos primeiro

Antes de desenhar caixas, combine o que o sistema deve fazer. Para este projeto:

Fora do escopo aqui: chamadas de voz e vídeo, busca e bots. A criptografia de ponta a ponta não está embutida neste projeto, mas as suas consequências são importantes o bastante para ter uma caixa no topo e a seção 9.1.

2. Um tamanho aproximado

As estimativas guiam o projeto; não precisam ser exatas. Suponha 50 milhões de usuários diários enviando 40 mensagens cada:

GrandezaCálculoResultado
mensagens por dia50 M × 402 bilhões
mensagens por segundo, em média2 × 10⁹ / 86 400cerca de 23 000
no pico diário (suponha 3 vezes a média)cerca de 70 000 por segundo
armazenamento por dia2 × 10⁹ × 100 bytes200 GB, ou cerca de 73 TB por ano antes da replicação
conexões simultâneassuponha 20% dos usuários online10 milhões

Duas coisas se destacam. A carga é pesada em escrita e somente de acréscimo (append-only): uma mensagem é escrita uma vez, raramente alterada e lida algumas vezes. E 10 milhões de conexões abertas simultâneas é a parte incomum para um sistema web, já que um serviço comum de requisição/resposta mantém uma conexão por milissegundos, enquanto um gateway de chat mantém cada uma por horas.

3. A arquitetura

Diagram: The main components of a chat system

Por que uma conexão persistente? O servidor precisa conseguir empurrar uma mensagem no momento em que ela chega. Com polling HTTP a cada poucos segundos, a latência é metade do intervalo em média e a maioria das requisições não encontra nada. O long polling, os server-sent events e os WebSockets mantêm um canal aberto; os WebSockets são a escolha usual para tráfego nos dois sentidos. Os clientes precisam reconectar automaticamente com atrasos aleatórios e crescentes, senão a reinicialização de um gateway faz 100 000 clientes reconectarem no mesmo segundo (tempestades de retries).

Diagram: Sending a message from Alice to Bob

4. Ordenação: quem decide o que veio primeiro?

Todos em uma conversa precisam ver as mensagens na mesma ordem, e as respostas devem vir depois das mensagens que respondem. A resposta tentadora é usar a hora que o celular do remetente pôs na mensagem. Simulei 2 000 mensagens de cinco pessoas cujos relógios de celular estão errados em até cerca de dois segundos (os deslocamentos aqui variaram de −0,2 a +1,7 s), em que cada mensagem é uma resposta à anterior:

Regra de ordenaçãoMensagens adjacentes mostradas na ordem errada
o relógio do remetente389 de 2 000 (19%)
a hora em que o servidor as recebeu131 (6,5%): mensagens enviadas com poucas centenas de milissegundos de diferença podem se trocar no caminho
um número de sequência atribuído pelo servidor na chegadaa mesma ordem em todos os clientes, sempre (por construção)

Os relógios de máquinas diferentes discordam, e nada os faz concordar exatamente (consenso e tempo, o artigo clássico de Lamport sobre a ordenação de eventos). O que os usuários precisam não é da ordem "verdadeira", que não existe quando duas pessoas digitam no mesmo instante, mas de uma ordem combinada. Por isso o projeto dá a cada conversa um único sequenciador: todas as mensagens de uma conversa vão para o mesmo shard do serviço de chat (particionado pelo id da conversa), que carimba cada uma com o próximo número (1, 2, 3, …) ao armazená-la. Os clientes exibem as mensagens ordenadas por esse número e mostram a própria mensagem recém-digitada de forma provisória, em cinza, até o número voltar. O número de sequência dá uma ordem, não uma garantia de entrega (a seção 5.1 mostra por quê e o que a completa). Depois, ele ajuda no resto:

A sequência é por conversa, não global: um contador global seria um gargalo e não seria necessário, já que mensagens de conversas diferentes não são comparadas. Como um shard é dono de uma conversa, o seu failover deve ser tratado com cuidado (um novo dono precisa continuar do maior número armazenado; veja eleição de líder).

5. Entrega: pelo menos uma vez, tornada exatamente uma vez

As redes perdem pacotes e as conexões caem no meio de uma mensagem. Um remetente que não recebe uma confirmação não pode saber se a mensagem chegou: ela pode ter se perdido na ida, ou a confirmação pode ter se perdido na volta. A única política segura é repetir até ser confirmado, o que significa que o servidor pode receber a mesma mensagem duas vezes. Isso é a entrega at-least-once; a forma de obter o efeito de exactly-once é a idempotência: o cliente dá a cada mensagem um id de mensagem do cliente único (um UUID gerado no dispositivo), e o servidor lembra os ids que já viu para a conversa, de modo que uma repetição seja reconhecida, não armazenada de novo e respondida com o número de sequência original. Percorra, depois ligue a confirmação perdida:

Interactive animation: chat delivery

Com a confirmação perdida, a mensagem foi enviada duas vezes, mas armazenada uma e mostrada ao destinatário uma, porque a segunda chegada foi reconhecida pelo seu id. A verificação de duplicatas pode ser uma restrição de unicidade em (conversa, id de mensagem do cliente) no armazenamento (idempotência em transações distribuídas), de modo que está correta mesmo se duas tentativas chegarem a servidores diferentes ao mesmo tempo.

O mesmo vale na saída: o servidor empurra uma mensagem para o Bob e espera a confirmação do cliente dele; se ela não vem, empurra de novo, e o cliente do Bob ignora números de sequência que já tem.

As confirmações (receipts) são pequenas mensagens à parte. "Enviada" é a confirmação do servidor; "entregue" é a confirmação do dispositivo do destinatário; "lida" é enviada quando o usuário abre a conversa e pode ser reduzida a um número ("lido até a seq N"). Em grupos grandes as confirmações por pessoa são caras e muitas vezes descartadas ou agregadas.

5.1 Uma mensagem, de ponta a ponta: confirmação, reconexão, reenvio e deduplicação

Um número de sequência é um dispositivo de ordenação, não uma garantia de entrega. Ele diz a todos como ordenar as mensagens que existem e permite que um cliente perceba um buraco abaixo do maior número que já viu. Ele não faz uma mensagem chegar: se a última mensagem de uma rajada se perde a caminho de um destinatário, esse destinatário não tem um número posterior para comparar e não tem como saber que algo falta. A entrega vem da combinação de quatro mecanismos, e cada um corrige algo que os outros não corrigem:

MecanismoCorrigeNão corrige
Número de sequência (por conversa)a ordem; buracos abaixo do maior número recebidouma última mensagem perdida; uma mensagem perdida para um dispositivo que estava offline
Confirmação e nova tentativa pelo remetenteum envio ou push que se perdeuduplicatas: uma confirmação perdida faz o remetente enviar de novo
Deduplicação (id de mensagem do cliente, único por conversa)duplicatas de novas tentativas, mesmo entre servidoresperdas
Sincronização ao reconectar e um "o meu último é N" periódico vindo do servidoro final perdido; o período offline; um buraco que nunca foi percebidonada por si só, pois exige que o armazenamento seja a verdade

O fluxo de uma conversa, com as falhas que a rede pode produzir:

  1. O cliente de Alice cria a mensagem A2 com um id de cliente novo e a envia; o servidor a armazena como seq 2, faz o push para Bob e devolve a confirmação, que se perde.
  2. O cliente de Alice estoura o tempo e tenta de novo com o mesmo id de cliente. O servidor encontra o id na sua tabela, não armazena nada novo e responde seq 2 outra vez. Este é o passo de deduplicação.
  3. O push da mensagem seguinte, seq 3, se perde a caminho de Bob. Bob tem 1 e 2 e não tem como saber que o 3 existe.
  4. Alice envia seq 4. Bob a recebe, vê que o seu maior número é 4 e que o 3 falta, e pede o buraco (fetch after 2). O servidor reenvia 3 e 4; Bob já tem o 4 e o ignora.
  5. Bob fica offline; seq 5 e seq 6 são armazenadas e o push falha. Quando Bob reconecta, envia sync after 4 (o maior número que tem), e o servidor reenvia 5 e 6.
  6. Se a última mensagem da conversa tivesse sido a perdida, só o mecanismo do passo 5 a encontraria: o cliente precisa perguntar ao reconectar, e uma conexão de longa duração deve carregar uma mensagem periódica do servidor com o último número, para que uma perda silenciosa no final seja percebida em segundos.

Para verificar que cada camada é necessária, simulei 1.000 conversas de cinco mensagens (5.000 mensagens) em que cada envio, push e confirmação pode se perder de forma independente, adicionando um mecanismo de cada vez (flow.py; no máximo 8 tentativas por mensagem):

ProjetoTaxa de perdaNunca armazenadasArmazenadas duas vezesArmazenadas, mas ausentes no destinatárioMostradas duas vezes
1. só números de sequência5%25802340
2. + novas tentativas do remetente5%0258242234
3. + deduplicação5%002420
4. + buscar os buracos que percebe5%00550
5. + sincronização ao reconectar / "o último é N"5%0000
1. só números de sequência20%99007970
2. + novas tentativas do remetente20%01.311845873
3. + deduplicação20%008450
4. + buscar os buracos que percebe20%002080
5. + sincronização ao reconectar / "o último é N"20%0000

As novas tentativas curaram os envios perdidos e criaram duplicatas; a deduplicação removeu as duplicatas; a detecção de buracos corrigiu a maior parte das mensagens ausentes, mas ainda deixou algumas (55 e 208), todas elas finais que nenhum número posterior poderia revelar; só a sincronização por pull fechou o resto. A simulação modela a lógica e não uma rede real: a perda é independente, não há reordenação e o sequenciador nunca falha. A falha do sequenciador é outro problema: um novo responsável precisa continuar acima do maior número armazenado, ou duas mensagens recebem o mesmo seq (veja a seção 4). Note também o que "exatamente uma vez" significa aqui: o remetente pode transmitir muitas vezes, o armazenamento guarda a mensagem uma vez e a tela do destinatário a mostra uma vez, porque o efeito é tornado idempotente. A rede não a entrega uma vez só.

6. Armazenamento e fan-out

Como uma mensagem de grupo deve ser armazenada? Há dois projetos:

Medi o lado do armazenamento no PostgreSQL enviando 2 000 mensagens a um grupo:

Tamanho do grupoCópia para cada membro: linhas, tempo, tamanhoArmazenar uma vez + cursores: linhas, tempo, tamanho
24 000 linhas, 0,01 s, 0,5 MB2 002 linhas, 0,00 s, 0,3 MB
1020 000 linhas, 0,04 s, 2,4 MB2 010 linhas, 0,00 s, 0,3 MB
100200 000 linhas, 0,42 s, 24 MB2 100 linhas, 0,01 s, 0,3 MB
1 0002 000 000 linhas, 4,7 s, 238 MB3 000 linhas, 0,01 s, 0,4 MB

(Os 1 000 cursores do segundo projeto são escritos uma vez, quando os membros entram, e não a cada mensagem; um cursor só é atualizado quando o seu dono lê.) O custo da cópia cresce em proporção ao tamanho do grupo, com cerca de 600 vezes mais armazenamento e várias centenas de vezes mais tempo de escrita para um grupo de 1 000, e uma mensagem em um grupo movimentado viraria milhares de escritas que precisam todas ser replicadas. Armazenar uma vez é plano. É por isso que os sistemas reais guardam um log da conversa e ponteiros por usuário.

O projeto de cópia por membro ainda tem o seu lugar: para chats um a um (fan-out de 2) ele simplifica o modelo, e para feeds de notificações você quer a lista por usuário pré-calculada. Muitos sistemas usam um híbrido: escrevem uma vez no log e fazem o fan-out apenas de uma pequena notificação (id da conversa, número de sequência, contagem de não lidas) para o gateway online ou token de push de cada membro. Essa pequena notificação é o que escala com o tamanho do grupo, e é barata e efêmera.

Escolhendo o armazenamento

O log de mensagens é escrito constantemente, quase nunca atualizado e lido por (conversa, faixa de sequência): sobretudo as mensagens recentes, as mais antigas quando se rola a tela. Isso combina com um armazenamento wide-column ou log-structured (LSM trees) como Cassandra, ScyllaDB ou HBase, particionado por conversa e dividido em baldes de tempo para que nenhuma partição cresça sem limite; os posts de engenharia do Discord descrevem exatamente isso. Um banco de dados relacional com particionamento (sharding) funciona bem em escala menor. Seja qual for a escolha, a chave é (id da conversa, número de sequência): os dados de uma conversa ficam juntos no disco, e uma página de histórico é uma leitura contígua. As mensagens recentes quentes podem ficar em cache (cache).

7. Conexões, roteamento e sincronização offline

O que custa manter uma conexão

Escrevi um servidor em Go que aceita conexões, uma goroutine cada uma com um buffer de 4 KB, e as deixa ociosas, e medi sua memória residente com 1 000, 5 000 e 15 000 clientes conectados:

Conexões ociosasMemória do servidorPor conexão
1 0009 MB5,2 KB
5 00027 MB4,7 KB
15 00073 MB4,8 KB

Cerca de 5 KB cada uma, em memória do processo, com conexões ociosas quase sem custo de CPU. Então 10 milhões de conexões precisam de pelo menos 48 GB de memória entre os gateways só para as conexões nuas, e com estado de TLS, buffers de WebSocket e dados por usuário em memória é várias vezes isso. Se um servidor segura confortavelmente 100 000 conexões, 10 milhões de usuários simultâneos precisam de cerca de 100 servidores de gateway mais folga. Isso é um limite inferior; os limites reais são o sistema operacional (descritores de arquivo, buffers do kernel), a carga dos heartbeats e a rajada quando milhares reconectam juntos. Também mostra por que os gateways devem ser finos e sem estado sobre as conversas: quando um morre, apenas suas conexões se perdem, e os clientes reconectam a outro.

Achando o destinatário

Os workers de entrega precisam saber qual gateway segura a conexão do Bob. O registro de sessões mapeia usuário → gateway (e dispositivo), escrito quando um cliente conecta e removido ao desconectar ou expirar. Um usuário pode ter vários dispositivos, então uma mensagem é entregue a todos eles. Se o Bob não tem conexão, o worker envia uma notificação push (APNs, FCM) pelo provedor da plataforma, e a mensagem espera no armazenamento. Alternativamente, canais de publish/subscribe por usuário ou por conversa deixam os gateways assinarem o que seus usuários conectados precisam, o que evita uma consulta ao custo de muitas assinaturas.

Sincronização offline e multidispositivo

O armazenamento é a verdade, e as conexões são uma otimização. Quando um dispositivo conecta, envia, por conversa, o maior número de sequência que tem; o servidor responde com tudo que é mais novo (ou com um sinal de "são muitas, busque em páginas"). O mesmo mecanismo cobre um celular novo, uma reconexão depois de um túnel e uma lacuna detectada no fluxo ao vivo. É por isso que um projeto que depende de as conexões nunca perderem nada é frágil, e um que trata a conexão como um caminho rápido sobre uma sincronização por pull é robusto.

8. Presença, digitação e grupos muito grandes

A presença ("online", "visto por último") parece simples e é cara se feita de forma ingênua. O método usual é um heartbeat: enquanto conectado, o cliente dá um ping a cada 20 a 30 segundos, e o armazenamento de presença mantém uma chave por usuário com uma expiração curta (cerca de 1,5 a 2 heartbeats), renovada a cada ping. Se os pings param, a chave expira e o usuário fica "offline", sem precisar que a desconexão seja percebida. Notificar os contatos é a parte cara: se cada mudança de status fosse empurrada para todos que têm você como contato, um usuário com 500 contatos que oscila entre wifi e dados móveis gera milhares de mensagens. Então a presença é buscada quando necessária (quando uma lista de contatos ou uma conversa é aberta) e empurrada apenas para os usuários que estão olhando para você agora, com um atraso ou "debounce" para desconexões breves.

Os indicadores de digitação e sinais parecidos são efêmeros: são enviados pela conexão ao vivo, não armazenados, e podem se perder sem dano. Marque-os assim no protocolo para que o sistema não lhes dê a maquinaria (armazenamento, retries) de que as mensagens precisam.

Grupos muito grandes (um canal com 100 000 membros) quebram o modelo. As confirmações por membro e as notificações por membro são demais. Os sistemas mudam as regras: sem confirmações de leitura, notificar só quando há menção, entregar apenas aos membros que estão online e olhando o canal e buscar o resto sob demanda. Um canal de broadcast com um milhão de leitores é mais um sistema de publish/subscribe com cache na borda do que um chat.

9. Escala, falha e o resto

9.1 Criptografia de ponta a ponta e limites com vários dispositivos

Em um projeto com E2EE, o dispositivo do remetente criptografa para cada dispositivo destinatário, não para cada usuário, e o servidor apenas roteia e armazena o texto cifrado. Construí um modelo pequeno da estrutura com acordo de chaves X25519 e AES-GCM (e2ee_model.py, usando o pacote Python cryptography). É um modelo simplificado da estrutura, não o protocolo Signal: não tem ratchet, nem sigilo futuro, nem verificação de chaves, e não deve ser usado para mensagens reais. Ele mostra cinco consequências que valem também para sistemas reais:

ConsequênciaNo modeloO que os produtos fazem a respeito
Um texto cifrado por dispositivouma mensagem para um grupo de 3 usuários com 1 dispositivo cada armazenou 3 textos cifrados; depois de Bob adicionar um notebook, a mensagem seguinte armazenou 4. Cada cópia tem 83 bytes para uma mensagem de 23 bytesas mensagens de grupo custam armazenamento e upload por dispositivo de cada membro; grupos grandes usam "sender keys" compartilhadas, que enfraquecem algumas garantias
O servidor não pode buscar nem filtraruma busca por uma palavra em tudo o que o servidor guarda encontrou 0 resultadosa busca roda no dispositivo, sobre o seu histórico local; denúncias de spam e abuso dependem de os usuários encaminharem o texto em claro, ou de verificações no dispositivo
Um dispositivo novo não lê mensagens antigaso notebook novo de Bob não conseguiu decifrar uma mensagem enviada antes de ele existir (a autenticação falhou) e leu a seguinteo histórico precisa de uma transferência entre dispositivos, ou de um backup criptografado; "sincronizar entre dispositivos" deixa de ser uma simples leitura de banco de dados
Perder o único dispositivo perde o históricoo celular perdido tinha a única chave das mensagens antigasbackups sob uma chave ou frase-senha do usuário; se o provedor puder recuperar a chave, o sistema não é de ponta a ponta para esses dados
Os metadados continuam visíveiso servidor ainda via remetente, dispositivos destinatários, conversa, número de sequência, tamanho e horáriominimize-os e faça-os expirar; o sealed sender e técnicas semelhantes reduzem, mas não removem, o que o servidor aprende

Dois limites passam facilmente despercebidos. Primeiro, vários dispositivos significam várias chaves: cada dispositivo vinculado é mais um lugar onde as mensagens podem ser lidas, de modo que vincular um dispositivo é uma ação crítica para a segurança, e um "cliente web" que baixa o seu código do servidor pode ser alterado pelo servidor para vazar texto em claro. Segundo, a E2EE protege as mensagens em trânsito e no servidor, não no dispositivo final: notificações, backups em uma conta na nuvem, capturas de tela e malware no celular ficam fora dela. Informe esses limites aos usuários, dentro do produto, com a mesma clareza da garantia. Para a criptografia em si, use um protocolo e uma biblioteca já verificados (o protocolo Signal ou o MLS), não um projeto próprio.

10. Erros comuns

11. Coisas a mencionar em uma entrevista

Resumo rápido

Apêndice: o código dos experimentos

Quatro arquivos. O order.py (biblioteca padrão do Python) simula 2 000 mensagens de cinco pessoas cujos relógios de celular estão errados em até cerca de dois segundos; a ordem verdadeira é conhecida, então os pares errados podem ser contados. O fanout.sql precisa de um servidor PostgreSQL 16 descartável e compara duas formas de armazenar uma mensagem de grupo para 2, 10, 100 e 1 000 membros. O server.go e o client.go (Go 1.24) seguram até 15 000 conexões TCP ociosas entre dois processos em uma máquina e relatam a memória residente do servidor por conexão. As conexões são TCP simples, uma goroutine e um buffer de leitura de 4 KB cada: um gateway real acrescenta o enquadramento WebSocket, o estado de TLS e dados da aplicação, então trate o número como um limite inferior, não um plano de capacidade. A simulação de ordenação usa números aleatórios com uma semente fixa. Os tempos do banco de dados são execuções únicas em uma pequena máquina virtual. As estimativas de capacidade da seção 2 são aritmética sobre entradas supostas, não medições de um serviço real.

order.py: ordenando mensagens por relógios do cliente, chegada ou um número de sequência

"""Ordering messages in a conversation: client clocks against a server-assigned sequence number."""
import random
r = random.Random(11)

# Five people in a chat, each with a phone clock that is wrong by up to +/- 2 seconds.
skew = {u: r.uniform(-2.0, 2.0) for u in "ABCDE"}
# A real conversation in which each message is a reply to the previous one: the true order is 0, 1, 2, ...
true_time, msgs = 0.0, []
for i in range(2000):
    true_time += r.expovariate(1 / 0.8)                    # a reply every 0.8 s on average
    sender = r.choice("ABCDE")
    msgs.append({"id": i, "sender": sender, "true": true_time, "client_ts": true_time + skew[sender]})

def wrong_pairs(order):
    """Adjacent messages whose displayed order differs from the true order (replies shown before the message they answer)."""
    return sum(1 for a, b in zip(order, order[1:]) if a["id"] > b["id"])

by_client = sorted(msgs, key=lambda m: m["client_ts"])
print(f"messages: {len(msgs)}, phone clocks off by {min(skew.values()):+.1f} to {max(skew.values()):+.1f} s")
print(f"sorted by the sender's clock: {wrong_pairs(by_client)} adjacent pairs shown in the wrong order ({wrong_pairs(by_client)/len(msgs)*100:.0f}% of messages)")

# The server receives messages over networks with random delay (20 to 400 ms), so arrival order is not true order either.
arrival = sorted(msgs, key=lambda m: m["true"] + r.uniform(0.02, 0.4))
print(f"sorted by server arrival time: {wrong_pairs(arrival)} pairs wrong (messages sent within a few hundred ms of each other can swap)")
# ...but what matters is that everybody sees the same order. The server assigns a sequence number as messages arrive:
seq = {m["id"]: n for n, m in enumerate(arrival)}
view = {u: sorted(msgs, key=lambda m: seq[m["id"]]) for u in "ABCDE"}
print("every client sorting by the server's sequence number sees the same order:", all([m["id"] for m in view[u]] == [m["id"] for m in view["A"]] for u in "ABCDE"))

fanout.sql: copiar para todo membro contra armazenar uma vez com cursores de leitura

-- Group chat storage: copy each message into every member's inbox (fan-out on write),
-- or store it once in the conversation and give each member a read cursor (fan-out on read).
-- Sends 2,000 messages to a group of N members, for several N.
\timing off
CREATE TEMP TABLE results (design text, members int, seconds numeric, rows_written bigint, size_mb numeric);
DO $$
DECLARE n int; t0 timestamptz; sz bigint; rows bigint;
BEGIN
  FOREACH n IN ARRAY ARRAY[2, 10, 100, 1000] LOOP
    -- design A: one row per message per recipient
    DROP TABLE IF EXISTS inbox; CREATE TABLE inbox (user_id int, conv_id int, seq int, body text, PRIMARY KEY (user_id, conv_id, seq));
    t0 := clock_timestamp();
    INSERT INTO inbox SELECT u, 1, s, 'hello, this is a chat message of average length' FROM generate_series(1, n) u, generate_series(1, 2000) s;
    GET DIAGNOSTICS rows = ROW_COUNT; sz := pg_total_relation_size('inbox');
    INSERT INTO results VALUES ('copy to each member', n, extract(epoch FROM clock_timestamp() - t0), rows, sz / 1048576.0);
    -- design B: one row per message, plus one cursor per member (updated when the member reads, not when a message is sent)
    DROP TABLE IF EXISTS messages, cursors; CREATE TABLE messages (conv_id int, seq int, body text, PRIMARY KEY (conv_id, seq)); CREATE TABLE cursors (user_id int, conv_id int, last_read int, PRIMARY KEY (user_id, conv_id));
    t0 := clock_timestamp();
    INSERT INTO messages SELECT 1, s, 'hello, this is a chat message of average length' FROM generate_series(1, 2000) s;
    GET DIAGNOSTICS rows = ROW_COUNT;
    INSERT INTO cursors SELECT u, 1, 0 FROM generate_series(1, n) u;
    INSERT INTO results VALUES ('store once + read cursors', n, extract(epoch FROM clock_timestamp() - t0), rows + n, (pg_total_relation_size('messages') + pg_total_relation_size('cursors')) / 1048576.0);
  END LOOP;
END $$;
SELECT design, members, round(seconds, 2) AS seconds, rows_written, round(size_mb, 1) AS size_mb FROM results ORDER BY members, design;

server.go: memória usada por conexões ociosas

// server.go: holds N idle connections, one goroutine each (like a chat gateway holding WebSockets), and prints its memory use.
package main

import (
	"bufio"
	"fmt"
	"net"
	"os"
	"runtime"
	"strconv"
	"time"
)

func rss() int { // resident memory in KB, from /proc
	b, _ := os.ReadFile("/proc/self/status")
	var kb int
	for _, l := range splitLines(string(b)) {
		if len(l) > 6 && l[:6] == "VmRSS:" {
			fmt.Sscanf(l[6:], "%d", &kb)
		}
	}
	return kb
}
func splitLines(s string) (out []string) {
	start := 0
	for i := range s {
		if s[i] == '\n' {
			out = append(out, s[start:i])
			start = i + 1
		}
	}
	return
}

func main() {
	want, _ := strconv.Atoi(os.Args[1])
	ln, _ := net.Listen("tcp", "127.0.0.1:9100")
	base := rss()
	count := 0
	done := make(chan struct{})
	for {
		c, err := ln.Accept()
		if err != nil {
			panic(err)
		}
		count++
		go func(c net.Conn) { // one goroutine per connection, blocked waiting for the next message
			r := bufio.NewReader(c)
			r.ReadByte()
		}(c)
		if count == want {
			time.Sleep(500 * time.Millisecond)
			runtime.GC()
			after := rss()
			fmt.Printf("server: %d idle connections, %d goroutines, resident memory %d MB (%.1f KB per connection, before any: %d MB)\n",
				count, runtime.NumGoroutine(), after/1024, float64(after-base)/float64(count), base/1024)
			close(done)
			break
		}
	}
	<-done
}

client.go: abre as conexões para o teste do servidor

// client.go: opens N connections to the server and keeps them open.
package main

import (
	"net"
	"os"
	"strconv"
	"time"
)

func main() {
	n, _ := strconv.Atoi(os.Args[1])
	conns := make([]net.Conn, 0, n)
	for i := 0; i < n; i++ {
		c, err := net.Dial("tcp", "127.0.0.1:9100")
		if err != nil {
			panic(err)
		}
		conns = append(conns, c)
	}
	time.Sleep(3 * time.Second)
	_ = conns
}

flow.py: números de sequência, novas tentativas, deduplicação e sincronização, uma camada de cada vez

Apenas a biblioteca padrão do Python; determinístico.

"""End-to-end delivery flow of a chat message: sequence numbers, acks, reconnect, replay, deduplication.
Deterministic, stdlib only. Each layer is switched on in turn so you can see what it adds."""
import random

def simulate(loss, retry, dedup, gap_fetch, heartbeat, seed=1, n=5):
    """One short conversation of n messages (a tail loss only shows up at the end of a conversation)."""
    rnd = random.Random(seed)
    store = {}            # server: seq -> client message id
    seen = {}             # dedup table: client message id -> seq
    next_seq = 1
    have = {}             # recipient: seq -> client message id
    never_stored = 0
    for cid in range(n):
        stored = False
        for attempt in range(8):
            if rnd.random() < loss: 
                if not retry: break
                continue                                      # the send was lost
            if dedup and cid in seen:
                seq = seen[cid]
            else:
                seq = next_seq; next_seq += 1
                store[seq] = cid; seen[cid] = seq
            stored = True
            if rnd.random() >= loss: have[seq] = cid          # push reaches the recipient
            if rnd.random() >= loss: break                    # ack reaches the sender: stop retrying
            if not retry: break
        if not stored: never_stored += 1
    if gap_fetch:                                             # only holes BELOW the highest number received are visible
        top = max(have) if have else 0
        for s in range(1, top + 1):
            if s in store: have[s] = store[s]
    if heartbeat:                                             # the server also says "my latest is N"
        for s in store: have[s] = store[s]
    shown_ids = list(have.values())
    return dict(never_stored=never_stored,
                stored_twice=len(store) - len(set(store.values())),
                missing=len(set(store.values()) - set(shown_ids)),
                shown_twice=len(shown_ids) - len(set(shown_ids)))

def many(loss, **kw):
    tot = dict(never_stored=0, stored_twice=0, missing=0, shown_twice=0)
    for seed in range(1000):
        for k, v in simulate(loss, seed=seed, **kw).items(): tot[k] += v
    return tot

rows = [
 ("1  sequence numbers only (no retry)",                 dict(retry=False, dedup=False, gap_fetch=False, heartbeat=False)),
 ("2  + sender retries until acked",                      dict(retry=True,  dedup=False, gap_fetch=False, heartbeat=False)),
 ("3  + server dedups on client message id",              dict(retry=True,  dedup=True,  gap_fetch=False, heartbeat=False)),
 ("4  + recipient fetches the gaps it notices",           dict(retry=True,  dedup=True,  gap_fetch=True,  heartbeat=False)),
 ("5  + sync on reconnect/heartbeat (latest seq known)",  dict(retry=True,  dedup=True,  gap_fetch=True,  heartbeat=True)),
]
for loss in (0.05, 0.20):
    print(f"\npacket loss {int(loss*100)}% on each of send, push and ack; 1,000 conversations of 5 messages = 5,000 messages")
    print(f"{'design':56s} never_stored stored_twice missing_on_recipient shown_twice")
    for name, kw in rows:
        r = many(loss, **kw)
        print(f"{name:56s} {r['never_stored']:>12} {r['stored_twice']:>12} {r['missing']:>20} {r['shown_twice']:>11}")

# One message, traced: send lost ack, retry, reconnect.
print("\nTrace of one conversation (ack of #2 lost, push of #3 lost, device offline for #4, #5):")
trace = [
 "alice -> server  m=A1 id=a1        server stores seq 1, pushes 1 to bob, acks alice",
 "alice -> server  m=A2 id=a2        server stores seq 2; the ACK is lost on the way back",
 "alice -> server  m=A2 id=a2 (retry) server finds id=a2 already stored -> answers seq 2, stores nothing new",
 "alice -> server  m=A3 id=a3        server stores seq 3; the PUSH to bob is lost",
 "bob receives seq 1, 2. Nothing arrives for 3. Bob cannot know that: he has no later number to compare",
 "alice -> server  m=A4 id=a4        server stores seq 4, pushes; bob now has 1,2,4 and sees the hole at 3",
 "bob -> server    fetch after=2     server replays seq 3, 4 (bob ignores 4: already has it)",
 "bob goes offline; alice sends A5, A6 (seq 5, 6) -> push fails, they stay in the store",
 "bob reconnects: sync after=4       server replays 5, 6; bob's screen now holds 1..6 exactly once",
]
print("\n".join(trace))

e2ee_model.py: um modelo simplificado de criptografia de ponta a ponta por dispositivo

Precisa do pacote Python cryptography. É apenas um modelo da estrutura; não é o protocolo Signal e não serve para uso real.

"""A simplified end-to-end encryption model: ONE ciphertext per recipient DEVICE (X25519 key agreement + HKDF + AES-GCM).
This shows the structural consequences (what the server stores, what a new device can read, what grows).
It is NOT the Signal protocol: no ratchet, no forward secrecy, no authentication of keys. Do not use it for real messages."""
import os
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.exceptions import InvalidTag

def pub(k): return k.public_key().public_bytes(serialization.Encoding.Raw, serialization.PublicFormat.Raw)
def kdf(shared): return HKDF(algorithm=hashes.SHA256(), length=32, salt=None, info=b"chat-demo").derive(shared)

class Device:
    def __init__(self, user, name): self.user, self.name, self.key = user, name, X25519PrivateKey.generate(); self.inbox = {}
    def public(self): return pub(self.key)

def encrypt_for(sender_eph, device, plaintext):
    shared = sender_eph.exchange(__import__("cryptography.hazmat.primitives.asymmetric.x25519", fromlist=["X25519PublicKey"]).X25519PublicKey.from_public_bytes(device.public()))
    nonce = os.urandom(12)
    return pub(sender_eph) + nonce + AESGCM(kdf(shared)).encrypt(nonce, plaintext, None)

def decrypt(device, blob):
    from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PublicKey
    eph, nonce, ct = blob[:32], blob[32:44], blob[44:]
    shared = device.key.exchange(X25519PublicKey.from_public_bytes(eph))
    return AESGCM(kdf(shared)).decrypt(nonce, ct, None)

server_store = []     # what the server keeps: (conversation, seq, device, ciphertext) plus metadata it can see
alice_phone = Device("alice", "phone")
bob_phone, bob_laptop = Device("bob", "phone"), Device("bob", "laptop")
carol_phone = Device("carol", "phone")
members = {"alice": [alice_phone], "bob": [bob_phone], "carol": [carol_phone]}

def send(sender, text, seq):
    eph = X25519PrivateKey.generate()
    n = 0
    for user, devs in members.items():
        for d in devs:                       # one ciphertext per device (including the sender's other devices)
            blob = encrypt_for(eph, d, text.encode())
            server_store.append(dict(conv="g1", seq=seq, sender=sender, to=f"{d.user}/{d.name}", size=len(blob), ct=blob)); n += 1
    return n

print("1. a group of 3 users, 1 device each:  ciphertexts stored for one 23-byte message =", send("alice", "meet at 9, bring slides", 1))
members["bob"].append(bob_laptop)
print("2. bob adds a laptop; a second message: ciphertexts stored =", send("alice", "ok, 9:15 instead", 2))

# what can the server do?
hit = [r for r in server_store if b"slides" in r["ct"]]
print("3. server searches its store for the word 'slides':", len(hit), "matches (it holds only ciphertext)")
print("   but it still sees: sender, recipient devices, conversation, sequence number, size, time -> metadata")

# can the NEW device read the OLD message?
old = [r for r in server_store if r["seq"] == 1 and r["to"] == "bob/phone"][0]["ct"]
try: decrypt(bob_laptop, old); print("4. laptop reads message 1: yes")
except InvalidTag: print("4. bob's new laptop tries to read message 1 (sent before it existed): cannot decrypt -> history needs a device-to-device transfer or a key backup")
new = [r for r in server_store if r["seq"] == 2 and r["to"] == "bob/laptop"][0]["ct"]
print("   laptop reads message 2:", decrypt(bob_laptop, new).decode())

# lost device
members["bob"].remove(bob_phone)
print("5. bob loses his phone: its key was the only copy of message 1 on bob's side ->",
      "history on the server is unreadable without a backup key; if the backup is protected only by the server, E2EE is not end-to-end")
print("6. size: 23-byte message -> ", [r["size"] for r in server_store][:1], "bytes per device copy (32-byte key + 12-byte nonce + 16-byte tag + text)")
print("   total stored for", len({r['seq'] for r in server_store}), "messages:", len(server_store), "copies")

Fontes

Pratique este tema: System Design System Design › Case studies

Mais guias