Design a Fair Job Scheduler for a Small Worker Pool
Teams share one small pool of worker machines for batch jobs whose run times nobody knows in advance. Design the scheduler that shares the pool fairly, keeps short jobs moving and finishes every accepted job, without building more than this scale needs.
Problem statement
For this exercise, assume a company runs one shared pool of worker machines for internal batch jobs, such as report builds, data checks and file conversions. About 40 teams submit jobs to it.
A job names its team, a command packaged as a container image with its arguments, and a key chosen by the caller so that sending the same submit twice does not create a second job. Each job runs on one worker slot until it ends.
Nobody knows in advance how long a job will run. Most jobs end within a few minutes, but some run for hours, and the same command can be short one day and long the next. Design the scheduler that decides which waiting job starts on each free slot.
It must share the pool fairly between teams, so that a team that submits thousands of jobs, or a few very long ones, cannot shut the other teams out. Every accepted job must end with a final result. The pool is small; size the design for it rather than copying what a much larger platform would need.
Also assume: - Fairness is between teams, and every team has the same share. Inside one team, jobs start in the order they were submitted. - A job cannot be paused. It can be stopped and started again from the beginning, which is safe but throws away the work it had done. - A job ends as succeeded, failed or cancelled.
A job whose own command fails is tried at most 3 times in total. - Job output and logs, dependencies between jobs, jobs that start at set times, and jobs that need more than one slot are out of scope.
What to build
- A team member or a team's program submits a job and gets back a job ID; sending the same submit again with the same key returns that job instead of creating a second one.
- When the pool is busy, every team with waiting jobs gets a fair share of it, whether the team submits many short jobs or a few long ones, and a team that had nothing running gets its next job started soon.
- Every accepted job ends as succeeded, failed or cancelled; no job is lost, left waiting forever, or left marked as running on a machine that has died.
- A team member can see a job's state, its runs and why it is still waiting, and can cancel a job that has not ended.
At scale
- For this exercise, assume 20 worker machines with 8 slots each, so 160 slots in total, and about 20,000 jobs a day. Submissions peak at about 100 a minute, and one team sometimes submits 2,000 jobs at once.
- For this exercise, assume about 90 percent of jobs end within 5 minutes, about 2 percent run longer than an hour, and the longest run for up to 8 hours. How long a job runs is known only when it ends.
- For this exercise, assume that when a team with nothing running submits a job while every slot is busy, that job starts within 5 minutes.
- For this exercise, assume an accepted job survives the loss of any one machine, whether a worker machine, the scheduler's machine or a database machine, a run lost with its machine is noticed within 1 minute, and job states and runs are kept for 30 days.