Design a Distributed Message Queue

Question

Design a distributed message queue system like Kafka. Cover partitioning strategies, consumer groups, exactly-once delivery semantics, replication, and handling backpressure at Meta's scale.

Codemia · Accepted Answer

### Functional Requirements
1. **Message Production**: The system should allow producers to publish messages to specific topics with a defined schema.
2. **Message Consumption**: Consumers should be able to subscribe to topics and receive messages in real-time.
3. **Partitioning**: Topics must be partitioned to facilitate parallel processing and load balancing among consumers.
4. **Consumer Groups**: Support consumer groups to allow multiple consumers to share the workload of processing messages from a topic.
5. **Message Acknowledgment**: Consumers must acknowledge messages to ensure they are processed only once.
6. **Exactly-Once Delivery**: Implement mechanisms to ensure messages are delivered exactly once to consumers.

### Non-Functional Requirements
1. **Scalability**: The system should scale horizontally to handle millions of messages per second.
2. **Availability**: The system should ensure high availability, with a downtime of less than 5 minutes per year.
3. **Durability**: Messages must be persisted to disk to prevent data loss.
4. **Latency**: The end-to-end latency from message production to consumption should be less than 100 milliseconds.
5. **Backpressure Handling**: The system should manage backpressure by throttling producers and consumers when necessary.

Let's estimate the scale at Meta. Assuming:
- **Number of Daily Active Users**: 3 billion
- **Average Messages per User per Day**: 50
- **Message Size**: 1 KB

#### Daily Message Volume
Total messages per day = 3 billion users * 50 messages/user = 150 billion messages/day.

#### Hourly Message Volume
Hourly messages = 150 billion / 24 hours = 6.25 billion messages/hour.

#### Per Second Message Volume
Per second messages = 6.25 billion / 3600 seconds ≈ 1.74 million messages/second.

#### Storage Requirements
If we retain messages for 7 days, total data storage = 150 billion messages/day * 7 days * 1 KB/message = 1.05 PB.

Thus, we need a system capable of handling at least 1.74 million messages per second and 1.05 PB of storage.

### Component Diagram
The architecture consists of the following components:
1. **Producers**: Applications that send messages to the message queue.
2. **Message Broker**: A distributed system (e.g., using Apache Kafka) that receives, stores, and serves messages.
3. **Partitions**: Each topic is divided into multiple partitions for load balancing.
4. **Consumers**: Services that read messages from the broker, grouped into consumer groups.
5. **Zookeeper**: For managing broker metadata and leader election.
6. **Schema Registry**: To manage and enforce message schemas.
7. **Monitoring Tools**: Tools like Prometheus and Grafana to monitor the health and performance of the system.

### Technology Choices
- **Message Broker**: Apache Kafka for its scalability and durability.
- **Database**: Apache Cassandra for storing message metadata and offsets.
- **Streaming Framework**: Apache Flink for processing streams of messages.

### Schema Design
1. **Topics Table**: 
   - `topic_id` (UUID, Primary Key)
   - `topic_name` (String)
   - `num_partitions` (Int)
   - `replication_factor` (Int)

2. **Messages Table**:
   - `message_id` (UUID, Primary Key)
   - `topic_id` (UUID, Foreign Key)
   - `partition_id` (Int)
   - `offset` (Long)
   - `payload` (Blob)
   - `timestamp` (Timestamp)

3. **Consumer Groups Table**:
   - `group_id` (UUID, Primary Key)
   - `topic_id` (UUID, Foreign Key)
   - `offsets` (Map: Partition ID -> Offset)
   - `last_seen` (Timestamp)

### Access Patterns
- Producers write to the Messages table, partitioned by `topic_id`.
- Consumers read from the Messages table, using `offsets` to track their position.

1. **Consistency vs. Availability**: Opting for eventual consistency to achieve high availability and partition tolerance (CAP theorem). This allows for faster message processing at scale, albeit risking temporary inconsistencies.
2. **Replication Factor vs. Latency**: Higher replication factors improve durability but increase latency due to additional write operations. A replication factor of 3 is chosen to balance durability and performance.
3. **Backpressure Management**: Deciding between throttling producers or consumers. Throttling consumers is chosen, as it allows producers to continue sending messages while consumers process at their pace.
4. **Partitioning Strategy**: Choosing a hash-based partitioning strategy for even load distribution across consumers, sacrificing ordering guarantees across partitions, which is acceptable for many use cases.

Design a Distributed Message Queue

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Requirements

Functional Requirements

Capacity Estimation

Daily Message Volume

Submit Your Answer

Meta 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