Design an iMessage-style messaging backend

I would clarify: is end-to-end encryption a hard requirement, and is it the same for groups as for one-to-one? How many devices per user, and can a new device read old history? What should the server be allowed to know (it will always know who talks to whom and when)? What is the loss tolerance during a regional outage? And is the content text and small attachments, with large media going to object storage as encrypted blobs?

Assumed scope: one-to-one and small groups, text plus attachment references, end-to-end encrypted, about three devices per user, offline delivery, two or more regions. Out of scope: designing the cryptographic protocol itself (I will name the pieces and defer to a vetted protocol), voice and video, spam filtering of content the server cannot see.

Planning figures for the exercise, not facts about any company.

• Users: 500 M registered, 200 M daily, about 8 B messages a day (40 per daily user). 8 B ÷ 86,400 is about 93,000 a second.
• Envelopes: with end-to-end encryption the sender encrypts a copy per recipient device. A one-to-one message to a user with 3 devices, from a sender with 3 devices, is 3 recipient copies plus 2 copies for the sender's other devices: 5 envelopes. 93,000 × 5 is about 460,000 a second on average, about 1.4 M at a 3x peak.
• Storage: at 1 KB per envelope, 8 B × 5 × 1 KB is 40 TB a day if everything were kept. The server only holds undelivered envelopes. If 2% are still waiting after a day, that is 0.8 TB a day, and with a 30-day expiry about 24 TB.
• Key directory: 500 M × 3 devices × 2 KB of public key material is about 3 TB. Small and cacheable.
• Connections: 100 M concurrently connected devices ÷ 250,000 per box is 400 gateways.
• Cross-region: US to Western Europe is 70 to 90 ms, so a message routed to the recipient's home region pays one such hop.

What the numbers force: the unit of work is the device envelope, not the message; the inbox queue is partitioned by device; and the key directory is a cached read-mostly service.

The central idea is that the server is a blind courier. It stores and forwards ciphertext, and the clients hold the keys.

• Key directory. Maps user_id to a list of devices, each with a public identity key and a supply of one-time prekeys. Devices upload prekeys; the directory hands one out per new session. Device lists carry a version number so a sender knows when its cached list is stale. Clients should surface a key change to the user and let them verify identities out of band, because a directory that can quietly swap keys is the main attack on this design. A transparency log of key changes is the stronger answer.
• Send path. The sender fetches the recipient's device list (cached by version), encrypts the message once per recipient device and per own other device using established pairwise sessions, and sends one request containing all envelopes plus a client message ID. For small groups use the same per-device fan-out. For larger groups, use a shared sender key per group, rotated whenever membership changes.
• Inbox store. One queue per device, keyed (device_id, inbox_seq), value is the envelope. The server assigns inbox_seq, which only orders delivery to that device. Writes are acked to the sender after a durable multi-AZ quorum write.
• Delivery. If the device has a live connection (registry lookup, as in any chat gateway design) push it; otherwise send a content-free wake-up through the platform push service. The device acks up to a sequence number and the server deletes everything at or below it. Expiry deletes whatever is never collected.
• Idempotency. A unique (sender_device, client_msg_id, recipient_device) key makes retries safe.

Message order is not the server's job when it cannot read content. Each message carries a hybrid logical clock from the sender and a per-conversation counter inside the encrypted payload. Receivers sort by (clock, sender device ID) and use the counters to spot gaps. Clamp a wildly wrong device clock by using max(local time, highest seen + 1), as covered in the time chapter.

Multi-region: every user has a home region where their device inboxes live. A sender in another region delivers to the recipient's home region, paying one cross-region hop. Inboxes replicate asynchronously to a second region for failover. A regional loss can drop the last few seconds of replicated envelopes, so the sender keeps each message until it sees a delivery confirmation, and receivers use the counters to request a resend when they find a gap. Say plainly that this is a recovery point of seconds, not zero.

Hard problems: first, a device is added or removed, so a message sent against a stale device list reaches the old set only. The server rejects sends whose device-list version is out of date and returns the new list, forcing the sender to re-encrypt. Second, the metadata still leaks. Keep logs short-lived, avoid storing contact graphs, and say honestly what remains visible.

• Per-device envelopes vs one shared ciphertext. One ciphertext is cheap but needs a shared key that every device and every membership change must manage. Per-device encryption multiplies server work by about 5. Pick per-device for one-to-one and small groups because it is the simplest to reason about, and flip to a group sender key for large groups where the multiplier hurts.
• Sync cross-region replication vs async. Synchronous means no loss but adds 70 to 90 ms or more to every send and ties availability to the farthest region. Pick async with client-side retention and gap detection. Flip to synchronous only for a small class of messages that cannot tolerate any loss.
• Server-assigned inbox order vs sender clocks. Server order is simple but only reflects arrival, not intent. Sender hybrid clocks reflect intent but can be skewed. Use both: server sequence for delivery, sender clock plus counters for display order.
• Long retention vs delete on ack. Keeping envelopes eases multi-device recovery but grows storage and legal exposure. Pick delete on ack with a short expiry, and flip only if a product feature needs server-held history, accepting the encryption design that comes with it.

• Putting plaintext on the server "for search and spam checks" in an end-to-end encrypted system.
• Encrypting once for the recipient and forgetting that each device has its own keys.
• Using the server clock or an auto-increment ID as the only ordering for display.
• Ignoring the key directory, which is the actual trust anchor and the easiest thing to attack.
• Claiming zero message loss across regions without paying for synchronous replication.
• Retaining delivered ciphertext forever.
• Forgetting that adding or removing a device changes who must receive a copy.
• Treating push notifications as the message channel rather than a wake-up.
• Inventing a custom cryptographic protocol instead of naming a vetted one.