Design a geo-distributed Chat System

Question

Design a geo-distributed chat system that handles millions of requests. Discuss trade-offs in consistency, availability, and performance.

Codemia · Accepted Answer

### Functional Requirements:
1. **Real-time Messaging**: Users should be able to send and receive messages instantly.
2. **User Presence**: Display online/offline status of users.
3. **Group Chats**: Support for one-on-one and group conversations.
4. **Message History**: Users should access previous messages.
5. **File Sharing**: Ability to send images and documents.

### Non-Functional Requirements:
1. **Scalability**: Support millions of concurrent users globally.
2. **Low Latency**: Messages should be delivered within milliseconds.
3. **High Availability**: System should have 99.99% uptime.
4. **Data Consistency**: Ensure messages are delivered exactly once without loss.
5. **Security**: End-to-end encryption for all messages.

Assuming:
- 10 million active users.
- Each user sends an average of 10 messages per day.
- Peak traffic: 1000 messages per second.

### Calculations:
1. **Total Messages per Day**: 10 million users * 10 messages = 100 million messages/day.
2. **Messages per Second**: 100 million / 86400 seconds in a day ≈ 1157 messages/second.
3. **Peak Load**: To accommodate burst traffic, assume a peak of 1,000 messages/second (allowing for spikes).
4. **Storage Needs**: If each message averages 1KB, daily storage = 100 million KB = ~100 GB/day, requiring estimates of 36.5 TB/year.

### Component Diagram:
- **Frontend**: React.js for the web client, native mobile apps for iOS/Android.
- **API Gateway**: AWS API Gateway to manage requests and rate limiting.
- **Message Broker**: Apache Kafka for handling real-time message streams.
- **Microservices**:
  - **User Service**: Handles user authentication and presence.
  - **Messaging Service**: Manages message storage and retrieval.
  - **Notification Service**: Sends real-time notifications for new messages.
- **Database**: Amazon DynamoDB for NoSQL storage (eventual consistency) and Redis for caching.
- **Global Load Balancer**: AWS Global Accelerator to route user traffic to the nearest data center.

### Schema Design:
1. **Users Table**:
   - `user_id`: string (PK)
   - `username`: string
   - `status`: string (online/offline)
   - `last_active`: timestamp

2. **Messages Table**:
   - `message_id`: string (PK)
   - `sender_id`: string (FK)
   - `receiver_id`: string (FK, can be a group ID)
   - `content`: string
   - `timestamp`: timestamp

3. **Groups Table**:
   - `group_id`: string (PK)
   - `member_ids`: list of user IDs

### Access Patterns:
- Frequent reads for message retrieval and user status.
- Writes on message sending and user presence updates.

### Architectural Decisions:
1. **CAP Theorem**: Prioritize availability and partition tolerance (AP) over strong consistency. Use eventual consistency for message delivery.
2. **Caching Strategy**: Use Redis for caching user presence and frequently accessed messages to reduce DB load.
3. **Conflict Resolution**: Implement last-write-wins with timestamps and handle conflicts in the messaging service.
4. **Operational Excellence**: Deploy using CI/CD pipelines, monitor with AWS CloudWatch, and use chaos engineering to test system resilience. Define SLOs for message delivery times and system uptime.

Design a geo-distributed Chat System

Capital One

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Practice a Similar Problem on Codemia

Sample Answer

Requirements

Functional Requirements:

Capacity Estimation

Calculations:

Submit Your Answer

Capital One Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search