阅读中文版本

Build a Delayed Job Scheduler

A scheduler that enqueues jobs for future execution using a hierarchical timing wheel, with cancellation, retry on failure, and a persistence layer for crash recovery.

delayed-job-scheduler/
├── src/wheel.ts
├── src/scheduler.ts
├── src/wal.ts
├── tests/scheduler.test.ts
└── package.json

const bucket = (currentTick + delay) % SIZE; wheel[bucket].push(job);

const due = wheel[currentTick++ % SIZE]; for (const job of due) dispatch(job);

wheel[bucket] = wheel[bucket].filter(j => j.id !== id);

await wal.append({op:"enqueue", job}); // on boot: for (const e of wal.read()) apply(e);

Project overview

A scheduler that scans every job on every tick to find the due ones is O(n) per tick, which is fine for ten jobs and wrong for ten million. A timing wheel makes enqueue and tick O(1) by placing each job in a bucket keyed by its due tick, so a tick just dispatches the current bucket without scanning.

The hierarchical wheel is what handles long delays without a large array. A single wheel of a million buckets is a million-slot array, which is wasteful for a schedule that mostly has short delays. A hierarchical wheel uses a small outer wheel for the low bits of the delay and inner wheels for the high bits, cascading entries from inner to outer as the tick advances, like a clock where the minute hand cascades into the hour hand.

The cancellation is what makes the scheduler usable for jobs that may be invalidated before they are due. A scheduled cache invalidation that is superseded by a newer write should be cancelled, not run. The scheduler removes a job by id from its bucket, so a cancellation before dispatch prevents the job.

The write-ahead log is what makes the scheduler survive a crash. Every enqueue and cancel is appended to a log on disk, and on restart the log is replayed to rebuild the wheel. The log is append-only, so recovery is a sequential scan, and the wheel is rebuilt in the order the ops were applied.

The value of this project is the O(1) tick, not the scheduling. Scheduling a job is trivial; doing it without scanning every job on every tick is the part worth learning, because that is what lets a scheduler handle millions of pending jobs without the tick itself becoming a bottleneck.

What you will build

The project delivers five capabilities, each driven by a test:

• Hierarchical timing wheel
• O(1) enqueue and tick
• Cancellation by job id
• Retry with backoff
• Disk persistence and recovery

A hierarchical timing wheel holds jobs in buckets keyed by their due tick. Enqueue computes the bucket from the delay; a tick advances the wheel and dispatches due buckets. A hierarchical wheel cascades overflow into inner wheels for long delays without a large array. A write-ahead log persists enqueues and cancellations for recovery.

Architecture and data model

The timing wheel is an array of buckets, each a list of jobs. The current tick is an index into the array. Enqueue computes the bucket as (current tick plus delay) modulo the array size, and adds the job to that bucket. A tick increments the current tick, dispatches the bucket at the new index, and clears it.

The hierarchical wheel has multiple levels. The outer wheel covers the low bits of the delay, and the inner wheels cover the high bits. A job with a delay longer than the outer wheel is placed in an inner wheel bucket. When the outer wheel wraps around, a cascade moves entries from the inner wheel to the outer, redistributing them by their remaining delay. This is like a clock: the second hand is the outer wheel, the minute hand is the inner, and when the second hand wraps, the minute hand advances.

The cascade is O(1) amortized per tick, because each entry is cascaded at most once per level. A job that is cascaded from the inner to the outer wheel is then dispatched from the outer, so the cascade cost is part of the dispatch, not an extra tick cost.

The cancellation removes a job by id from its bucket. The bucket is found by recomputing the bucket from the delay, which requires the original delay or the due tick to be stored with the job. A map from job id to bucket index makes cancellation O(1) at the cost of the map memory.

The write-ahead log appends every enqueue and cancel as a record. The record is the op type, the job id, the delay or due tick, and the job payload. On restart, the log is read sequentially and each op is applied to a fresh wheel, rebuilding the schedule. The log is fsynced before an enqueue is acknowledged, so a crash after the ack does not lose the job.

The retry with backoff is a dispatch outcome. A job that fails is re-enqueued with a delay that grows exponentially, up to a cap. The retry is a new enqueue, not a special path, so it uses the same wheel and the same WAL.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• A tick driver such as setInterval or an external clock

The dependencies cover the core needs:

• node:fs (built-in) — Write-ahead log persistence

pnpm init

pnpm add -D typescript tsx vitest

Keep secrets and configuration in the environment, and validate them at boot so a misconfigured service fails loudly instead of silently dropping work.

Directory structure

delayed-job-scheduler/ is organized so each concern is testable in isolation:

delayed-job-scheduler/
├── src/wheel.ts
├── src/scheduler.ts
├── src/wal.ts
├── tests/scheduler.test.ts
└── package.json

Phase 1: Enqueue

Compute the bucket from the delay and add the job; O(1) regardless of delay length.

const bucket = (currentTick + delay) % SIZE; wheel[bucket].push(job);

A hierarchical wheel cascades long delays into inner wheels.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 2: Tick and dispatch

Advance the current tick, dispatch the due bucket, and cascade inner-wheel entries as needed.

const due = wheel[currentTick++ % SIZE]; for (const job of due) dispatch(job);

A tick is O(1) plus the dispatch cost, regardless of how many jobs are scheduled.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 3: Cancel

Remove a job by id from its bucket before it is dispatched.

wheel[bucket] = wheel[bucket].filter(j => j.id !== id);

Cancellation is O(bucket size), which is small under uniform scheduling.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 4: Persist and recover

Append every enqueue and cancel to a write-ahead log; on restart, replay the log to rebuild the wheel.

await wal.append({op:"enqueue", job}); // on boot: for (const e of wal.read()) apply(e);

The WAL is append-only, so recovery is a sequential replay.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Testing

Schedule a job for 100 ticks, advance 99, and assert it has not run; advance one more and assert it runs; cancel a scheduled job and assert it never runs; crash and restart, and assert the schedule is recovered from the WAL.

The timing test schedules a job for 100 ticks, advances 99, and asserts it has not run, then advances one and asserts it runs, proving the bucket placement is correct. The long-delay test schedules a job for a delay longer than the outer wheel and asserts it cascades and runs at the right tick.

The cancellation test schedules a job, cancels it, advances past its due tick, and asserts it never runs. The cancel-after-dispatch test cancels a job that has already run and asserts the cancel is a no-op, not an error.

The recovery test schedules several jobs, simulates a crash by discarding the in-memory wheel, and restarts by replaying the WAL. It asserts every pending job is recovered and runs at its due tick. The WAL-order test interleaves enqueues and cancels and asserts the replay applies them in order, so a cancel after an enqueue prevents the job.

The O(1) test schedules a million jobs and measures the tick cost, asserting it is bounded by the dispatch cost of the due bucket, not the total job count. The retry test dispatches a failing job and asserts it is re-enqueued with a longer delay, up to the cap.

The cascade test schedules a job at the boundary of an inner wheel and asserts it cascades to the outer wheel at the right tick, not earlier or later.

pnpm vitest run

Observability

Track the hierarchical timing wheel rate, the scheduler resource usage, and the error count as the three primary signals for the delayed-job-scheduler system. A sudden change in any of these is the signal that something has shifted, not necessarily broken but worth a look before it becomes an incident. Chart the o(1) enqueue and tick alongside the hierarchical timing wheel so a correlation is visible at a glance, because a rising o(1) enqueue and tick with a stable hierarchical timing wheel means the system is doing more work per unit, not that it is failing.

Log every enqueue transition with the context that triggered it, because an operator who sees the symptom but not the cause will guess wrong. The log entry should carry the scheduler identifier, the input that caused the transition, and the outcome, so the operator can reconstruct what happened without re-running it. A log without context is a line of text; a log with context is a diagnosis.

Set alerts on the derived metrics, not the raw counters. A rate of change is more actionable than a total, because a total grows monotonically and never tells you when the growth accelerated. Alert on the hierarchical timing wheel error rate crossing a threshold, the scheduler utilization exceeding a percentage, and the o(1) enqueue and tick latency exceeding the SLO. Each alert should have a runbook link, so the operator who receives it at three in the morning knows what to do, not just what is wrong.

The delayed-job-scheduler system should expose its metrics in a format the existing dashboard can scrape, so the observability is additive, not a new tool. A metric that nobody reads is noise, so before adding one, confirm it has a consumer. The dashboard has three panels: throughput, error rate, and resource utilization, each with a threshold line that is the SLO, so a glance tells an operator whether the system is healthy without reading numbers.

Deployment and operations

Run one scheduler per schedule, because two schedulers sharing a wheel would double-dispatch. The tick driver is a single setInterval at the tick resolution, and the WAL is fsynced before an enqueue is acknowledged, so a crash after the ack does not lose the job.

Choose the tick resolution from the scheduling precision required. A one-second tick is fine for jobs that run on second boundaries; a one-millisecond tick is needed for sub-second precision. The tick resolution is the setInterval interval, and the wheel size is the scheduling horizon divided by the resolution.

Snapshot the wheel periodically to bound the recovery time. A WAL that grows forever makes restart slow, because replay is O(log size). A snapshot writes the current wheel state and truncates the WAL, so recovery replays only the tail since the snapshot.

Monitor the tick rate, the dispatch latency, and the WAL size. A tick rate below the resolution means the driver is drifting; a growing WAL means snapshots are not happening. Both are operator signals.

Do not run two schedulers on the same WAL. The WAL does not coordinate between schedulers, so two readers would both replay and both dispatch, doubling every job. A distributed scheduler needs a leader election or a shared queue, which is out of scope.

Security considerations

Treat every input to the delayed-job-scheduler system as untrusted, because the hierarchical timing wheel path is the one place an external caller controls what the system processes. Validate the input shape before any scheduler operation, and reject early with a clear error rather than letting a malformed input propagate into the enqueue phase where it causes a confusing failure that is hard to trace back to its source.

Keep secrets and configuration in the environment, never in the repository. The node:fs credentials, the signing keys, and the service endpoints are all environment variables, read once at boot and validated, so a misconfigured delayed-job-scheduler fails loudly at startup instead of silently misbehaving at runtime. A system that starts with a bad configuration and runs anyway is a system that will produce wrong results for hours before anyone notices.

Rate-limit the hierarchical timing wheel endpoint per caller, because an unbounded scheduler operation is a resource leak as much as a security problem. A caller that can trigger the tick and dispatch path without limit can exhaust the system, whether intentionally or not. The rate limit is a per-caller ceiling that costs legitimate callers nothing and stops the abuse before it reaches the enqueue logic.

Audit-log every state-changing operation with the caller identity, the input, and the timestamp. The audit log is not for debugging, it is for accountability: if something went wrong, the log says who did what and when. The delayed-job-scheduler system writes the audit log to an append-only store that the system itself cannot modify, so a compromised system cannot rewrite its history.

Do not expose internal errors to the caller. A stack trace is a map of the system internals, and an attacker who collects them learns the scheduler structure. Return a generic error with a correlation id, and log the full error internally with the same id, so an operator can trace it without leaking it.

Limitations and next steps

• The timing wheel is in memory; the WAL is the recovery path, but a WAL loss loses pending jobs.
• No distributed scheduling; two schedulers may double-dispatch a job.
• The tick resolution is fixed; sub-tick delays round to the nearest tick.

The timing wheel is in memory. The WAL is the recovery path, but a WAL loss loses pending jobs, because the wheel is not otherwise persisted. A replicated WAL would survive a disk failure, but that is a distributed system concern and out of scope.

There is no distributed scheduling. Two schedulers with the same WAL would both replay and both dispatch, because the WAL does not have a claim or a lease. A distributed scheduler needs a leader election or a shared queue, which is a different system.

The tick resolution is fixed. A job scheduled with a sub-tick delay rounds to the nearest tick, so a one-millisecond delay on a ten-millisecond tick runs at the next tick, up to ten milliseconds late. A multi-resolution wheel with multiple tick drivers would handle this, but it is out of scope.