A Point Is Not a Prefix: The Life and Times of a Four-Month-Old Bug

#

In the previous post I chased a Kubernetes control plane that was burning a core in one-minute bursts. The proximate cause turned out to be an infinite retry loop, and the loop turned out to be caused by a store returning the wrong object for a lookup. This is the part of that story I had to dig for: which commit introduced the wrong object, why a regression test was written for exactly this and still didn’t catch it, and how a second test ended up asserting the bug as a feature.

TL;DR

#

• A point query — Range(key, range_end="") — must exact-match one key. The store executed it as the half-open span [key, key+1), which also contains every key that has key as a strict prefix.
• The original implementation was correct. It scanned every key and filtered with a predicate whose point case was key == k.
• A performance commit replaced that scan with BTreeMap::range(). In the translation the point case was collapsed onto the range-from case, so a point Get began returning everything at or after the key.
• The very next commit was a “fix”: compute the successor of the key and use [key, successor). That narrowed the over-return from “everything after” to “everything prefixed by” — wrong, but invisible unless a longer key shares the prefix.
• In the same performance commit, the delete path’s point case was translated correctly, using an exact get(). The bug and the correct idiom landed together, about ninety lines apart.
• A regression test did fire on the breakage and went green on the incomplete fix — because its fixtures were …/a, …/b, …/c: equal-length siblings where the successor of /b happens to be /c. The fixture could not express the bug.
• A later test asserted count == 2 for a point query of k alongside k2, with the justification “both keys exist”. It encoded the defect.
• Four months latent. The trigger was unrelated: a cluster registration created …/import-token-local-<uid>-token, making the non-existent name …/import-token-local a strict prefix of a live key. A client deleting the non-existent name caused the API server to read back the sibling, retry forever, and pin a core.

What a point query has to mean

#

etcd’s wire protocol encodes a single-key read as a RangeRequest with key set and range_end empty. Empty range_end is not “to the end” — that’s the separately encoded key = "\0" / range_end = "\0" form. An empty range_end means: exactly this key.

The store had a small resolver that classified the request into one of five shapes — all, point, from-key, prefix, explicit range — and a predicate that answered “does this key belong?”

match bound {
    All          => true,
    Point(k)     => key == k,              // the correct meaning, in one line
    From(k)      => key >= k,
    Prefix(p)    => key.starts_with(p),
    Range(s, e)  => key >= s && key < e,
}

That predicate is right. It was right from the first KV commit. The bug is not that anyone misunderstood what a point query means. The bug is what happened when that predicate stopped being a predicate.

Three functions, two definitions

#

The read path originally looked like this:

let bound = classify(&req.key, &req.range_end);

for (k, ks) in state.keys.iter() {
    if !is_alive(ks) { continue; }
    if !bound.matches(k) { continue; }               // correct, and O(n)
    ...
}

A full scan of every key, filtered by the predicate. Correct by construction, and linear in the size of the keyspace.

Then came a commit titled “optimize: BTreeMap::range() for bounded iteration”. Reasonable: replace the scan with an ordered range so that a narrow query touches only the keys it needs. The translation looked like this:

let (start, end) = match bound {
    All       => (None, None),
    Point(k)  => (Some(k.to_vec()), None),        // ← collapsed onto From
    From(k)   => (Some(k.to_vec()), None),        // ← identical
    Prefix(p) => (Some(p.to_vec()), None),
    Range(s, e) => (Some(s.to_vec()), Some(e.to_vec())),
};

Point and From became the same arm. The predicate had been restated as a pair of bounds, and the restatement lost information: key >= k is not key == k. A point Get now returned every key at or after the requested one.

This is the classic shape of a performance refactor bug. Nothing about the API changed. No test was deleted. The meaning of an operation quietly changed because its implementation strategy changed, and the strategy carried a weaker invariant.

Now the detail that makes this story worth writing. In the same commit, the delete path’s point case was translated correctly:

Point(k) => state
    .keys
    .get(k)                      // exact
    .filter(|ks| ks.is_alive())
    .map(|_| k.to_vec())
    .collect(),

So in one diff we have two translations of the same concept — one collapsing it into a prefix-ish range, one doing an exact lookup — a few dozen lines apart. The correct idiom was in the diff. It just wasn’t applied to the read path, because a read path is where you reach for range().

The fix that made the test green

#

The very next commit was called “fix: Point range must use bounded range, not range-from”. It correctly diagnosed that range(start..) was returning too much, and repaired it like this:

Point(k) => {
    // produce a range that matches exactly one key
    let mut end = k.to_vec();
    if let Some(last) = end.last_mut() {
        *last = last.wrapping_add(1);          // successor of k
        if *last == 0 {
            end.push(0);
        }
    }
    (Some(k.to_vec()), Some(end))              // [k, k+1)
}

The comment states the intention: “produce a range that matches exactly one key.” The commit message goes further — “producing range(key..successor) that matches exactly one key.”

Both are false, and the reason is one sentence long: [k, k+1) contains one key only if nothing else in the keyspace starts with k. If k is a strict prefix of any other key, that key falls inside the span.

Concretely, for k = "…/import-token-local" the successor is "…/import-token-locam", and "…/import-token-local-5563138b-…" sorts inside [k, k+1) because - (0x2d) is less than m (0x6d).

So the “fix” changed the failure mode from returns everything after the key to returns everything prefixed by the key. Strictly less wrong; still wrong; and now wrong in a way that most data never exposes.

The test that fired, and why it didn’t matter

#

There was a regression test for this. It predates the breakage, and it was written precisely to pin “a point lookup returns one key, a from-key lookup returns many”:

let prefix = format!("aaa_pfk/{}", rand::random::<u16>());

client.put(format!("{prefix}/a"), "1", None).await.unwrap();
client.put(format!("{prefix}/b"), "2", None).await.unwrap();
client.put(format!("{prefix}/c"), "3", None).await.unwrap();

let point = client.get(format!("{prefix}/b"), None).await.unwrap();
assert_eq!(point.count(), 1, "point lookup should return exactly 1 key");

On the performance commit this test must have failed. A point Get for …/b with Point collapsed onto From returns …/b and …/c — count 2, assertion fails. The test did its job.

Then the successor “fix” landed and the test went green again. And here is the trap:

• keys are …/a, …/b, …/c
• successor of …/b is …/c
• the span is […/b, …/c)
• …/c is the exclusive end and is therefore not included

The span contains exactly …/b. The assertion passes — not because point semantics are correct, but because the fixture’s siblings are all the same length, so incrementing the last byte lands exactly on the next key. The test data was shaped like the bug’s assumption.

To expose the bug the fixture needs a key that is a strict, different-length prefix of another: …/a and …/ab. Nothing in the suite did that. The regression test was genuine, it fired, it caught a real regression, and it was satisfied by a fix that preserved the class of bug.

That is the most useful failure mode in the whole story, because it’s the one that generalises: a passing test only tells you the fixtures agree with the implementation.

The test that asserted the bug

#

Four days later, a feature commit added historical (revision-pinned) reads. It needed the same bounds translation for its BTreeMap phase-1 scan, so the successor logic was lifted into a shared helper — duplicating the defect into a second code path, including the WAL-reconstruction path behind it.

The same commit added a test whose purpose was to check that a non-compacted revision still works after the compaction guard is set:

store.put(key: b"k",  value: b"v").await;
store.put(key: b"k2", value: b"v2").await;

COMPACT_REV.store(current_revision(), SeqCst);

// revision 1 is now compacted → must error
// a non-compacted revision should still work
let ok = store.range(RangeRequest {
    key: b"k".to_vec(),
    revision: create_rev,
}).await.unwrap();

assert_eq!(ok.count, 2, "both keys exist at non-compacted rev");

A point query for k returning two results. The assertion message tells you exactly how it got there: “both keys exist at non-compacted rev”. Both keys do exist — but that is a fact about the fixture, not about the query. The number two was observed, the sentence was written afterwards to make it sound intentional, and from that moment the repository had a test that would fail on any attempt to fix the bug.

I want to be precise about the nature of this mistake, because it’s not laziness. It’s a characterization test wearing a specification test’s clothes. You run the thing, you see an output, you write an assertion that matches the output, and you give it a name that makes it sound like a requirement. The tell is grammatical: if the assertion message has to justify why the number is what it is, rather than state what the code must do, the test is describing the implementation.

Why it survived four months

#

The defect needs three things at once:

1. a point lookup or delete for a key that does not exist
2. a live key that has it as a strict prefix
3. a client that actually asks for (1)

None of those is exotic; all three together are rare, and for months nothing in the test cluster produced (2). Then, one night, an unrelated cluster registration created a service-account token secret named …/import-token-local-<uuid>-token. That single object made the absent name …/import-token-local a strict prefix of a live key.

Two hours and thirty-nine minutes later the first post-timeout activity error appeared in the API server log. That message means a request handler was still doing work after its deadline had passed — which is exactly what the delete retry loop does.

Here’s why it becomes a fire instead of a flicker. The API server’s conditional delete is a compare-and-delete loop:

txnResp, err := s.client.Kubernetes.OptimisticDelete(ctx, key, origState.rev, ...)
if !txnResp.Succeeded {
    origState, err = s.getState(ctx, txnResp.KV, key, ...)
    continue
}

The txn’s failure branch returns whatever it read, and the loop trusts it. With the wrong object returned:

1. the failure branch hands back the sibling’s KV
2. getState accepts it and adopts the sibling’s mod_revision
3. the next compare does an exact lookup of the requested key, finds nothing, and sees revision 0
4. 0 != sibling_revision → fail → refetch → same sibling → continue

There is no iteration bound. The loop runs until the request deadline, and each pass re-runs the entire delete-admission webhook chain — two webhook calls, because the mutating and validating configurations both match. Roughly a few hundred datastore deletes per second, about twice that in webhook calls, and no completed requests, because a request that never finishes is never counted. The request eventually returns 504, the client retries, and a minute later it starts again.

Four days and a few thousand post-timeout errors later it was obvious enough to investigate. The full ledger: introduced mid-June, latent for four months, triggered by a string, and eating a core for four days.

The fix

#

Two places, both made exact — and, in this case, faster.

The hot path. Instead of materialising [key, key+1) bounds and driving an iterator over them, do the lookup a point query deserves:

if let Point(key) = bound {
    let mut kvs = Vec::with_capacity(1);
    if let Some(ks) = state.keys.get(key) {      // exact, O(log n)
        if is_alive(ks) && satisfies_filters(ks, &req) {
            kvs.push(if req.keys_only { key_only(key) } else { ks.kv_bytes.clone() });
        }
    }
    return response(state, kvs, &req);           // count_only / limit / header
}

That’s a single tree lookup instead of bounds construction plus a boxed iterator plus a seek — no allocation for the bounds, no dynamic dispatch. The correct version is the cheap version. It also removes an unreachable!() hazard by construction: the general bounds path can no longer be handed a point.

The shared bounds helper used by the historical and WAL-reconstruction paths, where a BTreeMap range is still the right tool:

Point(k) => {
    // [k, k\0) contains only k: any longer key beginning with k sorts at or after k\0
    let mut end = k.to_vec();
    end.push(0);
    (Some(k.to_vec()), Some(end))
}

One extra byte instead of incrementing the last. k\0 is the smallest key that sorts strictly after k — smaller than k followed by any real suffix, because 0x00 is the minimum byte. So the span is exactly one key wide by definition, not by luck. The 0xFF carry handling that the successor version needed disappears: no wrap, no push-if-zero, no edge case.

What I’d take from it

#

• Translating a predicate into bounds is a semantics change, not a refactor. key == k and key >= k are one character apart in a diff and worlds apart in behaviour. When a refactor changes representation, the property “these are equivalent” needs a test of its own.
• Same commit, two translations, one correct. The exact-lookup version was in the diff the whole time. A review habit worth having: when a change restates one concept in several places, diff the restatements against each other.
• A fix that turns a test green may only narrow the bug. The successor bound was a real improvement — over-return went from unbounded to prefix-scoped — and that’s exactly why it felt finished.
• Fixtures decide what a test can see. a, b, c cannot express a strict-prefix collision. If an operation has a “same thing, different length” case, the fixture list needs one.
• Assert on the thing, not the count of things. assert_eq!(count, 2) would have been caught by a reviewer; assert_eq!(kvs[1].key, b"k2") would have been caught by the author. Naming what you expect is what makes the expectation reviewable.
• A justification in the assertion message is a red flag. “both keys exist at non-compacted rev” is an argument, and arguments in assertions are usually rationalisations of observed output.
• Latent bugs wait for data. Four months of green CI is not evidence of absence — it’s evidence that the inputs never had the right shape. This one needed a UUID in a name to turn on.
• A single source of truth for range semantics would have made all of this impossible. The codebase had two definitions of “point” from the very first commit: a correct predicate and, later, a bounds translation. They disagreed for months without either one being obviously wrong in isolation.

Coda

#

The tempting moral is “don’t optimise”. That’s wrong — the optimisation was good, and the fixed version is faster than the buggy one because an exact get beats a range scan. The actual lesson is narrower and more useful: when you swap a predicate for an index range, you have replaced a definition with an encoding of it. Encodings are lossy in exactly the cases nobody tests, and they fail silently until the data provides the case they lost.

The second moral is about the archaeology itself. Every step of this was in the history, in five commits across ten days, and each one was individually reasonable: a scan that was too slow, a translation that read naturally, a fix that made a red test green, a new feature that copied the bounds helper, a module split that moved the code. No single commit looks like a mistake. The bug is the composition — which is why “when was this line written” is a much less useful question than “what did this line mean when it was written, and what does it mean now”.