Code a task scheduler

In one minute

• A scheduler is a priority queue keyed by next run time plus a loop that pops everything due. A binary min-heap gives O(log n) insert and pop, and the earliest task is always at the root.
• Make time an input. Inject a clock for scheduling and drive execution with tick(now), so the same code runs in production (a loop that sleeps until the next deadline) and in tests (call tick(35) and assert what ran).
• Cancel lazily. Removing an item from the middle of a heap is awkward, so bump the task's version and let the stale heap entry be skipped when it surfaces.
• Fixed-rate tasks reschedule from their scheduled slot, not from when they finished, so they do not drift. Decide explicitly whether missed slots are caught up or skipped.
• Never run user code while holding the scheduler's lock. Tasks cancel and schedule other tasks from inside their own run, and a lock held across that call deadlocks.

Requirements

Functional:

• Schedule a one-off task to run after a delay.
• Schedule a fixed-rate recurring task with an initial delay and a period.
• Cancel a task before or during its run; a cancelled task never runs again.
• Retry a failed run with exponential backoff up to a per-task limit. A one-off task that exhausts its retries is marked failed; a recurring task skips that slot and continues with the next.
• Run tasks due at the same instant in the order they were scheduled, and report each run's outcome.
• Query a task's status: scheduled, running, done, failed or cancelled.

Non-functional:

• Deterministic and testable: no hidden reads of wall-clock time and no sleeps in the core.
• Schedule and cancel in O(log n) or better; finding the next due task in O(1).
• Thread-safe: many threads schedule and cancel while a dispatcher runs tasks.
• A task that throws does not stop the scheduler or other tasks.

Out of scope: persistence across restarts, distribution across machines (that is a job scheduler service), cron expressions and time zones, and a worker pool. The design leaves room for each.

Entities and relationships

Scheduler owns three things: a map from task ID to Task, a min-heap of entries, and a sequence counter. It also holds the injected clock and the base backoff.

Task is the unit the user cares about: ID, action, period (zero for one-off), current slot, retry limit, retries used so far, status and a version number. The version is how the heap and the map stay consistent without searching the heap.

HeapEntry is a small value: (runAt, seq, taskId, version). runAt orders the heap, seq breaks ties in insertion order, and version lets the scheduler tell a live entry from a stale one. A task has at most one live entry at a time.

Action is the callback. It receives its scheduled time and signals failure by throwing (Python, TypeScript) or returning an error (Go).

Clock is a function returning the current time. schedule reads it to turn a delay into an absolute time; tick(now) takes the time as an argument.

RetryPolicy is folded into the scheduler here as backoff * 2^(retry - 1), and is the obvious thing to extract as a strategy when requirements grow.

Class diagram

classDiagram
  class Scheduler {
    -tasks Map
    -heap MinHeap
    -seq int
    -clock Clock
    -backoff int
    +scheduleOnce(id, delay, action, maxRetries) bool
    +scheduleAtFixedRate(id, initialDelay, period, action, maxRetries) bool
    +cancel(id) bool
    +status(id) string
    +tick(now) list
  }
  class Task {
    +id
    +action Action
    +period int
    +slot int
    +maxRetries int
    +retries int
    +status string
    +version int
  }
  class HeapEntry {
    +runAt int
    +seq int
    +taskId
    +version int
  }
  class Action {
    <<interface>>
    +run(at)
  }
  class Clock {
    <<interface>>
    +now() int
  }
  class RetryPolicy {
    <<interface>>
    +delay(retry) int
  }
  Scheduler "1" *-- "many" Task
  Scheduler "1" *-- "many" HeapEntry
  HeapEntry ..> Task : points to by id and version
  Task --> Action
  Scheduler --> Clock
  Scheduler ..> RetryPolicy

Key flows

One tick(10) with a flaky one-off task once and a recurring task rate that always fails, both first due at time 0 with a base backoff of 1.

sequenceDiagram
  participant D as Dispatcher
  participant S as Scheduler
  participant H as MinHeap
  participant A as Task action
  D->>S: tick(10)
  S->>H: peek root, runAt 0 is due
  H-->>S: pop (0, once)
  S->>A: once.run(0)
  A-->>S: throws
  S->>H: push (1, once), retry 1
  S->>H: pop (0, rate)
  S->>A: rate.run(0)
  A-->>S: throws, no retries left
  S->>H: push (10, rate), next slot
  S->>H: pop (1, once)
  S->>A: once.run(1)
  A-->>S: ok, status done
  S->>H: pop (10, rate)
  S->>A: rate.run(10)
  A-->>S: throws
  S->>H: push (20, rate)
  S->>H: peek root, runAt 20 is not due
  S-->>D: once@0 retry, rate@0 failed, once@1 ok, rate@10 failed

The loop is "while the root is due, pop it, skip it if stale, run it, decide what comes next". Anything pushed during the tick with a time at or before now, such as a retry or a task scheduled by another task, runs in the same tick, still in time order.

Design patterns used and why

• Priority queue as the core data structure. Not a pattern from a catalogue, but the decision that makes the design: the next thing to do is always the minimum, and a heap gives that in O(1) peek and O(log n) update.
• Command (Action). A task wraps "what to do" as an object the scheduler can store, retry and cancel without knowing what it does. Java's Runnable and ScheduledFuture are the classic form.
• Strategy (RetryPolicy, Clock). Backoff curves and time sources vary by caller; both are passed in. The clock strategy is what makes the scheduler testable.
• State machine (task status). scheduled -> running -> done | failed | scheduled, and cancelled from scheduled or running. Writing the transitions down settles questions such as "can I cancel a running task?" (yes, it will not be rescheduled) before they become bugs.
• Lazy deletion with versioning. A general technique: instead of keeping two structures exactly in sync, let the secondary one go stale and validate on read. The same idea appears in Dijkstra implementations without decrease-key and in caches with generation numbers.

Concurrency and edge cases

• Run actions outside the lock. In Go, Tick locks to pop the due entry and mark the task running, unlocks, calls the action, then locks again to record the outcome. That lets an action call Cancel or ScheduleOnce on the same scheduler. Holding the lock across the call would deadlock on the first re-entrant call, since sync.Mutex is not reentrant.
• Cancel during a run. The task is running, the cancel succeeds and sets cancelled, and when the action returns the scheduler sees the status and does not reschedule. The run in progress is not interrupted; cancellation is cooperative.
• Stale heap entries. Cancel bumps the version. The old entry stays in the heap until it reaches the root, then is discarded. If cancellations are heavy, the heap fills with garbage; rebuild it when stale entries exceed half its size.
• Same-time ordering. Two tasks due at time 5 run in insertion order because of seq. Without it, heap order for equal keys is arbitrary and tests become flaky.
• Catch-up. If tick jumps from 9 to 35, a fixed-rate task with period 10 runs at 10, 20 and 30. That matches Java's scheduleAtFixedRate, which runs missed executions in quick succession. A "skip missed" policy is just as valid; choose one and document it.
• Retry storms. Exponential backoff spaces retries out, but many tasks failing against the same dependency at the same moment retry in lockstep. Add jitter in production (with a seeded random source in tests).
• Long-running tasks. A single-threaded dispatcher stalls everything behind a slow task. Hand actions to a worker pool, and decide whether a fixed-rate task may overlap with its own previous run (usually not).
• Duplicate IDs and bad periods. Reject a second task with the same ID and a non-positive period, or a fixed-rate task will loop forever inside one tick.

Down the stack

Extensibility

• Worker pool. tick hands due tasks to a pool instead of running them inline. The state machine gains a queued state, and fixed-rate tasks need a no-overlap rule.
• Fixed-delay tasks. Add a mode where the next run is finish time + delay instead of slot + period. It only changes the reschedule step.
• Cron schedules. Replace period with a NextTime(after) strategy. Fixed-rate becomes one implementation and cron another, with time zones handled inside it.
• Priorities. Extend the key to (runAt, priority, seq) so urgent tasks win ties, or keep separate heaps per priority if starvation matters.
• Persistence. Write each task and its next run time to a store and rebuild the heap on start. At that point you are designing a job scheduler service, with leases and at-least-once semantics.
• Observability. Record lag (actual start - runAt) per run. Lag is the single best signal that the scheduler is overloaded.

Leadership lens

• Insist on the injected clock and tick(now) from day one. A scheduler that can only be tested with sleep gets few tests, and the bugs live in the edge cases those tests would have caught.
• Ask in design review: what happens to missed runs after a pause, can a recurring task overlap with itself, and is cancellation cooperative or forced? Each has a right answer only for a given product.
• Prefer the platform's scheduler (ScheduledExecutorService, asyncio loop timers, Go time.Timer) for simple delays. Build your own when you need deterministic tests, custom retry, or visibility into the queue.
• Ownership split: the scheduler team owns timing, retries and lag metrics; task owners own idempotency, because retries mean a task can run more than once.
• Build first: one-off tasks, fixed rate, cancel and lag metrics. Retries and worker pools come next; persistence only when a restart losing tasks is a real incident.

Check yourself

1. Why does the heap entry carry a version, and what would go wrong without it?

   Show answer

   Cancelling or rescheduling leaves the old entry in the heap. Without a version check, the old entry would run a cancelled task or run a rescheduled task twice.

2. A fixed-rate task with period 10 started at 0 takes 3 units to run. When does it next run, and how is that different from fixed delay?

   Show answer

   At 10, because the next slot is the previous slot plus the period. Fixed delay would run at 13 (finish plus delay) and drift by the run time on every cycle.

3. Why is seq part of the heap key?

   Show answer

   Heaps do not preserve insertion order for equal keys, so tasks due at the same time would run in an arbitrary order. seq makes the order first-scheduled, first-run and the tests deterministic.

4. What breaks if the Go scheduler holds its mutex while calling the task's action?

   Show answer

   Any action that calls Cancel or a schedule method on the same scheduler deadlocks, and a slow action blocks every thread that wants to schedule or cancel.

Watch

• Implementations of Timing Wheels (Julian Squires, Systems We Love): how systems manage huge numbers of timers, and the trade-offs between wheels and heaps.

Free resources

• heapq: Heap queue algorithm (Python docs): the array heap invariant and a priority-queue recipe with lazy removal of cancelled entries.
• sched: Event scheduler (Python docs): a small standard-library scheduler with injectable time and delay functions, the same idea as tick(now).
• ScheduledThreadPoolExecutor (Java SE 21 API): fixed-rate versus fixed-delay semantics and the remove-on-cancel policy.
• Hashed and Hierarchical Timing Wheels (Varghese and Lauck, SOSP 1987): the classic paper on efficient timer data structures.
• Timeouts, retries and backoff with jitter (AWS Builders' Library): why retries need backoff, jitter and limits.
• Distributed periodic scheduling with Cron (Google SRE book): what changes when a scheduler must survive machine failures.