Task re-execution and blacklisting

Why does a large job need re-execution to finish at all, and what does blacklisting a node cost?

What it is. At job scale, failure stops being rare. Take a batch job with n = 10⁴ tasks, each with failure probability p = 10⁻³. The probability that no task fails is

(1 − p)ⁿ ≈ e⁻¹⁰ ≈ 4.5 × 10⁻⁵.

(Check: n × p = 10⁴ × 10⁻³ = 10, and (1 − p)ⁿ ≈ e^(−np) = e⁻¹⁰.) A job of this size almost always contains a failure. Job-level success is not something you can buy from reliable parts. It must be manufactured by re-execution. This is why batch engines have retry built in, while a single-process program does not: the same p that is negligible at n = 10 is certain at n = 10⁴. It is Wanjiru's billing-rollup.

Re-executing a failed task up to k times changes the formula from (1 − p)ⁿ to (1 − pᵏ)ⁿ. With k = 3: pᵏ = 10⁻⁹, so (1 − 10⁻⁹)^10,000 ≈ 1 − 10⁻⁵, nearly 1. This works only if attempts are independent, the third time this article has depended on that condition.

Blacklisting restores independence

When failures cluster on one node (a bad disk, a bad network card), retrying on the same node gives dependent attempts. Retrying elsewhere makes them independent again. So blacklisting (excluding a node from scheduling) is an online classifier that decides which failures are caused by the node. Like every classifier working on little evidence, it has two errors with different costs:

• Blacklist a healthy node: you lose capacity. Under broad, load-induced failure you can blacklist the entire fleet, a real and spectacular production outcome.
• Fail to blacklist a sick node: tasks keep landing on it, and the retry count is consumed by the same fault.

So every implementation has decay on entries (a node returns after some time), a quota (never exclude more than a fraction), and a scope decision (per stage or per application). Structurally this is the same object as a failure detector: a guess with unequal costs and no ground truth.

The unit of failure is not the unit of retry

Re-executing a task recovers a task. But losing an executor (a worker process) loses its cached blocks and its shuffle files too, so other tasks' completed work dies with it. The cost is greater than linear in the size of the failure. This repeats at every level: container, node, availability zone (a separate data centre building within a region).

Not covered here. Speculative execution (starting a second copy of a slow task) treats slowness rather than failure and is a different model. The record that kills every attempt is the poison pill of Making a repeat harmless.