Design a Distributed Job Scheduler: Leases, Fencing Tokens and the Missed Tick
A system design walkthrough for running millions of cron and one-off jobs on time, exactly as often as intended: why two schedulers double-fire, fencing tokens, deterministic run IDs, sharded due-time polling, the top-of-the-hour herd, missed-tick policies, time zones and DST, and what to measure.
A scheduler's hardest problem isn't timing. It's that any scheduler you can make highly available will sometimes fire the same tick twice. Accept that and design for it: a deterministic run ID per (job, scheduled time) so duplicates collapse, fencing tokens so a paused leader can't act on a lease it lost, and per-job policies for the ticks you miss.
At 02:00:00 the billing job fires on scheduler A. At 02:00:01 scheduler A's JVM starts a stop-the-world garbage collection that lasts 40 seconds. Its leadership lease expires at 02:00:15. Scheduler B takes over at 02:00:16, sees that the 02:00 run has no completion record, and fires it. At 02:00:41 scheduler A wakes up, still in the middle of what it thinks is its run, and carries on charging customers. Everyone gets billed twice, and every component involved behaved correctly.
That story, with the details changed, is the reason distributed schedulers are hard. Making a scheduler available means running more than one, and running more than one means that at some point two of them will believe they own the same job. Martin Kleppmann's classic essay on distributed locking uses almost exactly this pause scenario to argue that a lock alone can't protect you. Google's SRE book makes the same point about its own distributed cron: which jobs may run twice, and which may be skipped, is a property of each job, not of the scheduler.
A shared scheduler service for a company's batch work: cron-style recurring jobs, one-off "run at" jobs, and delayed retries. Working requirements (illustrative numbers):
10 million schedules, most recurring. Some run every minute; most hourly or daily.
Peak firing rate around 50,000 runs a second, concentrated at the top of each hour and minute (more on that below).
On time: 99% of runs start within 2 seconds of their scheduled time.
Exactly as often as intended, from the job's point of view. The scheduler is allowed to fire twice internally as long as the job only does its work once.
Survive the loss of any node or zone without losing schedules or skipping runs silently.
Fixed intervals are the simple case. A price monitoring system runs the same machinery with schedules whose intervals rewrite themselves after every run.
The simplest version is one process with an in-memory priority queue keyed by next fire time. It works perfectly and has one obvious flaw: when that process dies, nothing runs. The fix everyone reaches for is a second process and leader election.
How a paused leader double-fires a job
Scheduler A is the leader. At 02:00:00 it fires the nightly billing run and starts tracking it.
A stops the world for garbage collection. It isn't dead, so nothing tells it to stop; it just isn't running any code.
A's lease expires at 02:00:15 because it didn't renew. B acquires the lease, which is exactly what failover is supposed to do.
B sees the 02:00 run has no completion record and fires it. From B's point of view, A died mid-run.
A wakes up and carries on. Its code checked the lease before the pause, not after. Two runs of the same tick are now charging the same customers.
≡
5 steps. Press Play to walk through them, or click any part of the diagram.
Scheduler A fires the 02:00 run and pauses; its lease expires; B takes over and fires the same run; A resumes and continues, so the job runs twice.
You can shorten the window with tighter leases and faster renewals. You can't close it. A process can pause between checking its lease and acting on it, for garbage collection, a page fault, a VM migration or a slow disk. This is the same time-of-check to time-of-use gap that left AWS's DynamoDB endpoint with an empty DNS record in October 2025: a worker checked its plan was fresh, stalled, then wrote a stale one.
So the design stops trying to make the scheduler fire exactly once. It makes the second fire harmless.
When scheduler B fires the 02:00 run, it computes the same run_id that A did. Inserting the run record with a uniqueness constraint on run_id turns the second fire into a no-op: the insert fails, B sees the run exists, and moves on. Any number of schedulers firing the same tick produce one run.
That handles the case where B fires after A has recorded the run. It doesn't handle A continuing to act after losing ownership. For that you need the second defence.
Every time the lease changes hands, the lease store hands out a number that only goes up: A's lease came with token 33, B's comes with token 34. Every write the run makes to something important carries the token, and the receiving system remembers the highest token it has seen for that run and rejects anything lower.
When A acquired the lease, the lease store gave it token 33. A attaches 33 to every write the billing run makes.
A pauses, its lease expires, and B acquires it with token 34.
B's writes carry 34. The store records 34 as the highest token it has seen for this run.
A resumes and writes with token 33. The store compares, sees 33 is lower than 34, and refuses. A doesn't need to know it lost the lease; the store knows.
≡
4 steps. Press Play to walk through them, or click any part of the diagram.
A holds token 33 and pauses; B takes over with token 34 and writes; when A resumes, its writes carry 33 and the store rejects them.
The key move is where the check lives: in the resource, not in the client. A process can't reliably know whether it still holds a lease, because it can pause right after checking. The thing it's writing to can always compare numbers. Kleppmann's essay gives this exact argument for fencing over locks.
In practice you can't put fencing into every downstream system, especially third-party APIs. For those, pass the run_id as an idempotency key; many payment APIs accept one. That's how the payment ledger design avoids double charges when its own retries fire twice.
With duplicates made harmless, the rest of the design is about firing ten million schedules on time without one big box.
Distributed job scheduler
next_fire computed1poll: due in next 30s2insert run_id3enqueue at due time45status + token5Schedule APIcreate, pause, deleteSchedule storeby shard + next_fireShard ownersone lease per shardRun recordsunique run_idRun queueat-least-onceWorkersexecute + heartbeat
A new schedule is stored with its next fire time already computed, in UTC, and a shard number (a hash of the job ID, say 1 of 1,024 shards).
Each shard has one owner at a time, holding a lease with a fencing token. Every few seconds an owner queries its shard for schedules due in the next 30 seconds.
For each due schedule, the owner inserts a run record with the deterministic run_id and advances the schedule's next fire time, in one transaction.
Runs are released to the queue at their due time from a small in-memory timer wheel, so the database isn't polled every second for every job.
Workers pick up runs, execute them with the run_id as idempotency key, send heartbeats while running, and record the outcome with the shard's fencing token.
≡
5 steps. Press Play to walk through them, or click any part of the diagram.
Schedules live in a store partitioned by shard; shard owners poll for due work and write run records; a queue feeds workers that execute runs idempotently.
A few choices in that picture are worth defending:
Shard the ownership, not just the data. One global leader is simpler but caps throughput at one machine and makes every failover global. With 1,024 shards and leases per shard, a dead owner costs a 1,024th of the schedule for a few seconds, and owners rebalance shards among themselves as nodes come and go.
Poll a window, then time precisely in memory. Querying "everything due in the next 30 seconds" every few seconds keeps database load proportional to the firing rate, not the schedule count. An index on (shard, next_fire_time) makes it a range scan. The in-memory timer wheel gives sub-second precision for that small window. If the owner dies, its successor re-reads the same window; the run IDs make any overlap harmless.
Advance the schedule and create the run atomically. If those are separate writes, a crash between them either skips a run or creates one twice. One transaction (or one conditional write in a key-value store) keeps them together.
The queue is at-least-once, and that's fine. A worker that dies mid-run stops heartbeating, the queue redelivers, and the next worker sees the same run ID and the same fencing rules. The durable agent runtime design goes much deeper on making long-running work resumable.
Humans write cron expressions, and humans love round numbers. Ask a thousand teams to schedule a daily job and a large share will pick midnight, and almost all will pick minute zero of some hour. The SRE book calls this out directly: the "thundering herd" of jobs that all start at the same moment, and the load spike it puts on the scheduler and everything the jobs touch.
Three things help, in order of how much I'd rely on them:
01
Let jobs say they don't care. A schedule like daily, any time between 00:00 and 04:00 is honest about what most "midnight" jobs need. The scheduler picks a stable offset by hashing the job ID into the window, so each job runs at the same time every day but the fleet is spread out.
02
Add bounded jitter by default for jobs that don't specify, a few seconds to a few minutes depending on frequency, and let jobs opt out if they truly need second-precision.
03
Pre-fire the window. Because owners poll 30 seconds ahead, the run records for 00:00:00 are already written by 23:59:45. At midnight the scheduler only releases queue messages from memory, which is cheap.
Sometimes the scheduler is down, or a shard has no owner for a minute, or a job's previous run is still going. When it recovers, it finds ticks that should have fired. What to do with them can't be decided centrally.
Fire all missed runs
Right for jobs where each tick is distinct work (process the 02:00 hour's logs)
A long outage creates a burst of catch-up work at recovery
Wrong for jobs that just refresh state
Every tick that was due gets a run, oldest first
Fire the latest missed run once
Right for refresh jobs (rebuild a cache, sync a mirror)
Recovery cost is one run, however long the outage
Loses per-tick work if the job needed it
All missed ticks collapse into one run, now
vs
Verdict: Make it a field on the schedule, with 'fire the latest once' as the default and a maximum lateness after which even that is skipped.
Two catch-up policies for missed runs
(The third common option is to skip missed runs entirely, for jobs where a late run is worse than none, like a "send the 9 AM digest" email at 3 PM.)
Kubernetes CronJob has the same knobs, which makes it a useful reference: startingDeadlineSeconds bounds how late a run may start, and concurrencyPolicy decides whether a new run may start while the previous one is still running: allow both, forbid the new one, or replace the old one. Kubernetes' documentation also says plainly that jobs should be idempotent, because the controller can create more than one job for a tick in rare cases.
Overlap deserves its own policy for the same reason. An hourly job that takes 70 minutes will overlap itself forever unless the scheduler forbids, queues or replaces.
Store every schedule with its time zone and compute next fire times in that zone, converting to UTC only for storage and comparison. "Every day at 09:00 in Asia/Kolkata" and "every day at 03:30 UTC" are the same today, and the same forever, because India doesn't observe daylight saving time. "Every day at 09:00 in America/New_York" changes its UTC time twice a year.
The two awkward cases need written rules:
A time that doesn't exist. On the spring-forward day in New York, 02:30 never happens. Run it at the next valid instant (03:00), or skip; pick one and document it.
A time that happens twice. On the fall-back day, 01:30 happens twice. Running on the first occurrence only is the least surprising default, and the deterministic run ID makes enforcing that easy: the second 01:30 maps to the same local-time tick.
Never use the local clock of the scheduler machine for any of this. Compare against the database's clock or a well-synchronised UTC source, and treat a big jump in either as an incident.
A scheduler that's quietly late looks healthy on every dashboard except the one you forgot to build:
Lateness, as a histogram: actual start time minus scheduled time, per shard. This is the SLO.
Duplicate fires suppressed: how often a run ID insert hits the uniqueness constraint. A rising number means leases are flapping.
Fencing rejections: writes refused for a stale token. Each one is a double-execution that you prevented, and a hint about pauses or network partitions.
Missed ticks by policy: how many were fired, collapsed or skipped, so a long outage shows up as a number, not a mystery.
Shard ownership churn: lease handovers per minute. Healthy clusters are boring.