I have a set of background jobs that walk backwards through third-party APIs, pulling my own history out of them: scrobbles, check-ins, that sort of thing. Each one walks until it reaches the beginning, records that it has finished, and stops.
Two of them had stopped early. Both were recorded as complete. Neither had errored, retried, or logged anything unusual, and both had been sitting in that state long enough that I had stopped thinking about them.
The mechanism was the same in each case. The walk asks for the next page of history. It gets an empty response. It concludes there's no more history, marks itself done, and never asks again.
Reading an empty page as the end
An empty response is weak evidence. It usually means you have reached the end. It can also mean a transient upstream failure, a rate limit expressed as an empty body rather than an error, a gap in the data, or a query built wrongly enough to return nothing without complaining.
Treating one weak signal as proof would be a small bug on its own. What makes it permanent is the second half: the completed flag couldn't be reopened. Once a walk had written down that it was finished, nothing in the system was capable of disagreeing. The evidence was weak, the conclusion was absolute, and the conclusion outlived every chance to check it.
That combination turned a transient blip into silent, permanent data loss: the blip was harmless until it was recorded as the end of the history.
The fix has two halves, and I only had one at first
The first half is hysteresis: require three consecutive empty runs before accepting that history is exhausted. Any single empty response is now just an empty response. It takes a sustained pattern to mean anything.
The second half took me longer to see. Recording "finished" as a single boolean throws away the thing you need to audit it. So the walks now record the depth they actually reached, separately from the floor they were aiming at. Those are two different facts, and collapsing them into one flag is what made the original failure invisible. With both recorded, "I stopped" and "I stopped where I was supposed to" are distinguishable claims, and I can look at the gap between them without re-running anything.
I didn't apply the same treatment everywhere. One of the sources states its own history boundary explicitly. It tells you where the beginning is. That walk needs no strike logic, because it isn't inferring completion from absence, it's reading it from a stated fact. Adding hysteresis there would be cargo-culting: the same code, guarding against a failure mode that source doesn't have.
The rule isn't "always require three empties". It is "if you are inferring completion from absence of data, you need corroboration; if you are reading it from a declaration, you do not".
The bug underneath the bug
While fixing this I found why one of the walks had been returning empty pages in the first place, and it wasn't upstream at all.
The API in question reads a from parameter of zero as unset. My code was passing zero to mean "from the beginning of time", which is a reasonable thing to think zero means. The API took it as "no lower bound specified" and switched to an unbounded, newest-first fetch, which returned pages that had nothing to do with the window being asked for. Fixed by passing one instead of zero, and discarding anything outside the requested window.
So the sequence was: a parameter reinterpreted without warning, producing wrong pages, which looked like empty ones for the window in question, which got promoted to a permanent completion flag. Three layers, none of which raised anything.
The fix that had no effect
Persisted walk state carries a version. Bump the version, the stored state is discarded and the walk starts fresh. I changed how one walk decides it has finished, didn't bump the version because the change didn't feel like a data-format change, and shipped it. The new logic then ran against state written by the old logic, which had already recorded completion under the old, wrong rule. The fix was live and had no effect, because the thing it fixed had already been decided.
The rule I've written down since: any change to how a walk decides it's finished must bump the state version, even when the diff doesn't look like it needs to. The version isn't protecting the shape of the state. It's protecting the meaning of the conclusions stored in it, and a conclusion reached by different logic is a different conclusion regardless of whether it serialises the same.
What I still don't have is a way to notice this class of thing without going and looking. A job that stops early and reports success is indistinguishable, from the outside, from a job that finished. The only reason I caught these is that I happened to look at the data and think it seemed thin. Making "I finished" and "I gave up" look different, in a system where both write the same flag, is the problem I'd most like solved.