Bird
Raised Fist0

Design a Task Scheduler - Priority Queue, Cron, Distributed Execution

HLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design a Task Scheduler - Priority Queue, Cron, Distributed Execution
Design a scalable distributed task scheduler supporting priority queues and cron jobs with fault-tolerant execution
hardInfrastructure and Platform SystemsFreq: medium
Prerequisites:System Design FundamentalsCAP TheoremDistributed SystemsMessage QueuesCron Scheduling
⚙️
Functional Requirements
  • Support scheduling of one-time tasks with priority levels (high, medium, low).
  • Support cron-style recurring tasks with flexible schedules (e.g., every hour, daily at 2am).
  • Guarantee at-least-once execution semantics for all scheduled tasks.
  • Provide APIs to create, update, cancel, and query scheduled tasks.
  • Distribute task execution across multiple worker nodes for scalability.
  • Support task retries with exponential backoff on failure.
📊
Non-Functional Requirements
  • Handle up to 2 billion daily scheduled tasks (approx. 23K tasks/sec average).
  • Ensure 99.99% availability for scheduling and execution APIs.
  • Task execution latency P99 under 100ms from scheduled time.
  • System must scale horizontally to handle 10x peak load without downtime.
  • Data durability with replication factor of 3 and recovery within 5 minutes.
❓
Clarifying Questions to Ask
  • What is the maximum allowed delay between scheduled time and actual execution?
  • Are tasks idempotent or do we need deduplication to avoid multiple executions?
  • What is the expected size and complexity of task payloads?
  • Is strict ordering required for tasks with the same priority?
  • How should the system handle clock skew across distributed nodes?
  • What are the retry policies and maximum retry attempts for failed tasks?
Out of Scope
✗ Task payload execution logic (e.g., business logic inside tasks).
✗ User authentication and authorization mechanisms.
✗ UI or frontend for task management.
✗ Complex workflow orchestration beyond simple cron and priority queues.
📌
Assumptions
  • 2 billion tasks scheduled per day globally.
  • Average task payload size: 100 bytes metadata + 1 KB user payload.
  • Tasks per user per day: 40 (average).
  • Replication factor for storage: 3.
⚡
QPS Calculation
write qps2B tasks/day × 1 write per task / 86400 sec ≈ 23,148 writes/sec
peak write qpsAssuming 5x peak factor → 23,148 × 5 = 115,740 writes/sec
read qpsReads for task status queries and scheduling: estimated 2× write QPS = 46,296 reads/sec
💾
Storage Estimate
daily storage(2B tasks × 1.1 KB) ≈ 2.2 PB/day uncompressed
retention days7
total storage2.2 PB/day × 7 days = 15.4 PB
with replication15.4 PB × 3 replicas = 46.2 PB total storage
🖥️
Server Estimate
storage nodesAssuming 1 TB usable per node → 46,200 nodes for storage cluster
worker nodesTo handle 115K peak writes and 100ms P99 latency, estimate 5000 worker nodes with autoscaling
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          |  Client/API    |
          +-------+--------+
                  | REST/gRPC
          +-------v--------+
          |  Scheduler Svc |
          +-------+--------+
                  | Kafka Topics (Task Events)
          +-------v--------+
          |  Kafka Cluster |
          +-------+--------+
                  | Consumer Groups
          +-------v--------+
          |  Execution     |
          |  Workers       |
          +-------+--------+
                  | Task Status Updates
          +-------v--------+
          |  Metadata DB   |
          | (Cassandra)    |
          +----------------+
                  | Cron Trigger Polling
          +-------v--------+
          |  Cron Service  |
          +----------------+
🧩
Components
Scheduler Service
Receives task scheduling requests, validates, and publishes task events to Kafka.
Why thisStateless microservice enabling horizontal scaling and decoupling task ingestion from execution using Kafka.
Why notAvoided monolithic DB writes directly to prevent write bottlenecks and complex sharding.
Kafka Cluster
Durable distributed log for task events enabling asynchronous decoupling and replayability.
Why thisKafka supports high throughput (millions msgs/sec), partitioning, and consumer groups for parallelism.
Why notRabbitMQ lacks Kafka's horizontal scalability and retention guarantees at this scale.
Execution Workers
Consume task events from Kafka, execute tasks, and update task status in metadata DB.
Why thisStateless workers allow elastic scaling and fault isolation; Kafka consumer groups ensure load balancing.
Why notAvoided serverless due to cold start latency and limited control over retries.
Metadata DB (Apache Cassandra)
Stores task metadata, status, schedules, and execution history with high write throughput.
Why thisCassandra offers linear write scalability, tunable consistency, and multi-datacenter replication.
Why notPostgreSQL rejected due to complex manual sharding and write amplification at 100K+ writes/sec.
Cron Service
Polls metadata DB for cron schedules, generates task events, and publishes to Kafka.
Why thisDedicated service isolates cron logic and allows flexible schedule parsing and task generation.
Why notAvoided embedding cron logic in workers to prevent duplicated executions and complex coordination.
🔄
Data Flow
1
Client/API → Scheduler Service
Submit task scheduling request (one-time or cron).
Scheduler validates and enriches request metadata.
2
Scheduler Service → Kafka Cluster
Publish task event to appropriate Kafka topic partition.
Event includes priority, schedule, and payload metadata.
3
Cron Service → Metadata DB
Poll for due cron schedules and generate task events.
Cron service runs periodic scans to trigger recurring tasks.
4
Kafka Cluster → Execution Workers
Workers consume task events based on partition assignment.
Workers prioritize tasks by priority queue ordering.
5
Execution Workers → Metadata DB
Update task execution status and retry info.
Status updates enable client queries and retries.
6
Client/API → Metadata DB
Query task status and history.
Clients poll or subscribe for task completion info.
🗄️
tasks
PK: task_id
task_id UUIDpriority intscheduled_time timestampstatus textpayload blobretry_count intlast_updated timestamp
Stores all scheduled tasks with priority and execution metadata.
🗄️
cron_schedules
PK: cron_id
cron_id UUIDcron_expression textnext_run_time timestampenabled booleanlast_run_time timestamp
Stores cron job definitions and next scheduled run times.
🔌
CreateTask
Request
{
  "task_id": "UUID",
  "priority": "int",
  "schedule_time": "timestamp",
  "payload": "blob",
  "is_cron": "boolean",
  "cron_expression": "string (optional)"
}
Response
{
  "success": "boolean",
  "error_message": "string (optional)"
}
Creates a one-time or cron scheduled task.
🔌
UpdateTask
Request
{
  "task_id": "UUID",
  "priority": "int (optional)",
  "schedule_time": "timestamp (optional)",
  "payload": "blob (optional)",
  "enabled": "boolean (optional)"
}
Response
{
  "success": "boolean",
  "error_message": "string (optional)"
}
Updates task metadata or enables/disables cron tasks.
🔌
QueryTaskStatus
Request
{
  "task_id": "UUID"
}
Response
{
  "status": "string",
  "last_execution_time": "timestamp",
  "retry_count": "int"
}
Fetches current status and execution history of a task.

Practice

(1/5)
1. In the News Feed system, at step 4 the Delivery Worker reads from the fan-out queue to push updates to followers. What happens if the follower's cache entry for the feed is expired at this step?
easy
A. The Delivery Worker fetches the latest feed snapshot from the database before pushing
B. The Delivery Worker sends a stale cached feed to the follower
C. The Delivery Worker retries the message later without updating the cache
D. The Delivery Worker skips sending the update and marks it as delivered

Solution

  1. Step 1: Trace Delivery Worker decision at Step 4 -- follower cache TTL expired

    If the cache is expired, the Delivery Worker must fetch fresh data to ensure the follower receives the latest feed snapshot.

  2. Step 2: Evaluate other options

    Skipping (A) causes missed updates; retrying without cache update (C) delays delivery; sending stale data (D) violates freshness guarantees.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Expired cache triggers DB fetch for fresh feed [check]
Hint: Expired cache triggers DB fetch before delivery [check]
Common Mistakes:
2. In a request flow where a client sends a request through a forward proxy to an external server, at step 3 the forward proxy modifies the request headers. What exactly happens at this step?
easy
A. The forward proxy removes client-identifying headers and adds its own IP as the source
B. The forward proxy caches the response before forwarding the request
C. The forward proxy encrypts the entire request payload before forwarding
D. The forward proxy replaces the destination IP with its own IP before forwarding

Solution

  1. Step 1: Understand forward proxy header modification

    At step 3, the forward proxy removes headers that reveal client identity and inserts its own IP as the source to hide the client.

  2. Step 2: Eliminate other options

    It does not replace destination IP (that would break routing), nor encrypt payload (that's TLS), nor cache response before request forwarding.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Forward proxy masks client IP by header modification [check]
Hint: Forward proxy swaps client IP with its own in headers [check]
Common Mistakes:
3. In a Cassandra-based messaging system, at step 4 the coordinator node receives a write request for a message with partition key user123. What happens if the coordinator node's local replica is down?
easy
A. The coordinator immediately fails the write request with an error
B. The coordinator writes to a backup relational database instead
C. The coordinator routes the write to other replicas responsible for user123's partition
D. The coordinator retries the write on the same node until it recovers

Solution

  1. Step 1: Understand coordinator role in Cassandra write path

    The coordinator routes writes to all replicas responsible for the partition key; if one replica is down, it routes to the others.

  2. Step 2: Evaluate failure handling

    Writes are not failed immediately if a replica is down; coordinator does not retry indefinitely on the same node; no fallback to relational DB.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Coordinator routes writes to available replicas -> ensures write availability [check]
Hint: Coordinator routes writes to live replicas, not fail immediately [check]
Common Mistakes:
4. If the prefix hash map component fails and becomes unavailable, what is the immediate impact on the autocomplete system's behavior?
medium
A. The system returns no results for prefix queries until the prefix hash map recovers
B. The Trie component automatically handles prefix queries without any degradation in performance
C. Autocomplete queries fall back to Elasticsearch but with increased latency and less precise prefix matching
D. User input is cached locally on the client until the prefix hash map is restored

Solution

  1. Step 1: Understand component roles

    The prefix hash map is an optimization for O(1) prefix lookups, but the Trie is the primary data structure for prefix matching.

  2. Step 2: Trace failure impact

    If the prefix hash map fails, the system falls back to the Trie for prefix queries, which still works but may have slightly higher latency.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Trie fallback ensures prefix queries continue despite prefix hash map failure [check]
Hint: Trie fallback keeps prefix search alive if prefix hash fails [check]
Common Mistakes:
5. At 10x scale, which component in the real-time ML inference system is most likely to fail first and why?
hard
A. Model storage backend, due to increased read latency from large model files
B. Load balancer, since it cannot efficiently distribute traffic to a rapidly scaling number of servers
C. Kafka event stream, as partition count limits throughput and causes lag under heavy update load
D. Prediction API servers, because CPU-intensive model inference cannot be parallelized easily

Solution

  1. Step 1: Analyze scaling bottlenecks

    Model storage (A) scales with caching; Kafka (C) can be scaled by adding partitions; load balancers (D) scale horizontally.

  2. Step 2: Identify CPU bottleneck in inference

    Prediction API servers (B) perform CPU/GPU-bound inference; scaling is limited by hardware and model complexity, causing first failure under 10x load.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Inference servers hit CPU/GPU limits before storage or Kafka scale [check]
Hint: Inference servers hit CPU/GPU bottleneck before other components [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard