Job Scheduler

System design deep dive · HLD

Design a Distributed Job Scheduler (cron at scale): full high-level design.

Requirements, back-of-envelope capacity estimation, a high-level design diagram, a deeper deployment architecture diagram, sequence diagrams for leader-elected dispatch and misfire/retry handling, and an entity-relationship diagram for the data model - with the reasoning an interviewer expects behind every box and arrow.

Jump to HLD Architecture Sequence diagram ER diagram

10MActive job definitions

50K/sPeak trigger dispatch rate

<1sTrigger latency, p99

1. Clarify requirements before drawing any box

A strong system design answer starts by pinning down scope out loud. For a distributed job scheduler, that means separating "define a schedule" from "guarantee it fires exactly when promised, even across coordinator restarts, worker crashes, and leap-second-style clock weirdness."

Functional requirements

Schedule a jobGiven a cron expression or fixed interval plus a timezone, register a job that fires on that schedule.

Trigger dispatchAt the scheduled instant, hand the job off to a worker pool for execution, exactly once per scheduled instant.

Retry on failureFailed executions retry with exponential backoff up to a configurable attempt limit, then dead-letter.

Misfire recoveryIf the coordinator was down when a run was due, apply a configurable misfire policy (fire now / skip / catch up).

Non-functional requirements

No single point of failureThe scheduling coordinator itself must survive node loss without missing or double-firing triggers.

At-least-once with dedupExactly-once dispatch is not achievable across a network; the system guarantees at-least-once plus an idempotency key.

Low trigger jitterA job scheduled for 09:00:00 should fire within roughly one second of that instant under normal load.

Horizontal scaleMillions of job definitions, tens of thousands of triggers per second at peak (batch windows, top of every minute).

Explicitly out of scope A general-purpose workflow/DAG engine (step dependencies, branching), a UI cron-expression builder, and per-tenant billing for compute-seconds are called out as extensions rather than core requirements, so the core design stays focused on the scheduling and dispatch guarantee.

2. Back-of-the-envelope capacity estimation

These numbers decide whether a single leader can scan the due-jobs table on every tick, how many Kafka partitions the dispatch topic needs, and how big the worker fleet has to be at the "top of the minute" spike.

Metric	Assumption	Resulting estimate
Active job definitions	10 million across all tenants	~10M rows in job_definitions / schedules
Average trigger rate	Median job fires every ~20 minutes	10M / 1200s ≈ 8,300 triggers/sec average
Peak trigger rate	~40% of jobs are minute/hour-aligned ("top of the hour")	~50,000 triggers/sec during the worst 5-second burst
Storage per job definition	~600 bytes (cron expr, payload ref, metadata, indexes)	10M × 600B ≈ 6 GB for definitions; job_runs history dominates at ~2 TB/year
Worker fleet size	Median job runs ~3s of CPU work, want headroom for bursts	~2,000 concurrent worker slots to absorb the peak burst without backlog

Why this matters The peak-to-average ratio (50,000 vs 8,300 triggers/sec) is the number that justifies almost everything below: an in-memory time wheel instead of a per-second DB poll, a partitioned Kafka topic instead of a single queue, and an autoscaled worker pool rather than a fixed-size fleet.

3. High-level design (HLD)

The HLD names the major components and the one-directional data flow between them, without committing yet to replica counts or regions - that level of detail belongs in the architecture diagram in the next section.

Stateless servicesCoordination & hot stateDurable pipelineAsync / edge

What each box owns

Job service (CRUD path)

Accepts job definitions (cron expression, timezone, payload, retry policy), validates the cron syntax and timezone name, computes the initial next_run_at, and writes both the job definition and its schedule row. It is deliberately kept separate from the coordinator so a burst of job creations never competes with the latency-sensitive trigger path.

Scheduler coordinator (trigger path)

Only the elected leader is active; it renews its etcd lease on a short interval, maintains an in-memory time wheel of jobs due in the next few minutes, and on each tick pops due entries, stamps them with a fencing token, and publishes a trigger event to the dispatch queue. Every few minutes it reconciles the time wheel against the job store to pick up newly created or edited schedules and to recover state after a leader failover.

etcd (leader election)

Provides a lease-based election primitive: whichever coordinator instance holds the lease is the leader, and the lease carries a monotonically increasing fencing token. If the leader is partitioned from etcd and loses its lease, a standby is promoted, and any late trigger from the old leader carries a stale token that downstream consumers can reject - preventing split-brain double dispatch.

Job store, dispatch queue, worker pool, and run history

The job store is sharded by hash of job_id and holds the durable source of truth for schedules. The dispatch queue is a Kafka topic partitioned by job_id so that triggers for the same job are always processed in order. The worker pool consumes triggers, executes the job payload in an isolated runtime, and writes a row to the append-only run history table so a slow analytics query on run history can never block a new trigger from being dispatched.

4. Detailed architecture diagram

The architecture diagram takes every HLD box and answers "how is this actually deployed?" - replica counts, sharding, regions, and the specific technology choice, which is what an interviewer is checking for once they've accepted the high-level shape.

Decision	Choice	Reasoning
Leader election	etcd lease + Raft, not a DB advisory lock	Built-in TTL leases and fencing tokens give split-brain protection out of the box, with lower operational overhead than running a separate ZooKeeper ensemble.
Job store sharding key	Hash of job_id	Even write distribution; the due-job scan uses a secondary index on next_run_at within each shard, scattered-gathered by the leader once per tick rather than per request.
Dispatch queue partitioning	Partition by job_id, not round-robin	Guarantees two triggers for the same job are never processed out of order by different consumers, at the cost of a potential hot partition for an extremely frequent single job.
Disaster recovery	Warm standby coordinator in a second region, not active-active	Active-active dual dispatch risks duplicate triggers across regions; a single active leader with a documented failover runbook bounds blast radius without that complexity.

5. Sequence diagrams for the two critical flows

A sequence diagram is where an interviewer checks whether you actually understand call order, what is synchronous versus fire-and-forget, and how failure and recovery paths differ from the happy path.

5.1 Leader-elected trigger dispatch (happy path)

Step 2's fencing token is the detail that matters most: it is stamped onto the trigger event in step 5 and later checked by the worker (or a dedup layer in front of it) so that even if a stale former leader briefly resumes writing after losing its lease, its triggers carry an outdated token and are rejected rather than causing a duplicate execution. Step 7 is drawn as a non-blocking poll because the worker pool pulls from Kafka on its own cadence rather than being pushed to.

5.2 Misfire detection and retry with exponential backoff

The same coordinator that owns dispatch also owns retry scheduling, so a retry is really just another trigger with an incremented attempt counter and a future next_run_at - it re-enters the same time wheel rather than needing a separate retry subsystem. Jitter on step 4's backoff prevents thousands of jobs that failed at the same instant (a downstream outage) from all retrying in lockstep and re-causing the outage they were retrying against.

6. Entity-relationship (ER) diagram and schema

The data model has to answer three questions: what column does the coordinator scan on every tick, how is a race between two coordinator replicas prevented at the row level, and how does execution history stay queryable without slowing down that hot scan.

Key modeling decisions

next_run_at is indexed on a narrow schedules tableKept separate from job_definitions so the leader's due-job scan never has to read or lock the wide payload/config columns.

version column enables optimistic lockingA coordinator claiming a due schedule does a conditional UPDATE ... WHERE version=? to guard against a split-brain window before the etcd fencing token is even checked downstream.

job_runs is append-only and time-partitionedPartitioned by day so old partitions roll off to cold storage without locking the current partition's inserts, mirroring how high-volume event tables are typically managed.

NoSQL alternativeDynamoDB with next_run_at as a GSI sort key scales the due-job query well, but multi-row transactional updates (claim + reschedule atomically) are harder without conditional writes.

Storage choice	Use when	Watch out for
Relational (Postgres), sharded	You need an atomic claim-and-reschedule update and straightforward joins for the admin UI's job list.	Cross-shard range scans for "all due jobs across shards" require scatter-gather from the leader.
Key-value / wide-column (DynamoDB/Cassandra)	Access pattern is purely "jobs due before now" via a single GSI/secondary index.	Atomic claim-and-reschedule needs conditional writes; cross-job admin queries and ad-hoc joins are much harder.

7. Deep dives interviewers actually probe

How do you guarantee only one coordinator dispatches a given trigger?

Two layers: leader election via etcd ensures only one instance is actively scanning at a time, and a fencing token stamped on every trigger lets any downstream consumer reject a message from a leader that has since lost its lease. On top of that, an idempotency key of (job_id, scheduled_time) is enforced at the worker/dedup layer, so even a rare double-publish (e.g. during a leader handoff) results in the second execution being recognized and skipped rather than run twice.

Time wheel vs re-scanning the schedules table every second

Polling the database every second for 10 million rows does not scale. Instead the leader keeps a hierarchical timing wheel in memory - buckets for "due in the next second," "next minute," "next hour" - giving O(1) insert and fire operations regardless of job count. The database is still the source of truth: every few minutes the leader reconciles the wheel against schedules to pick up new/edited jobs and to rebuild its in-memory state from scratch after a failover.

// Simplified hierarchical wheel tick
class TimingWheel {
    Map<Long, List<Job>> secondBuckets; // key: epoch second
    void tick(long nowEpochSecond) {
        List<Job> due = secondBuckets.remove(nowEpochSecond);
        if (due != null) due.forEach(dispatcher::publishTrigger);
    }
}

What is the misfire policy when the coordinator was down?

If a leader outage or a full etcd quorum loss means next_run_at passed unnoticed, three configurable policies apply per job: FIRE_NOW (run once immediately on recovery, the default for most jobs), SKIP (drop the missed run and wait for the next naturally scheduled time - correct for a "send the 9am digest" job where a stale digest is worse than a missing one), and CATCH_UP (run once for every missed interval, capped at a configurable maximum to avoid a thundering herd of backlog runs after a long outage).

Retry/backoff strategy and permanently broken ("poison") jobs

Exponential backoff with jitter (30s, 60s, 120s, 240s...) up to a per-job max_attempts, after which the run is dead-lettered and an on-call alert fires rather than retrying forever. This protects both the job's downstream dependency (no retry storm) and the scheduler itself (a permanently failing job cannot monopolize worker capacity or dispatch queue throughput at the expense of healthy jobs.)

Clock skew, DST transitions, and timezone-aware cron

Every job stores an explicit IANA timezone (e.g. America/New_York), and next_run_at is computed with a timezone-aware date library rather than a fixed UTC offset, so a "9am daily" job doesn't silently shift by an hour across a DST boundary. Coordinator nodes rely on NTP-synchronized clocks, and the etcd lease TTL is set with enough margin (several seconds) above the worst observed clock skew between nodes to avoid a lease being wrongly considered expired.

What is the single biggest bottleneck as this scales 10x?

Not the time wheel itself - it is O(1) regardless of job count. The real constraint becomes the periodic reconciliation query against the schedules table across all shards, since it must observe every newly created or edited job within a bounded staleness window. That is solved by replacing polling reconciliation with a change-data-capture stream (e.g. Debezium on the schedules table) that pushes edits to the leader's in-memory wheel instead of the leader pulling on a timer.

8. Summary: what a strong answer covers

Clarified scope before designingJustified every number with a calculationLeader election with fencing tokens In-memory time wheel over per-second pollingConfigurable misfire policy per jobBounded exponential backoff with jitter

Interview tip When asked to design a distributed job scheduler, the strongest signal is treating "at-least-once plus idempotent dedup" as the actual guarantee (not exactly-once, which is not achievable), and explicitly naming the fencing-token mechanism that prevents a stale leader from causing a duplicate trigger during failover.