Merge Queues and What Speculative Testing Actually Proves

A change that passed its tests on its own branch has been tested against a base that no longer exists. Between the moment the branch was cut and the moment it merges, other changes landed, and the tree that results from combining them is a new object with new behaviour. The tests that ran on the branch say nothing about that tree. A merge queue exists to close this gap, and the way it closes it determines what a passing result actually certifies.

The stale base problem

Consider two changes, each adding a handler for the same event type. Both branches are cut from a common base that has no handler. Each adds its own, each passes its own tests, each is reviewed and approved. Merged together, the event now has two handlers, and depending on the dispatch mechanism one shadows the other or both run in an order nobody specified. There is no textual conflict; the lines are in different regions of different files, and the three-way merge combines them without complaint.

This is a semantic conflict, and it is the failure mode that branch-based testing structurally cannot catch. The branch tested a tree containing one handler. The merge produces a tree containing two. This is precisely the gap left by approvals that name a diff rather than a tree. The test suite, if it asserts the behaviour of the event, would have caught the problem — but it never ran against the combined tree.

The obvious fix is to test the merge result. Doing that by hand for every pair of concurrent changes is quadratic in the number of open changes, so the practical fix is to serialise: keep a queue of changes waiting to merge, and for each one, build and test the candidate tree formed by merging it into the current tip.

Serialising the candidate tree

The queue’s core operation is simple to state. Let $T$ be the current tip of the mainline. For the head candidate $C$, construct $M = \mathrm{merge}(T, C)$, run the verification suite against $M$, and if it passes, fast-forward $T$ to $M$ and admit the next candidate.

Two properties follow immediately. First, the test that runs is against the tree that will exist after merging, which is the tree that matters. Second, the queue is a serialisation point: only one candidate is being verified at a time, so the throughput of the mainline is bounded by the duration of the verification suite divided by the batch size.

That bound is the design constraint the whole mechanism is organised around. If verification takes twenty minutes, a strictly serial queue admits at most three changes per hour regardless of how many reviewers approved them. At any real merge rate the queue becomes the bottleneck, and everything downstream of it — developer wait time, the temptation to bypass it, the pressure to shorten the suite — follows from that single number.

Speculation: testing a projection of the future

The standard mitigation is to speculate. While candidate one is being verified against $T$, candidate two can be verified against the predicted tip $\mathrm{merge}(T, C_1)$, and candidate three against $\mathrm{merge}(\mathrm{merge}(T, C_1), C_2)$. Each is testing a tree that will exist only if all its predecessors succeed, which is what makes the work speculative.

The payoff is that verification of $n$ candidates takes roughly the time of the longest chain rather than the sum, provided the suite runs in parallel across candidates. The cost is wasted work: if candidate one fails, every tree built on top of it is invalid and the tests for candidates two and three must be discarded and re-run against the corrected tip.

The failure case is worth examining because it is common. Candidate one fails a test. The author is notified and pushes a fix, which becomes a new candidate at the back of the queue, since it must be verified against whatever the tip is by then. Candidates two and three, which had been speculatively verified on top of the failed version of candidate one, must be rebuilt on the new tip, and their speculative results are discarded even though their own content did not change. A single failure near the front invalidates the work of everything behind it, so the effective throughput depends on the failure rate as much as on the suite duration.

This is why queues are usually combined with a rule that a failing candidate is removed rather than retried in place, and why flaky tests are disproportionately expensive in a queued system: a flake is indistinguishable from a failure, invalidates the speculation behind it, and the re-run consumes the same wall-clock time as a real failure. A test that fails one percent of the time costs, in a queue of depth $d$, on the order of one percent of $d$ candidate verifications.

Batching and what a green result means

Most queues do not verify one candidate at a time. They group candidates into a batch, merge the batch onto the tip, and verify the batch tree. This raises throughput by amortising the fixed cost of building and running the suite, and it changes the semantics of the result in a way that reviewers should understand.

A green batch certifies that the batch tree passes. It does not certify that any individual candidate passes in isolation, and it does not certify that any pair within the batch is compatible in the sense the queue was built to check. If candidates two and three interact badly, the batch fails, and the queue’s response is to bisect: split the batch, re-verify the halves, and identify which candidate is responsible. Bisection costs additional verification runs, so batching trades throughput against diagnostic cost, and the trade is favourable only while interactions are rare.

A more subtle consequence is that a candidate’s result depends on its neighbours. The same change can pass in one batch and fail in another, not because of flakiness in the usual sense but because the batch composition differs. Anyone reading a queue’s history and concluding that a change is “verified” is reading a property of a specific batch, not of the change.

The batch’s composition is also an attack surface on review quality. If the batch is large enough, the probability that it contains at least one flaky test approaches one, and the queue’s throughput collapses to the bisection cost. The usual response is to cap batch size, which restores the earlier bound: throughput is suite duration divided by batch size, and batch size is capped by the failure rate.

The queue cannot see intent

Everything above concerns tree-level verification. None of it addresses the class of conflict that tests cannot detect, because the tests do not know what the changes meant.

Two changes, each correct, can combine into a tree that passes every test and is still wrong. A change that adds a cache and a change that adds a write path may combine into a system where the write path invalidates nothing, because neither change was written with the other in mind and no test asserts cache coherence across a write that neither change introduced. The queue verifies the tree it is given; it has no model of the invariants the tree is supposed to satisfy beyond what the suite encodes.

The practical implication is that queue verification raises the floor and does not raise the ceiling. It catches the conflicts that manifest as test failures, which is a large and otherwise invisible class. It cannot catch the conflicts that manifest as an untested interaction, and the only mechanism for those is a reviewer who knows both changes — which is an argument for routing changes that touch the same subsystem to the same reviewer, and for keeping concurrent changes to a subsystem few.

Ordering, priority, and fairness

A queue imposes an order on changes that review did not. The order is usually first-in-first-out, with an option to prioritise. Prioritisation is necessary — a change that fixes a broken mainline must not wait behind a feature — and it is also where the queue’s cost becomes visible to people rather than to machines.

Two effects are worth naming. Starvation: a change that keeps being deprioritised because higher priority work arrives never reaches the front, and the author’s branch drifts further from the tip, which makes its eventual restack more expensive. And head-of-line blocking: a candidate that is slow to verify holds the queue, so a single change with an unusually long suite delays every change behind it. Both are properties of any serialisation point, and both are usually addressed by policy rather than by the queue’s design.

The interaction with stacked changes is a further constraint. A stack must be landed in order, and a queue that admits candidates independently will reorder them. A queue that understands dependencies must verify the whole stack as a unit or hold the upper changes until the lower ones land, and either choice reduces the parallelism that speculation was meant to provide.

What the queue replaces

Before queues, the common mechanism was a lock: one person at a time merges, tests the tip afterwards, and reverts on failure. That mechanism verifies the tip after the merge, so a broken tree is visible to everyone who pulls during the interval, and the revert is itself a change requiring review in an emergency. The queue moves verification before the merge, which converts a public failure into a private retry.

The cost is latency, and the latency is visible to the author as a wait with no work to do. That wait is the mechanism’s honest price: the tree-level verification it buys cannot be obtained without serialising something, and the only question is what gets serialised and for how long.

# shape of a queue policy, not a specific tool's schema
batch:
  max_size: 5            # bounded by failure rate, not by appetite
  bisect_on_failure: true
  requeue_policy: back   # a failed candidate returns to the tail
verification:
  suite: required-checks
  timeout_minutes: 45
priority:
  - label: fix-broken-mainline
  - default

The numbers in such a policy are all derived from two measured quantities: how long the suite takes, and how often a candidate fails. Neither is a constant, and a queue tuned once and left alone drifts out of tune as the suite grows and the failure rate changes.