The Differential: Fourteen Ways a Key-Value Store Lied to Kubernetes

#

Over the last few days I replaced “does the store work?” with “does the store agree with etcd?”, operation by operation. The answer was no in fourteen places. One of them was a single request that aborted the control plane’s datastore. Several were invisible to every test the project had. Two were actively defended by tests that asserted the wrong behaviour. This is the method and the ledger.

TL;DR

#

• The store — an etcd-compatible key-value engine in Rust, sitting under a single-node k3s control plane — passed its own suite, ran the cluster, and was wrong in fourteen documented ways. All fourteen came from implementing a protocol from memory.
• The most dangerous one: LeaseGrant with a negative TTL panicked on an Instant + Duration overflow. In a debug build tokio caught it and only the request died. In the release build the profile sets panic = "abort", so the datastore process aborted — a one-request kill of the thing the control plane runs on.
• The method that found this was not reading the spec. It was a differential harness: the same sequence of operations issued to real etcd and to the store, one canonical CHECK|name|value line per check, diffed per name.
• The harness is committed, runs on demand (./scripts/conformance.sh) and in CI, and is gated by a two-sided ledger: a deviation not in the list fails the build, and a listed deviation that no longer reproduces also fails it. The list cannot rot in either direction.
• The findings ranged from the fatal (negative TTL, ignore_value on a missing key resurrecting an object with empty bytes — a data-corruption path for Kubernetes) to the cosmetic (lease-not-found message wording).
• Fixes went out in two batches, each merged, built, smoke-tested, rolled out to the running datastore and observed for fifteen minutes before the next one: zero restarts, zero errors, key count constant, control plane healthy.
• The ledger is now two entries: an accepted difference (auth is unimplemented) and one measured limitation (multi-op transaction rollback). Everything else matches.
• The meta-lesson is the one that generalises: a passing test only tells you the fixtures agree with the implementation. Two of the store’s tests were asserting bugs as correct behaviour.

Part 1: the night the cluster invented a ReplicaSet

#

The story starts with a Kubernetes controller that would not stop recreating a pod for a ReplicaSet nobody could see:

E replica_set.go:640] "Unhandled Error" err="sync \"media/web-service-85fc7f49bf\"
  failed with replicasets.apps \"web-service-85fc7f49bf\" not found"

get returned NotFound. The API server’s own cache agreed — reading the object directly said it did not exist. And yet the controller-manager kept reconciling it, creating pods, and failing to update a status on an object that was gone. Deleting the pod produced a new one within seconds. Something held a stale copy and never let go.

The first hypothesis was the datastore’s watch implementation, so I read the logs. The delete event for that object should have carried the deletion revision. It carried the previous write’s revision instead:

live Delete key="/registry/replicasets/.../web-service-85fc7f49bf"
             mod_rev=13  (delete_rev=14)
             mod_rev=15  (delete_rev=16)
             mod_rev=17  (delete_rev=18)

Kubernetes derives each watch event’s ResourceVersion from event.Kv.ModRevision. An event whose revision goes backwards is, to a watch cache, an event that has already been seen — and a watcher whose start revision is newer than that silently drops it. No error, no cancel, no relist. The informer kept a dead ReplicaSet in memory and reconciled it forever.

The store’s own protobuf file states the contract in one sentence:

// A DELETE/EXPIRE event contains the deleted key with
// its modification revision set to the revision of deletion.

The fix was three lines: build the tombstone with mod_revision = rev instead of reusing the previous key’s blob. That single bug is what turned “the store works” into a question I could no longer answer honestly. If the event payload could be wrong for months without a single test noticing, what else was wrong?

Part 2: why reading the spec had not worked

#

The store had already produced two other protocol bugs in the preceding weeks, both documented in earlier posts: a point query that matched prefixes (because a predicate had been restated as a BTreeMap range), and a watch start_revision of zero that replayed the entire history (because “no start revision” was implemented as “start from the beginning” instead of “start now”).

The pattern is identical in all three cases:

1. the behaviour is defined by a sentence in a protocol document,
2. the implementation encodes the sentence from memory,
3. the encoding is plausible, self-consistent, and wrong in a corner nobody exercises,
4. the tests were written from the same memory, so they agree.

You cannot audit your way out of this by reading the spec harder, because the failure mode is that you believe you read it. The only thing that reliably disagrees with your memory is an implementation that does not share it.

Part 3: the differential

#

So the rule became: before asserting what the protocol says, ask the protocol.

The harness is one Rust test file that issues a fixed sequence of operations against whatever ETCD_ENDPOINT points at and prints one line per check:

CHECK|range.keys_only|values_empty=true
CHECK|txn.revisions_for_3_writes|consumed=3
CHECK|watch.delete_event_mod_revision|kv_modrev_is_delete_rev=false prev_present=true

Values are canonical on purpose — no absolute revisions, no timestamps, no ids, no hashes. A check that reported “revision 30493821” would differ between two servers that agree perfectly; a check that reports consumed=1 differs only when the semantics differ.

A driver script downloads a pinned etcd, starts it and the store on loopback with throwaway data directories, runs the same suite against both, diffs the output by check name, and fails if anything is in the wrong state. Forty-five checks; the run takes a couple of minutes.

The ledger

#

The obvious problem: you cannot fix fourteen things at once, and a red CI is a CI nobody reads. So the deviations live in a committed list, and the gate is two-sided:

• a deviation that is not in the list fails the build;
• a deviation in the list that no longer reproduces also fails the build.

The second half is the important one. Without it, a fixed bug silently stays “known”, and six months later nobody can tell whether the list is debt or decoration. Each fix removes its own entry in the same pull request, which is what makes the count meaningful: it went 22 → 18 → 9 → 6 → 2 as the fixes landed.

Test the release build, not the debug build

#

One detail in the harness deserves its own paragraph. It builds the store in release profile deliberately, because panic = "abort" is a release-only property. The most serious finding in the whole audit — the negative lease TTL — is a panic:

thread 'tokio-rt-worker' panicked at tokio/src/time/instant.rs:169:
overflow when adding duration to instant

In a debug build, tokio catches the task panic: the request dies, the connection drops, and the server carries on. The check reports “connection cancelled” and looks like a small bug. In release, the same panic aborts the process. A test that only ever runs the debug build would have reported the store as merely fragile, when in production it was killable.

This is a general trap for anyone testing a daemon: the artifact you ship is not the artifact your tests exercise unless you make it so. The harness does.

Part 4: the findings

#

Fourteen deviations, ranked by blast radius on a control-plane datastore.

C1 — the one-request kill

#

LeaseGrant fed a client-supplied integer straight into:

let expires_at = Instant::now() + Duration::from_secs(ttl as u64);

A negative TTL casts to ~1.8×10¹⁹ seconds. The addition overflows and panics. Debug: the request dies. Release: the datastore dies. etcd clamps to a minimum of 2 and rejects above MaxLeaseTTL with OutOfRange.

The fix reproduces etcd’s bounds exactly, verified against the reference: 0, -5, 1 → 2; 9223372036 → OutOfRange: too large lease TTL; 9223372035 → accepted. It runs before any state is touched, so the instant arithmetic can only ever see a value in [2, 9223372035].

The broader lesson is about where validation lives: every user-controlled integer that becomes a Duration, an index, or a capacity is a potential panic, and panics are fatal in a server built with panic = "abort".

H2 — the silent corruption path

#

This is the one I would fix first if I could only fix one:

let value = if req.ignore_value {
    prev_entry.map(|k| k.value.to_vec()).unwrap_or_default()   // ← empty, no error

ignore_value means “write using the value already stored”. On a key that does not exist, etcd returns key not found and lets the client retry. The store instead created the key with zero bytes, and prev_kv came back empty as well.

Why this matters beyond theory: kube-apiserver sends IgnoreValue when an update does not change the object’s bytes. If the key is deleted between its read and its write — a legitimate concurrent delete — etcd returns an error and the API server retries. The store resurrected the object as an empty value. Silent, permanent, and invisible to any test that did not race a delete against an update.

H3 and M6 — the missing validation layer

#

There was no request validation at all. Zero-length keys were accepted on Put, Range and DeleteRange (etcd: key is not provided). ignore_value together with a non-empty value was accepted (etcd: value is provided), and so was ignore_lease with a non-zero lease.

An amusing detail: the project’s own tests were using key = "" with range_end = "\0" as “all keys” — an invalid request that real etcd rejects. The legal spelling is key = "\0". Once the validation existed, twenty-five test call sites had to be corrected, because they had been written against the implementation’s permissiveness rather than the protocol.

H1 — transactions that were sequences

#

The full design is in the next post, but the finding belongs here: each operation in a transaction allocated its own revision, so a three-write transaction consumed three revisions and a reader pinned to an intermediate one saw a torn transaction — one of two keys visible. Compares were also evaluated under a read lock and applied under a different one, a TOCTOU hole in what Kubernetes uses as optimistic concurrency control.

M2 and M3 — the revision errors

#

Reads at a revision above the current one were tolerated for gaps up to ten thousand revisions and silently served current state. A client that asked for revision N and received today’s data had no way to detect it. And both that error and the compaction error were returned with gRPC code Unavailable instead of OutOfRange — which matters because kube-apiserver’s compaction detection matches on the code, so a compaction would have surfaced as an internal error instead of triggering the relist path.

The removal of the tolerance was the one change I was cautious about, because it could theoretically break a client that relied on being served current state. Before merging, I checked the running store’s log for the message the tolerance emitted on every hit:

$ journalctl -u kudurru | grep -c "range future revision within tolerance"
0

Zero hits across the entire journal, and the deployed binary provably contains that string at info level. Nothing had ever read a future revision, so removing the tolerance could not change behaviour for any observed traffic. That is the standard I now want for “this might be load-bearing” changes: prove the branch never fires before deleting it.

M4 — sorting, and a small detour into binary hacks

#

sort_order and sort_target were ignored entirely. Implementing them looked like a Vec::sort_by and turned into the most interesting performance work of the batch, because the naive version decoded every key-value with prost — allocating a key and a value per element — just to compare one field.

Three stages, measured by a benchmark that is committed with the fix:

The store only ever produces these blobs from its own encoder, so the layout is fixed and the tags can be skipped rather than interpreted; the fixed-width “overlong” varints (5-byte lengths, a 10-byte mod_revision) decode without scanning for a terminator. Whole-range sort by value dropped from 1.13 ms to 0.26 ms at 5 000 keys, and from 13.13 ms to 2.55 ms at 50 000.

Two further details worth stealing:

• The key axis is free. Every range result comes from iterating a BTreeMap, so it is already ascending by key: ASCEND/KEY is a no-op and DESCEND/KEY is a reverse. No parsing, no sorting.
• Push the limit down, but measure it. select_nth_unstable_by plus sorting only the first k sounds like a clear win. It is worth ~20% at 5 000 keys for k ≤ 100, and nothing at 50 000, because the O(n) parse dominates and the standard sort is already fast. It is gated (k ≤ n/64) so it cannot regress, and the write-up says so plainly instead of claiming a win.

The same class of hack appeared in the delete-event fix: rather than re-encoding the entire key-value to change one field, patch the 10 bytes in place — the field is a fixed-width varint, so nothing shifts. Measured at 1.8–2.1× faster than re-encoding, and the code is shorter.

M1 — nested transactions that did nothing

#

A nested transaction returned a fabricated success:

Some(RequestTxn(_)) => responses.push(ResponseOp {
    response: Some(ResponseTxn(TxnResponse {
        header: None, succeeded: true, responses: vec![],
    })),
}),

Success, no operations run, no error. The store had a test asserting this:

// Kudurru's nested-txn handler is a stub: it returns succeeded: true but
// does NOT execute inner operations.
assert_eq!(get2.count(), 0, "inner txn ops are not executed (stub behavior)");

A test that documents the bug is better than nothing, but it is not a specification — and once written in that voice, it reads like one. The fix made nested transactions execute, at which point that test failed, which is exactly what should happen. Updating it to assert the correct behaviour was part of the fix.

Part 5: the tests that agreed with the bugs

#

Two of the fourteen were defended by existing tests.

The point-range bug from the earlier post had a regression test that fired on the breakage and went green on an incomplete fix, because the fixture’s keys were …/a, …/b, …/c — equal-length siblings where incrementing the last byte lands exactly on the next key. Another test asserted count == 2 for a point query, with the message “both keys exist at non-compacted rev”. Both keys did exist; that is a fact about the fixture, not about the query.

The nested-transaction test quoted above is the same pattern in a different disguise: a characterization test wearing a specification test’s clothes. You run the code, observe an output, write an assertion that matches the output, and give it a name that makes it sound intentional.

The tell is grammatical. If the assertion message has to justify why the value is what it is, rather than state what the code must do, the test is describing the implementation. assert_eq!(count, 2, "both keys exist") is an argument. Arguments in assertions are usually rationalisations of observed output.

This is why the differential harness earns its keep: it encodes etcd’s behaviour, not the store’s. It cannot be talked into agreeing with a bug, because it has nothing to agree with — it runs two servers and compares.

Part 6: rollout

#

The changes were not one big drop. Two batches, chosen by blast radius:

• Batch 1 — request validation, lease id semantics, nested transactions. Nothing that touches the read path Kubernetes uses.
• Batch 2 — range revision errors and sorting. Both rewrite the hottest read path.

Each batch: merge, release build, smoke test the exact artifact against the integration suite on a throwaway instance, back up the running binary, install atomically, restart, then observe for fifteen minutes before starting the next batch. The observation is not “the service is up” — it is revision continuity across the restart, stable key and watcher counts, zero restarts, zero ERROR/panic lines, and a healthy API server journal.

batch 1  ready: revision=30996124 keys=2608   +5m/+10m/+15m: 0 restarts, 0 errors
batch 2  ready: revision=31002263 keys=2608   +5m/+10m/+15m: 0 restarts, 0 errors

The second batch had a specific thing to watch: the future-revision tolerance was removed, so any client that had been (mis)using it would start getting errors. Fifteen minutes of grep -c 'future revision' across the API server journal stayed at zero, which is the empirical confirmation the log check predicted.

Part 7: what is left

#

• Multi-op transaction rollback on dynamic validation errors: measured, pinned in the ledger, and honestly documented. Single-op transactions are unaffected, and that is all Kubernetes issues.
• Snapshot streams a private format rather than an etcd/bbolt snapshot. Nothing consumes it today; a tool that trusted it would produce an unrestorable backup.
• Status / HashKV report fabricated values, which misleads etcdctl endpoint status and any dashboard gating on version.
• No request size limit, where etcd caps at 1.5 MiB. Defence in depth: the API server caps objects, but a LAN client can push arbitrarily large values into the WAL.

None of these are urgent, and all of them are now written down with a check or a paragraph instead of living as a suspicion.

What I’d take from it

#

• You cannot review your way to protocol compatibility. The failure mode is that you already believe you implemented it. A reference implementation that does not share your memory is the only reliable oracle.
• Diff semantics, not values. Canonicalise the output so agreement looks identical and disagreement looks like a difference in behaviour. Absolute revisions in a diff are noise; consumed=1 is signal.
• Gate the ledger both ways. A known-deviation list that only fails on new entries rots into decoration. Make a fixed entry fail too, and the count becomes a burn-down chart you can trust.
• Test the artifact you ship. panic = "abort" turned a caught task panic into a datastore kill. Half the severity of the worst finding was invisible in the build the tests used.
• Prove a branch never fires before deleting it. The future-revision tolerance was removed only after the deployed binary’s own log showed zero hits over the whole journal.
• A test can be wrong in the same direction as the code. Watch for assertions that justify their expected value. Prefer naming the property: assert_eq!(kvs[1].key, b"k2") over assert_eq!(count, 2).
• Measure before declaring a performance win. The top-k pushdown that “obviously” helps is worth ~20% in one corner and nothing in the general case. Say so, gate it, and keep the benchmark in the repository.
• Batch by blast radius, observe, then proceed. Two batches with fifteen minutes each is cheap. A datastore restart that nobody watched is not.

Coda

#

The uncomfortable part of this story is not that a hand-written store had fourteen deviations. It’s that the store had been running a production control plane through all of them, and that the thing which finally caught them was not a review, not a spec reading, and not the project’s own tests — it was running two servers side by side and comparing what they said.

The most valuable artifact from the week is not any of the fixes. It’s a script that starts a reference implementation, runs forty-five operations against both, and refuses to let the list of disagreements grow or quietly shrink. Every finding above is now either matched, or written down with a check that will notice the day it stops being true.

That’s the part I’d keep.