System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

• run jobs based on a schedule
• all jobs are independent, no dependencies between each other
• jobs have different priorities
• no concurrent execution of the same task
• each task should be executed at least once

Non-Functional:

List non-functional requirements for the system...

• highly reliable because we don't want the tasks to fail frequently during execution
• low latency, tasks should start executing within a couple seconds of their scheduled execution time
• consistency, we shouldn't miss a task, every task should be run at least once.
• high availability for task scheduling

Capacity estimation

Estimate the scale of the system you are going to design...

100 users, scheduling 100 tasks per day, 5 min per task.

Each task takes ~0.01 hour.

100*100=10^4 tasks per day

10^4/24=417tasks

417/0.01=4170 tasks/hour

API design

Define what APIs are expected from the system...

POST /tasks/create - this endpoint let user schedule a task with the schedule indicated in payload and task definition as a script

GET /tasks/task_id - get a log of execution by task_id

GET /users/user_id/tasks - get a log of all tasks belong to user_id

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

For user data and task metadata we can use mongo DB, shard on user_id to easily query for a list of tasks belong to a certain user. Task DB will have timestamp and status columns. Status is an important one, we have the following status enums:

new, enqueued, claimed, processing, retriable failure, success, fatal failure

Will talk about how to check for failed tasks in the sessions below.

For task definition, we can use a BLOB storage like S3 to store the task script files, we will have a S3 link in the task metadata table

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify..

Task store: task store contains the scheduling table and the task definition files on S3.

Store consumer: store consumer periodically polls the task store to find tasks that are ready for execution and pushes them onto the right queues. These could be tasks that are newly ready for execution, or older tasks that are ready for execution again because they failed or were dropped somewhere else.

Queue: The queue acts as a buffer between the store consumer and the controllers. Each priority gets a dedicated queue.

Controller: These are the workers dedicated for task execution. Each worker has one controller process responsible for polling tasks from the queues.

Executor: responsible for the actual task execution.

Heartbeat and status controller: It is responsible for setting task status after each step, and setting heartbeats during task execution.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

User flow:

When a user creates a task, it goes through the load balancer and server, it saves the task definition file in S3 and creates a link, it also saves the task metadata and the S3 link in mongo DB, the user row's task column will be updated to include the newly created tasks.

Task scheduling flow:

1. Client performs a scheduling request with task information and execution time.
2. Server creates the task entity in the scheduling table and S3 table.
3. When it is time to process the task, store consumer pulls the task from the database and push it to a queue.
4. Executor makes a call to the controller to indicate it is ready to process the next task. Controller pulls tasks from the queue, make a call to the heartbeat and status controller.
5. Once processing is done, executor calls heartbeat and status controller to update task status.
6. Heartbeat and status controller updates the task store upon getting heartbeat and task status.

Every state update in the lifecycle of a task is accompanied by an update to the next trigger timestamp in the scheduling store, this ensures that store consumer pulls the task again if there is no change in the state of the task within the next trigger timestamp. The helps to achieve the at-least-once-delivery guarantee by ensuring no task is dropped.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Tires:

We mentioned there will be many queues. For the executor and queue, we can divide them into different tiers with different hardware, for higher priority tasks we can send them to high tier executors maybe with more expensive hardware which can give us even better availability.

No concurrent task execution:

Concurrent task execution is avoided through a combination of two methods in ATF. First, tasks are explicitly claimed through an exclusive task state (Claimed) before starting execution. Once the task execution is complete, the task status is updated to one of Success, FatalFailure or RetriableFailure. A task can be claimed only if its existing task state is Enqueued (retried tasks go to the Enqueued state as well once they are re-pushed onto SQS).

However, there might be situations where once a long running task starts execution, its heartbeats might fail repeatedly yet the task execution continues. ATF would retry this task by polling it from the store consumer because the heartbeat timeouts would’ve expired. This task can then be claimed by another worker and lead to concurrent execution. 

To avoid this situation, there is a termination logic in the Executor processes whereby an Executor process terminates itself as soon as three consecutive heartbeat calls fail. Each heartbeat timeout is large enough to eclipse three consecutive heartbeat failures. This ensures that the Store Consumer cannot pull such tasks before the termination logic ends them—the second method that helps achieve this guarantee.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Message broker:

• Kafka

Kafka is one consumer per partition, where tasks can be stuck behind long running jobs

• In-memory queues

We choose to go with in-memory message broker because it allows many executors for each message broker. When a consumer idles it grabs a task. And since it's in-memory it is going to be relatively low latency.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Scenario where jobs will be run by more than 1 executor at a time

The aforementioned distributed lock solution isn't perfect for running a job only once, because we probably need a TTL on these locks, if one executor grabs a job and a lock, and it fails during execution, we probably want another executor to retry that job so we need a TTL on these locks. Now if the failed executor takes too long, the lock expired and some other executor grabs it and starts running the job, but then the failed executor now comes back and continues the same job, the job will be run at the same time by 2 executors.

How to reduce latency on reading the table?

• We can have many partitions on the table and all of them have something pulling them
• To avoid having to grab a lock to read from the nodes we are sending writes to, we can read from a read only replica and the leader will do the write. But what if the leader goes down and we don't update the replica because we aren't using strong consistency, we will just end up retrying more jobs which isn't the end of the world.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?