A distributed job scheduler, part 1: designing the claim

A run fires twice. The customer gets charged twice, or emailed twice, or their export job runs twice and the second one overwrites the first with a truncated file. You go looking, and the schedule looks fine — the job was configured to run once. The bug isn’t in the cron expression. It’s in the six lines that decide which worker picks up a due run, and whether two of them can pick up the same one.

That decision is the whole scheduler. Everything else — parsing schedules, storing jobs, exposing an API — is table stakes you can get right by being careful. The claim is where a distributed scheduler is actually hard, because it is the one place several processes race over shared state with no referee. This post is about designing that claim, and about the delivery guarantee that falls out of it — which is not the one people usually promise.

I built a reference implementation to have something concrete to point at: a Rust scheduler over Postgres and NATS, hexagonal, meant to be read rather than shipped. The design decisions below are all load-bearing in it.

# The claim: pulling disjoint work with no coordinator

Picture the steady state. A handful of engine replicas, no leader among them, each waking on a timer and asking the same question: what is due right now, and which of it is mine to run? If two replicas answer “these ten” and overlap on even one row, that row gets dispatched twice.

The mechanism that prevents it is one SQL clause:

WITH candidates AS (
    SELECT id FROM job_runs
     WHERE state = 'pending' AND scheduled_at <= $now
     ORDER BY scheduled_at
       FOR UPDATE SKIP LOCKED
     LIMIT $batch
)
UPDATE job_runs SET state = 'claimed', lease_owner = $owner, ...
 WHERE id IN (SELECT id FROM candidates)
RETURNING ...

SELECT … FOR UPDATE SKIP LOCKED locks the due rows this transaction reads and skips any row another transaction already holds a lock on. So replica A locks the first hundred due rows, replica B — running the identical query a millisecond later — passes over those hundred and takes the next hundred. Two disjoint batches, no coordination, no leader.

The reason this is worth dwelling on is that every intuitive alternative is wrong in a way that only shows up in production:

• SELECT then UPDATE, no locking. Two replicas read the same due rows and both dispatch them. Not occasionally, under a race — every run, every tick. The double-delivery is the default behaviour, not the edge case.
• SELECT … FOR UPDATE without SKIP LOCKED. Correct, and serial. The second replica blocks on the first one’s locks instead of stepping around them, so replicas queue behind each other and adding a replica adds latency instead of throughput. You’ve built a distributed system that scales negatively.
• A leader, or an advisory lock. Works — and reintroduces exactly the coordinator the whole design was trying to avoid, plus its failover story.

SKIP LOCKED is the one option that makes concurrency non-blocking: a contended row is passed over, not waited on. That property — disjoint batches from uncoordinated workers — is the foundation everything else sits on.

One subtlety that bites people: the ORDER BY scheduled_at belongs inside the locking select, where it decides which rows get claimed (oldest-due first, so a backlog can’t starve the newest work). It says nothing about the order of the batch you get back. RETURNING makes no ordering promise at all. Conflating the two is how “claim the oldest” quietly becomes “return them sorted,” which the database never agreed to.

# The lease: what happens when a worker dies mid-run

Claiming a run marks it claimed and records a lease — an owner and an expiry. The lease exists for one scenario: a worker claims a batch and then dies before finishing it. Without a lease, those runs sit claimed forever, owned by a process that no longer exists, and since the claim query only selects pending rows, nothing ever picks them up again. They’re lost.

So a reaper sweeps for leases whose expiry has passed and returns those runs to pending, where the next claim will pick them up. Simple enough — until you ask how long the lease should be, and discover the answer is not “some round number that feels safe.”

Here’s the trap, and it’s worth stating precisely because I got it wrong first. The message that dispatches a run goes through a broker with at-least-once redelivery: if a worker doesn’t acknowledge within ACK_WAIT, the broker redelivers, up to MAX_DELIVER times. That redelivery is normal — a worker restarting during a rollout triggers it. Now suppose the lease expires while that legitimate redelivery is still in flight. The reaper sees an expired lease, returns the run to pending, a later claim dispatches it again — and the reaper has just caused the duplicate execution it exists to prevent.

The lease therefore has to dominate the entire dispatch-to-completion path, including the broker’s redelivery window:

LEASE_SECS > publish + queue_wait + ACK_WAIT × (MAX_DELIVER − 1) + execution + complete

With the original LEASE_SECS = 30 and a five-second ACK_WAIT over five delivery attempts, up to twenty of those thirty seconds could be consumed by ordinary redelivery alone — leaving ten for everything else, and making the reaper a source of duplicates under a completely routine rollout. Raising it to 120 fixes it. Because that relationship is a correctness invariant, not a tuning knob, the reference implementation enforces it at compile time — a const _: () = assert!(LEASE_SECS > ACK_WAIT × (MAX_DELIVER − 1) × 3) that fails the build if someone lowers the lease back into the danger zone.

# The guarantee you can actually make

Now the uncomfortable part. Everyone wants exactly-once delivery. You cannot have it — not here, not with a broker, not anywhere the network can drop an acknowledgement. What you can build is at-least-once delivery plus idempotency, which composes into effectively-once: a run may be delivered more than once, but it is recorded exactly once, and if the work itself is idempotent, executed to the same effect once.

The precision matters, and rounding it to “exactly-once” isn’t a simplification — it’s a false promise that someone downstream will design against and get burned by. So the reference implementation refuses to use the phrase anywhere.

Three mechanisms make effectively-once real:

Idempotency lives in the schema, not the application. A UNIQUE (job_id, scheduled_at) constraint says a job’s run at a given instant is one run, forever. The materializer, a retried API call, and a redelivered message are three independent writers, and only the database sees all three. Put the guarantee anywhere else and one of the three writers slips past it.

The worker’s ordering is execute → complete → ack, and the order is the guarantee. Acknowledge the message first and a crash in the gap loses the run — the broker believes it delivered, the database never learned it ran, nothing is left to reconcile. Complete first and a crash in the gap causes a redelivery of a run that is already terminal, which the completion step reports as “changed nothing” so the second attempt skips the work and acks. The asymmetry is the whole argument: the tolerable failure is a duplicate delivery; the intolerable one is a lost run.

Claim-then-publish is a dual write, and it needs compensation. The claim commits claimed for a whole batch before any dispatch message is sent — there’s no distributed transaction spanning Postgres and the broker. If a publish fails partway through the batch, the runs that didn’t publish are claimed with nobody working them. So a publish failure releases those specific runs back to pending, and — critically — the dispatch loop does not abort on the first failure, because aborting would strand every later run in the batch as a silent loss. That exact bug shipped green once and was caught by a test that injects a publish failure in the middle of a batch and asserts the rest still went out.

# Why hexagonal, and why it’s checkable

The whole thing is ports-and-adapters: a domain crate that knows nothing about Postgres, NATS, HTTP, or async runtimes, with adapters plugged in around it. This isn’t a performance decision — in Rust the levers that move cost are dispatch strategy and the engine design, not the architecture style. It’s a testability and honesty decision, and its value is that the rule is enforceable rather than asserted:

cargo tree -p scheduler-domain --edges normal

The domain’s entire dependency set is thiserror, time, and uuid. A future commit that reaches for sqlx inside the domain shows up as one new line in that output. The architecture isn’t a diagram in a wiki that drifts from reality; it’s a property the build can check.

# Putting it together

The claim is the scheduler. Get SKIP LOCKED right and uncoordinated replicas pull disjoint work; get the lease timing right — dominating the broker’s redelivery window, not just some round number — and the recovery mechanism stops being a source of the very duplicates it exists to repair. And be honest about the guarantee: at-least-once plus idempotency, composed into effectively-once, never fake exactly-once.

Part 2 gets into building this in Rust — the ports, the adapters, and the handful of bugs that shipped green and were caught by running the thing rather than by the tests that were supposed to catch them.

# References

• PostgreSQL SELECT … FOR UPDATE SKIP LOCKED: https://www.postgresql.org/docs/current/sql-select.html#SQL-FOR-UPDATE-SHARE
• NATS JetStream delivery and redelivery: https://docs.nats.io/nats-concepts/jetstream/consumers
• Hexagonal (ports and adapters) architecture: https://alistair.cockburn.us/hexagonal-architecture/
• The two-generals / exactly-once impossibility, in practice: https://bravenewgeek.com/you-cannot-have-exactly-once-delivery/