Design a Durable Delayed Task Scheduler

Scenario

Many modern platforms require delayed or deferred execution of actions—such as sending follow-up emails after 24 hours, expiring shopping cart reservations after 15 minutes, or triggering customer support check-ins after a resolved ticket. You are asked to design a centralized, durable Delayed Task Scheduler service.

Clients should be able to submit tasks with an arbitrary payload and a scheduled execution timestamp (due_time). The scheduler must guarantee that tasks are not executed prematurely and are dispatched as close to due_time as possible (ideally within 1–2 seconds), even in the face of machine crashes, network partitions, and restarts.

Requirements

Functional Requirements

• Schedule Task: Submit a task with a payload, metadata, and an execution timestamp (due_time), returning a unique task_id.
• Cancel Task: Cancel a pending task prior to its dispatch.
• Task Execution: Dispatch due tasks to downstream worker endpoints or execution queues (e.g., Kafka, SQS, or webhook targets).
• Retry & Backoff: Automatically retry failed executions using exponential backoff with jitter up to a configurable maximum attempt count.

Non-Functional Requirements

• Durability: Zero task loss once an acknowledgment is returned to the client.
• Precision & Timeliness: At least 99% of tasks should be triggered within 2 seconds of their scheduled due_time.
• Delivery Guarantee: At-least-once execution. Downstream consumers are expected to be idempotent, but duplicate dispatches should be minimized.
• Fault Tolerance: If any scheduler or poller instance crashes, other nodes must pick up pending tasks without violating ordering or duplicating executions excessively.

Scale & Numbers

• 50 million total active pending tasks at any time.
• Ingestion rate: 5,000 tasks scheduled per second peak.
• Execution rate: 5,000 tasks due per second peak.
• Delay ranges: From 5 seconds up to 90 days in the future.

What to Cover

1. API & Data Model: Define the external API and the schema used for task storage, indexing by due time, and tracking execution states.
2. Time-Wheel vs. Polling vs. Sorted Index: Discuss trade-offs for scanning and discovering due tasks (e.g., Redis sorted sets, partitioned database indexes, hierarchical timing wheels).
3. Reliable Dispatching: How to claim tasks atomically to prevent multiple schedulers from executing the same task concurrently.
4. Failure Recovery & Edge Cases: Handling scheduler crashes mid-dispatch, clock drift across distributed nodes, and hot-shard mitigation when millions of tasks are scheduled for the exact same second.