Designing an Instant Messaging System
High Level Design·intermediate·~30 min read
- system-design
- messaging
- chat
- distributed-systems
- hld
What you'll learn
Problem Statement
Design a real-time messaging system supporting 1:1 chat, group chat, and online presence. Messages must be delivered in milliseconds to online users and persisted permanently. The system handles hundreds of millions of concurrent connect…
Requirements
Functional Requirements
1. 1:1 messaging — send/receive text messages between two users 2. Online/Offline status — show when contacts are available 3. Persistent message history — messages stored and accessible on any device 4. Group chat — multi-user conversat…
Non-Functional Requirements
1. Real-time delivery — Note on server sizing: The number of servers depends on how many connections each can hold. At 50K persistent connections per server (a conservative, production-safe figure), you need ~10K servers. At 5M connectio…
Design Evolution & Trade-offs
How this system grew from an MVP to what a production version looks like — and the choices you'd defend in an interview. Real messaging systems are not born with 10K chat servers, HBase clusters, and Redis routing registries. They start…
Stage 1 — MVP: One box, one database
The simplest thing that could possibly work for a chat app. - A single API server (monolith) exposing REST endpoints: POST /messages, GET /conversations/:id/messages. - A single relational database (Postgres) with two tables: users and m…
Stage 3 — Bottleneck: Connection state & message routing at scale
This is the problem that separates messaging from every other system-design topic. In a photo-sharing app or a URL shortener, every request is independent — any server can handle it. In messaging, a message from A→B is worthless unless i…
Cost vs Complexity — When to Pick What
| Concern | MVP choice | Growth choice | Enterprise choice | |---------|-----------|---------------|-------------------| | Transport | HTTP long-poll | WebSocket over TLS | WebSocket + QUIC fallback, geo-distributed edge terminators | |…
Migration Path (MVP → Enterprise)
The order matters. Each step buys you 5–10× more headroom, and each depends on the previous being stable. 1. Add WebSocket (or long-poll) push. Kill polling first — this is the single biggest latency win. Depends on: nothing. 2. Introduc…
High-Level Architecture
---
Detailed Component Design
Chat Server
Each chat server: - Holds millions of concurrent WebSocket connections - Maintains in-memory Connection Map: UserID → WebSocket - Processes incoming messages and routes them to recipients - Writes messages to persistent storage (async)
Message Router / Multiplexer Pattern
At 12K+ writes/second, you cannot give each user their own dedicated queue — "you can't have 1M queues." Instead, use a Message Router pattern: How it works: 1. A single inbound queue receives all new messages 2. The Message Router persi…
Routing Layer
When User A wants to message User B: - A's chat server needs to know WHICH server holds B's connection - Solution: Distributed routing registry (Redis cluster or consistent hashing) ---
Message Storage: Wide-Column Deep Dive
Why Wide-Column DB (HBase)?
The workload is write-heavy with sequential reads — the exact pattern wide-column stores are optimized for: 1. High-rate small writes: Messages are tiny (~100 bytes) arriving at massive throughput. HBase buffers these in memory then flus…
Why Not Other Databases?
| Database | Problem at This Scale | |----------|----------------------| | PostgreSQL/MySQL | B-tree writes are random I/O; 230K/s sustained writes causes disk thrashing; replication lag at this write volume | | MongoDB | Document model…
Data Model
Write Path (LSM-Tree Advantage)
Why this is fast: Steps 1-3 are in-memory (microseconds). The expensive disk work happens in the background. The client never waits for disk I/O.
Read Path
---
Message Ordering: Sequence Numbers
The Problem
Distributed systems cannot rely on timestamps: - Client clocks are inaccurate (seconds or minutes of skew) - Network delays can reorder packets - Two messages sent "simultaneously" need deterministic ordering
Why Not Timestamps?
Server-assigned timestamps cannot guarantee causal order that both parties perceive. Consider: - A sends "Want to grab lunch?" at timestamp 100 - B sends "I'm hungry" at timestamp 99 (B's clock is slightly ahead, or network is slightly f…
Per-Client Sequence Numbers for Multi-Device
Each client maintains its own sequence counter. When User A sends from Phone and Tablet simultaneously: - Phone sends with clientseq=5 - Tablet sends with clientseq=3 - Server sees both arrive, assigns a global conversation sequence to e…
Solution: Per-Conversation Atomic Counter
Client Synchronization
---
Online Status Service
Heartbeat Protocol
Why 5 Seconds?
| Interval | Trade-off | |----------|-----------| | 1 second | Very responsive but 500M heartbeats/second = 500M QPS | | 5 seconds | Good balance: 100M heartbeats/sec, 15s detection delay | | 30 seconds | Low overhead but unacceptable st…
Fan-out Optimization (Critical for Scale)
Naive: User A comes online → notify all 500 friends = 250 billion notifications/day at system scale Seven optimizations: 1. Do NOT broadcast online/offline to all friends — this is the single biggest mistake in status design 2. Pull on a…
Data Partitioning
Strategy: Hash on UserID
Alternative: Conversation-Based Sharding (1:1 Chat)
For 1:1 conversations specifically, an alternative approach avoids message duplication: By sorting the two IDs before hashing, all messages for a 1:1 conversation between User A and User B land on the same shard regardless of who sent th…
Why UserID (Not ConversationID)?
| If shard by UserID | If shard by ConversationID | |-------------------|---------------------------| | "Load all my conversations" = single-shard query | "Load all my conversations" = scatter-gather across many shards | | "Sync messages…
Logical vs Physical Partitioning
Start with many logical partitions mapped to fewer physical servers, then add physical capacity over time: Why this matters: If you hash directly to physical servers (hash(UserID) % numservers), adding a server reshuffles almost everythi…
The Duplication Trade-off
When A sends to B: - Message stored on A's shard (Shard 342) - Message ALSO stored on B's shard (Shard 891) Cost: 2x write amplification (store everything twice) Benefit: Every user's "load conversations" is a single-shard O(1) query At…
Caching Strategy
Per-User Message Cache
Cache Invalidation
- On new message: Append to cache (push oldest out) - On reconnect: Load from cache; if insufficient, hit DB for older messages - On conversation delete: Evict from cache ---
Handling Offline Users
Message Delivery States
---
Group Chat
Architecture
Storage for Group Messages
Difference from 1:1: - 1:1 messages duplicated (per-user sharding) - Group messages stored once (per-group sharding) - Separate table/column family for group messages ---
Fault Tolerance
Chat Server Failure
Database Replication
Network Partitions
- Reed-Solomon coding (optional): Erasure coding for extreme durability - Client-side retry: Failed sends are queued locally and retried - Idempotent delivery: Sequence numbers prevent duplicate delivery on retry ---
Load Balancing
Connection Assignment
When a new WebSocket connection comes in: 1. DNS/L4 load balancer routes to any available chat server 2. Prefer: Least Connections algorithm (balance connection count) 3. Alternative: Consistent hashing on UserID (same user always connec…
Internal Load Balancing
- Chat Server → DB: Requests routed to the user's shard (deterministic) - Chat Server → Chat Server: Direct connection for message forwarding - Status Service: Sharded by UserID (same as messages) ---
End-to-End Message Flow (Complete)
---
Key Trade-offs and Design Decisions
Consistency Over Availability
This system explicitly favors consistency over availability. Users must see the same message history on all their devices. If a partition occurs, it is better to temporarily refuse new messages than to deliver them inconsistently (which…
DB Writes Are Asynchronous to Acknowledgment
The server ACKs the sender immediately (after writing to the WAL/memtable), then persists to durable storage in the background. This keeps send latency under 100ms while still guaranteeing durability — the WAL ensures the message survive…
TCP Connection Failover is Impractical
Rather than attempting sophisticated TCP connection migration (handing off a connection from a dying server to a new one), the system relies on client auto-reconnect. Clients detect disconnection, reconnect with exponential backoff, and…
Queue-Per-User Does Not Scale
A naive design might create one message queue per user (500M queues). This is operationally impossible — queue infrastructure cannot manage millions of queues efficiently. The Message Router + handler-bucket pattern keeps queue count fix…
Summary: Key Architecture Decisions
| Decision | What it Solves | |----------|---------------| | WebSocket connections | Real-time bidirectional messaging | | In-memory connection map | O(1) routing to recipient's connection | | Redis routing registry | O(1) lookup of whic…