A Transaction Is a Point in Time

#

The key-value store under the cluster had passed every functional test I had, and it had a bug that no functional test could have found: its transactions were not transactions. They were sequences. A reader who asked for a revision in the middle of one got half of it. This is the design of the repair — including the two places where my mental model of etcd turned out to be simply wrong until I measured it.

TL;DR

#

• A transaction is a point in MVCC time. In the store, each operation dispatched to put() / delete_range(), each of which allocated its own revision. A three-write transaction consumed three revisions, and Range(revision: r+1) returned a torn view: one key of two.
• Compares were evaluated under a read lock, which was then dropped, and the writes applied afterwards under separate write locks. That is a TOCTOU hole: the compare could be invalidated between evaluation and application. Kubernetes’ optimistic concurrency is built on it not being one.
• I probed etcd 3.5.30 before writing code, because the previous bugs in this store had all come from implementing a protocol from memory. Two of my assumptions were wrong:
  • Reads inside a transaction see that transaction’s own earlier writes. My first design ran all reads before the writes, on a “snapshot” theory. etcd disagrees: put(k); get(k) returns the new value.
  • Writes in a transaction must be disjoint, but reads may overlap writes freely. put(k)+put(k) and delete(prefix)+put(inside) are rejected; get(k)+put(k) is legal.
• The fix: one write lock for the whole transaction, compares evaluated inside it, one revision allocated lazily on the first write, in-transaction reads served from the already-mutated state without taking a second lock, and historical reads deferred past the unlock (they need the WAL and a read lock, and running them under the write lock would stall every writer for the length of a WAL scan).
• Error rollback is not fixed here: a dynamic validation failure in the middle of a multi-op transaction still leaves earlier operations applied, where etcd rolls the whole thing back. Rather than leave that in prose, it now has a conformance check and a pinned entry in the ledger.
• Result: the differential harness went from 3 deviations to 2 — one is the accepted “auth is unimplemented” difference, the other is the rollback gap above. The two torn-transaction checks now match etcd.

The symptom

#

The evidence came from a differential harness, not from reasoning: the same operations issued against etcd and against kudurru, compared per check.

txn of 3 writes:                    etcd consumed=1   kudurru consumed=3
Range at the intermediate revision: etcd kvs=2        kudurru kvs=1

Read that second line carefully. Not “an error”, not “a missing key” — a transaction observed half-applied. Two keys written, one visible. Nothing in the logs, no failed request, no inconsistent response. Just a store that had quietly exported a weaker consistency model than the one clients were written against.

Every write kube-apiserver makes is a transaction: a GuaranteedUpdate is a compare plus a put, a conditionalDelete is a compare plus a delete. Even a single-write transaction depends on three properties:

1. the response’s header.revision is the revision of that write,
2. no other revision exists between the previous one and that write,
3. the compare still holds when the write lands.

The old implementation broke all three in one way or another: the revision was one of several, earlier writes in the same transaction had their own revisions (property 2), and the compare was evaluated before the lock was taken (property 3).

What the old code did

#

The transaction handler was a dispatcher:

for op in ops {
    match op.request {
        Request::RequestPut(p)      => responses.push(self.put(p).await?),
        Request::RequestDeleteRange(d) => responses.push(self.delete_range(d).await?),
        Request::RequestRange(r)    => responses.push(self.range(r).await?),
        ...
    }
}

and put did this:

let mut state = self.state.write();
let rev = state.alloc_revision();     // one per call
state.wal.append_kv(&record);
state.apply(key, value, lease, rev, None);

Each call was individually correct. The composition was not: “a transaction” was implemented as “a loop of independent operations that happen to share a request”. That is a very natural way to write it, and it is wrong in a way that only shows up under concurrent readers — which is to say, under exactly the workload a Kubernetes control plane generates.

There was even a warning in the code that knew:

tracing::warn!("txn_multi_op: partial execution possible on WAL write failure —
                txn is not atomic across multiple ops");

The comment identified the symptom, but diagnosed it as a failure-mode issue (WAL write failure), when in fact the transaction was non-atomic all the time, for every multi-op transaction, with no failure required. I removed the warning because the behaviour it warned about is now gone for the revision and visibility dimensions. It still exists for the error-rollback dimension, which I’ll come back to.

Measuring before designing

#

The previous bugs in this store — a point query that matched prefixes, a watch event carrying the wrong revision, a start_revision of zero that replayed the whole history — all had the same root cause: a protocol implemented from memory. So this time the first commit wasn’t code, it was a probe. Four questions, answered by running them:

I had two of the three wrong. Both would have produced a plausible-looking implementation that differed from etcd in ways no unit test I’d have written would have caught. The probe took fifteen minutes; the wrong version would have taken a week to notice, if ever.

Those four lines became permanent conformance checks, so the next person cannot quietly decide the other way.

Decision 1: one revision per transaction

#

Chosen: all writes in a transaction share a revision, returned in TxnResponse.header.revision.

The alternatives, and why not:

Consequence. Watch events from a transaction all carry the same revision, as etcd’s do. Range at any revision between this transaction and the next sees all of it or none of it, by construction — there is no longer an intermediate revision to ask for.

Decision 2: allocate lazily

#

rev: Option<u64>, filled by get_or_insert_with(alloc_revision) on the first write. A read-only transaction consumes nothing, and a transaction that fails validation consumes nothing. The alternative — allocate after compares, before applying — is one line shorter and burns a revision on every get-only transaction and every rejected request. Given that the harness measures revision consumption, this is not a style choice: it’s the difference between passing and failing a protocol check.

A small side effect lands in the direct RPCs too: put and delete_range now allocate after validation, so a rejected Put no longer leaves a hole in the revision sequence. Not a correctness property in etcd, but it keeps the numbering tight and makes revisions_for_3_writes meaningful.

Decision 3: one lock, and compares inside it

#

Chosen: take the write lock once, evaluate the compares under it, apply the branch under it, release.

The old code took a read lock for the compares, dropped it, then took a write lock per operation. Between the two, another writer could change the key the compare was about — and the transaction would still apply. Kubernetes’ GuaranteedUpdate uses that compare as its entire concurrency control; a compare that can be invalidated between check and write is not concurrency control.

That last con is the one to respect. A single write lock held across a transaction serialises other writers for as long as the transaction takes. Which is fine — provided every operation inside the critical section is bounded. Map operations are O(log n). The unbounded one is a historical read, which scans the WAL, and that is why it was moved out (Decision 6). Without that, this design would be a latency bomb.

Decision 4: split validation from application

#

To share a revision, “apply this put at revision R with the lock already held” has to be callable. The old put did everything: validate, lock, allocate, append, apply, respond.

The split also made the transaction helper sync — no async inside the critical section, which matters for a reason that is easy to miss: parking_lot guards are not Send, so an async function holding one across an await is not a valid tonic handler. Keeping the locked section synchronous is not stylistic; it is what lets the code compile as a Send future.

Decision 5: reads must see the transaction’s own writes

#

This is the decision the probe changed. My first design ran all range operations before the writes, on the theory that a transaction reads a snapshot of the state at its start. That is a common description of MVCC and it is not what etcd does: put(k); get(k) returns the new value, and the conformance check txn.read_own_writes now pins it.

So in-transaction reads need to read mutated state under the held write lock. The options:

The extraction was mechanical: the current-state path of range() already operated on a &StoreState after taking a read lock, so it became a function taking that reference, and both callers (the normal read path and the transaction) pass one. Range with a historical revision is a different path and cannot work this way — which is the next decision.

Decision 6: defer historical reads

#

A range with revision > 0 reconstructs old values from the WAL and takes read locks. Under the transaction’s write lock, both are impossible: the read lock deadlocks, and running the WAL scan while holding the write lock would block every writer for its duration — measured at ~100 ms on a 40 MB WAL, and growing.

The deferred op records its position in the response tree (Vec<usize>, because nested transactions nest responses), the transaction finishes and releases the lock, and the deferred range runs through the normal read path and is patched back in.

Why the result is correct even though it runs after the writes: the requested revision is at or below the current revision at the moment the transaction started, and the transaction’s own writes are at a later revision. A historical read pinned below the transaction cannot observe it. If the caller asks for the transaction’s own revision, the read finds the writes in the WAL, because they were appended as the transaction applied.

That path is easy to get subtly wrong — patch the wrong slot, or return the current value instead of the historical one — so it has its own test: a transaction with a write and a historical read, asserting the read returns the old value and the write still happened.

Decision 7: nested transactions

#

One level of nesting, as etcd allows, running under the same lock and the same revision. The alternatives are worse in obvious ways: flattening changes the response shape, a separate revision per level reintroduces the original bug one level down, and no depth limit invites recursion on attacker-controlled input.

Decision 8: disjoint writes, measured rules

#

etcd rejects transactions where writes collide, but the exact rule is not “no two operations touch the same key” — reads are exempt. Measured:

So the validation is over write intervals only: puts are point intervals [k, k\0), delete ranges normalise to [start, end) with None meaning unbounded (From, All, or a prefix of all 0xFF). Overlap is the standard interval test, O(n²) over at most a handful of operations.

The point interval is [k, k\0) rather than [k, k+1) for the same reason the point-query bug from an earlier post was fixed that way: k\0 is the smallest key strictly greater than k, so the interval contains exactly k by definition rather than by luck about key lengths.

The limitation, and why it is now a test

#

Here is the part I did not fix. A dynamic validation error in the middle of a multi-op transaction — the only case is ignore_value / ignore_lease referring to a key that does not exist at that point — leaves the earlier operations applied at the transaction’s revision. etcd rolls the entire transaction back.

The options:

I took the first, with an explicit argument for why it’s acceptable here: every transaction Kubernetes issues has a single write, and in a single-op transaction the failure happens before any write. The gap only exists for multi-op transactions that mix a write with ignore_* on a key the same transaction does not create.

The argument is fine. The reason I trust it more than prose is that it is measured:

etcd    : code=InvalidArgument msg=etcdserver: key not found first_write_survived=false
kudurru : code=InvalidArgument msg=etcdserver: key not found first_write_survived=true

That check is committed, and the deviation sits in the ledger with a pointer to the design document. It will show up in every CI run until someone implements the undo log, and the gate fails if it ever stops deviating without the ledger being updated. A limitation that only exists in a paragraph is a limitation that gets forgotten; one that fails the build is a to-do item.

Performance

#

No hot path outside transactions changed: put and delete_range are the same code moved behind one function call.

The cost is that the write lock is held for the whole transaction instead of per operation. For Kubernetes traffic that is the same wall time — a single operation — with fewer acquisitions. For a large multi-op transaction it serialises other writers for the transaction’s duration, which is why the only unbounded operation was moved out of the critical section.

What I’d take from it

#

• Probe the reference implementation before writing the protocol. Two of my three prior beliefs about transactions were wrong. Neither would have been caught by a test I invented, because I would have written the test from the same wrong belief. Fifteen minutes of probing beats a week of confident implementation.
• “Atomic” is not one property. Revision atomicity, visibility atomicity, compare/apply atomicity and error atomicity are four different things with four different costs. Fixing three and documenting the fourth is a legitimate outcome — but only if the fourth is measured, not just described.
• A per-operation loop is not a transaction, no matter what the function is called. The bug was not in any operation; it was in the composition. Those are the bugs that survive unit tests, because the tests exercise operations.
• A held lock changes what you can call. The read-your-writes requirement and the historical-read deferral are the same constraint seen twice: while you hold the write lock, anything that takes a read lock is a deadlock, and anything unbounded is a latency bomb.
• Re-derive the rules from behaviour, not from the shape of the API. “Writes must be disjoint” is true. “Operations must be disjoint” is false, and the difference is exactly the case optimistic-concurrency clients use.
• Keep the ledger two-sided. A known deviation that can silently disappear from the list is indistinguishable from a fixed bug. Failing on both “new deviation” and “baseline entry no longer deviates” is what keeps the list honest.

Coda

#

The fix is, in the end, a smaller change than it sounds: move a lock, move a revision allocation, and move one range path behind a function boundary. What made it slow was not the code — it was deciding what a transaction is, and discovering that two of my answers came from reading about MVCC rather than from the store I was supposed to be compatible with.

There is a version of this post where I implemented the snapshot theory I started with: reads before writes, one revision per transaction, compares under a lock. It would have passed every test I would have written, shipped, and produced a store that disagreed with etcd on the first transaction that read its own write. The difference between that version and this one is a fifteen-minute probe and a check in a list.