The Stage Barrier

## Two shapes of step A running job is a graph of steps inside one program. (It is not the graph of scheduled jobs an orchestrator runs — same picture, different edges, different subject.) Within that graph the steps come in two shapes: - **Steps that need only what the worker already holds.** Testing a predicate, dropping a field, converting a value. The worker reads its own **piece** — one contiguous share of the input that a single worker processes on its own — and writes its own output. Several such steps in a row are usually run record by record inside the piece with nothing crossing the network. - **Steps that need records other workers are holding.** A total per customer, a match between two inputs on an identifier, an end-to-end ordered result. The records that must meet are scattered across the cluster, so they have to be moved first. That move is a **redistribution**: every worker sends each record it holds to whichever worker will handle that record's key, so the step can run at all. The first shape never makes anybody wait. The second is where the line appears. (Which operations fall into which shape is a neighbouring subject; here the point is only that the second shape exists.) ## Why there is a line at all Two distinct causes, and separating them is what a strong answer does. 1. **The operator needs completeness.** A count for a key is not *the* count until the last record bearing that key has been folded in. The routing function — the rule applied to each record's key that names its one destination worker — guarantees that equal keys meet, so a consumer knows *where* a key's records land. It cannot know *whether more are coming* until every producing piece has run out of input. Emitting earlier means emitting a number that is simply wrong. 2. **The exchange is often blocking.** In the finite-job regime many engines have each producer write its output into one bucket per destination on the local disks of the machine that produced it, and make that output collectable only once the producer has finished. Other engines push records across the network as they are produced. The first choice makes the wait explicit and makes re-running cheap; the second moves bytes earlier but does not remove the operator's need for completeness. Together they draw a **stage barrier**: a line across the job where no downstream worker may compute until every upstream piece of the producing step has finished. ## What the line does and does not mean - It is a **line, not a step**. Nothing executes "at" it; it is a constraint on when downstream compute may begin. - It is about **correctness, not a slow network**. A faster network shortens the transfer, not the wait. - It governs **compute, not transfer**. Bytes from producers that have already finished can be collected while others are still running. - It is a property of the **step boundary, not of a record**. A record that arrives early buys nothing by arriving early. - It is **not** the marker injected into the record flow so that every worker records its state at the same logical point. That marker is a recovery device; it exists to capture a consistent picture, not to hold compute behind a completeness requirement. ## Which steps sit behind a line | Step shape | Needs records other workers hold? | Waits for the producing step to finish? | |---|---|---| | Per-record projection or filter | No | No — runs through inside the piece | | Fold per key over the whole input | Yes | Yes — the fold is wrong until every producer is done | | Match two large inputs on a key | Yes | Yes — the side being matched against must be complete | | End-to-end ordered result | Yes | Yes — order is a property of the whole input | ## What the line costs - The step is **paced by its slowest producing piece**. The line lifts when the last piece finishes, not when the median one does, so wall clock follows the maximum and not the average. - Capacity behind the line is **idle, or merely collecting bytes**, which is how a cluster manages to look busy while producing almost nothing. - Where the regime materialises producer output, each line adds a **write and a read of the intermediate bytes** on top of the compute either side of it. ## Where the line is absent An endless input never finishes, so a job whose operators hand each record downstream as it is produced never reaches "every producer has finished" and therefore has no such line; its operators must emit from partial input using whatever bounding device the pipeline gives them. A large part of this market sits in between, running continuous work as a rapid succession of small finite jobs — and inside each of those small jobs the lines are back.