Distributing Tests Across Workers Without Losing Determinism

Splitting a suite across workers is presented as a matter of passing a flag. The wall-clock time that flag buys is governed by the longest-running test rather than the average, the choice of what to hand to a worker determines which fixtures can be shared at all, and every source of non-determinism that was hidden by a fixed serial order becomes observable the moment two tests run at the same time. The scheduling problem is the part that can be reasoned about formally; the rest is consequences.

Makespan is dominated by the tail

If a suite contains jobs of sizes p₁ … pₙ and there are m identical workers, minimising the time until the last job finishes — the makespan — is list scheduling. The optimal assignment is a bin-packing problem and is NP-hard, but the greedy rule of dispatching the longest remaining job to the first free worker, known as longest processing time first, comes within a factor of 4/3 − 1/(3m) of the optimum in the worst case. That bound is the reason practical schedulers order by descending duration: it costs one sort and gets close to the best achievable without solving the hard problem.

The same bound explains why naive splitting performs badly. Dividing N tests into m equal groups by name or by index ignores duration entirely, and test durations are extremely skewed: a small number of integration tests typically account for most of the total, so the worker that receives a slow one finishes long after the others are idle. Equal-count partitioning gives the illusion of balance by counting the wrong quantity.

The practical consequence is that a scheduler wants historical durations, and it wants them keyed by something stable. That key is the test identifier assigned during collection, described in Test Discovery, Collection Order, and Import Side Effects, which is why the identifier’s stability is a scheduling concern and not just a reporting detail. A renamed or re-parametrised test loses its history and is scheduled blind, and a suite that regenerates identifiers on every run — because identifiers embed something positional — never accumulates useful history at all.

Static assignment from history and dynamic assignment from a work queue have different failure profiles. A static plan has no coordination traffic and no dependence on a central dispatcher, so it scales to hundreds of workers and remains stable if a worker dies slowly. It also cannot adapt when the history is wrong, and a machine that is slower because a colleague is compiling on it gets an inflated schedule. A dynamic queue adapts to everything, at the cost of the queue becoming a bottleneck at high worker counts and of results arriving in an order determined by completion rather than by plan.

The unit of distribution confines what can be shared

Work can be distributed per test, per file, per package, or per shard assembled by the scheduler, and the choice determines which fixtures remain valid. Session-scoped resources such as a database handle or a spawned server are only shareable within a worker. If the unit is a single test, then the widest useful fixture scope is the worker’s lifetime, and anything that must be created once per suite — a schema, a compiled binary, a service — has to be prepared before workers start or accepted as per-worker cost.

The common compromise is to keep whole files or whole classes on one worker, which preserves module- and class-scoped fixtures and keeps their reset logic valid, while still letting the scheduler balance at file granularity. The cost is granularity: a file containing one very slow test and thirty fast ones is an indivisible lump of work, and the makespan bound applies to the lumps rather than to the tests. Runners that offer both modes force the decision on the user, because the framework cannot know which fixtures are safe to instantiate per worker.

Ordering guarantees also change shape. In a serial run each test has a definite predecessor. Under distribution a test has a predecessor only within its worker, so a suite that depends on a cross-file order still passes in a serial run and fails, non-deterministically, in a parallel one. A correct suite should not depend on order at all; a suite that does is exposed by distribution more reliably than by a shuffle flag, because distribution changes the order in a way that varies with worker count and machine load, while a shuffle at least prints a seed.

Where concurrency creates non-determinism

Three mechanisms produce differences that have nothing to do with test order.

The first is per-process randomness. Languages seed their pseudo-random generators per process, and hash-based containers are randomised per process to resist collision attacks, so a dictionary iteration order or a generated identifier can differ between two workers in the same run. A test that asserts on the string form of a set is then passing or failing depending on which worker it landed on.

The second is timing. Any assertion with a deadline, a timeout, or a retry budget measures elapsed wall time, and elapsed wall time includes time spent waiting for CPU that other workers are using. A budget calibrated on a quiet machine becomes a flaky failure on a busy one. Go’s -short convention, which lets tests skip the expensive parts when the caller asks for a quick run, is one way of avoiding the problem by not coupling the suite to a time budget; another is to express the budget in terms of work performed rather than seconds.

The third is resource collision. Two workers in the same container competing for the same port, the same temporary path, or the same fixed-capacity connection pool fail in ways that a single worker never sees. The port case is the most common and the most confusing, because the error names an address rather than a test: the test that lost the race is reported as broken while the one that won is unaffected.

The remedy for all three is the same shape: derive every source of variation from the test’s identity plus one run-level seed, rather than from the process. A seed computed as a hash of the run seed and the test identifier produces the same random sequence for a test regardless of which worker executes it, which makes a failure reproducible by re-running that single test with the run seed. That property is what makes a failure report actionable, and it is also what makes failure text stable enough for the grouping discussed in How Assertion Libraries Recover Operands From a Failed Comparison.

Crashes, timeouts, and out-of-order reports

A worker is a process, and a process can die. When it does, every test it had been assigned and had not yet reported is in an unknown state — not failed, not passed. A runner that reports them as failures produces a misleading picture; the accurate report names them as not run and attributes them to the worker’s exit status. That distinction is the same failure-versus-error split described in Fixture Scoping and the Lifetime of Shared Test State, applied to a whole worker rather than to one fixture.

Timeouts need one more decision under distribution: whether the deadline applies to a single test or to an entire worker’s queue. A per-test deadline catches a hang in one test and lets the rest of the queue continue; a per-worker deadline catches a deadlock that spans tests but discards the worker’s remaining work. The escalation sequence is the one from the process boundary: terminate, wait, then kill. The grace period matters more in parallel runs because a worker being killed while it holds a lock or a port leaves that resource in a state another worker may then trip over.

Reporting itself has to be reassembled. Results arrive as workers finish, so a runner that prints as it receives produces output whose order changes between runs, which makes diffing two logs useless. The fix follows from the plan line: the full list of tests is known after collection, so a report can be emitted in collection order regardless of arrival order, with durations added afterwards. That is one more reason the eager collection phase cannot simply be deferred to execution.

import heapq

def schedule(durations, workers):
    """Longest-processing-time-first: order jobs, then assign each to the
    worker that currently finishes earliest."""
    free = [(0, w) for w in range(workers)]
    heapq.heapify(free)
    plan = {w: [] for w in range(workers)}
    for name, cost in sorted(durations.items(), key=lambda kv: -kv[1]):
        ready, w = heapq.heappop(free)
        plan[w].append(name)
        heapq.heappush(free, (ready + cost, w))
    return plan

The scheduler above is deterministic given the durations: ties are broken by worker index because the heap orders its tuples, so the same input always yields the same plan. That property is worth keeping. A scheduler with a random tie-break, or one that reads arrival order from a queue, produces a different distribution on each run, and a distribution that cannot be reproduced makes an order-dependent failure impossible to chase. When a test does fail only under a particular arrangement, re-running with a fixed plan is the only way to tell whether the failure is a genuine data race in the code under test or an accidental dependency in the suite.