Problem Statement

Design a messaging system like Facebook Messenger that supports 1:1 and group chats, real-time message delivery, read receipts, typing indicators, presence (online/offline), message history, and end-to-end encryption. The system must handle billions of messages per day and support both mobile and web clients.

Why This Problem Matters

• Real-time messaging is foundational to Meta's ecosystem. Understanding it demonstrates expertise in bidirectional communication, consistency, and offline support.
• Tests knowledge of WebSocket management, message ordering, delivery guarantees, and encryption.
• Reveals how to handle edge cases like offline users, message sync across devices, and group chat scalability.

Thought Process

Step-by-Step Reasoning

1. Connection: Client opens WebSocket to Gateway → Gateway authenticates and registers session → Session stored in distributed cache (user_id → gateway_id).
2. Send Message: Client sends message → Gateway forwards to Message Service → Store in Messages DB → Lookup recipient session → Route to recipient's Gateway → Push via WebSocket.
3. Offline Handling: If recipient has no active session, message stored in "pending" queue → When recipient connects, Gateway fetches pending messages → Delivered in order.
4. Group Chat: Message Service looks up all group members → Fan-out to each member's Gateway (or pending queue if offline) → Use Kafka topics per group for ordering.
5. Read Receipts: Recipient sends "read" event → Message Service updates message status → Notifies sender via WebSocket.
6. Sync Across Devices: Each message has conversation_id + sequence_num → Client requests messages where sequence > last_known → Server returns batch.

Dry Run

Complexity Analysis

Annotated Solution

// Message delivery pseudocode
public class MessageService {
    private MessageStore messageStore;
    private SessionRegistry sessionRegistry;
    private PendingQueue pendingQueue;
    private GatewayClient gatewayClient;

    public void sendMessage(Message message) {
        // 1. Persist message
        message.setSequence(getNextSequence(message.getConversationId()));
        message.setStatus(MessageStatus.SENT);
        messageStore.save(message);

        // 2. Find recipient sessions
        List<String> recipientIds = getRecipients(message);

        for (String recipientId : recipientIds) {
            Optional<Session> session = sessionRegistry.getSession(recipientId);

            if (session.isPresent()) {
                // Online: push immediately
                gatewayClient.push(session.get().getGatewayId(), message);
            } else {
                // Offline: queue for later
                pendingQueue.enqueue(recipientId, message);
            }
        }
    }

    public void onUserConnected(String userId, String gatewayId) {
        // Register session
        sessionRegistry.register(userId, gatewayId);

        // Deliver pending messages
        List<Message> pending = pendingQueue.drain(userId);
        for (Message message : pending) {
            gatewayClient.push(gatewayId, message);
        }
    }
}

Common Pitfalls

• Message ordering: Network delays can cause out-of-order delivery. Use vector clocks or sequence numbers per conversation.
• Thundering herd: When a user with many pending messages comes online, fetching all at once can overwhelm the system. Use pagination and rate limiting.
• Gateway hotspots: Popular users' sessions might concentrate on one Gateway. Use consistent hashing to distribute.
• E2E encryption key management: Lost device keys mean lost messages. Support key backup (encrypted with user password) or accept data loss.

Follow-Up Questions

• How would you implement message search? (Store encrypted index on device, or use server-side search with user consent)
• How do you handle 10,000-member group chats? (Hierarchical fan-out, lazy delivery, sampling for read receipts)
• How would you implement disappearing messages? (TTL on storage, client-side deletion confirmation)

Key Takeaways