Stragglers and Speculative Execution: A System Design Interview Topic

In a batch job split into thousands of tasks, the job finishes only when the last task finishes. A single slow machine, a straggler, can double total runtime. The MapReduce paper reported jobs taking 44% longer when backup tasks were disabled.

Where stragglers come from

• Hardware: a failing disk with retries, thermal throttling, a noisy neighbour.
• Data skew: one partition simply has more records (a hot key).
• Software: GC pauses, a task scheduled on an overloaded node.

Speculative execution

When a job is near completion, the scheduler launches duplicate copies of the slowest in-progress tasks on other machines. Whichever copy finishes first wins; the other is killed. Hadoop and Spark (spark.speculation) both support it.

How the scheduler picks candidates

Spark, for example, considers a task for speculation once a configurable fraction of tasks in the stage has finished and the task has been running longer than a multiple of the median task duration. Comparing to the median, not the mean, keeps one outlier from distorting the baseline.

Costs to mention (interviewers look for these)

1. Wasted resources: duplicate work consumes cluster capacity, so speculate only the tail.
2. Side effects: tasks must be idempotent, and output commits must be atomic (write to a temp location, rename on success), otherwise two copies may both write results.
3. Skew is not fixed by it: if the task is slow because its input is huge, a backup copy is just as slow. Fix skew with salting keys or splitting hot partitions.

Related idea: hedged requests

The online-serving cousin is sending a second request after the 95th-percentile latency has elapsed, from Google's "The Tail at Scale". Connecting the batch and online versions in one sentence is a strong signal of breadth.

Interview summary

"Job latency is governed by the slowest task, so I'd enable speculative execution for the tail, make tasks idempotent with atomic commits, and treat data skew separately because duplication can't fix it."

Disclosure: I am on the team behind an AI interview assistant (Linkjob AI). These notes are general study material.