Give every device its own key pair and have the sender encrypt each message once per recipient device, so the server relays only ciphertext plus routing metadata. Online devices get envelopes over a persistent connection; offline ones from a per-device queue kept for 30 days and deleted on acknowledgment. Read receipts are themselves encrypted messages.
hardPattern: Message queues and async workFrom Devana's Meta question set
Problem
Design one-to-one messaging for two billion users, with delivery and read receipts, delivery to devices that have been offline for weeks, several devices per user, and end-to-end encryption.
Be precise about what the server can see and what it cannot.
PUT /devices/{device_id}/keys {identity_key, one_time_keys[]} -> ok
GET /users/{user_id}/devices -> [{device_id, identity_key, one_time_key}]
Over the device's open connection:
send {message_id, envelopes: {device_id: ciphertext}}
deliver {message_id, from_device, ciphertext}
ack {message_id}This is one of Devana's own questions, written in the style of Meta's interviews. It is not a question leaked from Meta, and Devana is not affiliated with Meta.
Requirements
- 2 × 10^9 users.
- Messages must reach devices that have been offline for weeks.
- The server must not be able to read message content.
- A user may have several devices at once.
- Worth asking first: how long may an undelivered message wait, and are group chats in scope? Assume 30 days, and one-to-one only.
Scenarios
Scenario 1
Ana messages Ben, who has a phone and a laptop; the laptop is closed. Expected: The phone shows it at once, the laptop when it next connects, and Ana sees delivered when the phone acknowledges it.
Ana's device encrypted one envelope for each of Ben's devices. The phone's arrived over its open connection; the laptop's waits in the laptop's queue.
Scenario 2
Ben's laptop stays offline for 31 days. Expected: Its copy is deleted unread; the phone already has the message.
Every queued envelope expires after 30 days. A message that reached none of Ben's devices would stay at sent for Ana, and the server would keep nothing.
Hints
Open one at a time, and try the problem again after each.
Hint 1
Start from the requirement that the server cannot read content. Where must encryption and decryption happen, and what does that leave the server to do?
Hint 2
If the recipient has three devices, how many copies of the message does the sender encrypt, and with whose keys?
Hint 3
A device offline for weeks has to get its messages from somewhere. What does the server keep, and for how long?
Hint 4
A read receipt reveals that a message was read. Who can create one if the server cannot read anything?
A worked answer
Requirements and estimates
Assume a billion users are active on a given day and each sends 40 messages: 4 × 10^10 messages a day, about 4 × 10^5 a second on average, and around 10^6 at peak. Each message becomes several encrypted envelopes, one per device it must reach: say three for the recipient's devices and two for the sender's other devices, so about 5 × 10^6 envelopes a second at peak.
Storage is small, because the server keeps an envelope only until it is delivered, and most leave within seconds. The open connections cost more: assume 5 × 10^8 devices online at once and, as an assumption to confirm with a load test, 10^5 connections per gateway server, which is 5,000 gateways.
Keys and end-to-end encryption
Each device creates its own key pair, and the private key never leaves the device. Devices publish their public keys to a key directory, plus a batch of one-time keys so that others can start an encrypted session with them while they are offline.
To send, a device looks up the recipient's devices and the sender's own other devices, and encrypts the message once for each, with that device's keys. No key is copied between devices, and adding or removing a device changes the list of envelopes, nothing else. The directory could hand out a wrong key and read along, so clients show a security code built from both parties' keys that people can compare in person, and warn when a contact's key changes.
Connections and routing
Each online device keeps one persistent connection to a gateway. A session registry maps device ids to the gateway holding them. The router takes each envelope, looks up its device, and passes it to that gateway; a device with no session gets the envelope in its offline queue, and a push notification wakes it.
Offline delivery
Each device has its own queue of envelopes, stored durably and replicated. A device that reconnects drains its queue and acknowledges each envelope, which deletes it. Envelopes expire after 30 days: a user who never comes back loses those messages, and that limit is a product decision to state, not an accident.
Receipts, and what the server sees
Delivered: the server sees a recipient device acknowledge the envelope, so it can tell the sender. Read: only the reader's device knows, so it sends a small encrypted receipt to the sender's devices, routed like any other message.
The server never sees content, but it does see who sends to which devices, when, from which IP address, how large each envelope is and how many devices each user has. That metadata is real exposure: keep as little of it as possible, for as short a time as possible, and say so plainly rather than claiming the server learns nothing.
The whole design at a glance
How to say it in the interview
Start from the line about what the server cannot see, because it decides the architecture: keys live on devices, the sender encrypts once per device, and the server is a relay for ciphertext. Then walk one message to an online device and one to an offline device, and finish with what the server does see, metadata, and how little of it you keep.
The core in code
The relay's bookkeeping, which is the server's whole job here: a queue per device, envelopes that expire, acknowledgments that delete them, and the delivered receipt sent to the sender when the first of the recipient's devices acknowledges. To the relay, every envelope is opaque bytes.
Python
class Relay:
"""Store-and-forward for encrypted envelopes: one queue per device.
The relay sees ids and ciphertext, never the message itself."""
def __init__(self, ttl):
self.ttl = ttl
self.queues = {} # device -> {message id: (expires at, ciphertext)}
self.sender = {} # message id -> sending device, until delivered
self.recipients = {} # message id -> the recipient's devices
def send(self, msg_id, sender, envelopes, recipient_devices, now):
"""envelopes: {device: ciphertext}, one per device, made by the sender."""
for device, ciphertext in envelopes.items():
self.queues.setdefault(device, {})[msg_id] = (now + self.ttl, ciphertext)
self.sender[msg_id] = sender
self.recipients[msg_id] = set(recipient_devices)
def fetch(self, device, now):
self.expire(now)
return [(m, c) for m, (_, c) in self.queues.get(device, {}).items()]
def ack(self, device, msg_id):
"""Deletes the envelope. Returns a delivered receipt the first time
one of the recipient's devices has the message."""
if self.queues.get(device, {}).pop(msg_id, None) is None:
return None # unknown, or already acknowledged
if device in self.recipients.get(msg_id, ()):
del self.recipients[msg_id]
return ("delivered", msg_id, self.sender.pop(msg_id))
return None # the sender's own other device
def expire(self, now):
live = set()
for queue in self.queues.values():
for m, (until, _) in list(queue.items()):
if until <= now:
del queue[m]
else:
live.add(m)
for m in [m for m in self.sender if m not in live]:
del self.sender[m] # never delivered: keep nothing
self.recipients.pop(m, None)JavaScript
class Relay {
// Store-and-forward for encrypted envelopes: one queue per device.
// The relay sees ids and ciphertext, never the message itself.
constructor(ttl) {
this.ttl = ttl;
this.queues = new Map(); // device -> Map(message id -> [expires at, ciphertext])
this.sender = new Map(); // message id -> sending device, until delivered
this.recipients = new Map(); // message id -> Set of the recipient's devices
}
send(msgId, sender, envelopes, recipientDevices, now) {
// envelopes: {device: ciphertext}, one per device, made by the sender.
for (const [device, ciphertext] of Object.entries(envelopes)) {
if (!this.queues.has(device)) this.queues.set(device, new Map());
this.queues.get(device).set(msgId, [now + this.ttl, ciphertext]);
}
this.sender.set(msgId, sender);
this.recipients.set(msgId, new Set(recipientDevices));
}
fetch(device, now) {
this.expire(now);
return [...(this.queues.get(device) ?? new Map())].map(([m, [, c]]) => [m, c]);
}
ack(device, msgId) {
// Deletes the envelope. Returns a delivered receipt the first time
// one of the recipient's devices has the message.
const queue = this.queues.get(device);
if (!queue || !queue.delete(msgId)) return null; // unknown, or already acknowledged
if (this.recipients.get(msgId)?.has(device)) {
const from = this.sender.get(msgId);
this.sender.delete(msgId);
this.recipients.delete(msgId);
return ["delivered", msgId, from];
}
return null; // the sender's own other device
}
expire(now) {
const live = new Set();
for (const queue of this.queues.values()) {
for (const [m, [until]] of [...queue]) {
if (until <= now) queue.delete(m);
else live.add(m);
}
}
for (const m of [...this.sender.keys()]) {
if (!live.has(m)) { // never delivered: keep nothing
this.sender.delete(m);
this.recipients.delete(m);
}
}
}
}Both versions are tested against the same cases, including every example on this page.
- The delivered receipt goes out once, on the first acknowledgment from a recipient device; later acknowledgments, and those from the sender's own devices, only delete envelopes.
- Expiry runs when a device fetches. In production a background sweep does it too, so a device that never returns still has its envelopes removed on time.
- When the last envelope of an undelivered message expires, the relay forgets the message entirely: the sender's side simply never sees delivered.
Follow-up questions
What exactly does the server store, and what can it infer from that?
Ciphertext envelopes until they are delivered or expire, public keys, and routing metadata: who sent to which devices, when, envelope sizes and connection IP addresses. From that it can infer who talks to whom and how often, even without content. Keep those logs short-lived, and say plainly that metadata is visible.
How does a new device get the user's message history?
Not from the server, which deletes envelopes once they are delivered. One of the user's existing devices can transfer the history, encrypted to the new device's key, or the user restores a backup encrypted with a key the server does not hold. Without either, the new device starts empty.
How do read receipts work without the server reading messages?
The reader's device sends a small encrypted receipt to the sender's devices, routed like any message. The server can produce delivered receipts itself, because it sees acknowledgments, but it cannot know that a message was read.
What happens to undelivered messages if a user never comes back?
They expire from the device queues after the retention period, 30 days here, and the server keeps nothing. The sender's message stays at sent. State the limit up front: it is a product decision.
Common mistakes
- Storing messages on the server in a form it can read, and still calling the design end-to-end encrypted.
- One key per user, copied to every device, so a private key leaves the device that made it.
- Having the server create read receipts, which needs knowledge it should not have.
- Offline queues that never expire, so a user who never returns costs storage forever.
- Claiming the server learns nothing, when it sees who talks to whom and when.
Practice it in a mock interview
Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with a whiteboard he can read.
Related problems
- Design an Event and Webhook Platform: An outbox for exactly the committed changes, per-endpoint queues, signed deliveries and replay.
- Design a News Feed: Push to most followers, pull from the few huge accounts, and rank the merged candidates.
- Message queues and async work: the pattern guide, with more practice questions.