Cruxly

Cruxly › System design › Design Exercises

Real-time Messaging

connection state, ordering, offline delivery

Open the interactive lesson

Prompt: one-to-one text messaging. Delivered within a second when both parties are online; reliably delivered in order when the recipient reconnects after being offline. Sender sees sent / delivered / read.

40 minutes first. The hard part is that a connection is state, and state has a location.

Applying the four moves: Scope — one-to-one text, online delivery under a second, ordered offline catch-up, sent/delivered/read; groups, media and search out. Estimate — concurrent connections, not messages per second, is the sizing number, because a persistent connection is memory held on a specific box for as long as the user is online. Sketch — connection gateways holding sockets, a message store partitioned by conversation, and a routing layer that knows which gateway holds which user. Deep dive — the connection is state with a location: what happens when a gateway dies with 100k sockets on it, and how ordering survives a reconnect landing on a different gateway.

Scope and numbers

In scope: 1:1 text, real-time delivery, offline catch-up in order, three-state receipts. Out of scope: group chat, media, search, end-to-end encryption, voice. Say that group chat changes the fan-out story substantially and E2E changes the server's role from store to relay — naming what they would change is better than just listing them.

Estimate. 50M daily actives, 40 messages/user/day, 1 KB each.

50M daily actives x 20% 10,000,000 open sockets / 10k per node ~1,000 gateway nodes That thousand-node figure exists just to hold connections open — it is independent of how many messages anyone actually sends. This is the design: connection count, not message rate, sizes the fleet.
A 1:1 read:write ratio would normally suggest a boring partitioning problem — but the number that actually sizes this system is one nobody would think to compute for a CRUD service.

Connections: the part that is actually hard

Clients hold a persistent connection to a gateway tier — WebSocket, with long-polling fallback. Gateways terminate connections and do nothing else: no business logic, no storage. That separation matters because gateways scale by connection count while the logic tier scales by message rate, and those grow differently.

A sends logic tier lookup(user_id=B) session registry B → gateway 2 forward to gateway 2 gateway 1 gateway 2 gateway 3 B's socket no entry → B is offline → write to durable storage instead The registry is the only thing that knows which of a thousand nodes holds one user's socket.
A connection is pinned to exactly one gateway node. The registry is the map from "who" to "where" — without it, delivery has no way to find a specific open socket among thousands of nodes.

A connection is pinned to one gateway node, so to deliver a message you must find that node. A session registry maps user_id → gateway_node_id, in a shared in-memory store with a TTL refreshed by heartbeat — the TTL matters because a gateway that dies without cleaning up leaves stale entries, and the TTL is what bounds how long you route into a void.

If there is no entry, the recipient is offline and the message waits in durable storage — the registry lookup is what decides which of the two delivery paths a message takes.

:::warn Failure modes to raise unprompted A gateway dies. Ten thousand clients disconnect and reconnect at once — a thundering herd against your connection handshake and auth. Mitigate with randomised reconnect backoff in the client, plus a connection-rate limit at the gateway so a herd degrades into a queue rather than an outage.

The registry is stale. You route to a node that no longer holds the connection. That node should reply "not here" rather than dropping silently, and the sender falls back to the offline path — fail loudly at internal boundaries.

Two connections for one user. Phone and laptop. The registry maps to a set of nodes, and delivery goes to all of them — which also means read receipts must be per-device-aware, or you get odd behaviour.

Load balancing long-lived connections. Standard least-connections balancing is wrong here, because connections are long-lived and unevenly aged: a node restarted an hour ago has few connections and gets hammered. You want connection-count-aware placement plus a deliberate slow ramp for new nodes. :::

Storage and ordering

Messages in a wide-column store, partitioned by conversation_id, clustered by (sequence, message_id) descending. "Last 50 messages in this conversation" is then one sequential partition read — the dominant query, made trivial by the key.

50,000 writes/s exceeds a single primary, and partitioning by conversation puts all of a conversation's writes on one partition, which is also what makes ordering easy.

Ordering. Timestamps are not an ordering. Client clocks are wrong, sometimes by hours; server clocks disagree by milliseconds. Use a per-conversation sequence number, assigned server-side by the single partition that owns the conversation. Monotonic, gap-free, and it makes "what have I missed since sequence N" a single range query — which is exactly the offline sync operation.

This is the payoff of partitioning by conversation: the shard is a single writer for that conversation, so sequence assignment needs no distributed coordination at all. Say that link out loud; it is the moment the design becomes coherent rather than a pile of components.

Idempotency. The client generates a client_message_id (a UUID) and retries carry the same one. A uniqueness constraint on (conversation_id, client_message_id) makes a duplicate send a no-op that returns the original sequence number. Without this, every flaky network produces duplicate messages, which users notice immediately and remember.

TIMESTAMPS — client clocks disagree A: t=14:02:03.100 B: t=14:02:02.900 B's clock is fast — B appears to arrive FIRST, but didn't PER-CONVERSATION SEQUENCE — server-assigned, gap-free A: seq 41 B: seq 42 assigned by whichever arrived first at the shard — no clock involved one partition = one writer = no coordination
Partitioning by conversation was originally a scaling decision — it turns out to also be exactly what makes ordering free, since the shard that owns the conversation is the only thing that ever assigns its sequence numbers.

Offline delivery and receipts

Offline is the normal case, not the exception. Phones sleep, lose signal, and go through tunnels. Design for it as the default path and treat real-time as the optimisation.

Every message is durably written before any delivery attempt. Delivery is then best-effort on top of durable storage, never instead of it. This ordering is the whole reliability story and it should be stated explicitly.

Sync on reconnect. The client stores the highest sequence it has per conversation. On reconnect it sends {conversation_id: last_seq} for its active conversations and the server returns everything after. One range read per conversation, no per-message state on the server, and it is naturally idempotent — a client can re-sync any time with no harm.

For a client offline for a week with hundreds of conversations, cap it: return the most recent N conversations with counts, and let the client page the rest on demand. A sync that tries to be complete will time out.

Receipts are three transitions, and they are not equal:

Store two integers per (conversation, user), not a row per message per state. A high-water mark says "everything up to N" in one number, and the naive per-message design triples your write volume for information nobody needs at that granularity. That reduction is the neatest trick in this design — say it as a trade: "I lose the ability to know that message 7 specifically was read out of order, which cannot happen anyway."

Receipts are also the right place to be explicitly eventual: they can lag by seconds and nobody can tell.

PER-MESSAGE ROWS — one write per message per state 5 messages x 3 states = up to 15 writes HIGH-WATER MARK (chosen) — two integers, period read_mark = seq 5 one write covers messages 1-5 at once
The trade being made explicitly: losing the ability to say "message 3 specifically was read out of order" — which the durable, sequence-ordered store already makes impossible anyway.

Deep dives

Push notifications. If the recipient has no connection, the message goes to APNs/FCM. That is a third-party dependency with its own failure modes and rate limits, so it goes through a queue with retries, never inline on the message path. And it is fire-and-forget: you will never get reliable delivery confirmation from it, so it must never be the only delivery mechanism — the durable store plus reconnect sync is.

Backpressure on a slow client. A client on a poor connection cannot drain as fast as messages arrive. The gateway's per-connection send buffer grows. Policy: bound the buffer, and on overflow drop the connection rather than exhaust gateway memory. The client reconnects and syncs from its last sequence — which works precisely because sync is idempotent and sequence-based. One mechanism covering both the normal and the degenerate case is a sign the design is right.

Hot conversation. A very active conversation is one partition. Text messaging between two people has a natural ceiling, so this is mostly a group-chat problem — which is out of scope, but worth naming as the reason group chat is a harder problem than it looks: fan-out plus a hot partition at once.

Retention. 700 TB/year with reads almost entirely against the last few days. Tier: recent in the hot store, older to object storage with an index, accessed on demand with higher latency. A user scrolling far back waits a second; say that this is an acceptable, deliberate degradation.

Multi-region. Latency wants users served locally; conversations can span regions. Pin a conversation to a home region (by its creator, say) and accept cross-region latency for the minority of conversations that span them — rather than multi-leader writes, which would reintroduce ordering conflicts you just solved with the sequence number. Being able to explain why you are not doing multi-leader is the stronger answer.

SLOW CLIENT — buffer fills faster than it drains send buffer filling bound hit connection dropped client reconnects sync from last_seq — same path as an offline client
The overflow case and the "offline for a week" case resolve through the exact same sync mechanism — one design decision, two problems solved, which is the signal the design is actually right rather than merely patched.

How to say it in the interview

"The thing that makes this different from a CRUD service is that the server has to push, which means a long-lived connection, which means my app servers are not stateless any more. I want to deal with that first because everything else follows from it."

Checklist

Practice this interactively
Share this lessonWhatsAppLinkedInX

Related lessons