Job Scheduler
Materials — open to everyone, no sign-in
Topic: Job Scheduler
Interviewer: MiracleGuardian
Interviewee: Meng
Level: L5 (Senior)
Additional Resources:
Meeting notes:
https://docs.google.com/document/d/1-l4aji0aG-or-ZoTXpf-zuUOHLXWo6Ckj2vCNNhogQI/edit#
系统设计活动报名
职位申请报名
https://commitway.com/job-refer
YouTube channel
https://www.youtube.com/channel/UCKzpuki3fHTfCCngJDCZ_Mg
QRCode
Mock System Design Interview Summary
Interview Overview
Date: 1/14/2022
Target level: L5 - senior
Duration: 45 minutes
Topic covered: Job Scheduler
Drawing tool used:
Requirements
10k daily users
Each person 10 jobs everyday
Half are scheduled jobs - repeatable jobs
Half are immediately executed jobs
Check status of the jobs
Job duration - seconds to hours
Bonus feature: check job results
[40:50]
Functional:
Create/delete job schedule
Query the job by owner
Update and delete jobs
Query job history
Check job status
Job notification (bonus)
Need to implement job priorities
[38:00]
Non functional
High availability
High scalability
[Reliability - not missing jobs, not duplicate job]
Consistency - not miss job, no duplicate job
performance
[35:15]
Estimation
10k/seconds for write
20k / second for read
Storage
10K * 1 K * 100K = 1P
]34:22]
High level design
[30:28]
“Job” box is a database
[28:00]
Potential points of discussion
Database SQL vs NoSQL
Message queue: kafka
Both SQL and NoSQL works
NoSQL is preferred due to scalability
[26:10]
Key value store vs NoSQL
We don’t need to use graph
Job information can be more dynamic
[24:10]
Design database schema
Job
Job ID
Created Time
Scheduler ID
OwnerID
Repeatable
Job status - enum, scheduled, running, complete
Job result, success, failure
Retried (yes/no)
maxRetry
UUID as job ID
Scheduled ID is for the verification there is only one instance running
Partition: scheduled time
Q: what is the partition key for job table?
A:
partition key: scheduled time
Sort key: ownerID
Q: why not use the job ID for sorting?
A: for same user, the category is useful
A: we can use job ID
[17:45]
Delete, query, get
SQL:
Schedule service
Clarification: what’s the accuracy of the worker timing?
Answer: seconds
To scale up, we use sharding .
[11:00]
Kafka:
At most once, at least once, exactly once
The default is at most once. There are more performance degradation if we set “at least once” or “exactly once”
Because there are multiple workers, we may get duplicate work.
[9:00]
We will make each worker responsible for one partition
We will try to avoid bottleneck at database
If we dedupe at database level, then we can configure message queue to use at least once
[7:30]
Priority: we can implement in kafka
Q: No business logic in message queue to deal with priority. It may be in scheduler or executor
A: it’s combined with message queue
If we have 9 priorities
We can assign different number of workers to different priorities
Q: there will be idle workers
A: it’s a rudimentary implementation
How to handle redundancy
DB: master and replica
We can have read through for cache.
We can have multiple masters in the master-controller structure for the architecture
Kafka queue can handle failures
Database can have replicas
Audience Feedback
Interviewer Feedback
Overall performance is reasonable
May be a weak decline
This question is a classical question. Covered basic points
Suggestions for improvements
priority. Needs more detail for priority. It’s a core puzzle
Cache is not needed. We only need to read each entry one time.
Message queue: at least once. But it’s unclear how to design the execution.
If we deliver twice, what will happen? If the job is idempotent, then “at least once” is sufficient.
Job schema design. Some columns are not needed.
Job result
Max retry. Usually put retry related information in the job scheduler’s own database
Interviewee Self Assessment
Big problem was that time was insufficient
Agree with interviewer: priority should be more clearly implemented
Cache: we can use a daemon to page-ahead the job definition every 5 minute
Add a line to update status
Q: What if the job still fails
A: there 2 types of failures. The job can fail or the worker can fail. For platform related issues we need to retry.
Interviewer: the main issue is time control
REST API, RPC
Which one should we discuss first.
Interviewer
DB and API should be completed designed
Then need to understand the key question of the interviewer
Priority
Retry
Update status
Priority should be implemented at executor
We may be able set priority at DB schema
Audience: can we ask the interviewer which part is most important?
Interviewer: Most interviewers don’t bring up very quickly
Interviewee:
Key problem is the use of time
Database: schema
Audience: what is sharding key and sorting key
Interviewee:
Sharding key: schedule time
Sorting key: job ID
Audience: how do I see my jobs?
Interviewee: the main use is the executor
Audience: it seems user checking status is very important
Interviewer: what is the latency. 1ms -> 10 seconds
Audience: how to scan the available jobs?
Audience: Can DynamoDB support range query?
Audience: how do we get the shard ID?
Interviewee: modify the query into
Audience: We need to know the shard ID?
Audience: schedule time-> hash ID. We cannot figure out the right shard ID
Interviewer: we should know the datatype of the scheduled time, long, or timestamp?
Can use “begin with”. Partition key can support “begin with”
Audience: DB saves all jobs. Some repeat, some non-repeat. We need to scan all jobs including the non-repeat? Will the master scan through the non-repeat jobs of yesterday?
Audience: if 90% jobs are completed, then we will scan through the completed jobs
Audience 2: my main question is partition key
If partition key is based on scheduled time, it will be unbalanced to one shard
We also need to use very specific time to find the job
If we use UUID, job status query will be fast. But the problem is how to find currently scheduled job.
Interviewee: It’s better to always go to one shard instead of multiple shards
Audience: we can restruct the DB with 2 tables.
Interviewee: if we have time for the interview, I will add an archive
We can also split into
user, job history, user job
This may be better
What is better?
Audience:
Secondary index, global secondary index.
Single table design - dynamo DB
Audience:
We cannot support this query in dynamoDB
Audience:
UUID as partition key
Audience:
We can split the database into 2 parts, archived jobs, and future jobs
Audience:
Next 60 minutes, then it becomes 60 times, then it will issue 60 queries.
We only need sharding key there are lots of jobs
Interviewer:
Possible design
Job table
Meta data
History table
Each execution will create an entry
Schedule table table
It’s hard to know if DB is the focus of the interview
Interviewee: very hard to control time
Audience: fast diagram and use abbreviation is great
Audience: can ask the interviewer where to drill down
General hire, may not have a specific checklist
You can go through very thorough feature list, then ask which features are important
Message queue, schedule time
Audience: executor - may have capacity limit per machine
Audience:
we can use delayed message queue, e.g. rabbitMQ, rocketMQ
We can hash by user at database level
Priority: different priority map to different topic. Use different partition number for different topic
Dependency: airflow database
Audience:
Once the message is pushed to a delayed message queue, then the user updates the job, then the job may have wrong definition
Audience
We check the database before we execute the job