Build a high-throughput Task Scheduling Pipeline

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 Submission**: Users can submit tasks via a REST API.
2. **Task Scheduling**: The system schedules tasks based on priority and resource availability.
3. **Task Execution**: Once scheduled, tasks need to be executed in a timely manner, with results returned to the user.
4. **Task Monitoring**: Users can check the status of their tasks (pending, in progress, completed, failed).
5. **Rate Limiting**: Implement rate limiting to prevent abuse and ensure fair resource allocation.

### Non-Functional Requirements:
1. **Throughput**: The system must handle at least 10,000 requests per second (QPS).
2. **Latency**: Task submission should have a latency of less than 100 ms.
3. **Scalability**: The system should scale horizontally to accommodate rising task volumes.
4. **Availability**: Target 99.9% uptime to ensure users can submit tasks anytime.
5. **Consistency**: Eventually consistent task execution is acceptable, but users should receive updates promptly.

### Estimation for Scale:
- **User Base**: Assume 1 million active users.
- **Tasks Per User**: On average, each user submits 10 tasks per day.
- **Total Daily Tasks**: 1,000,000 users * 10 tasks/user = 10,000,000 tasks/day.
- **Peak Load**: Assuming peak usage of 20% of users submitting tasks, we have:
  - 200,000 users submitting tasks = 200,000 tasks at peak.
  - Spread across peak hours (4 hours), that’s 50,000 tasks/hour = ~14 tasks/second.
- **Storage Needs**: Assuming each task takes 1 KB of storage:
  - 10,000,000 tasks * 1 KB = 10 GB of storage per day, requiring scaling for historical data.
- **Message Queue**: If each task generates 1-2 messages (start, finish, status updates), we need to handle up to 20 million messages per day.

### Component Diagram:
1. **API Gateway**: Handles all incoming requests for task submission, status checks, etc.
2. **Load Balancer**: Distributes incoming requests to multiple application servers.
3. **Task Scheduler**: Responsible for prioritizing and scheduling tasks based on resource availability.
4. **Execution Workers**: A pool of worker nodes that execute tasks asynchronously.
5. **Message Queue**: Use Kafka or RabbitMQ for task queuing and processing.
6. **Database**: PostgreSQL for task persistence, with Redis for caching task status and results.
7. **Monitoring Tools**: Prometheus for metrics scraping and Grafana for visualization.

### Technology Choices:
- **API Gateway**: Amazon API Gateway or Kong.
- **Load Balancer**: NGINX or AWS ELB.
- **Message Queue**: Apache Kafka for high throughput.
- **Database**: PostgreSQL for ACID compliance and complex queries.

### Schema Design:
1. **Task Table**:
   - `id` (UUID, Primary Key)
   - `user_id` (UUID, Foreign Key)
   - `status` (ENUM: PENDING, IN_PROGRESS, COMPLETED, FAILED)
   - `priority` (INT)
   - `created_at` (TIMESTAMP)
   - `updated_at` (TIMESTAMP)
   - `result` (TEXT)

2. **User Table**:
   - `id` (UUID, Primary Key)
   - `name` (VARCHAR)
   - `email` (VARCHAR, UNIQUE)

### Access Patterns:
- **Task Submission**: Write to `Task Table`.
- **Task Status Check**: Read from `Task Table` and cache in Redis for quick access.
- **Task Execution**: Workers read from the message queue, update status in the database.

### Architectural Decisions:
1. **Consistency vs. Availability**: Opting for eventual consistency in task execution allows for higher availability and throughput. Users can view task status updates in real-time, while the system processes tasks asynchronously.
2. **Database Choice**: PostgreSQL provides ACID transactions but can become a bottleneck under high write loads. Redis is employed for caching to alleviate read pressure.
3. **Message Queue vs. Direct Processing**: By using a message queue, we decouple task submission from execution, enhancing scalability and resilience to spikes in load.
4. **Monitoring and Alerting**: Implementing Prometheus and Grafana allows for real-time monitoring of system performance. Alerts are set up for task failures and queue length to ensure quick response to issues.
5. **Partitioning Strategy**: Tasks can be sharded by user ID or by priority, allowing parallel processing and reducing contention in the database.

Build a high-throughput Task Scheduling Pipeline

Figma

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

Estimation for Scale:

Submit Your Answer

Figma 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