Katkat
Back

Design an At-Most-Once Job Scheduler

RobinhoodSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This question tests the ability to design a distributed, fault-tolerant job scheduler that guarantees tasks are executed no more than once, focusing on state management and concurrency control.

Design an At-Most-Once Job Scheduler

Design a distributed job scheduling system that allows users to submit jobs to be executed at a specific future time. The system must adhere to 'at-most-once' semantics: each job should be attempted no more than one time, even in the presence of system failures or node crashes.

Functional Requirements

  • submit(job_id, payload, execute_at): Schedules a job to run at a specific timestamp.
  • cancel(job_id): Removes a pending job from the schedule.
  • Execution Engine: The system must trigger the execution of the job at the requested time.

Non-Functional Requirements

  • Fault Tolerance: The system should not lose scheduled jobs if a node fails.
  • Scalability: The system should handle 10,000 requests per second and maintain a state of up to 100 million pending jobs.
  • At-Most-Once: Ensure no job is executed more than once.

Requirements for your Design

  1. Propose a high-level architecture including the API, storage layer, and worker selection mechanism.
  2. Explain the mechanism to ensure the 'at-most-once' guarantee during distributed execution.
  3. Discuss how you would handle clock skew across different nodes.
  4. Define the storage schema and how you would efficiently query for jobs due to be run.

Hints

Hint 1

Consider using a distributed database that supports atomic operations or conditional updates to manage job state transitions.

Hint 2

Think about how a 'claimed' state (e.g., PENDING -> CLAIMED -> COMPLETED) prevents multiple workers from picking up the same job.

Hint 3

A time-indexed data structure or partitioned database table can help workers efficiently find jobs due for execution without scanning the entire dataset.

Follow-up questions

  • How would your design change if the requirements shifted to 'at-least-once' execution?
  • What strategies would you implement to prevent 'hot spots' if a large number of jobs are scheduled for the exact same millisecond?
  • How would you implement monitoring and observability to detect if a significant number of jobs are failing to trigger?