Bisecting a Deploy Range When the Fault Is Not Monotone

The symptom appeared somewhere in the last two hundred commits, or the last eleven deploys, or the last four configuration revisions. Binary search over that range is the standard answer and it is usually correct: if the property “the symptom is present” holds for the newest revision and does not hold for the oldest, then searching the range finds a boundary in $\lceil \log_2 n \rceil$ tests. Two hundred commits need eight tests. That arithmetic is so attractive that the assumption underneath it gets skipped, and the assumption is stronger than it looks.

What binary search actually requires

The predicate must be monotone over the ordering. Formally, if $P(v_i)$ is true for revision $i$, then $P(v_j)$ must be true for all $j > i$. Without monotonicity there is no boundary to find, and the search converges on a revision that happens to satisfy the predicate rather than on the revision that introduced the defect. The algorithm will not report an error; it will return a plausible commit hash, and the investigation continues from a false premise.

Monotonicity fails in several ordinary ways, and they are not exotic.

A fix and a regression can land in the same range, with the regression masked by the fix and unmasked later by an unrelated change. The predicate is false at the fix, false for a while, then true again. Bisection over that range will report either the fix or a point in the masked interval, neither of which is the cause.

Flaky behaviour makes the predicate probabilistic. A test that fails one time in twenty has a different true probability at each revision, and a single run at each midpoint is a sample from a Bernoulli distribution, not a decision. The expected number of tests to localise a boundary in the presence of noise grows faster than the logarithm, and the result carries a confidence interval that the tool does not report.

The property may depend on state outside the version history. A cache warmed by an earlier deploy, a certificate that expired between two revisions, a downstream service that changed independently: none of these are in the ordered range, so the range does not contain the cause at all, and bisection faithfully reports the revision at which the external change became visible.

There is a fourth failure that is subtler. The predicate may be evaluated on a different population than the one that motivated the search. If the report was “checkout fails for users in one region”, and the test checks a synthetic request from a single location, the predicate measures something adjacent to the symptom, and its transition point is wherever regional behaviour changed, which may be unrelated.

Establishing monotonicity before spending tests

The check costs a handful of probes and it is the difference between a search and a guess. Sample the range at its ends and at two or three interior points, chosen so that a non-monotone pattern has a chance to appear. If the predicate is true at the oldest revision, the range is wrong: the symptom predates it. If the predicate is false at the newest revision, the reproduction is not faithful. If interior samples flip back and forth, the search needs a different strategy before any bisection runs.

For probabilistic predicates, the sample at each point needs a decision rule rather than a single observation. Running the reproduction $k$ times and declaring “present” when the failure count exceeds a threshold converts a noisy predicate into a monotone one at the cost of a factor of $k$ in test count. The threshold should be set so that the false-positive and false-negative rates are both small relative to the number of tests the search will make, because a single misclassified midpoint sends the search into the wrong half and there is no recovery mechanism inside the algorithm.

The practical form is to keep the reproduction as tight as possible: one request, one input, one account, with all caches and warm-up effects either controlled or acknowledged as uncontrolled. Tightening the reproduction is itself a search over the input space, which is where the second half of this problem lives, and each tightening step is a discriminating test that splits the conditions under which the failure is possible.

Delta debugging as bisection over structure

Inputs have no natural order, so binary search over versions does not apply to them. Delta debugging supplies the missing structure by treating the input as a set of parts — characters, lines, tokens, request fields, configuration entries — and searching for a subset that still triggers the failure. The assumption replaces monotonicity with something weaker and more defensible: that a subset of a failing input is more likely to remain failing than a superset, so removing parts tends to preserve the symptom until the minimal cause is reached.

The ddmin algorithm partitions the current set of parts into $n$ subsets, tests each, and keeps a subset that still fails, doubling $n$ when no subset fails and halving when one does. Its worst-case test count is quadratic in the number of parts, which sounds bad until compared with the exponential space of subsets; in practice, when the failure has a small cause, the count behaves close to linear in the size of the input, because each successful reduction removes a constant fraction of the remaining parts.

A reduced reproduction is worth more than its size suggests. It removes the interpretive burden: a failing 3,000-line request body requires the reader to decide which of many fields matters, while a failing three-field body makes the causal chain visible. It also makes the failure reproducible across environments, since a minimal input has fewer dependencies on incidental state.

The failure mode of reduction is that it optimises for the symptom, not for the mechanism. A reducer can produce an input that fails for a different reason than the original. The guard is to keep a second, independent check of the mechanism — an assertion, an error message, a log line that must appear — and to reject reductions that change which one fires.

Searching with git bisect in a repository that keeps moving

The mechanical details matter more than they seem. git bisect accepts a bad revision and one or more good revisions; with multiple good revisions it can narrow the range further than a single pair, because the boundary must lie after the newest good revision. A test command that exits with status 0 for good and non-zero for bad lets the search run unattended, and git bisect skip marks revisions that cannot be tested, which the tool handles by widening the interval around them.

Two operational hazards dominate. First, the working tree must be in a state where the test is meaningful: generated files, submodules, and dependency lockfiles all change the built artefact, and a bisect that silently reuses a stale build is measuring the build cache rather than the source. Second, the test must not depend on network services whose behaviour has drifted since the older revisions were written; a test that passes today for reasons unrelated to the commit is a monotone predicate over the wrong variable.

Merge commits are the third hazard and the one that most often produces a nonsense answer. On a branchy history, the set of commits reachable from a merge is not a linear order, and a midpoint may be an ancestor of the good revision in one branch and a descendant in another. Marking merge commits as skipped avoids the worst cases at the cost of fewer tests; running the search on a first-parent linearised history trades precision for a well-defined order. Which is correct depends on whether the regression is expected to be on the mainline or inside a merged branch.

Stopping rules and the cost of the last few tests

The search terminates when the interval contains one revision. That is rarely the point at which the investigation should stop, because the identified commit is a pointer to a diff, not to a cause. The remaining work is reading the diff with the mechanism in mind, and the article on reading a diff for the mechanism it changed takes that up.

The economics of parallel bisection are also worth stating, because they are counter-intuitive. Testing $m$ revisions concurrently reduces wall-clock time by roughly a factor of $m$ only if the tests are independent and the build pipeline can produce $m$ artefacts. With a shared build cache and a fixed number of build machines, the concurrency is bounded by the machines, and the marginal benefit of the fourth concurrent test is small. The expected number of tests also rises, since the parallel search must sample more points to maintain the same interval reduction, so total compute increases while elapsed time decreases. That trade is usually worth making during an incident and usually not worth making during routine hygiene work, where the search can run overnight at minimum cost.

The last consideration is what to do when the identified revision is enormous. A single commit that rewrote a subsystem is a legitimate answer to “where did the behaviour change” and a useless answer to “what is the mechanism”. At that point the ordered search has ended and the investigation moves to the structural one: reduce the input, reduce the conditions, and construct the separating case by hand. The transition between the two modes is the moment the ordering stops carrying information, and recognising that the ordered search has been exhausted is the skill.