Task Coordinator

What is a distributed task coordinator?

A distributed task coordinator accepts large jobs from clients, partitions each job into smaller tasks, and fans them out to a worker pool running across many machines. The completed results are aggregated and returned to the client. The central challenge is the coordination machinery itself: task assignment without coordinator bottlenecks, worker crash recovery without losing progress, and result aggregation without fan-in collapse at scale.

The central design question is: what happens when the coordinator is slower than the workers? That constraint drives the pull-based assignment model, the lease protocol, and the coordinator's high-availability design.

TL;DR

Use a coordinator to create durable job/task state, but keep per-task assignment decentralized: partition the input, publish tasks to Kafka, and let workers pull batches while recording leases and progress in Redis. Workers write idempotent partial results to object storage; a two-phase combiner avoids a single fan-in bottleneck. Protect the coordinator with etcd leader election and a replayable write-ahead log, and re-enqueue tasks whose heartbeats expire.

Scope and assumptions

• The baseline covers finite batch jobs, input partitioning, task assignment, worker failure recovery, and final aggregation.
• Inputs and partial/final outputs live in object storage; tasks are independently retryable and should be idempotent because leases provide at-least-once execution.
• A single region with up to 10,000 workers and 1 million tasks is sufficient for the primary design. Cross-region job state and compute isolation are extensions.
• The coordinator owns job-level state transitions, not the execution of every worker step. Workers pull work and report through a lease-based protocol.
• Priority scheduling, streaming computation, per-tenant quotas, and arbitrary DAG dependencies are outside the core question unless introduced as follow-ups.

Functional Requirements

Core Requirements

1. A client can submit a job specifying an input dataset and a processing function, and receives a job ID in return.
2. The system partitions the job into tasks, assigns tasks to available workers, and tracks completion.
3. A worker failure is automatically detected and its task is re-assigned to another worker without client involvement.
4. When all tasks complete, the system aggregates the results and makes the final output available to the client.

Below the Line (out of scope)

• Priority scheduling across multiple concurrent jobs
• Real-time streaming (as opposed to batch) computation
• Security isolation between tenants sharing the cluster
• Billing and resource quotas per job

The hardest part in scope: Coordinating task assignment at 50,000 tasks per second across 10,000 workers without the coordinator becoming a bottleneck, while detecting and recovering from up to 10% worker failures mid-job without losing progress.

Priority scheduling is below the line because it adds a fair-share queue and preemption machinery orthogonal to the core coordination design. To add it, maintain a separate priority queue of pending jobs and implement a weighted-fair-share scheduler that dequeues jobs by priority weight.

Real-time streaming is out of scope because stream processing requires continuous ingestion and windowed computation, whereas this design targets finite batch jobs with a defined completion. To extend it, replace the task queue with a Kafka consumer group and add windowed aggregation on the worker side.

Non-Functional Requirements

Core Requirements

• Scale: Support jobs with up to 1 million tasks. Up to 10,000 concurrent workers.
• Fault tolerance: Complete a job even if up to 10% of workers fail during execution.
• Coordinator availability: 99.99% uptime. A coordinator failure must not lose in-progress jobs.
• Assignment throughput: Coordinator assigns tasks at minimum 50,000 tasks per second to avoid being the bottleneck.
• Task execution time: Individual task execution time ranges from 100ms to 30 minutes.
• Read/write ratio on the task store: Writes dominate (status updates from workers heartbeating and completing). Batch reads occur when the coordinator scans for expired leases.

Below the Line

• Sub-second coordinator failover (15 seconds is acceptable for this design)
• Cross-region replication of in-progress job state
• Per-task compute isolation (all workers share the same cluster)

30-second answer

Accept a batch job, partition its input into balanced tasks, and publish them to a partitioned Kafka queue. Workers pull tasks, acquire a lease, heartbeat through a progress store, and write idempotent partial results to S3. A lease monitor re-enqueues expired tasks; a combiner fleet aggregates results in two phases. Use etcd leader election plus a durable transition log so a standby coordinator can resume without losing job state.

5-minute explanation

1. Set the contract. Support job submission/status, finite batch tasks, automatic retry after worker failure, and a final output. State the 50K assignments/s, 10K workers, 1M tasks, and 15-second failover assumptions.
2. Explain why push fails. A single coordinator that pushes each assignment serializes decisions and stalls all workers when its loop or network is slow.
3. Separate control from work. The coordinator partitions and publishes tasks; workers pull batches independently. Redis stores leases/status, Kafka buffers tasks, and object storage holds data and results.
4. Walk the task lifecycle. Claim with a TTL, heartbeat at a fraction of the TTL, write a deterministic output, and complete only if the lease is still owned. A reclaimed lease returns 410 so the worker stops.
5. Close the system. Re-enqueue expired work, use speculative execution for stragglers, aggregate through combiners, and replicate coordinator transitions through an append-only log for failover.

45-minute interview approach

1. 0–3 min — Clarify scope. Confirm batch versus streaming, input/output formats, task independence, retry semantics, maximum task count, worker count, and whether priority or DAG dependencies are required.
2. 3–8 min — Establish the numbers. Estimate task creation rate, task duration distribution, heartbeat volume, queue partitions, result size, coordinator failover target, and the tolerated duplicate work.
3. 8–13 min — Define entities and APIs. Sketch Job, Task, Worker, Result, job submission/status, claim, heartbeat, and completion contracts. Make lease expiry and idempotency explicit.
4. 13–22 min — Draw the baseline. Show Job API, Coordinator, Partition Service, Kafka, Worker Pool, Progress Store, object storage, Lease Monitor, and Combiner. Walk one task from claim to result.
5. 22–35 min — Prioritize the hard parts. Spend the largest block on pull-based scaling/work stealing, lease expiry and duplicate execution, straggler/speculative handling, two-phase aggregation, and coordinator failover with durable state replay.
6. 35–40 min — Cover reliability, security, and operations. Discuss at-least-once delivery, idempotent outputs, fencing stale workers, leader election, worker authentication, job isolation, queue depth, lease metrics, and recovery drills.
7. 40–44 min — Compare alternatives. Contrast push versus pull, one combiner versus a combiner tree, Redis versus a durable task database, and long versus short lease TTLs.
8. 44–45 min — Recap and invite follow-ups. Restate who owns assignment, what happens on a crash, and why duplicate execution is safe.

Core Entities

• Job: A unit of work submitted by a client. Contains job_id, input_path (pointer to input data in S3), function_id, status (queued / running / completed / failed), and submitted_at.
• Task: A subdivision of a job. Contains task_id, job_id, partition_spec (key range or file chunk), status (pending / in_progress / completed / failed), assigned_worker_id, and lease_expiry_ts.
• Worker: A machine that executes tasks. Registers its worker_id and capacity, heartbeats while alive, and reports task outcomes to the coordinator.
• Result: The output produced by a worker for a task. Contains task_id, output_path (S3 location of partial result), and whether it is a partial or final result.

API Design

Two surfaces exist: the client API (job submission and status) and the worker API (task pull, heartbeat, completion reporting).

// Client: submit a job for distributed execution
POST /jobs
Content-Type: application/json

{
  "input_path": "s3://jobs-input/dataset-2024-01.csv",
  "function_id": "word_count_v2",
  "output_path": "s3://jobs-output/run-abc123/"
}

Response: 201 Created | { "job_id": "job-abc123", "status": "queued" }

// Client: poll job status and retrieve output location
GET /jobs/{job_id}

Response: 200 OK
{
  "job_id": "job-abc123",
  "status": "completed",
  "tasks_total": 1000,
  "tasks_completed": 1000,
  "output_path": "s3://jobs-output/run-abc123/final"
}

// Worker: pull the next available task
POST /tasks/claim
Authorization: Bearer <worker-token>

Response: 200 OK
{
  "task_id": "task-77",
  "partition_spec": { "start_byte": 0, "end_byte": 104857600 },
  "input_path": "s3://jobs-input/dataset-2024-01.csv",
  "lease_ttl_seconds": 30
}

// Worker: extend task lease with a heartbeat
POST /tasks/{task_id}/heartbeat
Authorization: Bearer <worker-token>

Response: 200 OK | 410 Gone (task was reclaimed by coordinator)

// Worker: report task completion
POST /tasks/{task_id}/complete
Authorization: Bearer <worker-token>

{ "output_path": "s3://jobs-output/run-abc123/task-77.part" }

The 410 on heartbeat is the signal to a worker that its lease was reclaimed. The worker must stop executing and discard its partial output. The lease_ttl_seconds in the claim response tells the worker how often to heartbeat (at most every TTL / 3 seconds).

High-Level Design

1. Naive approach: push-based coordinator

The simplest design is a single coordinator that tracks available workers and pushes tasks to them one at a time. The coordinator holds the task queue in memory and drives completion by monitoring worker availability.

Request walkthrough (submit and execute):

1. Client sends POST /jobs with an input path and function ID.
2. Coordinator reads the input metadata, splits it into N tasks, and stores them as pending in the Task Store.
3. Coordinator finds idle workers and pushes one task to each.
4. Worker executes, completes, and notifies the coordinator via RPC.
5. Coordinator marks the task completed and pushes the next pending task to the now-idle worker.

This design is correct for small clusters. The coordinator becomes the bottleneck once the worker count grows because it serializes every assignment. It can work at tens of workers and fall apart at thousands when task completions are frequent.

The coordinator bottleneck problem:

At 10,000 workers completing sub-second tasks, the coordinator must process 10,000 assignments per second through a single loop on a single thread. Network call latency stacks up and the assignment loop serializes what should be parallel decisions. If the coordinator is slow for 10ms, all workers stall simultaneously.

2. Evolved approach: pull-based workers with a distributed task queue