Binary Search Over the System
Frontend or backend? Backend or database? Before commit X or after? Every debugging question that splits the candidate space in half is worth asking before any question that removes one candidate — and git bisect is the same move applied to history.
The situation, the reflex, and why it stalls
Every lesson starts where being stuck starts: someone has a problem, and the first move that comes to mind feels like progress.
The bug could be in any of five layers or any of forty commits. Which question do you ask first so that each answer removes the most candidates?
Payment failed, and it could be the UI, the network, the backend, the provider or the database. It also started some time in the last week, during which there were dozens of deploys. Checking each layer and each commit one by one would take the rest of the week.
Check the most likely one first. Usually that means the one you touched most recently or the one that was the cause last time. It is a reasonable prior, and it produces an answer quickly when the prior is right.
When the prior is wrong, the search is linear. Each candidate checked removes one candidate; five layers and forty commits is a long afternoon of "not that one".
- When the prior is wrong, the search is linear. Each candidate checked removes one candidate; five layers and forty commits is a long afternoon of "not that one".
- Suspicion is not evidence. "Probably the provider" leads to an hour on the provider dashboard for a bug the network tab would have placed in the backend in a minute.
- Checking a candidate that does not split the space produces no information even when the check is thorough. Confirming that the frontend renders "Payment failed" for a non-OK response confirms the frontend does what it does; it says nothing about which of the other four layers failed.
- The history question — when did this start? — is asked from memory and answered wrong, so the diff being read is not the diff that introduced the bug.
The move
Precisely enough to apply it to a problem you have never seen — not a slogan.
- Arrange the candidates along a line — the request path through the layers, or the commit history — and ask a question whose answer tells you which half the cause is in. Then repeat inside that half. Each answer removes half the candidates; the number of questions grows with the logarithm of the candidates rather than with the candidates.
- For the request path, the question is "is the data correct at this boundary?" asked at the middle boundary. If the request leaving the backend to the provider is correct, the problem is downstream; if not, upstream. The boundaries are where the system can be observed, which is why observation points at boundaries matter (Where Does My System End?).
- For history, the question is "does the bug exist at this commit?" asked at the midpoint between the last known-good and the first known-bad.
git bisectautomates the bookkeeping; the move is choosing the midpoint and having a reliable test for "bug present". - Pick the split that is cheap to observe and genuinely halves the candidates. A boundary with no logging is not a usable midpoint; a commit that does not build cannot be tested. The best next probe is the one that leaves the fewest candidates whichever way it answers.
Which split to make
The store's request path has several observable boundaries and two candidate lines — space and time. The decision is which to search first and where its middle is. The criteria are how cheap the observation is and how evenly it divides what remains.
Where do I make the first observation so that its answer removes the most candidates?
when The backend logs inbound requests and outbound provider calls with a request id; the bug is present now.
cost Needs the log to exist and to be searchable by request id; tells you the half, not the line.
when You are reproducing in a browser and want the status code and timing in seconds.
cost Splits only browser from everything else — a lopsided division when the backend is the larger half.
when The suspicion is downstream and the dashboard is quick to check.
cost Absence of an attempt is informative; presence of one tells you little about our handling of the response.
when It worked at a known commit, a reliable test exists, and the build is fast.
cost A build and a test per step; useless if "known-good" was remembered rather than verified.
The search as a loop
The same loop runs over the path and over history. The step that usually goes wrong is the first one — establishing the ends — because a "known good" that was not actually tested makes every later split meaningless.
- 1Establish the ends
A point where the data is definitely correct (or the commit where the test definitely passes) and one where it is definitely wrong.
fails by Remembering rather than testing the good end.
- 2Find the observable middle
The boundary or commit nearest the midpoint at which "correct or not" can actually be checked.
fails by Picking the exact middle when nothing can be seen there.
- 3Observe
Read the data at the boundary or run the test at the commit.
fails by An unreliable test or a log that does not identify the request.
- 4Keep one half
Move the good or bad end to the observed point.
fails by Keeping the suspicious half instead of the half the evidence named.
- 5Stop when one candidate remains
Switch to reading, or to reducing inside the remaining component.
fails by Continuing to split inside a single function where reading is faster.
The same move over history
Bisecting commits is the search with the bookkeeping automated. The only parts that require judgment are the two ends and the test; the reproduction from the previous lessons supplies the test, and the ends must be run, not recalled.
1# both ends verified by running the test, not by memory2git bisect start3git bisect bad HEAD4git bisect good v1.4.0 # the double-click test passes here — checked5 6# the test exits non-zero when the bug is present7git bisect run ./scripts/double-click-test.sh8 9# ... a handful of checkouts later:10# <sha> is the first bad commit11# refactor: cart items carried as a map instead of a list12git bisect resetThe script is the reproduction recipe made executable. If it is flaky the bisect will still terminate, confidently, on the wrong commit — reliability of the test is the precondition, not a nicety.
How to do it
Most important first.
- Write the candidates as an ordered list: for the path, browser → network → backend handler → provider call → database write; for time, the commits between known-good and known-bad.
- Find the observable boundary nearest the middle. For the store that is usually the backend's request log: it shows what arrived from the browser and what was sent to the provider.
- Observe there and decide the half. A correct request arriving and a 500 leaving places the bug inside the backend or its downstream; a malformed request arriving places it in the browser or the network.
- Repeat within the half until one component remains, then switch to The Minimal Reproduction inside it.
- For history, establish a known-good commit by actually testing it, not by remembering; write the "bug present" check as a script; run
git bisect runwith it.
Worked on a concrete problem
The move has to produce something. This is what it produced.
- The path. Midpoint: the backend request log. It shows the pay request arriving with a well-formed cart and the response leaving as a 500 — the browser and the network are out. Next midpoint inside the backend: the outbound call to the provider. The log shows no outbound call — the provider and the database write after it are out. What remains is the handler code before the provider call, and the stack trace lands there. Three observations removed five candidates.
- History. Known-bad: this morning. Known-good: verified by checking out last week's release tag and running the double-click test, which passes. Forty commits between. Bisect asks for the midpoint, the test fails; the midpoint of the first half, passes; two more rounds and the introducing commit is the cart refactor. Six checkouts instead of forty, and the diff to read is one commit long ("what changed?" from Do Not Randomly Change Things is the question; the bisect is how it is answered).
- A split that was worthless: "does the frontend show the message?" Every candidate cause produces the message, so the answer removes nothing. The lab makes this visible — some probes leave the whole candidate set intact, and the reader learns to tell before spending the time.
How you know it worked
What now exists that did not before, and what question you can now ask.
- Each observation you make removes roughly half of the remaining candidates, and you can say which half before you make it.
- You know the observable boundaries of the system and which of them are silent.
- The introducing commit is known from a test, not from memory, and the diff to read is short.
- You have stopped checking candidates because they are suspicious and started checking boundaries because they are in the middle.
The questions you can now ask
The field this whole domain exists for. After this lesson, these are the questions to put to an unfamiliar problem.
- ?Along which line — the request path, or time — are the candidates arranged, and where is the middle?
- ?What is the nearest observable boundary to the middle, and what does correct data look like there?
- ?Which half does that observation place the cause in?
- ?What is the last commit at which this test passes, verified rather than remembered?
- ?Does this question actually split the candidates, or does every cause answer it the same way?
What can go wrong
- Binary searching when the evidence already points at one place. A stack trace naming the line makes the search unnecessary; use the log first, the split second.
- A midpoint that is not observable. Choosing the boundary between handler and repository when nothing logs there means an experiment that cannot be run; pick the nearest boundary that can be seen, or add the log line first.
- Bisecting with a flaky test. If "bug present" is wrong one time in ten, the bisect converges on a random commit with confidence. The reproduction has to be reliable before the bisect starts (Reproduce It First).
- Treating the halves as equally likely when they are not. If strong evidence says the provider is fine, the split should be made inside the other half; binary search over an ordered space is a default, not a refusal to use priors.
- Binary search assumes a single cause on a line. Two interacting bugs, or a cause that lives in the interaction of two layers, produce contradictory halves and the search stalls; the response is to notice the contradiction and question the model.
- It ignores priors. When one candidate is far more likely, checking it directly is faster in expectation; the split wins when you honestly do not know, which is more often than it feels.
- Bisecting history costs a build and a test per step, and for a system with a slow build that is minutes per step; automating the check is worth it only when there are many commits.
- "So always start in the middle." Start at the nearest observable boundary to the middle, and only when you have no better evidence. A log line naming the layer beats any split.
- "git bisect finds the bug." It finds the commit that introduced the symptom, which is where the bug became visible — sometimes a correct change that exposed an older defect. The commit is where reading starts, not where it ends.
- "Binary search is for big systems." A three-layer store still benefits: one observation at the backend removes two layers.
Where this applies
Problem-solving advice is stated as universal far more often than it is. These labels say what each method is specific to — and where CONTESTED appears, the note gives the strongest form of the opposing view.
- GENERALAny ordered candidate space — layers along a request, commits in history, stages in a pipeline, elements of a large input — can be searched this way; the observation at the midpoint changes and the arithmetic does not.
- SCALE-SPECIFICWith three layers and a handful of commits, the difference between linear and binary is a few minutes and either works; with a dozen services and hundreds of commits since the last release, the split is the difference between an afternoon and a week.
- ILLUSTRATIVEThe forty commits, the six checkouts and the cart refactor are invented to show the arithmetic of the split; no real repository is described.
Where the depth lives
This domain asks the question and hands the answer off by name.
- — A version-control domain does not exist yet;
git bisect,git log -Sand reading a diff as evidence belong there and are used here only as the history form of the split.