System requirements

Functional:

One-on-one and group chat: Support text, images, videos, voice messages, and file sharing.

Presence: Show online/offline status.

Push notifications: For new messages and other events.

Message history: Store and retrieve past conversations.

Read receipts: Indicate message delivery and read status.

Calls and video calls: Real-time audio and video communication.

Non-Functional:

Low latency: Real-time message delivery.

High availability: Minimal downtime.

Scalability: Handle millions of concurrent users.

Reliability: Ensure message delivery and consistency.

Security: End-to-end encryption, user authentication.

Capacity estimation

1 million daily active users

Average 10 messages sent per user per day

Peak hours with 20% of users active simultaneously

Daily messages: 1 million users * 10 messages/user = 10 million messages

Messages per second (average): 10 million messages / 86400 seconds/day ≈ 116 messages/second

Peak concurrent users: 1 million users * 20% = 200,000 users

Peak messages per second: 116 messages/second * (200,000 users / 1 million users) = 232 messages/second

API design

Send a message:

POST /v1/conversations/{conversation_id}/messages

Get a message:

GET /v1/conversations/{conversation_id}/messages?limit=20

Update user profile:

PUT /v1/users/{user_id}

Database design

Users table:

• UserID (primary key)
• Name
• Email
• Profile Picture URL
• Status
• Last Seen

Messages table:

• MessageID (primary key)
• ConversationID (foreign key)
• SenderID (foreign key)
• Content
• Timestamp
• Type
• Status

Conversations table:

• ConversationID (primary key)
• Type
• CreatedAt

Participants table:

• ConversationID (foreign key)
• UserID (foreign key)

High-level design

Connection: When a user opens Messenger, the client establishes a WebSocket connection with the Chat Service. This connection is persistent and bi-directional.

Authentication: The client authenticates with the API Gateway, which verifies the user's identity.

Real-time Messaging:

• When a user sends a message, the client sends it to the Chat Service via the WebSocket connection.
• The Chat Service immediately delivers the message to the recipient(s) through their active WebSocket connections.
• Simultaneously, the Chat Service publishes the message to a message queue (e.g., Kafka) for persistence and to handle cases where the recipient is offline.

Offline Messages:

• If a recipient is offline, the message is stored in the message queue.
• When the recipient comes online and establishes a WebSocket connection, the Chat Service retrieves any pending messages from the queue and delivers them via the WebSocket.

History Service:

• The Chat Service also sends the message to the History Service to store it in the database (e.g., Cassandra) for persistent storage and retrieval of message history.

Notifications:

• For offline users, the Notification Service sends a push notification (via APNs or FCM) to inform them of the new message.

Request flows

1. Client-side:
   • User A composes a message in the Messenger app.
   • The client initiates a WebSocket connection to the Chat Service if one isn't already established.
   • The client sends a "send message" request over the WebSocket connection, including the message content, sender ID (User A), and recipient ID (User B).
2. API Gateway:
   • The WebSocket connection is routed through the API Gateway.
   • The API Gateway authenticates the request to verify User A's identity.
3. Chat Service:
   • Real-time Delivery:
     • The Chat Service receives the message and checks if User B is online and has an active WebSocket connection.
     • If User B is online, the Chat Service immediately delivers the message to User B's client via their WebSocket connection.
   • Persistence:
     • The Chat Service publishes the message to a message queue (e.g., Kafka) for persistence and to handle cases where User B is offline.
   • History:
     • The Chat Service sends the message to the History Service to be stored in the database (e.g., Cassandra).
4. History Service:
   • The History Service stores the message with relevant information (sender, recipient, timestamp, etc.) in the database.
5. Notification Service (if User B is offline):
   • The Chat Service notifies the Notification Service that User B has a new message.
   • The Notification Service sends a push notification to User B's device (via APNs or FCM) to inform them of the new message.
6. User B receives the message:
   • Online: If User B is online, they receive the message instantly via their WebSocket connection.
   • Offline: If User B is offline, they receive a push notification. When they open the Messenger app and establish a WebSocket connection, the Chat Service retrieves the pending message from the message queue and delivers it.

Additional Considerations:

• Presence Updates: The Chat Service continuously updates presence information (online/offline status) in the Presence service (Redis) and broadcasts these updates to relevant clients via WebSockets.
• Media Messages: If the message includes media (images, videos), the Chat Service interacts with the Media Service to store and deliver the media content.
• Group Chats: The flow is similar for group chats, with the Chat Service delivering the message to

Detailed component design

History Service

• Functionality:
  • Store and retrieve message history
  • Search and filter messages
• Scalability:
  • Data partitioning: Cassandra partitions data by conversation ID. This allows distributing data across multiple nodes and enables efficient retrieval of messages within a specific conversation.
  • Secondary indexes: Secondary indexes can be created on columns like sender ID or timestamp to support different query patterns. However, overuse of secondary indexes can impact write performance, so they should be used judiciously.
  • Read replicas: Cassandra allows creating read replicas of data to handle read-heavy workloads. This improves read performance and availability.
• Data Structures and Algorithms:
  • Sorted Merge Tree (SMT): Cassandra uses SMTs as its primary data structure. SMTs are efficient for storing sorted data and support range queries, which are common for retrieving message history within a time frame.

. Chat Service

• Functionality:
  • Real-time message delivery
  • Presence management
  • Connection management
• Scalability:
  • Horizontal scaling: Multiple instances of the Chat Service can be deployed to handle increasing traffic. This is achieved by using a load balancer to distribute incoming connections across the instances.
  • Sharding: To distribute the load even further and avoid a single point of failure, we can implement sharding. This involves partitioning users across different Chat Service instances based on their user ID. A consistent hashing algorithm can be used to map user IDs to shards, ensuring even distribution.
  • Asynchronous processing: Leveraging message queues for offline messaging allows the Chat Service to handle message delivery asynchronously. This prevents delays and ensures a smooth user experience even during peak usage.
• Data Structures and Algorithms:
  • Consistent Hashing: For sharding, consistent hashing ensures that most users remain on the same shard even when new shards are added or removed, minimizing data migration.
  • Priority Queue: Within each shard, a priority queue can be used to manage message delivery. Messages with higher priority (e.g., real-time messages to online users) are delivered first.

Trade offs/Tech choices

. NoSQL (Cassandra) vs. SQL Database for History Service

• Choice: Cassandra (NoSQL)
• Trade-off: Potentially less robust data consistency vs. high write throughput and scalability.
• Rationale: Cassandra's ability to handle massive write volumes and scale horizontally makes it a better choice for storing message history than a traditional SQL database. While it offers eventual consistency rather than strong consistency, this is an acceptable trade-off for a messaging system where slight delays in data consistency are generally tolerable

Redis vs. Memcached for Presence Service

• Choice: Redis
• Trade-off: Potentially higher memory usage vs. more advanced data structures and features.
• Rationale: Redis provides more advanced data structures (e.g., sorted sets) and features (e.g., pub/sub) that are useful for managing presence information and real-time updates. While it might consume slightly more memory than Memcached, its added functionality and flexibility make it a better fit for this use case.

Failure scenarios/bottlenecks

WebSocket Connection Failures:

• Scenario: Network issues, server overload, or bugs can cause WebSocket connections to drop.
• Mitigation:
  • Implement robust reconnection mechanisms on the client-side.
  • Utilize connection monitoring and heartbeats to detect and handle disconnections proactively.
  • Employ load balancing to distribute connections and prevent overload on individual servers.

Publish-Subscribe System (Kafka) Failures:

• Scenario: Kafka brokers going down, network partitions within the Kafka cluster, or issues with ZooKeeper (which Kafka uses for coordination) can disrupt message delivery.
• Mitigation:
  • Run Kafka with multiple brokers and partitions for redundancy.
  • Implement message delivery retries with exponential backoff.
  • Monitor Kafka health and performance metrics closely.

Future improvements

Kafka/RabbitMQ Failures: Utilize robust monitoring and alerting systems to quickly detect and address issues. Implement automatic failover mechanisms for brokers and queues.

Cassandra Failures: Employ multi-data center replication to ensure high availability even in case of regional outages. Regularly perform disaster recovery drills to test resilience.