WhatsApp Messaging System Design

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

SENDER'S DEVICE                    SERVER                    RECIPIENT'S DEVICE
━━━━━━━━━━━━━━━━━                    ━━━━━━                    ━━━━━━━━━━━━━━━━━━
 
1. User types message
   └── [Draft stored locally]
 
2. User presses send
   └── [Clock icon: Pending]
       │
       ├──── CREATE(msg_id, content, timestamp) ────────►
       │                                                  │
       │                                     3. Validate & persist
       │                                        └── [Write to queue]
       │                                        └── [Write to DB]
       │                                                  │
       │     ◄──────── ACK(msg_id, "ACCEPTED") ──────────┤
       │                                                  │
   └── [Single ✓: Sent]                                   │
                                                          │
                                          4. Route to recipient
                                             └── [Find recipient connection]
                                             └── [Push if online]
                                                          │
                                                          ├────── PUSH(msg_id, content) ────────►
                                                          │                                       │
                                                          │              5. Recipient receives
                                                          │                 └── [Store locally]
                                                          │                 └── [Display in UI]
                                                          │                 └── [Notify user]
                                                          │                                       │
                                                          │     ◄─── ACK(msg_id, "DELIVERED") ───┤
                                                          │
                                          6. Record delivery
                                             └── [Update message status]
                                                          │
       │     ◄────── NOTIFY(msg_id, "DELIVERED") ────────┤
       │
   └── [Double ✓✓: Delivered]
 
                                      [... User opens chat ...]
 
                                                          ├──── SEEN(msg_id, timestamp) ────────►
                                                          │                                       │
       │     ◄────── NOTIFY(msg_id, "READ") ─────────────┤
       │
   └── [Blue ✓✓: Read]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// Strategy 1: UUID v4 (Random)
// ─────────────────────────────
// Pros: Truly random, extremely low collision probability
// Cons: No ordering, 128 bits (16 bytes), not human-readable
import { v4 as uuidv4 } from 'uuid';
const messageId = uuidv4();  // "550e8400-e29b-41d4-a716-446655440000"
 
// Strategy 2: Snowflake ID (Twitter's approach)
// ─────────────────────────────────────────────
// 64-bit ID: timestamp (41b) + datacenter (5b) + worker (5b) + sequence (12b)
// Pros: Time-ordered, compact, high throughput (4096 IDs/ms per worker)
// Cons: Requires worker ID coordination
function generateSnowflakeId(datacenterId: number, workerId: number): bigint {
    const timestamp = BigInt(Date.now() - EPOCH);  // Custom epoch
    const sequence = getNextSequence();  // Increment per millisecond
    return (timestamp << 22n) | (BigInt(datacenterId) << 17n) | 
           (BigInt(workerId) << 12n) | BigInt(sequence);
}
 
// Strategy 3: ULID (Universally Unique Lexicographically Sortable ID)
// ──────────────────────────────────────────────────────────────────
// 128-bit: timestamp (48b) + randomness (80b)
// Pros: Time-ordered, sortable as strings, no coordination needed
// Cons: Slightly longer than Snowflake
import { ulid } from 'ulid';
const messageId = ulid();  // "01ARZ3NDEKTSV4RRFFQ69G5FAV"
 
// Strategy 4: Composite ID (Recommended for messaging)
// ────────────────────────────────────────────────────
// Combine device ID + local counter + timestamp
const messageId = `${deviceId}_${localCounter}_${Date.now()}`;
// This allows:
// - Client-side generation without server coordination
// - Natural ordering within a device's messages
// - Deduplication based on device + sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Protocol Buffer definition for acknowledgments
message Acknowledgment {
    string message_id = 1;           // Which message this ACK is for
    AckType type = 2;                // Type of acknowledgment
    int64 timestamp = 3;             // When the event occurred
    string sender_id = 4;            // Who sent this ACK
    optional string error_code = 5;  // Error details if REJECTED/FAILED
}
 
enum AckType {
    ACK_UNKNOWN = 0;
    ACK_ACCEPTED = 1;     // Server accepted message
    ACK_DELIVERED = 2;    // Recipient device received
    ACK_SEEN = 3;         // Recipient viewed message
    ACK_REJECTED = 4;     // Message rejected by server
    ACK_FAILED = 5;       // Delivery failed permanently
}
 
// Batch acknowledgments for efficiency
message BatchAcknowledgment {
    repeated Acknowledgment acks = 1;
}
 
// Example: Acknowledge 10 "delivered" receipts in one network call
// This reduces connections by 10x for high-volume scenarios

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

interface RetryConfig {
    initialDelayMs: number;      // First retry delay
    maxDelayMs: number;          // Cap on delay growth
    exponentialBase: number;     // Multiplier per retry
    maxRetries: number;          // Give up after this many
    jitterFactor: number;        // 0-1, randomization amount
}
 
const DEFAULT_CONFIG: RetryConfig = {
    initialDelayMs: 500,         // Start at 500ms
    maxDelayMs: 60000,           // Cap at 1 minute
    exponentialBase: 2,          // Double each time
    maxRetries: 10,              // Try up to 10 times
    jitterFactor: 0.3,           // ±30% randomization
};
 
function calculateRetryDelay(attempt: number, config: RetryConfig): number {
    // Exponential growth: delay = initial * base^attempt
    const exponentialDelay = config.initialDelayMs * 
                             Math.pow(config.exponentialBase, attempt);
    
    // Cap at maximum
    const cappedDelay = Math.min(exponentialDelay, config.maxDelayMs);
    
    // Add jitter: ±jitterFactor around the delay
    const jitterRange = cappedDelay * config.jitterFactor;
    const jitter = (Math.random() * 2 - 1) * jitterRange;  // Random in [-range, +range]
    
    return Math.max(0, cappedDelay + jitter);
}
 
// Example retry sequence (approximate, varies with jitter):
// Attempt 1: ~500ms
// Attempt 2: ~1000ms  
// Attempt 3: ~2000ms
// Attempt 4: ~4000ms
// Attempt 5: ~8000ms
// Attempt 6+: ~60000ms (capped)
 
async function sendWithRetry<T>(
    operation: () => Promise<T>,
    config: RetryConfig = DEFAULT_CONFIG
): Promise<T> {
    let lastError: Error;
    
    for (let attempt = 0; attempt < config.maxRetries; attempt++) {
        try {
            return await operation();
        } catch (error) {
            lastError = error as Error;
            
            // Don't retry non-retryable errors
            if (isNonRetryable(error)) {
                throw error;
            }
            
            const delay = calculateRetryDelay(attempt, config);
            console.log(`Retry attempt ${attempt + 1} after ${delay}ms`);
            await sleep(delay);
        }
    }
    
    throw new Error(`Operation failed after ${config.maxRetries} retries: ${lastError.message}`);
}
 
function isNonRetryable(error: any): boolean {
    // These errors won't be fixed by retrying
    return [
        'INVALID_MESSAGE',
        'USER_BLOCKED',
        'GROUP_NOT_FOUND',
        'AUTHENTICATION_FAILED',
    ].includes(error.code);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

SCENARIO 1: FIFO VIOLATION (Unacceptable)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Alice sends:     [1] "Hey!" → [2] "How are you?" → [3] "Want to grab lunch?"
Bob receives:    [2] "How are you?" → [1] "Hey!" → [3] "Want to grab lunch?"
 
Confusing! Bob sees "How are you?" before "Hey!"
 
 
SCENARIO 2: CAUSALITY VIOLATION (Unacceptable)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Alice: [1] "What's the capital of France?"
Bob:   [2] "Paris" (reply to message 1)
 
Charlie sees: [2] "Paris" → [1] "What's the capital of France?"
 
Completely confusing! Answer appears before question.
 
 
SCENARIO 3: ACCEPTABLE TOTAL ORDER DIFFERENCE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
At 10:00:00.100, Alice sends "Hello"
At 10:00:00.150, Bob sends "Hi there" (independent, not a reply)
 
Alice sees: "Hello" → "Hi there"
Bob sees:   "Hi there" → "Hello"
 
These are causally unrelated (sent concurrently without knowledge of each other).
Different ordering is acceptable, though showing same order is nicer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

CLIENT              PRIMARY             REPLICA-1           REPLICA-2
  │                    │                    │                    │
  │──SEND(msg)───────►│                    │                    │
  │                    │──REPLICATE────────►│                    │
  │                    │──REPLICATE───────────────────────────► │
  │                    │                    │                    │
  │                    │◄──ACK──────────────│                    │
  │                    │◄──ACK────────────────────────────────── │
  │                    │                    │                    │
  │                   [Wait for quorum: 2 of 3 ACKs]
  │                    │                    │                    │
  │◄──ACK(msg_id)──────│                    │                    │
  │                    │                    │                    │
 
Message is now durable: survives any single node failure.
Latency = max(RTT to replica-1, RTT to replica-2) + processing time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

interface SyncRequest {
    // Last known state for each conversation
    lastSyncTimestamps: Map<ConversationId, Timestamp>;
    
    // Or, simplified: single global sync point
    globalLastSyncTimestamp: Timestamp;
    
    // Maximum messages to receive per batch
    batchSize: number;
    
    // Whether to also fetch full media or just placeholders
    includeMedia: boolean;
}
 
interface SyncResponse {
    // Messages since last sync
    messages: Message[];
    
    // Are there more messages to fetch?
    hasMore: boolean;
    
    // New sync point (use this for next sync)
    newSyncTimestamp: Timestamp;
    
    // Conversations that have updates
    updatedConversations: ConversationMetadata[];
}
 
// Efficient sync flow:
// 1. Client connects with last sync timestamp
// 2. Server calculates: messages WHERE timestamp > lastSync
// 3. Server sends first batch (50-100 messages)
// 4. Client stores locally, updates UI
// 5. If hasMore, client requests next batch
// 6. Repeat until all caught up
 
// Optimization: Delta sync
// Instead of sending full messages, send only:
// - New messages (full content)
// - Status updates for existing messages (just IDs + new status)
// - Deleted message IDs (just IDs)
// This reduces bandwidth significantly for active users

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

interface MessageStore {
    // Returns true if message was stored, false if duplicate
    storeIfNotExists(message: Message): Promise<boolean>;
    
    // Get existing message by ID
    getById(messageId: string): Promise<Message | null>;
}
 
class MessageHandler {
    private store: MessageStore;
    private dedupeCache: LRUCache<string, boolean>;
    
    constructor(store: MessageStore) {
        this.store = store;
        // Hot cache for recent message IDs
        // 10M entries × ~32 bytes = ~320MB
        this.dedupeCache = new LRUCache<string, boolean>({ max: 10_000_000 });
    }
    
    async handleIncomingMessage(message: Message): Promise<HandleResult> {
        const messageId = message.id;
        
        // Fast path: check in-memory cache
        if (this.dedupeCache.has(messageId)) {
            // Definite duplicate - acknowledge without processing
            return { status: 'DUPLICATE', ack: true };
        }
        
        // Slow path: check database
        const stored = await this.store.storeIfNotExists(message);
        
        if (!stored) {
            // Database reports duplicate
            this.dedupeCache.set(messageId, true);
            return { status: 'DUPLICATE', ack: true };
        }
        
        // New message - proceed with processing
        this.dedupeCache.set(messageId, true);
        await this.routeToRecipient(message);
        return { status: 'NEW', ack: true };
    }
}
 
// Database implementation using INSERT ... ON CONFLICT
// PostgreSQL example:
async function storeIfNotExists(message: Message): Promise<boolean> {
    const result = await db.query(`
        INSERT INTO messages (id, sender_id, content, created_at)
        VALUES ($1, $2, $3, $4)
        ON CONFLICT (id) DO NOTHING
        RETURNING id
    `, [message.id, message.senderId, message.content, message.createdAt]);
    
    return result.rowCount > 0;  // True if inserted, false if conflict
}