Reference: Scheduling — Timing Wheels, Delay Queues, and Cron at Scale

What it is

A scheduler runs work at a future time: send this email in 10 minutes, run this report at midnight, retry this payment tomorrow. The core problem is deceptively simple: how does the system know which tasks are due right now among billions of pending ones, without scanning them all? The answer decides whether the system scales, and it is a data-structure choice: a database index, a sorted set, or a timing wheel.

Important

Key takeaway: The tick mechanism is what turns a scheduler from “a database with a timer” into a scalable system: it decides whether you scan all tasks or only the due ones each second. Separate finding due tasks (trigger, driven by time) from running them (dispatch, driven by worker capacity), and have workers pull.

When you care

“Design a job scheduler” and “design a delay queue” both land here, along with the follow-ups: what about millions of tasks due at midnight, what if a worker dies mid-task, and how do you run cron at scale?

Note

Interview signal: Walking from database polling to a sorted set to a time wheel, and saying why each fails at a billion tasks, is the move. Then naming the thundering herd at clock-aligned times (midnight) and pre-sharding those buckets is what separates levels.

Finding due tasks

Approach	How	Why it fails or wins
Database polling	Every N ms, `SELECT ... WHERE due_time <= now() AND status = 'pending' LIMIT n`	Simple, fine at small scale. At a billion tasks the query touches too many rows, especially in thundering-herd windows
Sorted set (for example Redis)	Task ids scored by due time; fetch the due range	O(log N) per operation, but one set cannot hold a billion entries, and clock-aligned spikes make the current-time shard hot
Time wheel	Time is divided into slots; each slot holds only the tasks due in that slot; a pointer advances one slot per tick	O(1) to find the due slot, O(bucket size) to process it; shardable by time

How a time wheel works. Picture a clock with 3,600 slots, one per second in an hour. Each slot is a bucket of task ids due at that second, and a pointer advances one slot a second. When it lands on a slot, everything in that bucket becomes ready.

Hierarchical wheels handle tasks further away: a second wheel (60 slots), a minute wheel (60), an hour wheel (24), a day wheel. A task due in 3 hours, 25 minutes, and 40 seconds goes into the hour wheel at +3. When the hour slot arrives, the task cascades into the minute wheel at +25; when that slot arrives, it cascades into the second wheel at +40, and fires. Each task is touched a few times, never scanned continuously.

Worked example. One billion tasks a day spread evenly is about 11,600 per second, so each second’s bucket holds roughly 12,000 tasks. A clock-aligned spike at midnight might put 300,000 in one bucket, which is still bounded and known in advance, so you can inspect the future bucket and pre-warm the dispatch pipeline.

Why a time wheel over a sorted set, for this problem:

Bounded scan cost. A bucket is pre-partitioned: O(1) lookup of the current slot, not a linear scan of the due range.
Shardable by time, not by key. Node A handles seconds 0 to 29 and node B 30 to 59; set sharding is by key hash, which does not map to time boundaries.
Pre-mitigated thundering herds. You can look ahead at a hot bucket; with a sorted set you discover the spike the moment it fires.

Trigger, dispatch, and the state machine

Task arrives. The task service computes the due time (immediate, delayed, or next cron instance) and inserts the id into the right bucket.
Wheel ticks. Every second the trigger engine advances and reads the current bucket; those ids are due.
Emit to a ready queue, partitioned by priority and worker type. This is the buffer between triggering and dispatch and absorbs thundering herds.
Workers pull from the ready queue and atomically claim a task with a compare-and-swap on a version column (pending to running).
Lease and heartbeat. The claimed task has a lease (for example 60 seconds); the worker must heartbeat within it, or the dispatcher assumes it died and re-enqueues the task.
Completion. The worker reports success or failure; the state moves to succeeded or failed, and a recurring task schedules its next instance.

CREATED -> PENDING -> READY -> RUNNING -> SUCCEEDED
                                       -> FAILED    -> PENDING (retry)
                                       -> TIMED_OUT -> PENDING (re-enqueue)

Each transition is a conditional update, UPDATE task SET status='running', version=version+1 WHERE task_id=? AND version=?. If the compare-and-swap fails, another worker already claimed it, and the loser backs off. That gives at most one active execution without a distributed lock.

Caution

Common mistake: Push-based dispatch, where the scheduler pushes tasks to workers. During a thundering herd the dispatcher overwhelms slow workers with more than they can handle. Pull is self-regulating: workers take work only when they have capacity, which is also why the ready queue is a buffer and not a bottleneck.

Warning

Production reality: Even a compare-and-swap creates contention when 300,000 tasks become ready together. At that scale, partition the task table and the ready queue so each shard handles a slice of the burst, and make task handlers idempotent: a lease expiry can run a task twice.

Recurring tasks (cron)

Do not store all future instances of a recurring task. Store the cron expression and generate the next instance only:

The user submits a cron expression (0 0 * * *, daily at midnight).
The cron resolver computes the next due time and inserts that one instance into the wheel.
When it fires and completes, the resolver computes the following instance and inserts it.

This keeps storage proportional to the number of schedules, not to how far ahead they run. Handle missed runs (a scheduler outage over midnight) with an explicit policy: run once to catch up, run every missed instance, or skip.

Delay queues and DAGs

A delay queue is the same wheel with a different front end: the task’s “due time” is now plus a delay, and when due it is delivered to a queue instead of a worker fleet. A dependency graph of tasks is a scheduler that fires a task only when its upstream tasks have succeeded: track an unmet-dependency count per task, decrement when an upstream finishes, and place the task in the wheel or ready queue when the count reaches zero.

When to pick what

Situation	Choose	Why
Modest volume, one database	Polling with an index	Simplest
Millions of delayed items, no coordination overhead	A sorted set	O(log N), easy
Billions of tasks, clock-aligned spikes	A hierarchical time wheel, sharded by time	Bounded scan, pre-shardable
Dispatching to workers	Pull from a ready queue with leases	Self-regulating; handles worker death
Exactly one execution at a time	Compare-and-swap on a version column	No distributed lock needed
Recurring jobs	Store the cron expression; materialize the next instance	Storage stays small

Walkthrough: Designing a Distributed Job Scheduler — the full scheduler design this tick mechanism drives.
Walkthrough: Designing a Notification System — scheduled and delayed sends through a delay queue.
Reference: Distributed Locks and Fencing Tokens — what a lease expiry means when the old worker is only paused.

Tags #system-design#concepts#scheduling#reference