Chapter 60: Design Distributed Task Scheduler

1. Requirements

Functional Requirements

Requirement	Description	Examples
One-Time Tasks	Schedule task to execute once at specific time	Send notification at 3 PM, process batch at midnight
Recurring Tasks	Execute tasks on cron schedule	Daily reports, hourly cleanup, weekly backups
Priority Support	High-priority tasks execute before low-priority	Critical alerts > routine maintenance
Task Cancellation	Cancel scheduled or running tasks	User cancels scheduled job
Task Status Query	Check task execution status and history	Pending, running, completed, failed

Non-Functional Requirements

Requirement	Target	Rationale
Throughput	100M tasks/day (1,150 tasks/sec)	Support enterprise-scale workloads
Latency	Execute within 1 second of scheduled time	Near real-time execution for time-sensitive tasks
Reliability	At-least-once execution guarantee	No tasks lost due to failures
Availability	99.9% uptime	Critical infrastructure component
Durability	Tasks persisted to disk	Survive crashes and restarts
Scalability	Horizontal scaling for workers and schedulers	Handle load spikes and growth

Interview Tip: Clarify execution semantics early. At-least-once is standard (duplicates tolerated), exactly-once is complex and expensive. Most systems accept at-least-once with idempotent task handlers.

2. High-Level Design

Component Responsibilities

Component	Responsibility	Technology Options
API Gateway	Task submission, cancellation, status queries	REST API, gRPC, GraphQL
Task Store	Persist tasks, scheduling metadata, execution history	PostgreSQL, MongoDB, DynamoDB
Scheduler Service	Poll due tasks, enqueue to ready queue	Custom service with leader election (Zookeeper, etcd)
Ready Queue	Hold tasks ready for immediate execution	Redis (ZSET), Kafka, RabbitMQ, SQS
Worker Pool	Execute tasks, retry on failure, update status	Kubernetes pods, EC2 instances, Lambda
Dead Letter Queue	Store permanently failed tasks for investigation	SQS DLQ, Kafka topic, database table

Interview Tip: Separate scheduling (time-based logic) from execution (worker logic). Scheduler is stateless and can be replicated with leader election. Workers are horizontally scalable.

3. Task Model

Task Schema

Field	Type	Description	Example
task_id	UUID	Unique task identifier	a1b2c3d4-e5f6-7890-abcd-ef1234567890
task_type	String	Task handler type	send_email, process_batch, cleanup_logs
payload	JSON	Task execution parameters	{"user_id": 123, "email": "user@example.com"}
schedule_type	Enum	one_time, recurring	one_time
scheduled_at	Timestamp	When to execute (one-time)	2026-05-12T15:00:00Z
cron_expression	String	Cron schedule (recurring)	0 9 * * MON-FRI (9 AM weekdays)
priority	Integer	0 (highest) to 10 (lowest)	3
timeout	Integer	Max execution time (seconds)	300
max_retries	Integer	Retry attempts before DLQ	3
retry_backoff	String	exponential, linear, fixed	exponential
status	Enum	pending, running, completed, failed, cancelled	pending
attempt_count	Integer	Current retry attempt	0
last_error	Text	Error message from last failure	Connection timeout to database
created_at	Timestamp	Task creation time	2026-05-12T14:00:00Z
started_at	Timestamp	Execution start time	2026-05-12T15:00:01Z
completed_at	Timestamp	Execution completion time	2026-05-12T15:02:34Z
worker_id	String	Worker executing the task	worker-pod-7a3c
lease_expires_at	Timestamp	Worker lease expiration (for recovery)	2026-05-12T15:05:00Z

Indexes for Performance

Index	Columns	Purpose
idx_scheduled_tasks	(status, scheduled_at, priority)	Scheduler polling for due tasks by priority
idx_task_type	(task_type, status)	Query tasks by type and status
idx_lease_expiration	(lease_expires_at, status)	Find expired leases for recovery
idx_created_at	(created_at)	Historical queries and cleanup

4. Scheduling Approaches

Approach 1: Polling Database

Aspect	Details
Mechanism	Scheduler polls database every N seconds for tasks where scheduled_at <= NOW()
Query	`SELECT * FROM tasks WHERE status='pending' AND scheduled_at <= NOW() ORDER BY priority, scheduled_at LIMIT 1000`
Pros	Simple, durable (DB-backed), no additional infrastructure
Cons	Database load scales with task count, polling delay (1-5 sec granularity), inefficient for millions of tasks
Use Case	Low-scale systems (<10K tasks/day), non-latency-sensitive workloads

Approach 2: Delay Queue (Redis ZSET)

Aspect	Details
Mechanism	Store tasks in Redis sorted set (ZSET) with scheduled_at as score. Poll with ZRANGEBYSCORE.
Commands	`ZADD delay_queue {timestamp} {task_id}` `ZRANGEBYSCORE delay_queue 0 {now} LIMIT 0 1000`
Pros	Fast (in-memory), efficient polling, sub-second latency, handles millions of tasks
Cons	Redis durability trade-off (AOF/RDB), memory constraints for large task counts
Use Case	Medium-scale systems (1M-100M tasks/day), low-latency requirements

Approach 3: Time-Wheel (Kafka-Based)

Aspect	Details
Mechanism	Partition time into buckets (e.g., 1-minute slots). Store tasks in Kafka topic partitioned by time bucket.
Example	Task scheduled for 15:37:00 goes to bucket 937 (minutes since epoch % total buckets)
Pros	Extremely high throughput, distributed, durable (Kafka replication), O(1) scheduling
Cons	Complex implementation, time-wheel granularity trade-off, rebalancing on partition changes
Use Case	Large-scale systems (100M+ tasks/day), high-throughput batch processing

Comparison Matrix

Criteria	Polling DB	Redis Delay Queue	Kafka Time-Wheel
Throughput	Low (1K tasks/sec)	Medium (10K tasks/sec)	High (100K+ tasks/sec)
Latency	1-5 seconds	<1 second	<1 second
Complexity	Low	Medium	High
Durability	High (DB WAL)	Medium (Redis AOF)	High (Kafka replication)
Scalability	Vertical (DB)	Horizontal (Redis Cluster)	Horizontal (Kafka partitions)
Operational Overhead	Low	Medium	High

Interview Tip: For 100M tasks/day requirement, recommend Redis delay queue as sweet spot (proven, fast, moderate complexity). Mention Kafka time-wheel as future optimization if scaling beyond 1B tasks/day.

5. Cron Scheduling

Cron Expression Format

Field	Values	Special Characters	Example
Minute	0-59	* , - /	*/15 (every 15 min)
Hour	0-23	* , - /	9-17 (9 AM to 5 PM)
Day of Month	1-31	* , - / L W	L (last day of month)
Month	1-12 or JAN-DEC	* , - /	JAN,APR,JUL,OCT (quarterly)
Day of Week	0-6 or SUN-SAT	* , - / L #	MON-FRI (weekdays)

Cron Expression Examples

Expression	Description	Use Case
0 0 * * *	Daily at midnight	Daily reports, log rotation
0 9 * * MON-FRI	9 AM on weekdays	Business day notifications
/5 * * *	Every 5 minutes	Health checks, monitoring
0 0 1 * *	First day of month at midnight	Monthly billing, reports
0 0 * * 0	Sundays at midnight	Weekly backups
0 2 * * SUN	Sundays at 2 AM	Maintenance windows

Cron Task Lifecycle

Step	Action	Details
1. Registration	Store cron task	Persist cron_expression, task_type, payload. Store next_run_at timestamp.
2. Calculation	Compute next run time	Parse cron expression. Calculate next occurrence from current time. Account for timezone.
3. Scheduling	Create one-time task instance	Generate task with scheduled_at = next_run_at. Link to parent cron task.
4. Execution	Worker executes task	Standard task execution flow.
5. Regeneration	Schedule next occurrence	After completion, calculate next_run_at. Create new task instance. Repeat cycle.

Timezone Handling

Challenge	Solution
DST Transitions	Use timezone-aware libraries (pytz, ZonedDateTime). Recalculate next_run in target timezone.
Cross-Timezone Users	Store user's timezone with cron task. Convert to UTC for scheduling. Display in user's local time.
Missing Hours (DST forward)	If scheduled time doesn't exist (2 AM on spring forward), skip to next occurrence or execute immediately after transition.
Duplicate Hours (DST backward)	Execute only once using UTC timestamps to avoid double execution.

Interview Tip: Cron parsing is complex. Mention using battle-tested libraries (croniter, quartz) rather than implementing from scratch. Discuss edge cases: DST, leap years, invalid dates (Feb 30).

6. Task Assignment

Pull-Based Model (Recommended)

Aspect	Details
Mechanism	Workers poll ready queue and pull tasks when idle
Implementation	Worker: `task = queue.pop(timeout=10); execute(task); ack(task)`
Load Balancing	Natural load balancing (fast workers get more tasks)
Failure Handling	Worker crash: lease timeout returns task to queue
Pros	Simple, self-balancing, no central coordinator, worker auto-scaling friendly
Cons	Potential thundering herd on empty queue, need lease mechanism

Push-Based Model

Aspect	Details
Mechanism	Central scheduler assigns tasks to workers via RPC/gRPC
Implementation	Scheduler: `worker = select_least_loaded(); worker.execute(task)`
Load Balancing	Scheduler tracks worker load, uses round-robin or least-connections
Failure Handling	Scheduler detects worker failure via heartbeat, reassigns tasks
Pros	Fine-grained control, optimal placement (e.g., affinity-based routing)
Cons	Scheduler is bottleneck, complex state management, harder to scale

Scheduler High Availability

Component	Strategy	Implementation
Leader Election	Single active scheduler, hot standbys	Zookeeper, etcd, Redis SETNX with TTL
Heartbeat	Leader sends heartbeat every 5 sec	Update TTL in coordination service
Failover	Standby detects leader failure (no heartbeat for 15 sec), becomes new leader	Acquire lock in coordination service
Split-Brain Prevention	Use fencing tokens (monotonic counter)	Queue rejects writes from old leader with lower token

Leader Election Example (etcd)

// Scheduler startup
leader_key = "/schedulers/leader"
session = etcd.create_session(ttl=10)  // 10-sec TTL

while true:
    try:
        // Try to acquire leadership
        etcd.put(leader_key, scheduler_id, lease=session)
        LOG("Became leader")

        // Run scheduling loop
        while is_leader():
            poll_and_enqueue_tasks()
            time.sleep(1)
    except LeaseExpired:
        LOG("Lost leadership, entering standby mode")
        time.sleep(5)  // Wait before retry

Interview Tip: Pull-based is industry standard (Celery, Temporal, Sidekiq) for good reason: simplicity and natural load balancing. Only choose push-based if you need advanced placement logic (GPU affinity, geographic routing).

7. Exactly-Once Execution

Challenge: Duplicate Execution Scenarios

Scenario	Root Cause	Example
Worker Crash	Worker pulls task, crashes mid-execution, task re-queued	Payment processed, worker dies before ack, re-processed
Network Partition	Worker loses connection, scheduler assumes failure, reassigns task	Email sent, connection drops, email sent again
Slow Worker	Task exceeds lease timeout, scheduler reassigns to another worker	DB update takes 5 min, lease expires at 3 min, duplicate update
Split-Brain	Two schedulers both think they are leader	Both schedulers enqueue same task

Solution 1: Distributed Locking (Redis)

Step	Action	Redis Command
1. Acquire Lock	Worker attempts to acquire lock for task_id	`SET lock:task_id worker_id NX PX 60000`
2. Execute	If lock acquired, execute task	Process task logic
3. Heartbeat	Extend lock TTL every 10 sec if still executing	`PEXPIRE lock:task_id 60000` (with Lua script to verify owner)
4. Release	Delete lock after completion	`DEL lock:task_id` (with Lua script to verify owner)
Conflict	If lock acquisition fails, another worker is executing	Skip task or wait and retry

Correct Lock Release (Lua Script)

-- Only delete lock if owned by this worker (prevent zombie deletion)
if redis.call("get", KEYS[1]) == ARGV[1] then
    return redis.call("del", KEYS[1])
else
    return 0
end

-- Usage: EVAL script 1 lock:task_id worker_id

Solution 2: Lease-Based Execution

Step	Action	Database Update
1. Claim Task	Worker claims task with compare-and-swap	`UPDATE tasks SET status='running', worker_id='w1', lease_expires_at=NOW()+60 WHERE task_id=? AND status='pending'`
2. Check	Verify claim succeeded (updated row count = 1)	If 0 rows updated, another worker claimed it
3. Execute	Perform task work	Business logic
4. Heartbeat	Extend lease every 20 sec	`UPDATE tasks SET lease_expires_at=NOW()+60 WHERE task_id=? AND worker_id='w1'`
5. Complete	Mark task completed	`UPDATE tasks SET status='completed' WHERE task_id=? AND worker_id='w1'`
Timeout	Scheduler finds expired leases, resets to pending	`UPDATE tasks SET status='pending', worker_id=NULL WHERE lease_expires_at < NOW()`

Solution 3: Fencing Tokens

Aspect	Details
Concept	Monotonically increasing token per task. Higher token invalidates lower token.
Implementation	Task store maintains fencing_token (bigint, auto-increment). When task reassigned, increment token.
Worker Logic	Worker receives task with token=42. Before writing results, verify current token still 42. If 43, abort (another worker took over).
Example	Worker A gets task (token=42), hangs. Scheduler reassigns to Worker B (token=43). Worker A wakes up, tries to write results, check fails (token mismatch).
Pros	Prevents zombie workers from corrupting state

Interview Tip: True exactly-once is expensive and often unnecessary. Most systems use at-least-once with idempotent handlers (e.g., INSERT with unique constraint, upsert with version). Discuss trade-offs: idempotency is simpler than distributed locking.

8. Priority Queue

Priority Levels

Priority	Value	Use Case	SLA
Critical	0	Security alerts, system failures	Execute immediately (<1 sec)
High	1-3	User-facing notifications, time-sensitive operations	<5 seconds
Normal	4-6	Background jobs, report generation	<1 minute
Low	7-9	Cleanup, archival, non-urgent maintenance	<1 hour
Batch	10	Bulk processing, analytics	Best effort

Implementation: Multiple Queues

Queue	Priority Range	Worker Allocation
critical_queue	0	20% of workers
high_queue	1-3	40% of workers
normal_queue	4-6	30% of workers
low_queue	7-10	10% of workers

Starvation Prevention: Priority Aging

Mechanism	Formula	Example
Age-Based Boost	`effective_priority = initial_priority - (age_in_minutes / 10)`	Priority 8 task waiting 50 min becomes priority 3
Time-To-Live	After waiting N minutes, escalate to next priority tier	Low-priority task waiting 30 min promoted to normal
Fair Share	Reserve X% of worker capacity for each priority level	Guarantee 10% of workers always serve low-priority queue

Redis Priority Queue Implementation

-- Enqueue with priority as score (lower = higher priority)
ZADD task_queue {priority + timestamp_nanos} {task_id}

-- Worker poll: Get highest priority (lowest score) tasks
ZPOPMIN task_queue 10

-- With aging: Recompute scores periodically
-- Scheduler background job (every 1 min)
tasks = ZRANGE task_queue 0 -1 WITHSCORES
for task, score in tasks:
    age_minutes = (now - task.created_at).minutes
    new_score = task.initial_priority - (age_minutes / 10)
    ZADD task_queue new_score task.id

Weighted Fair Queuing

Priority	Weight	Polling Strategy
Critical	50	Poll critical queue 50 times per cycle
High	30	Poll high queue 30 times per cycle
Normal	15	Poll normal queue 15 times per cycle
Low	5	Poll low queue 5 times per cycle

Interview Tip: Strict priority causes starvation. Low-priority tasks can wait forever if high-priority tasks keep arriving. Always implement aging or fair-share guarantees to prevent indefinite starvation.

9. Failure Handling

Retry Strategy: Exponential Backoff

Attempt	Delay Formula	Delay (base=2s, multiplier=2)	Cumulative Time
1	base * multiplier^0	2 seconds	2s
2	base * multiplier^1	4 seconds	6s
3	base * multiplier^2	8 seconds	14s
4	base * multiplier^3	16 seconds	30s
5	base * multiplier^4	32 seconds	62s
6	min(base * multiplier^5, max_delay)	64 seconds (or max cap)	126s

Retry Configuration

Parameter	Description	Typical Value
max_retries	Maximum retry attempts before DLQ	3-5
base_delay	Initial retry delay	1-5 seconds
multiplier	Backoff multiplier	2 (double each time)
max_delay	Cap on retry delay	300 seconds (5 min)
jitter	Random offset to prevent thundering herd	0-25% of computed delay

Retry Decision Logic

Error Type	Retryable?	Reason
Network Timeout	Yes	Transient issue, likely to succeed on retry
503 Service Unavailable	Yes	Downstream service temporarily down
429 Rate Limit	Yes (with backoff)	Retry after rate limit window expires
DB Deadlock	Yes	Transaction conflict, retry should succeed
400 Bad Request	No	Invalid input, retry won't fix it
401 Unauthorized	No	Invalid credentials, requires manual fix
404 Not Found	No	Resource doesn't exist, retry pointless
Validation Error	No	Task payload is malformed

Retry Implementation

def execute_task_with_retry(task):
    attempt = 0
    while attempt <= task.max_retries:
        try:
            result = execute_task(task)
            mark_completed(task, result)
            return
        except RetryableError as e:
            attempt += 1
            if attempt > task.max_retries:
                send_to_dlq(task, e)
                return

            delay = calculate_backoff(attempt, task.base_delay, task.multiplier, task.max_delay)
            jitter = random.uniform(0, delay * 0.25)

            LOG(f"Attempt {attempt} failed: {e}. Retrying in {delay + jitter}s")
            update_task_status(task.id, status='retrying', attempt=attempt, next_retry_at=now() + delay + jitter)
            reschedule_task(task, delay + jitter)
            return
        except NonRetryableError as e:
            LOG(f"Non-retryable error: {e}. Sending to DLQ")
            send_to_dlq(task, e)
            return

Dead Letter Queue Handling

Action	Implementation
Store Failed Task	Move task to DLQ with full context (payload, error, stack trace, attempts)
Alert	Send alert to on-call engineer (PagerDuty, Slack)
Investigate	Engineer reviews DLQ, identifies root cause (bug, bad data, external dependency down)
Fix	Deploy fix (code patch, data correction, config change)
Replay	Re-enqueue tasks from DLQ back to main queue for re-execution
Discard	If task is no longer relevant (e.g., stale notification), mark as discarded

Interview Tip: Distinguish transient vs. permanent failures. Blindly retrying validation errors wastes resources. Add jitter to exponential backoff to prevent synchronized retry storms after mass failures.

10. Scalability

Partitioning Strategy

Approach	Partition Key	Pros	Cons
Hash-Based	hash(task_id) % num_partitions	Uniform distribution, simple	No affinity, rebalancing on partition change
Range-Based	scheduled_at timestamp ranges	Natural for time-based queries	Hot partitions (recent tasks), requires rebalancing
Task-Type-Based	hash(task_type)	Affinity (same worker pool handles same types)	Uneven load if some types dominate
Priority-Based	priority level	Dedicated resources per priority	Requires careful capacity planning

Scheduler Sharding

Component	Scaling Strategy
Single Scheduler	1 active scheduler with leader election. Handles up to 10K tasks/sec. Simple but bottleneck.
Multiple Schedulers (Sharded)	Each scheduler owns subset of partitions. Scheduler 1: partitions 0-9, Scheduler 2: partitions 10-19. Scales to 100K+ tasks/sec.
Shard Assignment	Consistent hashing or static configuration. On scheduler failure, reassign its partitions to remaining schedulers.
Coordination	Use Zookeeper/etcd to track scheduler-to-partition mapping. Schedulers watch for changes and rebalance.

Worker Auto-Scaling

Metric	Scale-Up Threshold	Scale-Down Threshold
Queue Depth	> 1000 tasks waiting	< 100 tasks waiting for 5+ min
Queue Age	Oldest task > 2 min old	All tasks < 10 sec old
Worker Utilization	> 80% of workers busy	< 30% of workers busy for 10+ min
Task Throughput	Incoming rate > processing rate	Processing rate > 2x incoming rate

Auto-Scaling Policy

// Kubernetes HPA (Horizontal Pod Autoscaler) config
apiVersion: autoscaling/v2
kind: HorizontalPodAutoscaler
metadata:
  name: task-worker-hpa
spec:
  scaleTargetRef:
    apiVersion: apps/v1
    kind: Deployment
    name: task-worker
  minReplicas: 10
  maxReplicas: 100
  metrics:
  - type: External
    external:
      metric:
        name: redis_queue_depth
        selector:
          matchLabels:
            queue: ready_queue
      target:
        type: AverageValue
        averageValue: "50"  // Target 50 tasks per worker
  behavior:
    scaleUp:
      stabilizationWindowSeconds: 60  // Wait 1 min before scale up
      policies:
      - type: Percent
        value: 50  // Scale up by 50% at a time
        periodSeconds: 60
    scaleDown:
      stabilizationWindowSeconds: 300  // Wait 5 min before scale down
      policies:
      - type: Pods
        value: 1  // Scale down 1 pod at a time
        periodSeconds: 120

Database Optimization

Optimization	Implementation	Impact
Read Replicas	Route status queries to read replicas, writes to primary	Reduce load on primary, improve query latency
Archival	Move completed tasks older than 30 days to cold storage (S3, archive DB)	Keep active table small, fast queries
Partitioning	Partition tasks table by created_at (monthly partitions)	Faster queries, easy archival (drop old partitions)
Index Tuning	Composite index on (status, scheduled_at, priority) for scheduler poll	Index-only scan, avoid table lookups
Connection Pooling	Use PgBouncer for PostgreSQL, limit connections per worker	Prevent connection exhaustion

Scalability Numbers

Component	Capacity	Bottleneck	Solution
PostgreSQL	10K writes/sec	Disk I/O, connection limit	Sharding, write-through cache, read replicas
Redis (single node)	100K ops/sec	Single-threaded, memory	Redis Cluster (sharding), more memory
Kafka	1M msgs/sec	Partition count, broker count	More partitions, more brokers
Worker (CPU-bound)	10 tasks/sec	CPU per worker	Horizontal scaling (more workers)
Worker (I/O-bound)	100 tasks/sec	Async I/O, connection pooling	Increase concurrency per worker

Interview Tip: For 100M tasks/day (1,150 tasks/sec avg, 10K tasks/sec peak), Redis delay queue + 100 workers + PostgreSQL with read replicas is sufficient. Discuss monitoring: queue depth, worker lag, error rate, P99 latency. Mention graceful degradation: shed low-priority tasks under load.

Design Summary

Chosen Architecture

Component	Technology	Rationale
Task Store	PostgreSQL (sharded)	Strong consistency, ACID, complex queries
Ready Queue	Redis ZSET (delay queue)	Fast, sub-second latency, proven at scale
Scheduler	Multiple instances (sharded by partition)	High availability, horizontal scaling
Workers	Kubernetes pods (auto-scaling)	Pull-based, elastic capacity
Coordination	etcd	Leader election, shard assignment

Key Trade-Offs

Decision	Chosen	Alternative	Reason
Execution Semantics	At-least-once + idempotency	Exactly-once with locking	Simpler, better performance, acceptable for most tasks
Task Assignment	Pull-based (workers poll)	Push-based (scheduler assigns)	Natural load balancing, easier to scale workers
Scheduling	Redis delay queue	Kafka time-wheel	Sweet spot for 100M tasks/day, less complexity
Priority	Multiple queues + aging	Single queue with priority score	Prevents starvation, clearer SLAs

Monitoring Dashboards

Metric	Alert Threshold	Action
Queue Depth	> 10,000 tasks	Scale up workers, investigate backlog
Task Lag (age of oldest task)	> 5 minutes	Check worker health, scale up
Error Rate	> 5%	Investigate errors, check DLQ
DLQ Size	> 100 tasks	Review failed tasks, fix root cause
Worker CPU	> 90%	Scale up workers or optimize task handlers
P99 Execution Latency	> 60 seconds	Investigate slow tasks, optimize or increase timeout
Scheduler Downtime	> 10 seconds	Leader election issue, check etcd