The Last Worker Problem

I ran into this while parallelizing PDF generation. One process used to render an entire job. Splitting the work across several workers made rendering much faster, but introduced a new bug: two workers could finish together, both decide the job was complete, and both start the next step.

The PDFs are incidental. The same problem appears whenever a system fans one job out into many parts and joins their results at the end: ETL, media processing, bulk notifications, web crawls, and parallel API calls.

I will call the parent a job, each unit of work a part, and its durable output a result. The goal is not to identify the worker that happens to finish last. It is to let any worker finish last while only one of them commits the job's completion.

Table of contents

1. The fan-out and fan-in shape
2. Why more workers do not mean linear speedup
3. Two races hiding in ordinary code
4. Pattern 1: make the state transition conditional
5. Pattern 2: accumulate without read-modify-write
6. A stronger completion protocol
7. Keep transactions short, but keep invariants together
8. Retries make idempotency part of correctness
9. Where the CAS analogy stops
10. How to test the race, not the timing

The fan-out and fan-in shape

Suppose one job contains thousands of independent units. A coordinator divides them into parts, workers process those parts in parallel, and the last completion advances the job to its next stage.

The expensive work fans out. Progress updates fan back into the same job row. That shared row is where the race lives.

The intended state machine is small:

For this design, correct completion means:

1. each part contributes to progress once;
2. one worker changes the job from Running to Completed;
3. that same transaction records the event that announces completion.

Retries and a healthy relay are still needed to make progress. The transaction only prevents conflicting outcomes.

Why more workers do not mean linear speedup

Amdahl's law is a useful check before adding workers. If $P$ is the fraction of runtime that parallelizes perfectly, the best possible speedup with $N$ workers is

If 90% of the runtime is parallelizable, six workers top out at

That is 4×, not 6×, before queue latency, database contention, storage bandwidth, retries, or worker startup. In practice I would measure wall-clock time and lock waits at each worker count rather than infer capacity from the number of consumers.

Two races hiding in ordinary code

Race 1: the lost update

Two workers complete together and increment a shared counter:

// Wrong: the read and write are separate database operations.
const job = await getJob(jobId);

await updateJob(jobId, {
  completedParts: job.completedParts + 1,
});

An unlucky interleaving loses one completion:

Worker A reads completedParts = 7
Worker B reads completedParts = 7
Worker A writes 8
Worker B writes 8

Expected: 9
Actual:   8

Both writes are valid, but both were calculated from the same stale value.

Race 2: check, then act

The last worker should mark the job complete and emit one event:

// Wrong: another worker can pass both checks before this update commits.
const pendingParts = await countPendingParts(jobId);
const job = await getJob(jobId);

if (pendingParts === 0 && job.status === 'running') {
  await setStatus(jobId, 'completed');
  await publish({ type: 'JobCompleted', jobId });
}

Two workers can both observe pendingParts === 0 and status === 'running'. Both then update the status and publish. An idempotent status assignment hides the race in the table, while duplicate downstream work reveals it later.

The shared pattern is read-modify-write: read a fact, decide in application code, then write as though the fact were still current.

Pattern 1: make the state transition conditional

The first fix is to move the status check into the write:

UPDATE batch_jobs
SET status = 'completed',
    completed_at = now()
WHERE id = $1
  AND status = 'running'
RETURNING id;

This is the database version of compare-and-swap: update the value only if it still has the value we expect. Under PostgreSQL's default Read Committed isolation, competing updates serialize on the row. After the first commits, the second rechecks the WHERE clause and returns no row.

This post assumes Read Committed. At Repeatable Read or Serializable, PostgreSQL can abort a competing transaction instead; in that case the caller must retry the whole transaction.

A returned row elects one winner, but it does not prove that every part is finished. It also does not make a subsequent broker publish atomic. The full protocol below checks the part count and writes a uniquely keyed outbox event in the same transaction. The relay may still publish that event more than once, so consumers must be idempotent.

Pattern 2: accumulate without read-modify-write

Each worker may also need to record a result reference: an object key, output ID, checkpoint, or other durable handle. Rebuilding a shared array in application memory has the same lost-update race as the counter:

// Wrong under concurrency.
const job = await getJob(jobId);
const next = [...job.resultRefs, resultRef];
await updateJob(jobId, { resultRefs: next });

If the job really stores an array, append inside the database:

UPDATE batch_jobs
SET result_refs = array_append(result_refs, $2)
WHERE id = $1;

That prevents lost writes, but retries can still append duplicates and every worker still locks the parent row. I prefer one row per part. The coordinator creates the complete set before dispatching work:

CREATE TABLE job_parts (
  job_id       uuid    NOT NULL REFERENCES batch_jobs(id),
  part_index   integer NOT NULL CHECK (part_index >= 0),
  status       text    NOT NULL DEFAULT 'pending'
                       CHECK (status IN ('pending', 'completed')),
  result_ref   text,
  completed_at timestamptz,
  PRIMARY KEY (job_id, part_index)
);

A worker completes a part with another conditional update:

UPDATE job_parts
SET status = 'completed',
    result_ref = $3,
    completed_at = now()
WHERE job_id = $1
  AND part_index = $2
  AND status = 'pending'
RETURNING part_index;

The primary key limits the job to one row per expected part. The status condition makes a retry a no-op. If no row is returned, the worker checks whether this is the same result arriving again; an unknown part or a different result is an error. Results are assembled with ORDER BY part_index, not their completion order.

A stronger completion protocol

The coordinator creates every part and initializes remaining_parts integer NOT NULL CHECK (remaining_parts >= 0) in one transaction. After the job starts, the part set is immutable. A zero-part job is completed by the coordinator because no worker will arrive to do it.

Work dispatch has its own failure window. I would either create work-item outbox rows with the parts or run a reconciler that republishes undispatched parts.

Each completion then follows one short transaction:

await db.transaction(async (tx) => {
  const part = await completePartIfPending(tx, {
    jobId,
    partIndex,
    resultRef,
  });

  if (!part.changed) {
    await assertSameCompletedResult(tx, { jobId, partIndex, resultRef });
    return; // Safe retry.
  }

  const progress = await decrementRemainingIfRunning(tx, jobId);
  if (!progress) throw new Error('Job is not running');
  if (!progress.isLast) return;

  const completed = await completeJobIfRunningAndEmpty(tx, jobId);
  if (!completed) throw new Error('Final state transition failed');

  await insertOutboxEvent(tx, {
    eventKey: `job-completed:${jobId}`,
    type: 'JobCompleted',
    payload: { jobId },
  });
});

The helpers above are conditional SQL statements like the two shown earlier. decrementRemainingIfRunning returns remaining_parts = 0 AS is_last. The outbox has a unique event_key, and its insert fails rather than silently accepting an unexpected conflict.

Four details carry most of the design:

• only pending → completed decrements the counter;
• concurrent decrements serialize on the parent row;
• the worker that reaches zero changes the status and writes the outbox event;
• a retry must match the result already recorded for that part.

The counter can still drift if another write path bypasses this transaction, so I would keep a reconciliation query for repair and monitoring.

Failure needs a separate policy. Transient failures leave the part pending and retry. An exhausted part needs a terminal state, a running → failed transition, and a failure event. Without that path, one poison message can leave a job running forever.

Every completion briefly locks the parent row. I would keep this design for moderate fan-out because it is easy to reason about. If lock waits become meaningful, then I would consider partitioned counters or reconciliation instead of coordinating every completion through one row.

Keep transactions short, but keep invariants together

The slow phase might transcode media, call an external API, transform a dataset, or upload a large object. A database transaction should not remain open around that work: long transactions hold resources, delay cleanup, increase lock time, and make failures expensive.

Split the handler into three phases:

I keep slow, fallible I/O outside the transaction and put only the writes that establish one invariant inside it. Transaction scope follows the invariant, not the whole handler.

This split cannot make external output and the database commit atomic. A crash or rejected completion can leave an orphaned object, so use stable immutable references plus reconciliation or lifecycle cleanup. If the slow phase itself has side effects, it needs the idempotency treatment in the next section.

Retries make idempotency part of correctness

Queues and outbox relays commonly provide at-least-once delivery. A worker can finish its work and crash before acknowledging the message, so the same message arrives again. This is normal operation, not an edge case.

I use stable identifiers at every boundary:

• (job_id, part_index) identifies a part;
• jobs/{jobId}/parts/{partIndex} can identify stored output;
• job-completed:{jobId} identifies the completion event;
• the same event key identifies the consumer's processed-event record.

A database consumer inserts that event key and applies its business change in one transaction, only when the insert succeeds. An external API needs its own idempotency contract or a reconciliation step; another outbox makes retries durable but cannot undo a remote call whose acknowledgement was lost.

Delivery remains at least once. Stable identities and conditional writes make the business operation idempotent.

Where the CAS analogy stops

Linearizability

An operation is linearizable when it appears to take effect at one instant between invocation and response, even if operations overlap in real time.

For the narrow running → completed operation, the successful commit is that instant. The transaction also makes the part, counter, status, and outbox visible together. That does not make the entire distributed workflow linearizable; the claim stops at the database transaction.

Consensus numbers

In Herlihy's shared-memory model, compare-and-swap has an infinite consensus number, which is why it is called a universal primitive. The SQL update above borrows the shape of CAS, not its progress guarantee. A database update can wait on a row lock, deadlock, or fail over the network, so this design is not wait-free.

How to test the race, not the timing

Starting two promises and hoping they overlap does not reliably test the race. Put a barrier after the reads so both workers see the same value before either one writes.

For the broken read-modify-write implementation:

1. Pause both workers after they read the same row.
2. Release both only after both reads have completed.
3. Let each write its derived value.
4. Assert that the invariant fails.

For the corrected protocol, run many workers with duplicate part messages and assert properties rather than execution order:

• There is exactly one result per expected part index.
• remaining_parts never becomes negative.
• Exactly one running → completed update returns a row.
• One logical completion event exists in the outbox.
• A zero-part job completes without waiting for a worker.
• Replaying every input changes no final state.

Also inject failures at the boundaries that ordinary tests skip:

• after the external result is produced but before the database transaction;
• after the database commit but before queue acknowledgement;
• after the relay publishes but before it marks the outbox row sent.

After each injected failure, replay the message and check the same invariants. I would also test the terminal-failure path and a part that was committed but never dispatched.

Practical checklist

When parallelizing a batch workflow:

1. Draw the state machine and write the invariants in plain language.
2. Find every read-modify-write and check-then-act sequence.
3. Replace them with conditional writes and uniqueness constraints.
4. Commit state transitions and outbox events together.
5. Assume every message can arrive more than once.
6. Define zero-work, terminal-failure, and reconciliation paths.
7. Measure lock waits before adding more workers.

For moderate fan-out, I would start with explicit part rows, one guarded parent counter, and an outbox. It is not lock-free, but its failure modes are visible and repairable.

References

• Gene M. Amdahl, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities" (1967).
• Maurice Herlihy and Jeannette Wing, "Linearizability: A Correctness Condition for Concurrent Objects" (1990).
• Maurice Herlihy, "Wait-Free Synchronization" (1991).
• Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, Revised Reprint (2012).
• PostgreSQL, "Transaction Isolation".
• PostgreSQL, "Row Security Policies".
• AWS Prescriptive Guidance, "Transactional outbox pattern".