10. Distributed Job Scheduler Advanced + Distributed Systems

A. Realistic Interview Prompt

Plain cron works fine on one machine because that one machine is both the clock and the executor — there's nothing to coordinate. The moment scheduling has to survive a single machine's failure, "what time should this run" and "did this already run" become distributed-systems questions with no single obviously-correct answer, and the entire design is really about answering those two questions correctly under failure, not about scheduling logic itself.

B. Difficulty

Advanced, distributed-systems-heavy — the core mechanics (a schedule, a queue, workers) are simple; what's hard is guaranteeing a job runs despite crashes, network partitions, and clock skew, without either silently skipping it or running it twice in a way that matters (e.g., double-charging a customer, double-sending an email).

C. What This Problem Tests

• Recognizing that "the scheduler" is a role that must itself be highly available — a single machine deciding "what's due to run right now" is a single point of failure for the entire system's core function
• Leader election as a concrete mechanism (not just a buzzword) for ensuring exactly one instance is actively making triggering decisions at a time, while the rest stand by ready to take over
• Honest engagement with "exactly-once" execution — recognizing it's unachievable in the strict distributed-systems sense over an unreliable network, and designing instead for effectively-once semantics via idempotency, which is the actual, correct engineering answer
• Designing retry and failure-handling policy (backoff, max attempts, dead-lettering) as a first-class feature, not an afterthought
• Comfort with job dependency graphs (job B should only run after job A succeeds) as a natural, expected extension of a scheduling system

D. Requirements

Functional

1. Users can register a job with a schedule — a cron-style recurring expression, or a one-time future timestamp
2. The system triggers each job's execution at (or very close to) its scheduled time
3. Users can view a job's execution history and status (success, failure, retrying)
4. A failed job execution is retried according to a configurable policy

Non-Functional

• High availability of the scheduling function itself — the system must keep triggering jobs on time even if individual machines (including whichever one was "in charge" of triggering) crash
• Effectively-once execution — a job should not be silently skipped, and should not run twice in a way that produces a duplicated real-world side effect (this document's standard illustrative example: a scheduled job that charges a customer's credit card must never double-charge them)
• Timing accuracy — triggering within a small tolerance window (illustratively, a few seconds) of the scheduled time, not "sometime that minute" or later
• Horizontal scalability — supporting a very large number of registered jobs (millions) and a large number of jobs due to fire at the same instant (e.g. everything scheduled for "midnight UTC")

Out of scope: a full workflow/DAG orchestration UI, arbitrary job-code sandboxing/security model, cross-region job migration.

E. Clarifying Questions

F. Assumptions

• Confirmed: cron-style recurring and one-time job registration, on-time triggering, execution history, configurable retries.
• Assumption: effectively-once semantics via idempotency (E's clarifying question 1) — the honest, achievable, and actually-expected answer to this problem, not literal exactly-once delivery.
• Assumption: job dependency graphs are in scope (E's clarifying question 2) — the more complete and commonly-discussed version of this problem.
• Assumption: jobs are lightweight triggers (an HTTP callback or a message enqueued to a downstream system), not arbitrary heavy compute (E's clarifying question 3) — keeps the design focused on scheduling/triggering correctness rather than a general compute-cluster scheduler.
• Assumption: a several-second timing tolerance (E's clarifying question 5) — realistic for the vast majority of real scheduled-job use cases (daily reports, periodic cleanups, reminder emails).

G. Capacity Estimation

H. Core Entities

I. API Design

POST   /v1/jobs                    { schedule_expr, target, depends_on? } -> { job_id }
GET    /v1/jobs/{id}/executions    -> [{ execution_id, scheduled_for, status, attempt_count }]
DELETE /v1/jobs/{id}                                                       (unregister)
-- internal, not client-facing:
(leader-only) scan Job store for next_run_at <= now()                      (M, N)
(worker-facing) POST /internal/executions/claim  -> { execution_id, lease } (O)
(worker-facing) POST /internal/executions/{id}/complete { status }         (O, P)

Why the trigger/scan step has no client-facing endpoint at all: "decide what's due to run" is a purely internal system responsibility performed by whichever instance currently holds the leader role (M) — exposing it as an API would imply any caller should be able to trigger job evaluation, which is meaningless; only the internal claim/complete lifecycle needs to be a well-defined contract, since that's what the worker fleet (R) actually interacts with.

J. Basic / Naive High-Level Design (V1)

The simplest thing that satisfies the functional requirement in isolation: one server holds all job definitions in memory (or polls a database), loops every few seconds checking which jobs are due, and directly executes each due job itself.

V1 — a single always-on process. Works fine until that one process crashes.

Why this breaks immediately, not eventually: the single scheduler server is a hard single point of failure for the entire system's core purpose — if it crashes, restarts, or is mid-deploy at the exact moment a job is due, that job simply doesn't run, with no other instance positioned to notice or take over. Worse, if a naive fix is "just run two scheduler instances for redundancy," both instances would independently see the same due job and both trigger it — turning one failure mode (missed jobs) into another (duplicate execution), unless something coordinates which instance is actually allowed to act.

K. Data Model & Store Choice

A relational or strongly-consistent store for job definitions and the leader lock: both next_run_at updates and leader-lock acquisition (M) need atomic conditional writes — the exact same "reach for the storage layer's native atomicity primitive" principle used for Ticketmaster's seat holds and Rate Limiter's counter, here applied to "claim the leader role" and "claim this due job for a worker" instead.

A separate, append-heavy store for execution history: executions are written far more frequently than job definitions change, and are queried mostly by recent time range per job — a natural fit for a wide-column or time-series-oriented store, kept apart from the comparatively small, slowly-changing job-definition table for the same reason Chat System separates its message store from user/conversation metadata.

Indexing jobs by next_run_at: the leader's core operation is "find all jobs due now," which is fundamentally a range scan on next_run_at — this index is the single most performance-critical structure in the whole data model, directly enabling N's scale-out approach.

L. End-to-End Flow — One Scheduled Job, Triggered and Executed

M. Deep Dive 1 — Leader Election for the Triggering Role

Requirement this addresses: directly fixes V1's fatal flaw (J) — the single idea that makes the triggering function itself highly available without causing duplicate triggers.

Why only one instance is ever allowed to actively trigger, rather than letting all standby instances also scan-and-trigger "just in case": exactly one active triggering authority is what prevents the duplicate-trigger failure mode named in J — every non-leader instance still runs, watching the lease and ready to take over the instant it expires unrenewed, but deliberately does nothing else while standing by.

N. Deep Dive 2 — Scaling the Trigger Path (The Midnight Spike)

Requirement this addresses: the horizontal-scalability NFR (D) and G's "midnight spike" — hundreds of thousands of jobs sharing a common due time is a fundamentally different load shape than a smooth, evenly-distributed trigger rate.

Why a single leader triggering everything doesn't mean a single leader executing everything: the leader's job is narrowly just to identify due jobs and enqueue their executions (L) — a comparatively cheap operation per job — while the actual execution work (calling each job's target) is handled by an entirely separate, horizontally-scaled worker fleet (R) pulling from a queue. This split is what lets the trigger burst be absorbed: the leader can enqueue hundreds of thousands of executions quickly, and the queue naturally smooths the burst into whatever rate the worker fleet can sustainably process, the same buffering role a message queue plays in Video Streaming's transcoding pipeline.

Sharding the job-scanning work itself, if a single leader's scan becomes the bottleneck: jobs can be partitioned (e.g. by job_id hash range) across multiple concurrently-active leader-per-partition roles, each independently elected (M) and each responsible only for scanning and triggering its own partition — turning one large scan into several smaller, parallel ones without reintroducing any duplicate-trigger risk, since each partition still has exactly one active leader.

O. Deep Dive 3 — Exactly-Once-Ish Execution

Requirement this addresses: the effectively-once NFR (D) — the central technical decision of this entire problem, in the same way overselling-prevention was Ticketmaster's and OT-vs-CRDT was Google Docs's.

Why literal exactly-once is not actually achievable: at some point a worker calls a job's target (an HTTP request, a queue publish) and then must record that it succeeded — if the worker crashes between "the call went through" and "the success was recorded," there is no way to distinguish that from "the call never went through" without asking the target system itself, which most targets can't answer. The honest engineering answer is at-least-once delivery of the trigger, combined with idempotent execution, producing an effectively-once outcome even though the underlying delivery mechanism can occasionally deliver twice.

• Idempotency keys on every execution — each execution carries a stable, unique key (derived from job_id + scheduled_for); a job's target is expected to recognize a repeated key and treat a second delivery as a no-op — the exact same idempotent-retry principle as Chat System's client_msg_id and Ticketmaster's payment-confirmation key, here protecting against duplicate job side effects instead of duplicate messages or charges.
• Leases on claimed executions (H), not permanent locks — a worker that claims an execution holds a short-TTL lease; if the worker crashes mid-execution, the lease simply expires and another worker can claim and retry it, at the cost of a possible duplicate attempt, which idempotency is specifically there to absorb.
• Atomically advancing next_run_at at trigger time, not after execution completes — the leader marks a recurring job's next occurrence immediately upon triggering the current one, so a slow or failed execution never blocks or duplicates the next scheduled trigger; execution success/failure and scheduling the next run are deliberately decoupled.

Why this framing is the strong, senior-level answer rather than a weakness to hide: claiming literal exactly-once execution over a network is either wrong or hiding the same idempotency mechanism under a different name — stating plainly that true exactly-once isn't achievable, and that idempotent effectively-once is the correct and sufficient goal, is a mark of real distributed-systems judgment.

P. Deep Dive 4 — Retries & Failure Handling

Requirement this addresses: the configurable-retry functional requirement (D) — a job execution can fail for reasons ranging from a transient network blip to a permanently broken target, and the two need different handling.

Exponential backoff with a bounded maximum attempt count: a failed execution is retried after a delay that grows with each successive attempt (avoiding a failing target being hammered repeatedly at full speed) up to a configurable attempt limit — standard, well-precedented retry policy, reused conceptually rather than invented fresh.

Dead-lettering after exhausting retries: an execution that fails every allowed attempt moves to a distinct "failed permanently" state, surfaced in execution history (D) for a human to investigate, rather than being retried forever or silently dropped — the same dead-letter-queue pattern common to message-queue-based systems generally.

Why retry policy is per-job configurable, not a single global default: a job that sends a best-effort notification email has very different acceptable-failure tolerance than a job that reconciles financial records — letting each job's owner set its own retry count/backoff respects that difference instead of forcing one policy onto fundamentally different risk profiles.

Q. Deep Dive 5 — Job Dependency Graphs

Requirement this addresses: dependency support (E's clarifying question 2, confirmed in F) — turns a flat set of independently-triggered jobs into a directed-acyclic-graph scheduling problem.

A dependent job's real trigger condition is "upstream succeeded," not just "the clock reached a time."

Why a dependent job is triggered by an upstream completion event, not by its own independent schedule check: a job with a depends_on field isn't evaluated against next_run_at at all during the leader's normal time-based scan (L) — instead, a successful execution completion (O) for its dependency emits an event that makes the dependent job immediately eligible to run, decoupling "is it time" from "is it ready."

Cycle detection at registration time, not at run time: validating the dependency graph is acyclic when a job is created (I) catches a configuration mistake immediately with a clear error, rather than allowing a cycle to silently deadlock a chain of jobs that never actually become eligible to run.

R. Deep Dive 6 — Worker Fleet & Isolation

Requirement this addresses: the actual execution half of the system, decoupled from triggering (N) — a horizontally-scaled fleet of stateless workers pulling executions off the trigger queue.

Why workers are stateless and horizontally scaled independently from the leader/triggering tier: triggering (deciding what's due) and executing (actually calling a job's target) have entirely different scaling shapes — triggering needs exactly one active authority (M) per partition, while execution benefits from as many parallel workers as the queue's backlog demands, with no coordination needed between workers beyond the per-execution lease (O).

Resource isolation between jobs: since F assumes lightweight callback-style jobs rather than arbitrary heavy compute, isolation is comparatively simple (a request timeout per execution, rate limits per job or per target host) — a fundamentally different and harder problem if E's clarifying question 3 had instead confirmed arbitrary long-running compute jobs, which would push this toward a full container-orchestration-style worker design instead.

S. Deep Dive 7 — Missed Runs & Backfill

Requirement this addresses: E's clarifying question 4 — what happens if the whole system (or a given partition's leader lineage) is down when a scheduled time passes.

Why detecting a missed run is just a variant of the normal scan, not a special code path: when a new leader takes over (M) or a recovering system resumes scanning (L), any job whose next_run_at is now in the past is, by definition, both due and late — the same range-scan-on-next_run_at query (K) naturally surfaces it without needing separate missed-run detection logic.

Configurable catch-up policy per job: some jobs should run exactly once to "catch up" (a daily report — running it once late is fine, running it 10 times for 10 missed days is wasteful and wrong), while others genuinely need every missed occurrence backfilled (a per-hour data-aggregation job where each hour's data matters individually) — this is a per-job policy choice (analogous to P's per-job retry policy), not a single global rule.

T. Full Solution at Scale — Final Architecture

Everything above is the composition of M through S — no new component introduced here.

U. Design Evolution

• V1 — single scheduler process, triggers directly (J): a hard single point of failure with no redundancy possible without risking duplicate triggers.
• V2 — leader election among multiple scheduler instances: exactly one active triggering authority at a time, with automatic failover (M).
• V3 — decoupled trigger queue + separate worker fleet: absorbs the midnight-spike burst and lets execution scale independently of triggering (N, R).
• V4 — idempotency keys + leases instead of claimed literal exactly-once: the correctness fix that makes at-least-once delivery safe in practice (O).
• V5 — per-job configurable retry/backoff + dead-lettering: failures are handled as policy, not left to fail silently or retry forever (P).
• V6 — dependency-event-driven triggering for dependent jobs: extends the model beyond pure time-based scheduling (Q).
• V7 — sharded leader-per-partition scanning: scales the trigger-evaluation path itself for very large job counts (N).
• V8 — per-job missed-run/backfill policy: recovers correctly from extended downtime without a separate code path (S).

What stays stable throughout: the register-once, trigger-many-times job contract from I — every later refinement changes how triggering is coordinated, delivered, or recovered, never the basic shape of what a client registers.

V. Consistency Model

The leader-election and job-triggering path (M) requires genuine strong consistency — exactly one instance must be recognized as the active leader at a time, enforced via the same atomic conditional-write primitive used for Ticketmaster's seat holds. Execution delivery itself is deliberately at-least-once, not exactly-once, with idempotency (O) doing the work of making that safe — a close relative of Chat System's "deliver reliably, dedupe on the client" philosophy, here deduping on the job target instead of a chat client. Execution history and job-status visibility (D) can tolerate brief staleness (a status view lagging the true state by a second or two) without any correctness impact, the same "narrow strong-consistency island, eventually-consistent everywhere else" shape used throughout this document.

W. Failure Scenarios

• The active leader crashes: its lease (M) expires unrenewed and a standby instance acquires it within one lease TTL — a brief gap in triggering, bounded and self-healing, never a permanently missed function.
• A worker crashes mid-execution: its lease on that execution (O) expires, and another worker claims and retries it — the idempotency key ensures a possible duplicate delivery doesn't produce a duplicate real-world side effect.
• A job's target is persistently broken: retries exhaust per its configured policy (P) and the execution is dead-lettered for investigation, rather than retried forever or silently dropped.
• The whole system is down across a scheduled time: the next active leader's scan naturally identifies the job as overdue (S) and applies that job's configured catch-up policy.
• A dependency job fails: the dependent job is never triggered (Q) — no wasted work is performed on data that was never successfully produced upstream.

X. Bottlenecks & Scaling Boundary

Y. Design Trade-Offs

Z. Common Bad Designs

• A single always-on scheduler process with no redundancy. A hard single point of failure for the system's entire purpose — the most important mistake to avoid on this problem.
• Running multiple scheduler instances with no coordination between them. "Fixes" the single-point-of-failure problem by directly causing duplicate triggering instead — worse than the problem it was meant to solve.
• Claiming literal exactly-once execution without idempotency. Either quietly relies on the same idempotency mechanism under a different name, or is simply incorrect about what's achievable over a network.
• No retry policy, or unlimited retries with no backoff. Either silently loses failed jobs, or hammers an already-failing target at full speed indefinitely.
• Coupling job triggering and job execution into one tier. Forces the highly-available, low-throughput leader role and the high-throughput worker workload to scale together, when they have fundamentally different scaling needs.

AA. Interviewer Follow-Ups

AB. Interviewer Evaluation Rubric

• Weak candidate: proposes a single always-on scheduler process with no discussion of what happens if it crashes; claims "exactly once" without any mechanism to actually achieve it.
• Mid-level: recognizes the single scheduler is a point of failure and proposes running more than one, but doesn't identify the duplicate-triggering risk that naively creates, or hasn't designed leader election concretely.
• Senior: proactively designs lease-based leader election; correctly reframes "exactly-once" as at-least-once-plus-idempotency unprompted; decouples triggering from execution via a queue and separate worker fleet.
• Staff+: reasons about scaling the trigger-evaluation path itself (sharded leaders) for very large job counts, not just the worker fleet; designs per-job retry and missed-run/backfill policy as configurable rather than one-size-fits-all; raises dependency graphs and clock-skew/jitter considerations unprompted.

AC. Interview Simulation

AD. Online Solution Comparison

AE. Interview Cheat Sheet