Loading...
List the key functional requirements for the system (Ask the AI for hints if stuck)...
List the key non-functional requirements (performance, scalability, reliability, etc.)...
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
Assuming 1 million daily active users, each scheduling on average 10 tasks per day, and view the tasks page 100 times, and peak QPS is double of average QPS.
Peak read QPS = 1 million * 100 / 3600 / 24 * 2 = 2.3K
Peak write QPS = 230
Assuming that for each task, the task metadata takes 1MB to store. On each day, we store 10 million new tasks, so we need 10TB of new storage per day.
For data that is over 1 year old or not read in the last 6 months, we move them to cold storage.
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...
Here are the APIs:
To schedule a task:
POST v1/schedule_task {
task_scheduled_time: Timestamp,
task_recurring_cadence: String,
task_name: String,
task_contents: String,
task_scheduler_user_id: UUID,
}
To cancel a task:
POST v1/cancel_task {
task_id: UUID
}
To edit a task:
POST v1/edit_task {
task_id: UUID,
edited_recurring_cadence: String,
edited_scheduled_time: Timestamp,
edited_task_contents: String,
edit_task_user_id: UUID
}
To view the current tasks:
GET v1/view_tasks {
user_id: UUID,
start_time: Timestamp,
end_time: Timestamp
}
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.
For all requests sent to the system, we go through Edge API gateway, which enforces rate limiting and authentication. It then goes through load balancers, which routes requests to different servers with consistent hashing of user_id.
There are 3 flows in this system:
Task scheduler, task viewer and task executor
For scheduling a task, we send a request to task scheduler. If the task is going to be executed in the next hour, we store it in the redis cluster's sorted set
Every 5 minutes, task scheduler also pulls the tasks that will be executed in the next hour from relational databse, and add them to the redis sorted set.
When a user edits a task or change its recurring cadence, we make corresponding changes to the task in relational database. If that task is going to be executed soon, we also update it in the redis cluster.
For viewing tasks, users can choose to view tasks that are scheduled to be executed in a given time period. If users want to view tasks that are going to be executed soon (in the next hour), we can query the redis cluster's sorted set. If users want to see past/future or longer time periods, we query the relational database directly. Most frequent queries will be handled by the redis cluster.
For executing tasks, task executor regularly pull the tasks to be executed from the redis sorted set. Upon a task's scheduled start time, the task executor sends a request to the task execution servers, which execute the tasks. Given different servers have clock skew, we also set up a NTP server to synchronize the time between different servers. If a task completes/fails, we send a request to the notification service which pushs a notification to user client.
When a task fails, we also trigger retry of the task, up to user's designated times. For each retry, we use the same idempotent key as the original request, so duplicate requests are not processed twice.
To handle problems like midnight scaling, where a lot of tasks are scheduled to be triggered at the same time, we need to scale the redis cluster and the task execution servers.
For task execution servers, we can configure auto-scaling based on CPU utilization. When CPU usage of all pods reaches 40%, we start to horizontally scale more pods. When traffic decreases, we scale back down.
For our storage, if the redis cluster goes down, we can also go to the underlying relational database for polling.
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...
For this system, we need to store all the scheduled tasks, and their associated metadata.
For storing them, we should use a relational database, for below benefits:
Here's a data model:
table tasks {
task_id: UUID,
task_scheduled_time: Timestamp,
task_expected_duration: Int,
task_created_at: Timestamp,
task_created_by: UUID,
task_updated_at: Timestamp,
task_updated_by: UUID,
task_name: String,
task_contents: String,
task_status: String,
task_execution_cadence: String
}
As the system grows and data size grows, we can shard the database by hashing the task_id using consistent hashing. We can also create read replicas for each write replica, and use leader-follower replication. For each write, all replicas need to acknowledge the write. This will increase latency but can ensure consistency on the data read from different replicas.
To support huge read traffic, especially for client to easily find the tasks that are going to be executed soon, we should use sorted sets sorted by run_at where tasks due to be executed in the next hour will be added to the sorted set.
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
For this system, we need to store all the scheduled tasks, and their associated metadata.
For storing them, we should use a relational database, for below benefits:
Here's a data model:
table tasks {
task_id: UUID,
task_scheduled_time: Timestamp,
task_expected_duration: Int,
task_created_at: Timestamp,
task_created_by: UUID,
task_updated_at: Timestamp,
task_updated_by: UUID,
task_name: String,
task_contents: String,
task_status: String,
task_execution_cadence: String
}
As the system grows and data size grows, we can shard the database by hashing the task_id using consistent hashing. We can also create read replicas for each write replica, and use leader-follower replication. For each write, all replicas need to acknowledge the write. This will increase latency but can ensure consistency on the data read from different replicas.
To support huge read traffic, especially for client to easily find the tasks that are going to be executed soon, we should use sorted sets in a redis cluster sorted by run_at where tasks due to be executed in the next hour will be added to the sorted set.
For all requests sent to the system, we go through Edge API gateway, which enforces rate limiting and authentication. It then goes through load balancers, which routes requests to different servers with consistent hashing of user_id.
There are 3 flows in this system:
Task scheduler, task viewer and task executor
For scheduling a task, we send a request to task scheduler. If the task is going to be executed in the next hour, we store it in the redis cluster's sorted set
Every 5 minutes, task scheduler also pulls the tasks that will be executed in the next hour from relational databse, and add them to the redis sorted set.
When a user edits a task or change its recurring cadence, we make corresponding changes to the task in relational database. If that task is going to be executed soon, we also update it in the redis cluster.
For viewing tasks, users can choose to view tasks that are scheduled to be executed in a given time period. If users want to view tasks that are going to be executed soon (in the next hour), we can query the redis cluster's sorted set. If users want to see past/future or longer time periods, we query the relational database directly. Most frequent queries will be handled by the redis cluster.
For executing tasks, task executor regularly pull the tasks to be executed from the redis sorted set. Upon a task's scheduled start time, the task executor sends a request to the task execution servers, which execute the tasks. Given different servers have clock skew, we also set up a NTP server to synchronize the time between different servers. If a task completes/fails, we send a request to the notification service which pushs a notification to user client.
When a task fails, we also trigger retry of the task, up to user's designated times. For each retry, we use the same idempotent key as the original request, so duplicate requests are not processed twice.
To handle problems like midnight scaling, where a lot of tasks are scheduled to be triggered at the same time, we need to scale the redis cluster and the task execution servers.
For task execution servers, we can configure auto-scaling based on CPU utilization. When CPU usage of all pods reaches 40%, we start to horizontally scale more pods. When traffic decreases, we scale back down.
For our storage, if the redis cluster goes down, we can also go to the underlying relational database for polling.