Holding Delayed Jobs: Buckets, Timers, and the Cost of Time-Ordered Scans

Retry backoff, reminder mails, and scheduled reports all produce the same structure: a job that must not run yet. If the queue is a table, that structure is a timestamp and an index, and it is easy to assume the index solves the problem. It does not solve it, because every worker’s claim query asks for the same thing — the earliest runnable row — and the earliest runnable row lives at the same place in the index for everyone.

The leaf page everyone wants

With an index on available_at, the claim described in The Job Record State Machine reads from the leftmost qualifying entry. SKIP LOCKED lets the second worker step past rows the first has locked, so the scan advances, but it advances one row at a time through the same region of the index. The pages being read and the locks being taken are all in the same small part of the tree, and the throughput limit stops being the storage’s commit rate and becomes contention on a handful of pages.

The effect is worst when the queue is nearly empty of runnable work and full of delayed work. A claim with WHERE available_at <= now() searches the leftmost position satisfying the predicate and finds nothing, which is cheap per query; but a hundred workers each running that query several times a second all touch the same index root and the same rightmost-in-the-past leaf. The scans return no rows and still consume buffer-pin traffic and lock-manager work.

Delayed work makes this worse in a second way. A row whose available_at is three days out sits in the index at a position that will not be visited for three days, occupying space in the same structure that the runnable rows use, and dragging the index size — and therefore its depth — up with the size of the future backlog rather than the size of the runnable set.

Separating the future from the present

The first structural fix is to stop asking one structure both questions. Delayed jobs get their own table, or their own partition range, and the runnable table holds only jobs that are due now. Claims then scan a structure proportional to the runnable set, and the future backlog costs nothing until it becomes due.

A time-partitioned table achieves the same separation with one schema: partitions by available_at range, one per hour or per day, with the claim query pruning to the current partition. PostgreSQL’s partition pruning restricts the scan to partitions whose bounds overlap the predicate, so a query for available_at <= now() touches the current partition and any older ones, while the partitions holding next week’s jobs are never opened.

Bucketing the timestamp into a column is a coarser version that works on any database: bucket = floor(extract(epoch from available_at) / 60) with a composite index on (bucket, available_at), and the claim adds bucket <= current_bucket. The index is then sorted by bucket first, so a claim reads one bucket’s range rather than a global ordering, and inserting a far-future job never touches the pages that claims use. The bucket size is a trade between index fan-out and the size of each bucket’s range; a minute is the natural unit when scheduling resolution is a minute, and a second when it is finer.

Neither variant removes the head-of-index contention for due work; they only stop the future backlog from making it worse. That contention is the reason the next step exists.

Promotion as its own transaction

Rather than having every worker scan for due jobs, one mover does it in bulk and writes the results into the structure the workers read:

WITH due AS (
  SELECT id FROM delayed_jobs
  WHERE available_at <= now()
  ORDER BY available_at
  FOR UPDATE SKIP LOCKED
  LIMIT 500
)
UPDATE delayed_jobs d
SET promoted_at = now()
FROM due
WHERE d.id = due.id
RETURNING d.id, d.payload;

The mover then inserts those rows into the runnable structure and deletes or marks the source rows. Workers now contend only on the runnable structure, and there is exactly one scanner of the time-ordered index.

The trade is latency against contention. A mover that runs every second makes jobs up to a second late; a mover that runs every hundred milliseconds makes them tens of milliseconds late and costs ten times the scan rate. The resolution the product needs sets the period, and the period sets the cost.

The mover is also a single point of failure with a quiet failure mode: when it stops, jobs remain due and unclaimed, and nothing in the worker pool reports an error because the workers see an empty queue. The check that catches it is a count of rows with available_at <= now() and no promotion time, which grows without bound when the mover is dead. That count belongs on a dashboard, not in a log line.

Bulk promotion also makes the burst explicit. Five hundred jobs whose availability passed at the same instant arrive in the runnable set in one statement, and then a pool of workers starts them all. Spreading their availability times at enqueue — adding a random offset within a window for jobs that have no exact deadline — is the cheapest mitigation, and it belongs to the producer, because only the producer knows whether the exact instant matters.

Timers that live in memory

A timing wheel holds pending timers in an array of buckets indexed by the low bits of their deadline, with each slot representing a fixed span. Insertion is O(1) if the deadline falls within the wheel’s range, and the tick that advances to the next slot moves the entries of the expiring slot forward — either firing them or cascading them into a finer wheel. Varghese and Lauck’s hierarchical variant uses several wheels of increasing span so that a deadline days away does not require an array with a slot per tick, and it is the structure behind timer facilities in kernels and network stacks.

A wheel is the right shape for a queue that must fire thousands of timers per second with low latency, and the wrong shape for durability. The wheel’s state is in memory, so a restart loses every pending timer, and a replica that did not hold the timer cannot fire it. A durable system therefore uses the wheel as a front stage: the authoritative schedule lives in storage, the wheel holds only timers for the next few seconds, and a rebuild on startup reloads the near-term items from the store. The rebuild itself is a range query over the near-term window, which is bounded by the window rather than by the backlog.

The other use of an in-memory timer is the sleep-until-next-due loop. Instead of polling at a fixed interval, a worker reads the minimum availability time and waits until then, waking early when a new job is inserted with an earlier time. That requires a notification path from the producer, which most databases offer as LISTEN/NOTIFY in PostgreSQL, and it converts a poll into an event. It reduces idle query load to nearly nothing and adds a dependency on a notification channel that can lose messages; the loop still needs a periodic fallback wake-up, so the poll becomes a slow safety net rather than the primary mechanism.

When the clock steps

All of this compares the storage’s clock against a timestamp that was written earlier, possibly by a different machine. A wall clock that steps backwards — an NTP correction, a manual change, a virtual machine resuming from a snapshot with a stale clock — makes scheduled jobs wait longer than intended, and a clock that steps forward releases the entire delayed set at once.

The forward step is the dangerous direction, and its size determines the damage. An hour of drift is a burst of whatever was due in that hour; a day is the whole day’s schedule firing together. Computing availability from a monotonic source where possible, and keeping the wall clock only for calendar-anchored schedules, limits the exposure: an interval-based delay of five minutes can be expressed against a monotonic reading, while a job scheduled for 09:00 local time cannot.

Where the delay must survive a restart, the timestamp is necessarily wall-clock, and the mitigation is the same one that applies to catch-up in Cron Triggers, Misfire Policy, and the Runs That Never Happen: a bound on how many delayed jobs may be released per unit time, so a clock jump degrades into a slow trickle rather than a spike.

What the poll really costs

The polling rate is usually chosen by feel. The honest accounting has three terms: the number of queries per second, the cost of a query that finds nothing, and the cost of a query that finds something.

A query that finds nothing walks the index to the leftmost position past now(), touches a few pages that are almost certainly cached, and returns zero rows — one round trip and a small amount of server CPU. A query that finds rows pays for row locks, the transaction, and the commit. Ten workers polling five times a second is fifty near-empty queries per second, which is negligible on a database that is not otherwise busy; a thousand workers at the same rate is fifty thousand, which is not.

The design that scales changes the ratio rather than the constant. Fewer, bulkier claims — each worker claiming twenty jobs and processing them in a batch — reduce the query count per job by a factor of twenty. A dedicated mover that polls once per period reduces the scan count to one per period regardless of worker count. Both are ways of making the number of scans independent of the number of consumers, which is the property that actually matters, and both leave the same residual risk: a structural change in the workload, such as a producer that suddenly schedules a million jobs for the same instant, arrives as a burst in whichever structure is nearest the present.