Chained Jobs and Fan-In Completion Without a Coordinator

A single job that does one thing is a solved shape. The interesting work is a graph: a job that splits an input into pieces, a job per piece, and a final job that assembles the results. The graph introduces a question that no single job has to answer — when is the whole thing done — and in a system with leases, retries, and crashes, the answer cannot be “when the parent sees all the children return”, because the parent may not be running.

The two structural choices are who holds the state that describes progress, and who performs the transition when it completes. A parent that stays resident and waits holds a worker for the duration of the children, which is unbounded and defeats the point of distributing the work. A parent that polls is not running and cannot poll. That leaves either a persistent counter that the children decrement, or completion derived from the children’s own records.

The parent that waits holds a worker

The naive fan-out keeps the parent in its handler, starts children, and blocks on their completion. In a system where the handler is a claimed job with a lease, that means the parent’s worker is occupied for the entire duration of the slowest child, and the lease has to be renewed throughout. Ten parents with a thousand children each occupy ten workers while doing nothing but waiting.

It also puts an unbounded dependency on the parent’s own durability. If the parent’s worker dies, the children continue and complete, and their results are attached to a parent that will be re-claimed and re-spawn them — because the parent has no way to distinguish “children not yet started” from “children already running”. The re-spawn is a duplicate fan-out, and every child runs twice.

Distributing the work therefore requires the parent to finish after producing the children, which moves the completion question somewhere that survives the parent’s death.

Counting terminal outcomes, not successes

The counter form stores, beside the batch, the number of children still outstanding. Each child, on reaching a terminal state, decrements it. The child that observes the counter reach zero performs the successor step.

BEGIN;

UPDATE batches
SET remaining = remaining - 1
WHERE id = $1 AND remaining > 0
RETURNING remaining;          -- exactly one transaction sees 0

-- only when the value returned was 0
INSERT INTO jobs (kind, payload, available_at)
VALUES ('assemble', $2, now());

COMMIT;

Two properties of that statement are load-bearing. The remaining > 0 predicate stops a stray second decrement from taking the counter negative and re-triggering the successor, and the row lock serialises concurrent decrements so exactly one observes the transition to zero. The successor insert in the same transaction means the counter and the successor are consistent: either the batch is finished and its continuation exists, or neither.

The decision that causes the most trouble is what counts as terminal. If only successes decrement the counter, a batch with one permanently failed child never completes — the counter sits at one forever and the successor never runs, which is often the correct outcome but is indistinguishable from a stuck system. If terminal failure decrements it too, the successor runs with partial input and must be written to handle missing pieces.

The count should therefore be over terminal outcomes, successes and dead-lettered children alike, and the batch record should carry both a completion count and a failure count. The successor decides what to do with failures, which keeps that decision in one place instead of in the counting mechanism. A batch that completes with three failures is a normal batch, not an anomaly, and the successor can retry those pieces, report them, or refuse to merge.

The counter must also be initialised atomically with the child inserts. Computing the count in application code, inserting children, then writing the counter leaves windows in which a child finishes before the counter exists, or the counter is written higher than the number of children actually created. A single transaction that inserts the children and sets remaining to the number inserted closes both. Where the children span partitions or queues and cannot be inserted in one transaction, the counter is initialised to the planned count before any child is enqueued, and enqueue failures must decrement it — which is a second chance to get the arithmetic wrong.

Who fires the successor, and how once

Only one child’s transaction sees zero, so only one enqueues. That is the whole reason for the conditional decrement, and the enqueue must not be a separate step outside the transaction, or a crash between the two loses the continuation while the batch looks complete.

Duplicate successors arise from a different mechanism: a child that is acknowledged twice. The conditional acknowledgement from The Job Record State Machine prevents the second acknowledgement from reaching the state change at all, so the decrement happens once per child. A child whose lease expired mid-execution may run twice, but only one execution commits a terminal state.

A duplicate can still appear if the successor insert is retried after a timeout in which the first insert succeeded. A unique key on the successor’s logical identity — the batch identifier plus the step name — turns the second insert into a conflict rather than a second job, which is the producer-side deduplication from Idempotency at the Effect Boundary applied to job creation rather than to an external effect.

The last child does more work than the others: it decrements, inserts the successor, and commits. That skew is inherent to the design and is measured in one extra transaction, not in one extra unit of real work. It matters only when the successor insert is itself expensive, for example when it fans out again.

Completion derived from the children

The counter is state, and state drifts. A child that was never enqueued, or enqueued and then purged, leaves the counter above zero and the batch permanently incomplete.

The alternative derives completion from the records themselves: the batch is complete when no child of it is in a non-terminal state.

SELECT count(*) = 0 AS complete
FROM jobs
WHERE parent_batch = $1
  AND status NOT IN ('succeeded', 'dead');

The query is the check, and a partial index on the non-terminal statuses keeps its cost proportional to the number of unfinished children rather than the total. With such an index, a batch with a thousand children and two outstanding scans two index entries.

Every child runs the query on completion, so the total work is one query per child, each reading a set that shrinks. That is more total work than a counter’s single decrement per child, and it is stateless: a lost child does not leave the batch incomplete, because a child that does not exist is not counted. The failure mode it cannot detect is a child that was planned and never created — the query cannot count what is absent — so the planned count still has to be compared against the created count somewhere, usually at the end.

A hybrid is common: the counter for the fast path, and a periodic reconciliation that recomputes remaining from the child records and finalises batches whose counter is inconsistent. Reconciliation is the same argument as a ledger rebuild, and it requires that the child records be the authority, which they are when the counter is derived rather than independently assigned.

Compensation when a step fails for good

A chain that splits into parallel steps and then merges has no rollback in the transactional sense. Step two may have committed before step three fails permanently, and the compensations are new jobs that undo the effects of the completed steps, in reverse order.

Garcia-Molina and Salem’s sagas describe exactly this: a long-lived transaction decomposed into steps, each with a compensating action, such that a failure triggers the compensations of the already-committed steps. Implementing it on a job system means storing, per chain, which steps have completed, and generating compensation jobs from the terminal failure.

The compensations are themselves jobs and inherit every property already described: they can fail, they can be retried, and they must be idempotent. A compensation that reverses a ledger entry is naturally a new entry keyed by the original’s identity, which makes a repeated compensation a no-op rather than a double reversal. A compensation that sends a cancellation mail has the same duplicate problem as the original mail and needs the same key.

Not every step is compensable. A step that sent an email or transferred funds to an external party that does not accept reversals has no mechanical undo, and the chain’s design has to record that the compensation is a manual action. The saga’s guarantee is that each step has a defined outcome on failure, not that the outcome is a reversal.

Bounds on width and depth

A job that spawns children based on its input can spawn an unbounded number of them. A job that spawns a child of its own kind can recurse without limit. Neither is prevented by the retry mechanism, which counts attempts on one job rather than descendants of it.

The width bound is a cap on children per batch, with the remainder split into additional batches or processed in a second pass. The depth bound is a counter carried in the payload, incremented at spawn, with jobs past a limit promoted to a terminal failure that a human can inspect. Both bounds exist because a runaway spawn is not a performance problem but a data problem: a million jobs enqueued by a misconfigured split are a million durable writes and a million downstream effects, and stopping the producer after the fact does not remove them.

The chain also has a total-time question that no single job’s deadline answers. A batch whose children each have a generous deadline can take days; the successor needs its own deadline and its own staleness policy, and the batch record needs a give_up_at after which the successor runs with whatever arrived. That finalisation is the same misfire decision as a schedule that missed its window — proceed with partial data, or abandon — and it should be made explicitly rather than emerging from whichever child happens to finish last.