Design a Job Scheduler with Explicit Execution Guarantees
Company: Robinhood
Role: Software Engineer
Category: System Design
Difficulty: medium
Interview Round: Onsite
Design a job scheduler service. Clients submit jobs to run either now or at a later time. The scheduler must run each due job on a pool of workers, retry failed jobs, and let clients check a job's status or cancel it.
```hint Separate "due" from "owned"
Finding the jobs whose time has arrived and making sure each one is held by only one worker at a time are separate problems with separate failure modes.
```
```hint A worker can die after doing the work
Consider a worker that performs the job's effect and then crashes before it records completion.
```
### Constraints and Clarifications
- Scale, timing precision, and the required execution guarantee are not given. State your assumptions and size the design from them.
- Jobs run arbitrary handler code on workers, and a worker can crash or stall at any point.
### Clarifying Questions
- Are jobs only one-time (immediate or delayed), or also recurring or triggered by other jobs finishing?
- How late may a job start after its scheduled time, and is running a job twice ever acceptable?
- How long can a job run, and should a running job be cancellable?
- Do tenants or job types need isolation or fair shares of the worker pool?
### What a Strong Answer Covers
- Requirements, sizing estimates, and an API for submitting, checking, and cancelling jobs.
- A durable job model, an index for finding due jobs, and a concrete protocol for claiming, heartbeating, and completing a job.
- The execution guarantee actually provided, plus retries with backoff, terminal states, and cancellation that cannot be overwritten by a late result.
- A weighed alternative dispatch design, scaling for bursts of due jobs, and the metrics that reveal lag.
### Follow-up Questions
- How do you stop a cancelled job's late result from being recorded as success?
- What happens when hundreds of thousands of jobs are all due at the same minute?
- How would you add recurring schedules without ever creating the same occurrence twice?
Overview: Design a job scheduler that accepts immediate and delayed jobs, runs each due job on a worker pool, and supports status checks, retries, and cancellation. The question tests durable job storage, finding due jobs, worker claims with leases, execution guarantees, and handling bursts of jobs that become due at once.