Chat

"Projete um aplicativo de chat como o WhatsApp ou o Slack: conversas individuais e em grupo, confirmações de entrega e de leitura, presença online, e tem que funcionar em celulares com rede instável."

O chat é o problema clássico com estado e em tempo real. Todo o resto desta disciplina prefere servidores sem estado atrás de um balanceador de carga; o chat precisa de milhões de conexões de longa duração, então os servidores que as seguram têm estado e o sistema precisa saber em qual servidor cada usuário está conectado. Por cima disso vêm as perguntas que separam níveis: como ordenar mensagens sem um relógio global, como entregar exatamente uma vez na tela numa rede que repete envios, e o que acontece com uma mensagem enviada para alguém cujo celular está num túnel?

O BoxOffice também tem chat: cada evento tem um grupo de fãs onde quem tem ingresso conversa antes e durante o show, e os fãs falam com atendentes sobre seus pedidos. Num festival, dezenas de milhares de fãs no mesmo grupo do evento é o follow-up do "canal gigante" desta página.

1. Esclarecer os requisitos

(roteiro de entrevista)

Requisitos funcionais

1. Conversas individuais e em grupo (grupos de até, digamos, 500 membros).
2. Enviar e receber mensagens de texto em tempo real; mídia (imagens, áudio) como anexos.
3. Confirmações de entrega e de leitura (✓ enviada, ✓✓ entregue, lida).
4. Presença online e "visto por último".
5. Entrega offline: mensagens para um usuário offline chegam quando ele reconecta, mais uma notificação push.
6. Vários dispositivos por usuário (celular + desktop), todos sincronizados; o histórico persiste.

Requisitos não funcionais

Fora do escopo (diga explicitamente)

Detalhes do protocolo de criptografia de ponta a ponta (cite que ele muda busca e moderação), chamadas de voz/vídeo, busca de mensagens, bots. Canais de transmissão gigantes ficam para um follow-up.

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

# Chat: assumptions (illustrative)
dau             = 50_000_000
msgs_per_user   = 40            # messages sent per user per day
peak_factor     = 3
online_share    = 0.3           # share of DAU connected at peak
conns_per_gw    = 50_000        # WebSocket connections one gateway node holds comfortably
group_share     = 0.3           # share of messages sent to groups
avg_group       = 20            # members per group
msg_b           = 300           # message + metadata, bytes
replication     = 3
heartbeat_s     = 30            # app-level heartbeat interval

msgs_day        = dau * msgs_per_user
msg_qps         = msgs_day / 86_400
peak_msg_qps    = msg_qps * peak_factor
deliveries_qps  = peak_msg_qps * ((1 - group_share) * 1 + group_share * avg_group)
connections     = dau * online_share
gateways        = connections / conns_per_gw
heartbeats_qps  = connections / heartbeat_s
storage_tb_day  = msgs_day * msg_b * replication / 1e12
storage_pb_year = storage_tb_day * 365 / 1e3

rows = [
    ("msgs_day", msgs_day, "msgs"), ("msg_qps", msg_qps, "msgs/s"),
    ("peak_msg_qps", peak_msg_qps, "msgs/s"), ("deliveries_qps", deliveries_qps, "deliveries/s"),
    ("connections", connections, "sockets"), ("gateways", gateways, "nodes"),
    ("heartbeats_qps", heartbeats_qps, "pings/s"), ("storage_tb_day", storage_tb_day, "TB/day"),
    ("storage_pb_year", storage_pb_year, "PB/year"),
]
print("| quantity | value | unit |\n|---|---:|---|")
for name, value, unit in rows:
    v = f"{value:,.0f}" if abs(value) >= 100 else f"{value:,.2f}"
    print(f"| `{name}` | {v} | {unit} |")

O que os números dizem:

• ~23 mil mensagens/s em média, ~70 mil no pico, e o fan-out dos grupos as transforma em ~460 mil entregas/s. ⇒ a entrega é um problema de roteamento entre muitas máquinas, não um problema de banco de dados.
• 15 M de conexões simultâneas precisam de ~300 nós de gateway. ⇒ os gateways são uma frota grande e com estado: deploys, quedas e escalonamento desconectam usuários, então a reconexão precisa ser barata e bem-comportada.
• Se cada cliente mandasse um heartbeat de aplicação para um serviço central de presença, seriam 500 mil escritas/s só para dizer "ainda estou aqui". ⇒ a presença precisa ser derivada da própria conexão no gateway, e só as mudanças publicadas.
• O histórico cresce ~1,8 TB/dia replicado, ~0,66 PB/ano. ⇒ um armazenamento horizontalmente escalável e otimizado para escrita (wide-column / LSM), particionado por conversa.

3. API

O tráfego em tempo real passa por um WebSocket por dispositivo; histórico e configuração usam REST comum.

# WebSocket frames (JSON or protobuf), client ⇄ gateway
→ send     {"type":"send", "clientMsgId":"c-7f3a", "conversationId":"g-42", "body":"See you at gate B!"}
← ack      {"type":"ack",  "clientMsgId":"c-7f3a", "msgId":"m-918273", "seq":1043, "ts":1767261600123}
← message  {"type":"msg",  "conversationId":"g-42", "seq":1043, "msgId":"m-918273", "from":"u-7", "body":"…"}
→ receipt  {"type":"receipt", "conversationId":"g-42", "upToSeq":1043, "kind":"delivered|read"}
← presence {"type":"presence", "userId":"u-7", "status":"online|offline", "lastSeen":1767261590000}
→ sync     {"type":"sync", "cursors":{"g-42":1040, "d-7-9":88}}     # after reconnect

GET  /v1/conversations?updatedSince=…                   → 200 [conversation summaries, last seq]
GET  /v1/conversations/{id}/messages?beforeSeq=1040&limit=50 → 200 [messages]   (scroll back)
POST /v1/conversations  {"members": ["u-7","u-9"], "name": "Rock in Rio crew"} → 201
POST /v1/media                                           → 201 {mediaId, uploadUrl}

• O clientMsgId é gerado pelo dispositivo de quem envia; um send repetido com o mesmo ID é confirmado de novo, mas guardado uma vez só.
• O seq é atribuído pelo servidor, por conversa, estritamente crescente — a ordem que todos os membros vão exibir.
• As confirmações são cumulativas (upToSeq): um frame confirma muitas mensagens.

4. Modelo de dados

-- Messages: partitioned by conversation and time bucket, ordered by seq (wide-column)
CREATE TABLE messages (
    conversation_id TEXT,
    bucket          INT,            -- e.g. days since epoch, or seq / 10 000: bounds partition size
    seq             BIGINT,
    msg_id          TEXT,
    client_msg_id   TEXT,
    sender_id       TEXT,
    body            BLOB,
    created_at      TIMESTAMP,
    PRIMARY KEY ((conversation_id, bucket), seq)
) WITH CLUSTERING ORDER BY (seq DESC);

CREATE TABLE conversation_members (
    conversation_id TEXT, user_id TEXT, joined_at TIMESTAMP, last_read_seq BIGINT,
    PRIMARY KEY ((conversation_id), user_id)
);

CREATE TABLE user_conversations (          -- the "inbox": which conversations, newest first
    user_id TEXT, conversation_id TEXT, last_seq BIGINT, updated_at TIMESTAMP,
    PRIMARY KEY ((user_id), conversation_id)
);

# Session registry (Redis): where is each device connected?
session:u-9        → { "phone": "gw-117", "desktop": "gw-031" }    TTL refreshed by the gateway
# Presence (Redis): last seen, only written on state changes
presence:u-9       → { status: "online", lastSeen: 1767261590000 }
# Per-conversation sequence counter (if not owned by a single partition leader)
seq:g-42           → 1043

5. Design de alto nível

flowchart LR
    a([Celular da Alice]) --> lb["Balanceador L4<br/>TCP de longa duração"]
    b([Desktop do Bob]) --> lb
    lb --> gw1["Gateway gw-031<br/>WebSockets"]
    lb --> gw2["Gateway gw-117<br/>WebSockets"]
    gw1 --> cs["Serviço de chat<br/>sequenciador, fan-out"]
    gw2 --> cs
    cs --> db[("Mensagens<br/>wide-column")]
    cs --> reg[("Registro de sessões<br/>+ presença")]
    cs --> ps[["Pub/sub<br/>canal por gateway"]]
    ps --> gw1
    ps --> gw2
    cs --> push["Notificações<br/>APNs / FCM"]
    a -. mídia .-> obj[("Object store + CDN")]

A Alice envia uma mensagem ao Bob, que está online em outro gateway:

sequenceDiagram
    autonumber
    participant A as Alice (gw-031)
    participant C as Serviço de chat
    participant D as Banco de mensagens
    participant R as Registro de sessões
    participant P as Pub/sub
    participant B as Bob (gw-117)
    A->>C: send {clientMsgId c-7f3a, conv d-7-9}
    C->>C: seq = next(d-7-9) → 88
    C->>D: insere (d-7-9, 88) se o clientMsgId for novo
    C-->>A: ack {msgId, seq 88}  ✓ enviada
    C->>R: onde está o Bob? → gw-117
    C->>P: publica no canal gw-117
    P->>B: entrega {seq 88}
    B-->>C: confirmação de entrega upToSeq 88
    C-->>A: ✓✓ entregue

Se o Bob não tem sessão, o serviço de chat guarda a mensagem (ela já está no banco) e pede ao serviço de notificações um push; o app do Bob busca as mensagens com um sync quando reconecta.

6. Aprofundamentos (deep dives)

6.1 Segurando milhões de conexões

Operando a frota de gateways:

• Gateways só seguram sockets. Eles autenticam a conexão, registram usuário/dispositivo → gateway no registro de sessões, encaminham os frames ao serviço de chat e entregam o que chega no seu canal de pub/sub. Nenhuma lógica de negócio — por isso são simples de escalar e reiniciar.
• Heartbeats no nível da conexão. Ping/pong do WebSocket a cada ~30 s detecta conexões mortas (redes móveis caem em silêncio); o gateway renova o TTL das sessões em lote, não uma escrita por ping.
• Deploys e quedas desconectam usuários. Drene aos poucos (pare de aceitar, peça aos clientes que reconectem ao longo de minutos) e faça os clientes reconectarem com backoff exponencial e jitter — senão 50 000 celulares reconectando no mesmo segundo formam uma tempestade de reconexão que derruba o próximo gateway (padrões de confiabilidade).
• Apps móveis em segundo plano não conseguem manter um socket aberto; é para isso que servem as notificações push.

6.2 Ordem e exibição exatamente uma vez

Timestamps dos dispositivos não ordenam mensagens: relógios derivam e dois celulares podem discordar em segundos (tempo e relógios). Ordem global é desnecessária e cara. O que os usuários precisam é de uma ordem por conversa, a mesma para todos os membros.

• Um sequenciador por conversa. Encaminhe todas as escritas de uma conversa para o mesmo dono — uma partição do serviço de chat escolhida por hash(conversation_id), ou uma partição do Kafka com chave pela conversa — que atribui seq = último + 1. O dono é o único escritor, então não são necessários locks.
• Pelo menos uma vez + idempotência = efeito de exatamente uma vez. O dispositivo repete o send até receber um ack (a rede pode ter perdido a requisição ou o ack). O servidor deduplica por (conversation_id, client_msg_id) e devolve o mesmo seq de novo (semântica de entrega).
• O dispositivo exibe por seq e deduplica por msgId; um buraco (seq 90 chega antes do 89) dispara uma espera curta ou um sync do intervalo que falta.

sequenceDiagram
    autonumber
    participant A as Celular da Alice
    participant C as Serviço de chat
    A->>C: send c-7f3a "Portão B"
    C->>C: guarda, seq 88
    C--xA: ack perdido (túnel)
    A->>C: repete send c-7f3a "Portão B"
    C->>C: c-7f3a já guardada → seq 88
    C-->>A: ack seq 88 (o mesmo)
    Note over A,C: guardada uma vez, exibida uma vez

6.3 Entrega offline e sincronização entre dispositivos

• Guarde primeiro, entregue depois. Uma mensagem é durável assim que confirmada, esteja o destinatário online ou não; a entrega é uma tentativa de empurrá-la para sockets ativos.
• Cursor por dispositivo. Cada dispositivo lembra o último seq que tem em cada conversa. Ao reconectar, envia sync {conversa: últimoSeq} e recebe tudo o que veio depois — a tabela de inbox diz quais conversas mudaram (last_seq > cursor).
• Notificações push acordam o dispositivo (APNs no iOS, FCM no Android). Elas levam uma prévia curta ou só "nova mensagem" (sempre a segunda com criptografia de ponta a ponta); o conteúdo é buscado pelo sync.
• O estado de leitura é por usuário (sincronizado entre dispositivos): ler no desktop limpa o contador no celular por meio de um evento de confirmação.

6.4 Presença sem derreter o sistema

Presença parece barata e não é: toda mudança de status de um usuário interessa a todos os seus contatos.

• Derive a presença da conexão: online quando o primeiro dispositivo conecta, offline quando o último desconecta mais um período de tolerância (digamos 30 s, para esconder oscilações da rede).
• Publique só mudanças, e só para usuários que estão online e olhando (a lista de contatos ou a conversa aberta se inscreve; um app fechado não).
• Em grupos com mais de algumas dezenas de membros, não faça fan-out de presença — mostre "visto por último" sob demanda.
• Guarde o lastSeen com TTL no cache; tudo bem perdê-lo.

7. Gargalos, modos de falha e trade-offs

Os trade-offs para dizer em voz alta: ordem por conversa, não global (barata e suficiente), pelo menos uma vez + dedupe em vez de "entrega exatamente uma vez" (a única garantia honesta sobre uma rede), e gateways com estado mantidos burros (estado na conexão, lógica em outro lugar).

8. Experimente no playground

O cenário chat tem gateways segurando conexões WebSocket, uma camada de pub/sub entre eles e armazenamento para as mensagens.

Abrir o playground completo

9. Perguntas de follow-up que o entrevistador faz

10. Rubrica de autoavaliação

Relacionados: Protocolos (WebSockets, SSE), Semântica de mensageria, Particionamento, Caso do sistema de notificações, Hands-on 7.

Como se conecta

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

flowchart LR
    CASE(["Chat"]) --> EDG["Edge<br/>WebSockets, L4 LB, stateful gateways"]:::tech
    CASE --> MSG["Messaging<br/>pub/sub per gateway, at-least-once"]:::tech
    CASE --> DIS["Distributed<br/>per-conversation sequence, no device clocks"]:::tech
    CASE --> DB["Databases<br/>wide-column, partition by conversation"]:::tech
    CASE --> REL["Reliability<br/>reconnect storms: backoff + jitter"]:::tech
    CASE --> CMP["Compute<br/>push for offline devices"]:::tech
    EDG -.-> k1["lb · app"]:::comp
    MSG -.-> k2["pubsub"]:::comp
    DB -.-> k3["nosql · cache<br/>(session registry)"]:::comp
    CMP -.-> k4["notifications"]:::comp
    classDef comp fill:#1e9e5a22,stroke:#1e9e5a
    classDef tech fill:#2f6fed22,stroke:#2f6fed

Aulas que ele testa: Borda — protocolos · Borda — balanceamento de carga · Mensageria — semântica · Distribuídos — tempo e relógios · Bancos de dados — particionamento · Confiabilidade — padrões · Hands-on 7. Componentes da paleta: lb · app · pubsub · nosql · cache · notifications · objstore · cdn. Cenários: chat.

Referências

• XU, A. System Design Interview — An Insider's Guide, vol. 1, cap. 12 "Design a Chat System"¹.
• O protocolo WebSocket².
• Como o Discord guarda mensagens em escala³.
• LAMPORT, L. Time, Clocks, and the Ordering of Events in a Distributed System⁴.