20: Distributed Job Scheduler | Systems Design Interview Questions With Ex-Google SWE

Main Ideas

A distributed job scheduler accepts executable binaries, stores them in object storage such as S3, and runs them on available worker machines. It supports both recurring jobs with Cron-style schedules and workflows in which tasks depend on other tasks (DAGs). Because the service may handle millions of jobs a day, it needs to be highly available, quick to poll, and resilient to failures.

Requirements and High-Level Design

• Users can upload binaries and request that they run on a schedule.
• Users can check whether a job is pending, running, successful, or failed, and inspect error information.
• A workflow can express dependencies between jobs. A task becomes eligible only when its prerequisites have completed.
• Jobs should ideally run once. In practice, retries and failures make strict exactly-once execution difficult, so the design aims to reduce duplicate effects and handle duplicates safely.
• A scheduler periodically polls a scheduling table, sends eligible tasks to a queue, and workers retrieve and execute them. Workers fetch the binary from S3 and update the job status afterward.

Scheduling Cron Jobs

The proposed design uses two kinds of records:

• Cron metadata: Stores the recurring schedule and related information, such as the job or parent workflow ID.
• Scheduled tasks: Stores the next concrete run to be executed.

When a Cron job is created, its metadata and first upcoming run are recorded. When a worker completes an iteration, the system schedules the next one. This keeps only the next run in the scheduling table rather than pre-populating every future occurrence.

The final architecture can use change data capture (CDC) to move scheduling changes into the scheduler’s data flow, avoiding a two-phase commit for that process.

Scheduling DAG Workflows

A DAG records jobs and their dependencies. For example, two root tasks can run at their scheduled times, and a downstream task becomes eligible after both have completed.

The proposed process is:

1. Store each workflow’s jobs, schedules, child relationships, and dependency progress in a DAG-specific table.
2. When the workflow is first uploaded, identify and schedule its root tasks. A topological sort may be needed to determine which tasks have no prerequisites.
3. Track progress by epoch: when a prerequisite completes for a given run, update the corresponding dependency’s epoch in its child task.
4. Schedule a task once all its dependencies have reached the same epoch.
5. After the leaf tasks complete, allow the next recurring workflow run to begin. The design models the recurring roots as dependent on the leaves, preventing a new iteration from overlapping with the previous one.
6. If a task fails, propagate the failure to downstream tasks that cannot run, so the workflow can still be marked as completed—with errors—and its recurring roots can be scheduled again.

Because completing a task can update multiple dependency records, these updates need to be atomic. The presenter discusses MySQL, then favors a document database such as MongoDB for the flexibility of representing DAG structures. Data should be sharded by DAG ID so that one workflow’s related records are colocated and can be updated together without distributed transactions.

Scheduling-Table Performance

The scheduling table holds the next run time, job ID, binary location, and status. The scheduler queries for tasks whose run time has arrived and whose status is not completed or failed.

• Each time a job advances through the process, its run timestamp is moved forward. That timestamp also serves as a timeout: if the job does not progress before the timeout, it can be retried.
• Indexing by both status and run timestamp helps find runnable work without repeatedly scanning completed or failed jobs.
• Frequent timestamp updates can make indexes expensive to maintain, and concurrent reads and writes can cause lock contention.
• Possible scaling approaches include partitioning the scheduling table across multiple databases and reading from read-only replicas. Replica reads may be stale, potentially causing extra retries, but the presenter considers that an acceptable trade-off for user-facing status queries.
• The presenter also suggests distributing data using time ranges and a hash or other partition key derived from the job ID.

Distributing Work Across Workers

A conventional load balancer is not ideal for assigning jobs: consistent hashing can leave a worker stuck with a long-running job, while having every worker report its status to one load-balancer node can create a bottleneck and a single point of failure.

Instead, the design uses a message broker so idle workers can take work when available:

• A log-based broker such as Kafka, with one consumer per partition, can cause head-of-line blocking: a long-running task may prevent other tasks in that partition from being processed.
• An in-memory queue broker, such as ActiveMQ or RabbitMQ, is presented as a better fit. Multiple workers can take tasks as they become idle, with relatively low latency.
• For jobs that need different levels of computing power, the system can use multiple priority queues. A task that cannot finish within a lower-tier timeout can be retried on a higher-priority queue serviced by more powerful workers. Higher-tier workers can also take lower-tier work when their preferred queues are empty.

Retries, Status, and Duplicate Execution

Retries improve reliability but mean a job may run more than once. Duplicates can arise if, for example:

• A worker completes or claims a task, but its acknowledgement does not reach the queue.
• The scheduler’s timeout expires while a job is still running.
• A broker or worker fails and the job is reissued.

A distributed lock, for example through ZooKeeper, can reduce the risk of the same job running concurrently on multiple workers. However, locks need a time-to-live (TTL): without one, a crashed worker could leave a job locked indefinitely. With one, a slow but still-active worker may lose its lock and overlap with a replacement worker. The presenter emphasizes that this cannot eliminate every failure case.

The practical recommendation is to make jobs idempotent or deterministic where possible, especially when they write important state. Some duplicate effects may be tolerable—for example, sending an extra email—but important database updates should be designed to handle retries safely. The presenter notes that checking the scheduling table alone cannot reliably guarantee exactly-once execution because concurrent workers can race.

Overall Architecture

The final design connects these components:

• Cron and DAG metadata tables store recurring schedules and workflow dependencies.
• CDC and Kafka carry metadata changes to the appropriate scheduling logic.
• A scheduler polls the scheduled-tasks table and places runnable work into priority queues.
• Workers fetch binaries from S3, execute them, and update job status.
• Read replicas serve user status queries so they do not slow the scheduler’s main table.
• DAG completion updates dependency epochs and can trigger downstream tasks through the DAG scheduling flow.

Speakers and Sources Featured

• Speaker: Jordan, the video’s narrator. No guest speakers are featured.
• Technical systems and technologies mentioned: S3, MySQL, MongoDB, Kafka, ActiveMQ, RabbitMQ, ZooKeeper, CDC, and Cron scheduling. These are discussed as examples or design components, not as additional speakers.