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:
- Chat um a um e em grupo (grupos de até algumas centenas de membros; canais muito grandes são outro problema, veja a seção 8).
- Mensagens de texto, mais anexos (imagens, arquivos).
- Entrega em tempo real a usuários online, e a usuários offline quando voltarem, mais notificações push.
- Histórico de mensagens que sincroniza entre os dispositivos de um usuário.
- Indicadores de enviada, entregue e lida, e presença ("online", "visto por último").
- Não funcionais: baixa latência (uma mensagem deve aparecer em bem menos de um segundo), nenhuma mensagem perdida, nenhuma duplicata, a mesma ordem para todos em uma conversa, alta disponibilidade e crescimento até centenas de milhões de usuários.
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:
| Grandeza | Cálculo | Resultado |
|---|---|---|
| mensagens por dia | 50 M × 40 | 2 bilhões |
| mensagens por segundo, em média | 2 × 10⁹ / 86 400 | cerca de 23 000 |
| no pico diário (suponha 3 vezes a média) | cerca de 70 000 por segundo | |
| armazenamento por dia | 2 × 10⁹ × 100 bytes | 200 GB, ou cerca de 73 TB por ano antes da replicação |
| conexões simultâneas | suponha 20% dos usuários online | 10 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
- Os gateways mantêm as conexões persistentes (WebSocket, ou um protocolo parecido; o polling HTTP simples é um desperdício, veja abaixo). Fazem pouco: autenticam, mantêm a conexão viva, passam mensagens para dentro e para fora. Mantê-los finos permite escalá-los separadamente e reiniciá-los sem perder dados.
- O serviço de chat não tem estado: valida uma mensagem, atribui o seu lugar na conversa, a armazena e a publica para entrega.
- O armazenamento de mensagens é o sistema de registro. Os workers de entrega leem de uma fila, descobrem onde cada destinatário está conectado pelo registro de sessões e empurram a mensagem para lá; os destinatários offline recebem uma notificação push e buscam o histórico quando voltam.
- Os anexos não viajam pelo caminho do chat: o cliente envia para um armazenamento de objetos (com uma URL assinada de vida curta), e a mensagem carrega apenas um link e metadados. Uma CDN os serve (DNS e CDNs).
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ção | Mensagens adjacentes mostradas na ordem errada |
|---|---|
| o relógio do remetente | 389 de 2 000 (19%) |
| a hora em que o servidor as recebeu | 131 (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 chegada | a 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:
- Detecção de lacunas: um cliente que tem a seq 41 e recebe a seq 43 sabe que perdeu a 42 e a pede.
- Sincronização: um dispositivo que volta diz "tenho até 87", e o servidor envia tudo depois de 87 (seção 7).
- Posição de leitura e confirmações: "lido até 87" é um número pequeno por membro.
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:
| Mecanismo | Corrige | Não corrige |
|---|---|---|
| Número de sequência (por conversa) | a ordem; buracos abaixo do maior número recebido | uma última mensagem perdida; uma mensagem perdida para um dispositivo que estava offline |
| Confirmação e nova tentativa pelo remetente | um envio ou push que se perdeu | duplicatas: 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 servidores | perdas |
| Sincronização ao reconectar e um "o meu último é N" periódico vindo do servidor | o final perdido; o período offline; um buraco que nunca foi percebido | nada por si só, pois exige que o armazenamento seja a verdade |
O fluxo de uma conversa, com as falhas que a rede pode produzir:
- 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. - 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 2outra vez. Este é o passo de deduplicação. - 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. - 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. - Bob fica offline;
seq 5eseq 6são armazenadas e o push falha. Quando Bob reconecta, enviasync after 4(o maior número que tem), e o servidor reenvia 5 e 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):
| Projeto | Taxa de perda | Nunca armazenadas | Armazenadas duas vezes | Armazenadas, mas ausentes no destinatário | Mostradas duas vezes |
|---|---|---|---|---|---|
| 1. só números de sequência | 5% | 258 | 0 | 234 | 0 |
| 2. + novas tentativas do remetente | 5% | 0 | 258 | 242 | 234 |
| 3. + deduplicação | 5% | 0 | 0 | 242 | 0 |
| 4. + buscar os buracos que percebe | 5% | 0 | 0 | 55 | 0 |
| 5. + sincronização ao reconectar / "o último é N" | 5% | 0 | 0 | 0 | 0 |
| 1. só números de sequência | 20% | 990 | 0 | 797 | 0 |
| 2. + novas tentativas do remetente | 20% | 0 | 1.311 | 845 | 873 |
| 3. + deduplicação | 20% | 0 | 0 | 845 | 0 |
| 4. + buscar os buracos que percebe | 20% | 0 | 0 | 208 | 0 |
| 5. + sincronização ao reconectar / "o último é N" | 20% | 0 | 0 | 0 | 0 |
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:
- Fan-out na escrita: quando uma mensagem é enviada, escreva uma cópia na caixa de entrada de cada membro. Ler é trivial (tudo para mim está em um só lugar), escrever é multiplicado pelo tamanho do grupo.
- Fan-out na leitura (armazenar uma vez): escreva a mensagem uma vez no log da conversa e dê a cada membro um cursor (seu último número de sequência lido). O cliente de um membro lê, dos logs, as conversas de que faz parte. O custo da escrita é o mesmo qualquer que seja o tamanho do grupo.
Medi o lado do armazenamento no PostgreSQL enviando 2 000 mensagens a um grupo:
| Tamanho do grupo | Cópia para cada membro: linhas, tempo, tamanho | Armazenar uma vez + cursores: linhas, tempo, tamanho |
|---|---|---|
| 2 | 4 000 linhas, 0,01 s, 0,5 MB | 2 002 linhas, 0,00 s, 0,3 MB |
| 10 | 20 000 linhas, 0,04 s, 2,4 MB | 2 010 linhas, 0,00 s, 0,3 MB |
| 100 | 200 000 linhas, 0,42 s, 24 MB | 2 100 linhas, 0,01 s, 0,3 MB |
| 1 000 | 2 000 000 linhas, 4,7 s, 238 MB | 3 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 ociosas | Memória do servidor | Por conexão |
|---|---|---|
| 1 000 | 9 MB | 5,2 KB |
| 5 000 | 27 MB | 4,7 KB |
| 15 000 | 73 MB | 4,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
- Particione pelo id da conversa em todo o caminho de escrita (serviço de chat, armazenamento, sequenciador), para que o trabalho de uma conversa fique em um shard, e adicione shards conforme os números crescem, com hashing consistente ou um diretório, para evitar movimentação em massa (particionamento).
- Replique o armazenamento entre zonas e escreva em um quórum, para que uma mensagem confirmada sobreviva à falha de uma máquina. A confirmação ao remetente deve vir depois de a mensagem estar armazenada de forma durável; essa é a promessa "se você vê enviado, não será perdida".
- Um gateway ou uma região falha: os clientes reconectam (com backoff com jitter) e sincronizam a partir do último número de sequência que têm.
- Limites de taxa e controles de abuso sobre os remetentes, limites de tamanho de anexos, análise dos arquivos enviados e a capacidade de bloquear usuários.
- Retenção e exclusão: apagar uma mensagem, "apagar para todos", a exclusão de conta e as regras legais de retenção precisam, todas, de um lugar no modelo de dados desde o início (dados pessoais devem poder ser removidos a pedido).
- A busca no histórico é um índice separado (busca), atualizado de forma assíncrona a partir do fluxo de mensagens.
- Segurança: autentique a conexão e autorize no servidor cada ação sobre uma conversa; nunca confie na afirmação do cliente sobre quem enviou uma mensagem. Mensagens e anexos são criptografados em trânsito e em repouso (segurança). Com a criptografia de ponta a ponta (o protocolo Signal e seus parentes), os servidores guardam apenas texto cifrado, o que torna muito mais difíceis a busca no servidor, as verificações de spam e a sincronização do histórico entre vários dispositivos: cada dispositivo tem as suas chaves, e uma mensagem de grupo é criptografada para o dispositivo de cada membro. É uma decisão de produto com custos reais.
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ência | No modelo | O que os produtos fazem a respeito |
|---|---|---|
| Um texto cifrado por dispositivo | uma 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 bytes | as 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 filtrar | uma busca por uma palavra em tudo o que o servidor guarda encontrou 0 resultados | a 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 antigas | o notebook novo de Bob não conseguiu decifrar uma mensagem enviada antes de ele existir (a autenticação falhou) e leu a seguinte | o 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órico | o celular perdido tinha a única chave das mensagens antigas | backups 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íveis | o servidor ainda via remetente, dispositivos destinatários, conversa, número de sequência, tamanho e horário | minimize-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.
- Observabilidade: latência de entrega de ponta a ponta (do envio à entrega), taxa de duplicatas e de buracos, número de conexões e taxas de reconexão, profundidade das filas (observabilidade).
10. Erros comuns
- Ordenar pelo timestamp do cliente, ou pela chegada ao servidor que por acaso a recebeu.
- Repetir sem uma chave de idempotência, de modo que um problema de rede produz mensagens duplicadas.
- Confirmar ao remetente antes de a mensagem estar armazenada de forma durável.
- Copiar toda mensagem de grupo para a caixa de entrada de todo membro.
- Usar um único contador global para os números de sequência.
- Tornar os gateways com estado (mantendo estado de conversa na memória deles), de modo que toda reinicialização perde dados.
- Lógica de reconexão sem backoff e jitter.
- Empurrar a presença para todos a cada mudança.
- Tratar a conexão ao vivo como o único caminho de entrega, sem sincronização por pull.
- Confiar em afirmações de identidade do cliente e devolver mensagens sem conferir que quem chama pertence à conversa.
11. Coisas a mencionar em uma entrevista
- Esclareça os requisitos e depois estime: mensagens por segundo, armazenamento por ano, conexões simultâneas.
- Conexões persistentes (WebSocket) contra polling, gateways finos, registro de sessões, notificações push para usuários offline.
- Ordenação por um número de sequência por conversa vindo de um único sequenciador, não por relógios; detecção de lacunas; sincronização a partir da última sequência.
- Entrega at-least-once com ids de mensagem do cliente para a idempotência, dando armazenamento exactly-once; confirmar depois do armazenamento durável; receipts.
- Fan-out na escrita contra na leitura, com os números (o custo cresce com o tamanho do grupo), e o híbrido com pequenas notificações.
- Um armazenamento particionado e log-structured com chave (conversa, sequência); anexos em armazenamento de objetos.
- Presença por heartbeat com expiração e busca por necessidade; sinais efêmeros; grupos grandes mudam as regras.
- Tratamento de falhas: reconectar com jitter, replicar o log, failover do sequenciador; trocas de segurança e de criptografia de ponta a ponta.
Resumo rápido
- Um sistema de chat é pesado em escrita e somente de acréscimo, com conexões de longa duração: a estimativa de exemplo foi de cerca de 23 000 mensagens por segundo em média (70 000 no pico), 73 TB por ano e 10 milhões de conexões simultâneas.
- Ordene por um número de sequência por conversa atribuído pelo servidor, não por relógios: ordenar pelos relógios dos remetentes pôs 19% das mensagens adjacentes na ordem errada na simulação.
- Retry mais idempotência: um id de mensagem gerado pelo cliente faz uma confirmação perdida levar a um reenvio que é armazenado uma vez.
- Armazene uma mensagem de grupo uma vez com cursores por membro: em um grupo de 1 000, copiar para todos os membros significou 2 000 000 de linhas e 238 MB contra 3 000 linhas e 0,4 MB.
- Uma conexão mantida custou cerca de 4,8 KB no mínimo, então os gateways são muitos, finos e descartáveis, e o armazenamento com sincronização por pull (a partir do último número de sequência) é a verdadeira fonte da verdade.
- A presença é um heartbeat com expiração, buscada por necessidade; grupos enormes mudam as regras; e a criptografia de ponta a ponta troca recursos do lado do servidor por privacidade.
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
- Alex Xu, System Design Interview (autopublicado, 2020), capítulo 12 "Design a Chat System", e Alex Xu e Sahil Ghosh, System Design Interview Volume 2 (2022).
- Facebook Engineering, Building Mobile-First Infrastructure for Messenger (2014); e Slack Engineering, Real-time Messaging (2023).
- Rick Reed, Scaling to Millions of Simultaneous Connections (Erlang Factory, 2012), sobre os servidores de conexão do WhatsApp.
- Discord Engineering, How Discord Stores Trillions of Messages (2023) e How Discord Stores Billions of Messages (2017), sobre o particionamento de mensagens por canal e por intervalo de tempo.
- I. Fette e A. Melnikov, RFC 6455: The WebSocket Protocol (2011); Mozilla, WebSockets API e Server-sent events.
- Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, Communications of the ACM, 1978.
- Signal, The Double Ratchet Algorithm e documentação do protocolo Signal (criptografia de ponta a ponta).
- Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), capítulos 5, 8 e 9 (replicação, relógios não confiáveis, garantias de ordenação).
- Signal, The X3DH Key Agreement Protocol e Sesame: multi-device messaging; IETF, The Messaging Layer Security (MLS) Protocol, RFC 9420.
Pratique este tema: System Design System Design › Case studies