Design a Task Scheduler

Question

Design a distributed job scheduling system. Cover job prioritization, cron-like recurring tasks, failure handling and retries, resource allocation, and ensuring exactly-once execution semantics.

Codemia · Accepted Answer

- **Functional Requirements**:
  - Job submission: Users should be able to submit jobs with parameters such as priority, schedule (cron-like), and resource requirements.
  - Job prioritization: The system should allow for jobs to be prioritized based on user-defined criteria.
  - Recurring tasks: Support for cron-like scheduling to execute jobs at defined intervals.
  - Failure handling: Implement retry mechanisms for jobs that fail during execution.
  - Exactly-once execution: Ensure that each job runs only once, even in the case of failures.

- **Non-Functional Requirements**:
  - Scalability: The system should handle thousands of jobs daily, scaling horizontally to accommodate increased load.
  - Availability: Aim for 99.99% uptime to ensure that job scheduling is reliable.
  - Latency: The time from job submission to execution should be minimized, ideally under 1 second for high-priority jobs.

Assuming Google has a user base that submits a large number of jobs:
- **Daily Job Estimates**: 
  - If we estimate 10 million jobs submitted per day, that’s approximately 115 jobs per second.
- **Job Specifications**:
  - If each job requires an average of 100MB of memory and runs for about 10 seconds, we will need enough resources to handle concurrent executions.
- **Resource Allocation**:
  - Assuming a job runs on average for 10 seconds, we can handle about 6 jobs per core at a time. To process 115 jobs/sec, we’d need approximately 20 cores active continuously.
- **Storage Needs**:
  - If each job's metadata and logs consume about 1KB, storing logs for a week would require about 1.2TB of storage (10 million jobs * 7 days * 1KB).

The architecture consists of several key components:
- **Job API Layer**: A RESTful API built with **gRPC** for high-performance job submission and management.
- **Job Scheduler**: A distributed scheduler using **Apache Kafka** for message queuing and **Zookeeper** for coordination, ensuring high availability and fault tolerance.
- **Worker Nodes**: Stateless worker nodes running on **Kubernetes** to ensure scalability and manage job execution. Each worker can dynamically pull jobs from the scheduler.
- **Persistent Storage**: **Google Cloud Spanner** for storing job metadata, scheduling information, and logs, ensuring strong consistency and scalability.
- **Monitoring & Alerting**: Use **Prometheus** for metrics collection and **Grafana** for visualization, alongside alerting through **PagerDuty**.

The schema design focuses on efficient access patterns for job management:
- **Jobs Table**:
  - `job_id (UUID) PRIMARY KEY`
  - `user_id (UUID) NOT NULL`
  - `status (ENUM('pending', 'running', 'completed', 'failed'))`
  - `priority (INT) NOT NULL`
  - `schedule (STRING)`
  - `resource_requirements (JSON)`
  - `created_at (TIMESTAMP)`
  - `updated_at (TIMESTAMP)`

- **Job Logs Table**:
  - `log_id (UUID) PRIMARY KEY`
  - `job_id (UUID) REFERENCES Jobs(job_id)`
  - `message (TEXT)`
  - `timestamp (TIMESTAMP)`

This structure allows for efficient querying based on job status, user, and scheduling, enhancing retrieval speed for job management.

- **Consistency vs. Availability**: Choosing Google Cloud Spanner provides strong consistency but may introduce latency during peak loads. We have to ensure that the job submission can handle spikes without degrading performance.
- **Complexity of Exactly-Once Semantics**: Implementing exactly-once execution can add complexity, requiring careful design of the job handling mechanism to avoid duplicate processing, especially in failure scenarios.
- **Resource Allocation**: Static resource allocation might lead to under-utilization during low loads, while dynamic allocation can lead to challenges in job prioritization and scheduling efficiency. We need a balance between responsiveness and resource management.

Design a Task Scheduler

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Requirements

Capacity Estimation

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search