skip to content

A stage keeps only back-off delays above a ceiling the endless producer never reaches, and taking one element hangs - why?

level: seniorimportance: should knowfreq 36%

answer

  1. bounded results, unbounded examination
  2. a discarding stage amplifies demand
  3. the source must be able to match
  4. values converged, sequence still endless
  5. bound the search, not just the result

basics

~20 s

A bounded demand terminates only if the source can satisfy it. The discarding stage keeps pulling to find a match, the clamped producer yields values below the ceiling forever, and the request for one element is never answered.

solid answer

~50 s

Asking for one element bounds **how many results you want**, not **how many elements get examined**. Every stage that discards elements amplifies demand: one unit of downstream demand becomes as many upstream pulls as it takes to find a match. So a bounded pull terminates only when two things hold - each element is produced in finite time, *and* the filtered source still yields matches. Here the producer doubles its delay and then clamps at a ceiling, so it emits that ceiling value forever; a predicate looking for something strictly larger can never be satisfied. Neither half is wrong on its own, which is what makes this hard to see in review: the defect lives in the composition, and the repair is to bound the **search** - a prefix on the source, an examined-element ceiling, or a deadline - so that "no match" becomes a result rather than a hang.

code

pseudocode · 13 lines
pseudocode
function clamped_backoff(start, factor, ceiling):
    return sequence(start, function(d) return min(d * factor, ceiling))

delays = clamped_backoff(100, 2, 30000)
// 100, 200, 400, ... 25600, 30000, 30000, 30000, ... forever

slow = keep_if(delays, function(d) return d > 60000)   // matches nothing

take(slow, 1)
// hangs: one element demanded, pulls upstream without end

take(keep_if(take(delays, 20), function(d) return d > 60000), 1)
// returns nothing: the source is bounded, so the search can end

go deeper

for a junior

Remember that asking a filtered endless source for one match can run forever: your request bounds how many results you want, not how many elements get examined to find them.

for a middle

Explain the amplification - every element the predicate rejects is another pull upstream - and state the condition a bounded pull needs: the source must still be able to satisfy it.

for a senior

Diagnose the composed failure: two correct parts, a hang with no error, and a fix that bounds how much gets examined rather than how much gets returned.

for a principal

Set the rule for the codebase: where an unbounded source may be searched at all, and what ceiling - examined elements or a deadline - every such search must carry before it ships.

## Demand is not the same as pulls It is natural to read "take one element" as "do a little work". It means nothing of the kind. A bounded demand constrains the number of elements **delivered to the consumer**, and says nothing about the number of elements **pulled from the producer**. Any stage that can discard an element sits between the two numbers and drives them apart: - A stage that transforms each element passes demand through one-for-one: one wanted, one pulled. - A stage that **discards** elements does not. One wanted becomes *pull until something matches* - which is unbounded if nothing ever does. - A stage that must reach the end before answering ignores downstream demand entirely. So the request for a single delay above the ceiling is a perfectly bounded request sitting on top of an unbounded search. ## Why the source cannot satisfy it The producer is a clamped growth rule: double the previous delay, but never exceed a ceiling. From a seed of 100 with a ceiling of 30000, it emits 100, 200, 400, 800, 1600, 3200, 6400, 12800, 25600, then 30000 - and then 30000 again, forever. This is a completely reasonable back-off policy and a completely legitimate endless producer: every element is produced in finite time, and there is always another one. The predicate asks for a delay strictly above 60000. No element of that sequence ever satisfies it. The search therefore has no answer, and nothing in the pipeline is in a position to say so, because **"this source will never match" is not a fact any stage can observe**. A stage can only observe that the source answered another pull. ## The condition a bounded pull actually needs 1. **Every element must be produced in finite time.** A step rule that hangs makes even the first demand hang. 2. **The filtered source must still yield matches.** If a discarding stage lies between the consumer and the producer, the producer must satisfy the predicate at least as many times as the consumer asks. 3. **No stage downstream of the source may require the end.** A whole-sequence step ignores the bound entirely. The first and third are usually checked. The second is the one this scenario breaks, and it is the one nobody writes down. ## Pulls per delivered element | pipeline shape | pulls per delivered element | terminates? | |---|---|---| | endless source, transform, take one | 1 | yes | | endless source, discard some, take one | 1 to k, where k is the gap between matches | yes, if matches keep coming | | endless source, discard all, take one | unbounded | no | | finite prefix, discard all, take one | at most the prefix length | yes, returns nothing | ## Two correct parts, one hang This is the shape that survives code review. The producer is idiomatic and tested. The predicate is a one-liner that is obviously right. Each was written by someone who was thinking clearly. What nobody owned was the **join**: a search over a source whose range provably never enters the region being searched. When the ceiling was later lowered from 90000 to 30000 as a latency fix, the predicate that used to match became unsatisfiable, and a change with no relationship to this code turned a working pipeline into a hang. ## How teams stop it happening - **Bound the source before the search.** Hand the discarding stage a finite prefix, so an unsatisfied search ends and returns nothing. "No match" then becomes a value the caller can handle. - **Give the search its own ceiling.** A maximum number of elements examined, or a deadline, so the search can report exhaustion instead of continuing. - **Treat "no match" as a real outcome in the design.** If the calling code has no branch for an empty result, that absence is a hint that somebody assumed a match was guaranteed - which is precisely the assumption that failed. - **Keep the source's range and the predicate's range in one reviewable place.** The bug is only visible when both are on screen together. ## What it looks like in production A thread pinned at full load with a flat memory profile and no error. A stack that points into the discarding stage or into the producer's step rule, which is exactly where nothing is wrong. Elapsed time grows without bound while throughput for the affected path goes to zero, and a restart clears it until the same input comes back. The diagnostic question to ask first is not "which stage is slow" but "can this source ever produce what this stage is looking for".

  • Is the producer or the discarding stage at fault here?
    Neither on its own. The producer is a legitimate endless source in which every element arrives in finite time, and the predicate is a legitimate test. The defect is the composition: a search with no possible match, over a source that never ends, has no answer to give. Whoever wires the two together owns bounding the search.
  • What bound makes a search over an endless source safe?
    One on the pulls, not only on the results. Either bound the source to a prefix before the discarding stage sees it, so an unsatisfied search ends with nothing, or give the search its own ceiling - a maximum number of elements examined, or a deadline - so that "no match found" is a result it can return rather than a state it stays in.
  • Why does this defect often appear long after the code was written?
    Because it is created by a change to either side. Lowering the producer's ceiling, or raising the predicate's threshold, can move a previously satisfiable search out of reach without touching the pipeline at all. Neither change looks risky in isolation, which is why the source's range and the predicate's range belong in one reviewable place.

saying these in an interview costs you the question

  • Says asking for one element can only ever pull a few.
  • Blames the endless producer, which is correct on its own.
  • Assumes a discarding stage passes demand upstream one for one.
  • Expects the pipeline to report that nothing matched.
  • Thinks a clamped producer is finite because its values stop growing.