Design a Chat System

Functional:
  - 1:1 messaging
  - Group messaging (up to 500 members)
  - Read receipts, typing indicators
  - Online/offline presence
  - Message history search

Non-functional:
  - Message delivery latency: < 100ms (online users)
  - Message ordering: Per-conversation
  - Durability: No message loss
  - 500M daily active users
  - 100B messages per day

User ──WebSocket──► Chat Server Instance
                     │
                     ├── User → Server mapping (Redis):
                     │   user:123 → server-us-east-1a
                     │   user:456 → server-us-west-2a
                     │
                     └── Server → User mapping (local):
                         server-us-east-1a → [user:123, user:789, ...]

Message routing:
  Sender (server-us-east-1a) → Lookup receiver's server → Forward

1. User A sends message to User B
2. Chat server A receives message
3. Assign monotonically increasing message ID
4. Store message in database
5. Lookup User B's connected server
6. If online: Forward to Chat server B → Deliver via WebSocket
7. If offline: Store in message queue for later delivery
8. Send delivery receipt to User A

# On each heartbeat (every 30 seconds):
def heartbeat(user_id: str):
    redis.setex(f"presence:{user_id}", 90, "online")
    # TTL of 90 seconds = 3 missed heartbeats = offline

# To check presence:
def is_online(user_id: str) -> bool:
    return redis.exists(f"presence:{user_id}")

# Background worker to detect offline users:
def check_stale_presences():
    # Scan for keys that have expired
    # Publish presence-change events to all interested clients

CREATE TABLE messages (
    conversation_id UUID,
    message_time TIMESTAMP,
    message_id TIMEUUID,
    sender_id UUID,
    content TEXT,
    PRIMARY KEY (conversation_id, message_time, message_id)
) WITH CLUSTERING ORDER BY (message_time DESC);

-- Query: Get last 50 messages in a conversation
SELECT * FROM messages 
WHERE conversation_id = ?
ORDER BY message_time DESC 
LIMIT 50;