Delayed job scheduler that runs each job after its delay

Design and code a scheduler that accepts a job and a delay and runs the job that many seconds later. This is a low-level design question: name the classes, the APIs and the data structures, show how jobs survive a restart, and say how you would test it.

Requirements

• Functional: schedule(job, delay_seconds) -> job_id; cancel(job_id) -> bool; jobs run at or soon after their due time; a cap on how many jobs run at once.
• Non-functional: jobs survive a process restart; a job runs at least once, and the design states whether it can run twice; insert, cancel and "next due job" are fast; correct under many concurrent callers; robust to clock changes.

Clarifying questions

• How many jobs are pending at once, and how far in the future can they be?
• How precise must the start time be: milliseconds or seconds?
• Must a job run exactly once, or is at-least-once with idempotent jobs acceptable?
• One process, or many scheduler instances sharing the work?
• What happens to a job that fails: retry, and with what backoff?

What a strong answer covers

• Classes: Scheduler (public API), Job (id, payload, due time, state, attempts), a JobStore for persistence, a timer or dispatcher thread, and a WorkerPool with a concurrency limit.
• The due-time structure: a min-heap keyed by due time (O(log n) insert and pop, lazy deletion for cancel), or a hierarchical timing wheel for very many timers; the trade-off between them.
• The dispatcher loop: wait on a condition variable until the earliest due time or until a new earlier job arrives, then hand due jobs to workers; no busy waiting.
• Durability: write the job before acknowledging schedule; on restart reload pending jobs and run anything overdue.
• Delivery semantics: mark a job as claimed with a lease, retry on timeout, and why that gives at-least-once; idempotency keys for jobs that must not repeat.
• Time: a monotonic clock for waiting, wall-clock due times stored for durability, and how clock jumps are handled.
• Thread safety: one lock around the heap and its state, or a lock-free handoff queue; cancel racing with dispatch.
• Tests with an injected fake clock: ordering, cancel, restart recovery, concurrency limit, a failure and its retry.

Follow-ups

• Recurring jobs (cron expressions).
• Scale out to many scheduler nodes: partition jobs by id and handle a node that dies.
• Priorities among jobs that are due at the same time.