Design a Real-Time Chat & Instant Messaging System

1. Problem Statement & Scope Clarification

System Mission

Design a globally distributed, highly scalable, real-time instant messaging platform (similar to WhatsApp, Slack, and Discord) capable of supporting ultra-low latency 1-on-1 direct messaging, group conversations (up to 1,000 members), real-time presence tracking (Online/Offline/Last Seen), multi-device synchronization, read receipts, and durable offline catch-up delivery for hundreds of millions of users worldwide.

Functional Requirements

1. 1-on-1 Direct Messaging (SEND_MESSAGE): Bi-directional real-time text and media messaging with instant delivery confirmations ($P99 < 100\text{ ms}$).
2. Group Chats & Fan-Out: Scalable group channels supporting up to 1,000 participants with persistent membership, unread badge tracking, and read-state management.
3. Presence & Heartbeat Engine: Real-time user online/offline status detection with debounce mechanisms to suppress connection flapping on mobile cellular transitions.
4. Message Delivery Receipts: Three-stage message lifecycle states: SENT (Server Ack), DELIVERED (Device Ack), and READ (User Seen).
5. Offline Message Synchronization: Durable message storage allowing offline devices to fetch missed messages using sequential sync cursors upon reconnect.
6. Push Notifications: Fallback push notification dispatch (Apple APNs / Google FCM via Amazon SNS) when a recipient is disconnected.

Non-Functional Requirements (SLAs & SLOs)

• High Availability: $99.999\%$ uptime SLA globally across multi-AZ and multi-region AWS deployments.
• Latency:
  • 1-on-1 Message Delivery: $P50 < 30\text{ ms}$, $P99 < 100\text{ ms}$.
  • Presence State Broadcast: $P99 < 500\text{ ms}$.
• Data Durability: Zero message loss ($\text{Durability} \ge 99.999999999\% / \text{11 Nines}$) for all acknowledged messages.
• Connection Scale: Support $20,000,000$ concurrent active persistent WebSocket connections.
• Consistency: Monotonic sequence order per conversation ($K$-ordered Snowflake sequences); eventual consistency for global presence broadcasts.

---

2. Capacity & Scale Estimation (Back-of-the-Envelope Math)

User & Traffic Profile

• Daily Active Users (DAU): $100,000,000$ ($100\text{M DAU}$).
• Peak Concurrent WebSocket Connections: $20,000,000$ ($20\text{M concurrent sockets}$).
• Daily Messages Sent: $5.0 \times 10^9\text{ messages/day}$ (5 Billion messages/day).
• Average Message Size: $1\text{ KB}$ (Text content + metadata headers).

Throughput & QPS Derivations

• Average Message Ingest QPS: $\text{Ingest QPS}_{\text{avg}} = \frac{5 \times 10^9\text{ messages}}{86,400\text{ sec}} \approx \mathbf{57,870\text{ msg/sec}}$
• Peak Message Ingest QPS ($3\times$ multiplier): $\text{Ingest QPS}_{\text{peak}} = 57,870 \times 3 \approx \mathbf{173,610\text{ msg/sec}} \approx \mathbf{174,000\text{ QPS}}$
• Group Fan-Out Amplification: Assuming $40\%$ of messages are sent to groups with an average size of 8 active online members: $\text{Fan-Out Multiplier} = (0.60 \times 1) + (0.40 \times 8) = 0.60 + 3.20 = \mathbf{3.8\times}$ $\text{Peak Delivery Egress QPS} = 173,610 \times 3.8 \approx \mathbf{659,718\text{ msg/sec}} \approx \mathbf{660,000\text{ QPS}}$

Network Bandwidth

• Ingress Bandwidth (Writes): $\text{Bandwidth}_{\text{in}} = 174,000\text{ msg/sec} \times 1\text{ KB} = 174\text{ MB/sec} \approx \mathbf{1.39\text{ Gbps}}$
• Egress Bandwidth (Delivery to WebSocket Clients): $\text{Bandwidth}_{\text{out}} = 660,000\text{ msg/sec} \times 1\text{ KB} = 660\text{ MB/sec} \approx \mathbf{5.28\text{ Gbps}}$

Memory & Connection Fleet Sizing

• RAM per Idle WebSocket Connection: $\approx 10\text{ KB}$ (TCP socket buffer + SSL session context in kernel/user space).
• Total In-Memory Socket State: $\text{Socket Memory} = 20,000,000 \times 10\text{ KB} = 200,000,000\text{ KB} \approx \mathbf{200\text{ GB RAM}}$
• WebSocket Gateway Cluster Provisioning: Deploying ECS tasks sized like a c6g.2xlarge ($8\text{ vCPU}, 16\text{ GB RAM}$; on Fargate this is a task size, on EC2 launch type it is the instance type), capped at $50,000$ persistent sockets per task so that socket state stays near $500\text{ MB}$, file-descriptor limits are never approached, and a single task failure drops at most $0.25\%$ of the fleet's connections: $\text{Required Gateway Tasks} = \frac{20,000,000\text{ connections}}{50,000\text{ connections/node}} = \mathbf{400\text{ ECS Tasks}}$ Provisioned across 3 AWS Availability Zones ($134\text{ tasks/AZ}$).

Storage Footprint (5-Year Horizon)

• Daily Ingestion Storage: $\text{Daily Storage} = 5 \times 10^9\text{ msg/day} \times 1\text{ KB} = \mathbf{5\text{ TB/day}}$
• 5-Year Storage Footprint (Single Copy): $\text{Storage}_{5\text{yr}} = 5\text{ TB/day} \times 365.25 \times 5 \approx \mathbf{9.13\text{ PB}}$
• DynamoDB Throughput Provisioning:
  • Peak Write: $174,000\text{ msg/sec} \times 1\text{ KB} = \mathbf{174,000\text{ WCU}}$.
  • Peak Read (Sync + History): $\approx \mathbf{120,000\text{ RCU}}$.
  • DynamoDB partitions older messages ($> 90\text{ days}$) off to Amazon S3 Standard-IA / Glacier via DynamoDB Streams and Kinesis Data Firehose, reducing live transactional table size by $95\%$.

---

3. High-Level Architecture & AWS Component Mapping

Synthesizing vector architecture diagram...

Follow Alice's message to Bob. Both phones keep a WebSocket open, entering through Global Accelerator and the NLB to one gateway node. When a client connects, its gateway records it in the "Presence Registry & Pub/Sub Backplane" panel (Redis for presence, a DynamoDB registry with a 120 s TTL that heartbeats keep alive). Alice's gateway writes the message to Kinesis, and in the "Chat Ingestion & Pipeline" panel workers persist it to DynamoDB, then deliver it: if Bob is online, through Redis Pub/Sub to whichever gateway holds his socket; if he is offline, through SNS as a push notification. Writing to the stream before delivering means an acknowledged message is never lost, even if a gateway crashes.

Data Flow Walkthrough

1. Connection Establishment:
   • Clients connect via AWS Global Accelerator to the nearest edge PoP, traversing AWS dedicated fiber to an internal Network Load Balancer (NLB).
   • The NLB forwards TCP handshakes to the WebSocket Gateway Fleet (ECS Fargate running Rust/Netty).
   • Upon authentication, the gateway node records the connection mapping (user_id -> connection_id, node_ip) in ElastiCache Redis and DynamoDB Connection Registry (with a 120-second TTL), subscribing the gateway node to the user's private Redis Pub/Sub channel.
2. Message Ingestion & Sequencing:
   • Alice dispatches SEND_MESSAGE over her established WebSocket. The receiving gateway node generates a globally unique 64-bit Snowflake ID (server_msg_id), claims the next per-conversation sequence number with one atomic DynamoDB UpdateItem ... ADD seq :1 on the CONV#<id>/META item ($\approx 3\text{ ms}$), emits a MESSAGE_SENT_ACK back to Alice carrying both, and writes the event to Amazon Kinesis Data Streams.
   • Why two identifiers? Snowflake IDs are unique and roughly time-ordered across the whole platform, but two gateways can never produce a gap-free sequence for one conversation without coordination. The per-conversation counter is gap-free ($10482, 10483, \ldots$), which is what clients need for gap detection (Section 8.3) and offline catch-up; the Snowflake ID is what the platform needs for global uniqueness, idempotent persistence, and cross-conversation ordering (search, moderation, analytics).
   • Decoupled worker fleets on Amazon EKS consume from Kinesis, persisting the record to the ChatPlatformTable in Amazon DynamoDB.
3. Presence Evaluation & Real-Time Routing:
   • The worker inspects Bob's presence key in ElastiCache Redis (presence:usr_bob).
   • Case A (Bob Online): Redis returns Bob's active gateway node (WS_NODE_2). The worker executes PUBLISH channel:WS_NODE_2 payload, and WS_NODE_2 pushes the message to Bob's socket in $< 30\text{ ms}$.
   • Case B (Bob Offline): If no active presence exists, the worker enqueues a push payload to Amazon SNS, which relays to Apple APNs or Google FCM.
4. Offline Catch-Up Sync:
   • When Bob reconnects, his client presents its last confirmed sequence cursor (last_sync_seq). The gateway executes a range query against DynamoDB (SK > MSG#<last_sync_seq>) to stream missed messages in bulk, in order, with no gaps.

Concrete Step-by-Step Request Walkthrough: Tracing Direct Message & Delivery State

---

4. API Interface Design & Wire Protocols

1. Client-to-Gateway WebSocket Protocol (JSON Framing)

jsonCopy
// 1. Client Sending a Message
{
  "action": "SEND_MESSAGE",
  "client_msg_id": "9b1deb4d-3b7d-4bad-9bdd-2b0d7b3dcb6d",
  "conversation_id": "conv_991823",
  "recipient_id": "usr_bob_402",
  "content_type": "TEXT",
  "body": "Hey Bob, let's review the architectural blueprint.",
  "timestamp_client_ms": 1767225600120
}

// 2. Server Acknowledgment to Sender (Status: SENT)
{
  "event": "MESSAGE_SENT_ACK",
  "client_msg_id": "9b1deb4d-3b7d-4bad-9bdd-2b0d7b3dcb6d",
  "server_msg_id": "718293847561029384",
  "conversation_id": "conv_991823",
  "sequence_number": 10482,
  "timestamp_server_ms": 1767225600135
}

// 3. Server Delivery to Receiver Device
{
  "event": "RECEIVE_MESSAGE",
  "server_msg_id": "718293847561029384",
  "conversation_id": "conv_991823",
  "sender_id": "usr_alice_101",
  "content_type": "TEXT",
  "body": "Hey Bob, let's review the architectural blueprint.",
  "sequence_number": 10482,
  "timestamp_server_ms": 1767225600135
}

// 4. Client Read Receipt Update
{
  "action": "READ_RECEIPT",
  "conversation_id": "conv_991823",
  "last_read_sequence_number": 10482,
  "timestamp_read_ms": 1767225605000
}

2. REST Management Endpoints

Create / Initialize Conversation

httpCopy
POST /v1/conversations
Host: api.chat.aws.internal
Authorization: Bearer <jwt_access_token>
Content-Type: application/json

{
  "type": "DIRECT",
  "participants": ["usr_bob_402"]
}

Response: 201 Created
{
  "conversation_id": "conv_991823",
  "type": "DIRECT",
  "created_at": 1767225500000,
  "participants": ["usr_alice_101", "usr_bob_402"]
}

Fetch Historical Messages (Cursor-Based Pagination)

httpCopy
GET /v1/conversations/conv_991823/messages?limit=50&before_seq=10482
Host: api.chat.aws.internal
Authorization: Bearer <jwt_access_token>

Response: 200 OK
{
  "messages": [
    {
      "server_msg_id": "718293847561029384",
      "sender_id": "usr_alice_101",
      "body": "Hey Bob, let's review the architectural blueprint.",
      "sequence_number": 10482,
      "status": "READ",
      "timestamp_server_ms": 1767225600135
    }
  ],
  "has_more": false,
  "next_cursor": null
}

Pre-Signed URL for Media Uploads

httpCopy
POST /v1/media/upload-url
Host: api.chat.aws.internal
Authorization: Bearer <jwt_access_token>
Content-Type: application/json

{
  "conversation_id": "conv_991823",
  "content_type": "image/jpeg",
  "byte_size": 2048576
}

Response: 200 OK
{
  "upload_url": "https://chat-media-bucket.s3.amazonaws.com/uploads/conv_991823/img_01.jpg?AWSAccessKeyId=...",
  "cdn_url": "https://cdn.chat.internal/media/conv_991823/img_01.jpg",
  "expires_in_seconds": 900
}

---

5. Data Models & DynamoDB Single-Table Schema

To achieve predictable sub-millisecond query performance at PB scale, we utilize a single-table DynamoDB design partitioned by conversation_id and sorted by the gap-free per-conversation sequence number (zero-padded so lexical order equals numeric order). The Snowflake server_msg_id is stored as an attribute and is the idempotency key for the persistence worker.

DynamoDB Table: ChatPlatformTable

• Partition Key (PK): Entity identifier.
• Sort Key (SK): Specific entity instance or sequence cursor.
• Global Secondary Index 1 (GSI1): Inbox index (GSI1-PK: USER#<user_id>, GSI1-SK: UPDATED#<timestamp>) for listing user chats.

Range Query for Message History & Offline Catch-Up

jsonCopy
{
  "TableName": "ChatPlatformTable",
  "KeyConditionExpression": "PK = :conv_pk AND SK > :last_sync_sk",
  "ExpressionAttributeValues": {
    ":conv_pk": {"S": "CONV#conv_991823"},
    ":last_sync_sk": {"S": "MSG#000000010481"}
  },
  "Limit": 50,
  "ScanIndexForward": true
}

---