Design a Task Scheduling Service

Question

Design a high-throughput task scheduling system that handles millions of requests. Discuss trade-offs in consistency, availability, and performance.

Codemia · Accepted Answer

### Functional Requirements:
1. **Task Creation**: Users can create tasks with metadata such as priority, execution time, and dependencies.
2. **Task Scheduling**: The system should schedule tasks based on priority and resource availability.
3. **Task Execution**: Execute tasks and provide real-time status updates (e.g., running, completed, failed).
4. **Task Retries**: Automatically retry failed tasks based on defined policies.
5. **Task Cancellation**: Users can cancel tasks before execution.

### Non-Functional Requirements:
1. **Scalability**: The system must handle millions of requests per day.
2. **High Availability**: 99.99% uptime with minimal downtime during maintenance.
3. **Latency**: Response time for task scheduling requests should be under 100ms.
4. **Data Consistency**: Eventual consistency in task status updates across distributed systems.
5. **Security**: Implement OAuth 2.0 for user authentication and role-based access control.

Assuming Workday handles 10 million tasks per day:
1. **Requests per Second**: 10,000,000 tasks / 86400 seconds = ~115.74 requests per second.
2. **Peak Load**: Assuming 70% of tasks are scheduled during peak hours (8 hours), the peak would be 7,000,000 tasks / 28800 seconds = ~243.06 requests per second.
3. **Data Storage**: If each task requires 1KB (including metadata), the total storage requirement would be approximately 10 million KB = ~9.54 GB per day, assuming tasks are kept for a month, total = ~286.2 GB.
4. **Concurrency**: Assuming an average of 5 simultaneous tasks, we should design for at least 1,200 concurrent requests.

### Component Diagram:
- **API Gateway**: Handles incoming requests, routes to appropriate services.
- **Task Management Service**: Core service for creating and scheduling tasks. 
- **Execution Engine**: Responsible for executing tasks and managing retries. 
- **Database**: A distributed NoSQL database (e.g., Cassandra) for storing task data and metadata.
- **Cache**: Redis for caching frequently accessed task statuses.
- **Message Queue**: RabbitMQ for task dispatching to the Execution Engine.
- **Monitoring and Logging**: Prometheus for monitoring, ELK stack for logging.

### Technology Choices:
- **API Gateway**: AWS API Gateway
- **Database**: Apache Cassandra for horizontal scalability and availability.
- **Cache**: Redis for fast access to task states.
- **Message Queue**: RabbitMQ for decoupled task execution.

### Schema Design:
1. **Tasks Table**:
   - `task_id` (UUID, Primary Key)
   - `user_id` (UUID, Foreign Key)
   - `priority` (Integer)
   - `status` (String, e.g., Pending, Running, Completed, Failed)
   - `created_at` (Timestamp)
   - `updated_at` (Timestamp)
   - `execution_time` (Timestamp)
   - `retry_count` (Integer)

2. **User Table**:
   - `user_id` (UUID, Primary Key)
   - `name` (String)
   - `email` (String, Unique)
   - `roles` (Array of Strings)

### Access Patterns:
- **Frequent Reads**: Most reads will be for task status, hence caching is crucial.
- **Bulk Writes**: During batch task creation, optimize for bulk inserts.

### Architectural Decisions:
1. **Consistency vs. Availability**: Leveraging Cassandra allows for high availability but introduces eventual consistency, which is acceptable given users can tolerate slight delays in task status updates.
2. **Caching Strategy**: Using Redis for caching task states reduces read latency but introduces complexity in cache invalidation. Cache will be updated on task state change events.
3. **Message Queue vs. Direct Execution**: Using RabbitMQ to decouple task scheduling from execution allows for better scalability but adds potential latency. Tasks will be queued for execution to handle spikes in load.
4. **Multi-Region Deployment**: To ensure global availability, we will deploy in AWS regions across North America and Europe, but this requires careful management of data replication and consistency.

Design a Task Scheduling Service

Workday

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Practice a Similar Problem on Codemia

Sample Answer

Requirements

Functional Requirements:

Capacity Estimation

Submit Your Answer

Workday 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