Loading...
1 MQ -> 1000 topics -> 10 messages/second/topic -> 10000 messages/second
message size (avg) = 50 KB -> 50 MB/sec
Assuming 30 days average retention period -> 50 * 10^6 * 30 * 10^5 = 150 TB
Replication factor =3 for data loss prevention - total memory footprint = 450 TB
Partitions - 3 (average case)
Broker - 3 partitions with replications (average)
Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...
Publisher -
Create new topic: POST topics/:topicName -> boolean
Get all topics: GET topics/ -> topicName[]
Post message to topic -> POST topics/:topicName
{
message: byte[]
key: string
retryCount
} -> boolean
Consumer -
Subscribe to topic: POST subscriptions/:topicName/
Get all topics: GET topics/ -> topicName[]
Fetch from topic -> GET topics/:topicName?limit={}&offset={}
Commit offset -> PUT topics/:topicName/commit?offset={}
Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.
The producer will publish a message via the producer SDK. The SDK handles communication with the message queue server. It does time and size based batching of outbound messages. It waits for message acknowledgement from the server for handling retries.
When the message arrives in the message queue it goes to the routing service. The routing service will route the message to the appropriate partition based on the message key. If the message key is not present then the routing will be done in a preconfigured manner via a routing algorithm like round Robin or smallest partition first. Within a given partition, the ordering of messages is maintained - this ensures no out of order events from a single partition.
The brokers will contain multiple partitions of different topics. Some of these partitions will be leader partitions and some will be replicas.
The routing service will route the message to the leader partition. Once the leader receives the message the follower partitions will try to sync that message from the leader. Data semantics will depend on when the MQ sends back the write acknowledgement to the publisher - on arrival of the message / on the message being written to the leader / on all replicas being synced with the message.
The message is also written to a WAL which is flushed to disk - since the messages are immutable once sent - we only need to append to the log. This sequential access pattern helps leverage hard disks for storage which are cost effective and provide high throughput for the given access pattern.
We also have zookeeper to take care of leader election for replicas in case the leader replica or partition goes down. The zookeeper does that by listening to broker heartbeats. It also is responsible for coordinating during partition rebalancing for a given topic.
We have multiple consumer groups subscribing to different topics from this message queue. Each group contains a set of consumers which subscribe to different partitions for different topics. No two different consumers within the same consumer group should subscribe to the same partition for a given topic.
Based on when the consumer sends the acknowledgement to the message queue after receiving the message, we have different delivery semantics. For at least once delivery semantics the consumer processes the message first and then upon successful processing sends the acknowledgement to the message queue. For at most one semantics the consumer sends the acknowledgement to the message queue as soon as it gets the message and before it process it.
For exactly once delivery semantics the consumer SDK needs to have a deduplication logic in place so that it can filter out duplicate messages based on the message key.
Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...
The database in this system design question refers to the message persistence layer within the message queue. For this we can utilise any persistent storage solution. One of the cheapest storage solution is hard disk and it fits our use case since we require sequential access patterns for both writing and reading from a particular offset.
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
Producer SDK - We have a trade-off for throughput versus latency in case we sent each message as soon as it gets produced from the producer SDK to the message queue. The latency would decrease as each message is delivered to the queue as soon as it gets created, however, the throughput in this case will reduce as the IO operations will take a significant chunk of time. We can increase this throughput by batching messages at the producer level using a producer SDK which takes into factor the time and size of the batching and send them to the message queue.
Another component is when we send the acknowledgement of a successful message back to the producer. Because we have replication we have more than one way of doing this. One way is as soon as the message arrives at the message queue we send the acknowledgement to the producer -in this case the message can be lost if the leader fails? Another is we write the message to the leader send back the acknowledgement and wait for the synchronisation between the leader and the replicas to complete - in this case we can have lost messages or partial messages persisted to subset of total number of replicas in case the leader fails. One of the strongest guarantees is we write to the leader wait for the synchronisation between the leader and the replicas to complete and then send that acknowledgement message. The trade off in this case is the guarantee of message persistence and replication versus acknowledgement time.
Zookeeper is used for leader election between replicas in case the leader goes down. Zookeeper does this by keeping a list of broker heart beats and listening to them. To check which brokers are active and which are not? This coordination service also helps during partition rebalancing. We flush the messages to a write ahead log which is writing to disk with sequential writes.
Consumers read from partitions and commit the read offset. This can be done using a consumer SDK and decides the message delivery semantics as explained earlier.
Consumers subscribe to a topic and the messages can either be polled by the consumer or pushed by the message queue to the consumer. The trade of between polling versus pushing is that in polling the consumers can take time to process different messages and given the retention policy for the message queue they can read messages at their own will. So in case a consumer is delayed during processing the messages can be read at a later point of time. This effects the latency of message arrival at the consumer since message that is written to the partition will only be read when the consumer polls. In contrast the push mechanism has lesser latencies since it pushes the message as it arrives. However this can cause issues if the consumer is already processing a lot of messages and is lagging in terms of published messages.