Design a Distributed Job Scheduling Service

Design a distributed job scheduling system, implemented as a microservice-based architecture running in the cloud, with the following requirements:

Functional Requirements

1. Create Scheduled Jobs A client can create a job via an API, specifying:

   • An optional job identifier (otherwise system-generated).
   • A schedule (e.g., cron-style, specific time, or recurring interval).
   • The task to run (e.g., a script name, container image, or executable description).
   • High-level resource requirements (e.g., CPU/memory tier, machine type).
   • A timeout value.
   • A timeout handler (e.g., kill, mark failed, retry, or other specified action).

2. Run Jobs Reliably at the Designated Time

   • Each job should execute as close as possible to its scheduled time.
   • The system must be distributed, allowing jobs to run across many worker machines or microservices.
   • The system must tolerate machine failures and restarts without losing jobs.

3. Handle Jobs That Don't Finish on Time If a job exceeds its declared timeout, the system must:

   • Detect this condition.
   • Execute the configured timeout behavior (e.g., kill the job, mark as failed, trigger a handler job, or reschedule).

4. Query Past Job Status Provide an API to query:

   • The status of a specific job run (e.g., PENDING, RUNNING, SUCCESS, FAILED, TIMED_OUT).
   • The history of runs for a job (e.g., last N runs, including timestamps and outcomes).

5. Query Job Logs Provide an API to fetch logs for a past job run (e.g., stdout/stderr or structured logs).

6. Distributed Microservice Model The architecture should be microservice-based, horizontally scalable, with components hosted as cloud services (e.g., containers/VMs) capable of independent scaling.

Non-Functional Requirements (Assume Reasonable Scale)

• Support on the order of hundreds of thousands of active scheduled jobs.
• Jobs may be scheduled with minute-level granularity (or better).
• The system must be fault tolerant: if a scheduler instance or worker crashes, jobs should still eventually run.
• Favor reliability over perfect exact timing (e.g., running a job a few seconds late is acceptable, but skipping it completely is not).

Expected Discussion Areas

Describe and justify your design for the following aspects:

1. High-level architecture: Define microservices (e.g., API, metadata, scheduler, worker, log service) and their communication methods (e.g., HTTP/REST, message queues).
2. Data model and storage: How job definitions, schedules, run history, statuses, and logs are stored. Justify database choices (relational vs. NoSQL, object storage).
3. Scheduling logic: How the system determines when to run jobs, implements a distributed and fault-tolerant scheduler (e.g., number of instances, work sharing, leader election, avoiding double-scheduling or missed jobs).
4. Job execution: How jobs are dispatched to workers, how start/end times are tracked, exit codes collected, and timeouts enforced. How logs are communicated back.
5. Reliability and failure handling: What happens if a scheduler or worker crashes mid-job. How to avoid running the same job twice vs. accepting at-least-once execution with idempotent jobs. Recovery mechanisms after restarts.
6. APIs: Example REST endpoints for creating/updating/deleting jobs, fetching configuration, run history, and logs.
7. Scalability considerations: Horizontal scaling strategies for increasing job or worker counts, including sharding or partitioning of data and schedules.

Throughout your explanation, detail your design step-by-step, highlight trade-offs, and explicitly state any assumptions made (e.g., scheduling accuracy, execution semantics, log retention).