Transactions and MVCC
Transactions and MVCC
The problem
Readers must not block writers and writers must not block readers, while each reader still sees a coherent view of the database. The standard answer is multi-version concurrency control: never overwrite, always append a new version, and let each reader decide which versions it may see.
That turns concurrency control into a question about numbers. Every write gets a sequence; every reader gets a ceiling; a version is visible if its sequence is at or below the ceiling. No locks are involved in a read.
The engine’s MVCC core is deliberately pure — it knows sequence numbers and precomputed key hashes, not engine structures — so it builds and tests standalone.
The clock
Four things live in the clock:
A monotonic counter. Every commit draws a sequence from it. Sequences are never reused; the counter only moves forward, including across restarts (see Recovery).
A commit-status ring. Drawing a sequence and completing a commit are not the same instant, so a sequence that has been drawn but not finished must be invisible — otherwise a reader could see half a batch. The ring records, for the most recent sequences, whether each one is in progress, committed, or aborted, each slot tagged with the sequence it describes so a slot reused by a later sequence never reads as a decision about an earlier one.
A watermark. Readers do not consult the ring. What they take their ceiling from is the watermark: the highest sequence below which every drawn sequence has been decided, committed or aborted. Every commit ends by deciding its sequence and carrying the watermark forward over every decided sequence above it, and every failure path after the draw decides the sequence as aborted for the same reason. A sequence is committed only after its batch is applied in full, so everything at or below the watermark is whole and final, and a ceiling taken from it never admits a version that could still change or disappear.
Carrying it forward is a store of the committer’s own decision followed by loads of its neighbours’, and the two are separated by a full barrier. Without one, two committers deciding neighbouring sequences at the same instant could each miss the other’s store while it sat in a store buffer; each would stop at the other’s slot, the watermark would stand below both, and the higher committer would wait on a publication no one was left to make until some third commit arrived. With the barrier at least one of the two sees the other’s decision and carries it.
A commit does not return until the watermark has passed its own sequence. The wait is on the commits in flight below it, each inside its own commit window, and it is what makes a commit’s writes visible to the caller’s very next transaction — the watermark publishes in order, and “returned” means “published”.
The ring is bounded, and the bound is enforced rather than assumed: the clock will not draw a sequence a ring’s width above the watermark, so a slot the watermark has yet to read is never recycled underneath it, and a slot always describes the sequence it is asked about. The room is checked and the sequence taken in one compare-and-swap. Checked apart, every committer that saw the last free slot took a sequence, the ones past the ring recycled the slot of a sequence the watermark had yet to read, its decision was lost, and the watermark stopped for good: every later commit waited out its spin budget and a read-committed reader never saw another commit. A draw that has to wait for room does so before it announces itself to validators, for the reason given under Claims. Nothing reads the ring below the watermark — a reader’s question is answered by the watermark alone — so there is no rule for sequences that have aged out of it.
The sequence a two-phase transaction drew at its prepare is spent the moment its record is durable: phase two commits at a fresh one, so no version ever carries it, and it is decided as aborted so the watermark passes it. What holds the batch’s keys through the in-doubt window is not the ring but the claim set — see Two-phase commit.
An in-flight claim set for conflict detection, described below.
Snapshots
A snapshot is a sequence ceiling, and the isolation level decides what it is:
| Level | Ceiling |
|---|---|
| Read uncommitted | Unbounded — even in-progress sequences are visible |
| Read committed | The watermark, re-read for each operation |
| Repeatable read, snapshot, serializable | The watermark when the transaction begins, frozen |
Freezing at begin is what makes repeated reads stable: the ceiling does not move, so a version that committed after the transaction started is invisible no matter how many times it looks. Taking it from the watermark rather than from the sequence counter is what makes the snapshot a snapshot: every sequence at or below it is already decided, so nothing that was in flight when the transaction began can land inside its view later, and no batch is ever seen half applied.
The ceiling is not quite the only filter. A commit whose batch reached the log but failed to enter the memtable leaves entries behind at a sequence that never committed, and those are stepped over in favour of an older visible version at every level — including read uncommitted, whose unbounded ceiling would otherwise return them. “Uncommitted” means a sequence still in flight, not one that was given up on. A flush waits for every sequence in a memtable to be decided before it builds, so those entries are dropped there and never reach an sstable; the memtable is the only place they can ever be, and the record of them is forgotten once the memtables that could hold them have retired.
A snapshot costs nothing to take — it is a number — but holding one is not free. The oldest live
snapshot is the floor below which compaction may drop old versions and
tombstones. A transaction left open holds that floor down and keeps garbage alive, which surfaces
as min_snapshot_seq in the database statistics and as space that will not reclaim.
Named snapshots
A transaction’s snapshot is a number it draws at begin and drops when it ends. A named snapshot
is the same number held deliberately: tidesdb_snapshot_create captures the watermark and keeps
it, and a transaction opened against it reads as of that point.
The mechanism is already everywhere. Every read resolves at a ceiling, and the memtable and the btree both take the newest version at or below one, so reading the past needs no new path — only a way to say which ceiling. What the handle adds is the retention.
A snapshot is registered exactly as a repeatable-read transaction is, so it appears in the minimum the registry publishes and holds the reclamation floor at its own sequence. That is what keeps the versions it resolves to alive: compaction may not discard above the floor, and a flush carries a key’s chain into L1 on the same rule.
A snapshot is the stronger of the two. It holds the floor from the moment it is taken, so the point stays readable; a bare sequence is readable only while something else happens to be holding the floor under it, and on an idle database the next merge takes that away.
The cost is the cost of a long-running transaction, because it is the same mechanism: a snapshot
left open pins min_snapshot_seq and the space below it will not reclaim. It shows up in exactly
the place a leaked transaction does, and is diagnosed the same way.
One thing a snapshot does not restore. Expiry is judged against the published clock at the moment of the read, not against the snapshot’s sequence, so an entry whose lifetime has elapsed reads as a tombstone through a snapshot taken while it was live. A snapshot travels over versions, not over deadlines.
Claims: what a commit in flight holds
At repeatable read and above, a commit must not silently overwrite a write it did not see, and must not commit on a read that a commit sequenced before it has already invalidated. Each question has two halves: a rival that has already committed, which the data itself answers (the conflict scan below), and a rival that is committing right now, which nothing in the data can answer yet. The in-flight claim set answers the second.
A claim names a key — its family, its bytes and its owner, the commit holding it. The set is a hash table of chains under striped locks, and a claim is compared by its bytes, never by its hash alone, so two different keys in one chain are two claims, not a collision. Nothing about it is a fixed number of slots per key: two commits of different keys never conflict on it, however wide either is, and a commit never refuses itself. A table of hashed slots — one per key, then a run of four — did both, and a table load of a hundred thousand rows in one transaction was refused for colliding with its own keys.
Claims are taken before the sequence is drawn, in one fixed order — family, then key bytes. The order is what makes two commits sharing keys meet at the same first key, so exactly one yields rather than each holding half. The position is what makes validation sound: any commit whose sequence is below mine had finished claiming before I drew, so my validation, which runs after my draw, sees its claims. In the other order two commits could each validate against a set that did not yet hold the other, and both go through.
What a claim meets when it joins its chain decides it:
- A write claim meeting another owner’s write claim is refused at snapshot and serializable — that owner is in flight, one of the two must lose, and the later claimant does. First-committer- wins, decided at the claim rather than after the fact.
- At repeatable read a write claim is recorded and refuses nothing; two blind writers of one key both commit there. What it is for is being seen by a rival’s read validation.
- A read claim — taken by a prepare at repeatable read or above on every key it read — is never refused, and refuses every later write claim on its key for as long as its owner is undecided. Why a prepare needs one is in Two-phase commit.
- A scanned interval is the read claim of a scan. A prepare at repeatable read or above attaches every interval its scans covered to its record in the list of commits in flight, and a writer inside one — a point write or a range delete meeting it — is refused for as long as the prepare is undecided. The intervals live on the record rather than in the table of held intervals, so a prepare with many scans takes no slot a range delete needs.
A claim carries its owner’s sequence once drawn; until then it reads as drawing, and a validator that meets one spins for the store, which is a few instructions away. It is a few instructions away because a draw that finds the ring full waits for room before it says drawing: the validator it would otherwise keep spinning may hold the lowest undecided sequence, whose decision is what makes the room, and announced first the two waited on each other for the length of the spin budget. Validation at repeatable read and serializable asks the set, for every key the transaction read, whether another owner’s write claim sits below my sequence: that writer lands before me, my read of the key is stale at my position, and I am refused. For every interval a scan of the transaction covered it asks the same of every commit in flight — a write claim on a key inside it below my sequence is a phantom about to exist — which is what the list of commits in flight is for, since an interval has no one chain to look in. A write claim above my sequence is not my problem — that commit is sequenced after me and validates against mine. A prepared owner’s write claims read as future, since its final sequence will exceed every current one, so a reader of a key it writes is serialized before the batch and not refused, while a writer of that key at snapshot or above is. A reader that is itself a prepare is the exception, covered in Two-phase commit.
Every writing commit claims, read committed and below included; those levels only drop the first-committer promise, so their claims refuse nothing at the claim. The claim is what lets the order above hold: validation asks the claims before the store because a claimed writer lets go only once its version is in the store, so a writer below me is in one or the other. When read committed wrote without claims, such a writer was in neither between its draw and its apply, and a repeatable-read commit drawn just above one that wrote a key it read validated past it and committed on a read it had already invalidated. Covering that by making validating commits wait for every sequence below them to settle cost a mixed load about a sixth of its time; the claim covers it at no cost the load could measure.
The claims go with the commit. A refused claim drops the ones already taken, a failed commit drops them all, and a successful one drops them once the watermark has passed its sequence, so a rival validating against the data finds what the claims were standing in for. Nothing is renamed, aged out or handed over.
That hand-over fixes the order validation asks its two questions in: the claims first, then the store. A writer drops its claims only once its version is in the store, so a claim a validator finds gone is a version the store check after it will see. Asked the other way round, a writer sequenced just below could apply after the store check and drop its claims before the claim check, and neither would see it. Snapshot and serializable refuse a second writer at its claim, which hid the gap for them; repeatable read refuses nothing at the claim and relied on validation alone, and two read-modify-writes of one key both committed.
Losing a claim is TDB_ERR_CONFLICT, raised before anything durable has been written.
The subtlety is what each write is validated against. Not the transaction’s snapshot, but the
version this transaction actually read for that key, recorded when
tidesdb_txn_get was called. A blind write with no prior
read falls back to the snapshot.
This is why the API distinguishes tracking and non-tracking reads. A read that feeds a write must be tracked, so the write is validated against what it was based on. A probe whose answer does not determine what is written should be untracked, because widening the footprint only creates conflicts that are not real.
An interval has no key to claim
A range delete writes an interval, not a key, so there is no key for it to claim and no one chain a writer inside it could look in.
A second, small table holds the intervals themselves, at repeatable read and above, taken with the claims and before the draw. A point write checks that table alongside its chain: an interval another commit holds over its key refuses it under first-committer-wins, and is recorded beside it at repeatable read. Under first-committer-wins the interval is checked the other way as it is taken — entered in the table first, then compared against every commit in flight, whose claims are complete arrays by the time the commit is on the list — so a point writer and a range delete meeting in the same instant find each other whichever was first, and one of the two yields. An interval also yields to another interval meeting it, and to a prepared reader holding a key inside it, which cannot be the one to yield. At repeatable read the interval is entered and refuses nothing, exactly as a write claim at that level is; what it is for is being met by the writers at snapshot and above and by the readers validating under it. After the draw a range delete under first-committer-wins validates like a write: the store for a version inside the interval above its snapshot, and the commits in flight for a write claim inside it sequenced below it.
A version inside an interval is not only a key written there. A range delete writes no key at all, only a tombstone over its bounds, so the store’s answer for an interval also asks every memtable’s range tombstones and every table’s interval block whether one overlapping it carries a sequence in the window. Walking the keys alone, two overlapping range deletes both committed, and a serializable scan whose rows a range delete removed after its snapshot committed on rows that no longer existed. A table’s newest sequence and key range are those of its keys, so its intervals are asked before either is used to rule it out.
The table is almost always empty, so a point write’s check is one relaxed load; only when a range delete is actually in flight does a write compare its key against a handful of bounds. That is also what carries a two-phase range delete through the window between its prepare and its commit.
The interval goes back once the batch is visible, and not before — with the batch’s key claims, and for the same reason: what replaces either is the committed write, which a later writer’s conflict scan finds. Releasing earlier leaves the gap between the two uncovered, and not releasing at all spends the table: it has a fixed number of slots, so one leaked per commit ends with every later range delete in the database refused as a conflict that no retry could clear.
The slots are a fixed width, which is where the public
TDB_MAX_RANGE_BOUND_SIZE limit on a range
delete’s bounds comes from. A longer bound is turned away at the API rather than narrowed to fit,
since a narrowed bound describes a wider range than the caller asked for.
A scan’s footprint
An iterator at repeatable read or serializable keeps the interval it has covered — from the key it sought or the first key of its range to the last key it stood on, or to the end when it ran off it, absent keys included — and hands it to the transaction’s read set when it is freed. At commit the interval is validated like a read: the store is asked whether any version inside it sits above the snapshot, and the commits in flight whether one sequenced below this commit writes a key inside it. Either is a phantom, a row the scan would have seen had it run a moment later, and the commit is refused. That is what makes serializable PL-3 rather than PL-3 over point reads alone: a write skew that depends on a scan having seen no row is refused with the rest. Snapshot isolation validates no read and keeps no footprint. An iterator whose footprint cannot be recorded fails its transaction rather than let it commit unchecked.
The conflict scan, and what it does not read
The claim set catches a transaction that is committing right now. It cannot catch one that committed and finished between this transaction’s snapshot and its commit — that writer has dropped its claims. So a commit at snapshot isolation or above also scans its write set against the data itself, and repeatable-read and serializable scan the read set the same way, the keys read and the intervals scanned both.
The question that scan asks is narrow. Not what is the newest version of this key, but only does any version of it exist above my snapshot and below my own sequence. That distinction is worth a great deal, because answering the first question means descending a btree in every overlapping sstable at every level, parsing nodes and verifying checksums, purely to discard the answer.
The upper bound matters as much as the lower. The scan runs after the commit has drawn its sequence, and a writer that drew a higher one may already have applied its batch — commits overlap, and the apply is the last step of each. That writer is ordered after this commit, so its version stales nothing this commit read and contests nothing it writes; it is that writer’s own validation, against this commit’s version, that decides between them. Asking about every version there is refused both, and a pair of concurrent writers to one key could each be refused on account of the other. So the store is asked only about versions sequenced below the commit; writers above it are not its concern, and writers below it that have not applied yet are in the claim set.
Every sstable records the newest sequence it contains in its footer. An sstable whose newest sequence is at or below the transaction’s snapshot cannot hold a conflicting version, so the scan skips it on that field alone — no descent, no node read, no checksum. Skipping it stays correct even when that sstable does hold the key, because the only thing being asked is whether something newer exists, and a skipped sstable’s answer is no.
Since flush and compaction continuously produce sstables while transactions are short, nearly every sstable predates any live transaction’s snapshot, and nearly the whole scan resolves from metadata.
Memtables get the same skip from the highest sequence each one has applied. A sealed memtable waiting for its flush was usually filled before the snapshot, so its highest sequence is at or below it and the scan passes it without a search. The bound is raised as part of the apply, before the commit gives up its claims, so a commit the scan no longer finds among the claims has already raised it. The scan also asks only for the sequence it finds, so a value held as a value log id is never fetched to answer it.
A range delete asks the same question over an interval rather than a key: does any key in these bounds sit above my snapshot. It prunes on the same footer field — a table whose newest sequence is at or below the snapshot holds nothing newer wherever its keys fall — and stops at the first key it finds, since one is all the commit needs to know.
Two things differ from the point form. Every source is asked rather than the first one holding the key, because a newer key in an interval can be in any of them and a shallower source says nothing about what a deeper one holds elsewhere in the range. And there is no fallback: a source that cannot answer an interval reports busy, which the commit retries, rather than being stood in for by a full read the way a source without a point probe is. A missing implementation must never read as a clear run.
Busy has to mean transient, though. The retry is bounded, and a source that answers busy for a
reason that will hold every time — a bound too long for a buffer, say — turns a permanent condition
into TDB_ERR_IO after the retries run out. A condition the caller cannot clear belongs at the API,
as an argument error, not on this path.
The write and read sets
The write set buffers operations in insertion order. Order is what makes savepoints work: a savepoint is a position in the sequence, rolling back to it discards the tail, and releasing it forgets the mark without discarding anything.
Beside the ordered ops the set keeps the same skip list the memtable keeps, over the family-prefixed keys, holding for each key one version per write of it with the write’s position as the value and the newest at the head. A read-your-own-writes lookup reads one head; a scan inside the transaction walks the list with the memtable’s own cursor and folds it over the committed view. Both once walked the ops instead — the lookup comparing every buffered key, the scan sorting a copy of them per iterator — so every operation of a transaction cost as much as it had already buffered, and a bulk load of a hundred thousand rows was quadratic in the rows, twenty-one seconds where it now takes a fraction of one. The interval deletes are few and cover keys they were never written beside, so they stay in a short list of their own, walked newest first: a key’s newest point write answers unless an interval buffered after it covers it, and a scan honours the transaction’s own interval deletes the same way, hiding the committed keys under them and showing a key the transaction wrote under one afterwards. The commit’s dedup asks the same list which write of a key is the newest.
The read set records what tracking reads observed — key and version — and the intervals the transaction’s scans covered, each at the snapshot it scanned at. It exists to feed the read validation at commit and, at a prepare, the read claims. A key read again is found through an index over the entries rather than a walk of them, for the same reason.
Both are per-transaction and single-threaded, which is why a transaction handle is not
thread-safe. The one exception is the flag
tidesdb_txn_request_abort sets: it is the only
field another thread ever writes, and it changes nothing else, so the thread that owns the
transaction is still the only one that moves its state.
The registry
Live transactions are registered so the engine can compute the reclamation floor: the smallest sequence any of them still reads at. A repeatable-read or stronger transaction holds it at its frozen snapshot for its whole life. A read-committed transaction holds it only while a read or a scan is in flight, at the ceiling that read took from the watermark — a read takes its ceiling and then reads the store, and a collection starting in between would otherwise keep one version per key and drop the ones the read still resolves to. The ceiling is published before the store is read and withdrawn after; a scan’s stays published until its iterator is freed, and a point read inside an open scan does not lift it. Read-uncommitted resolves to the newest version, which no collection drops, so it registers nothing.
A collection takes the floor in two scans with its high-water mark published between them, behind a full barrier, and a read publishes its ceiling behind one before it checks the mark. So a read whose ceiling the first scan missed is either seen by the second, and the floor stays at or below it, or sees a mark above its ceiling and takes the ceiling again above the floor it missed. The floor is never above the watermark, since nothing a collection reads is above it.
The registry is on the commit path, so its cost matters: each transaction holds its own slot and leaves in constant time rather than by scanning a list.
It is also sharded, because joining and leaving are per-transaction rather than per unit of work — every transaction does both exactly once, whatever else it does — so a single lock made this a database-wide serialization point that got worse with concurrency, not with load.
A transaction takes the shard of the thread that joins it, claimed once per thread from a counter. The thread is what actually contends, so it is what the shards have to spread. Deriving the shard from the transaction’s own address instead looks equivalent and is not: a caller running one short transaction at a time — a statement-scoped transaction under autocommit, say — frees and reallocates at the same few addresses, so the shards collapse onto a handful of slots and unrelated threads queue on one lock. Measured on sixteen threads that difference is most of the throughput.
The transaction stores the slot it landed in rather than recomputing it, so a leave can never disagree with its add about which lock it needs — which is also what lets a transaction be freed on a thread other than the one that began it.
The two readers of the set treat the sharding differently, and deliberately:
- The reclamation floor takes one shard at a time. The answer can come out too low but never too high, and too low is the safe direction for a reclamation floor — it keeps a version some reader might still want. It cannot come out too high, because a transaction registering after its shard was read draws its snapshot from a monotonic clock and so is above the minimum already, and one that leaves only raises the true minimum above what was reported. A read-committed ceiling published after its shard was read is the one case that argument does not cover, and the second scan behind the high-water mark is what covers it.
- Enumeration, which the statistics call lists live transactions with, holds every shard for the whole walk, so it reports one instant of the live set rather than a smear across shards. The shards are taken in index order, the only order anything takes them in, so two walks cannot deadlock against each other. Holding all of them is affordable precisely because the walk is rare — never the write path, which touches one shard.
Timeouts
A transaction that is begun and never resolved is not merely idle. It holds its snapshot, so the reclamation floor cannot rise past it — compaction may not drop the versions below that floor, and the value log may not reclaim their bytes. A leaked transaction therefore costs disk for as long as the database is open, and nothing else in the engine can decide it is safe to let go of.
A timeout bounds that. It is off by default (txn_timeout_seconds is 0), applies to every
transaction when set, and a single transaction overrides it through tidesdb_txn_set_timeout.
Two properties are worth knowing:
- Expiry is lazy. No background thread aborts anything. The next operation on the transaction
notices its deadline has passed, aborts it there, and returns
TDB_ERR_TXN_EXPIRED. A transaction that is never touched again is never expired — it is resolved at close instead. - The clock is cached, not read per check. A ticker publishes the current second, and a check is one relaxed load against it. That is what keeps a transaction with no timeout paying nothing, and it also means a deadline is accurate to about a second rather than exactly.
Two-phase commit
Ordinary commit decides and applies in one step. Two-phase commit splits the decision from the application so an external coordinator can gather votes from several participants first.
Phase one — prepare. Takes the same claims and runs the same conflict checks as commit, and
durably logs the write batch under a caller-supplied transaction id, but leaves the writes invisible
and unapplied. The transaction keeps its claims until it is resolved — on the keys it wrote, and at
repeatable read or above on the keys it read as well — so an undecided prepared transaction applies
backpressure to anything contending for its keys, and its snapshot holds the min_snapshot_seq
floor down. Deciding promptly is not optional in a busy system. The sequence the prepare drew is
spent for the watermark as soon as its record is durable — no version ever carries it, since phase
two commits at a fresh one — so an undecided prepare never holds readers’ ceilings down.
A read-only transaction prepares with nothing durable and needs no phase two.
A prepared batch that separated any of its values is also the only thing naming them. Its entries are in no memtable and no sstable until phase two decides it, so the value log counts a staged batch’s references alongside the installed tables and holds a floor over their segments — the same reason its write-ahead log generation is pinned, applied to the other store.
Phase two — commit or roll back. Durably logs the decision, then applies the batch and makes it visible.
The critical detail is the sequence. Phase two draws a fresh sequence at decision time and carries the batch inside the commit record, rather than applying at the sequence the prepare held.
Re-sequencing is also why a prepare holds its reads. Its reads were validated at prepare time, and phase two lands the batch above everything that committed while it was in doubt. A transaction that wrote a key the prepare read, committing inside that window, would leave the batch with a stale read at its final position — the shape every anomaly needs — and the prepared side can no longer be the one to yield, since a participant that voted yes must be able to commit. So the writer is refused: at repeatable read and above the prepare takes a read claim on every key it read and holds every interval it scanned, and a writer of such a key, or inside such an interval, is refused for as long as the batch is undecided. A range delete meeting either is refused the same way, repeatable read included, where the delete otherwise asks nothing of the claims in flight. Read committed validates nothing of its own, yet it is held to this too: a prepare counts itself in the clock before it draws, so a read-committed commit drawn above it finds the count raised and checks its writes against the prepares’ reads, and one drawn below it is found in the claims by the prepare’s own validation. With no prepare holding reads the check is one load.
A prepare that validates its reads also yields to another prepare that writes what it read, whatever the two drew. A plain reader of such a key is serialized before the batch, which holds because it commits now, below any phase two to come. A prepare’s position is not decided now: both are placed by their phase twos, and the batch that voted first may be decided first and land below the reader, which then read a version older than one beneath it. So a prepare meeting another prepare’s write claim, or its interval, on something it read or scanned is refused, and a prepare at read committed claims what it writes for this reason, since the reader has nothing else to find the pending write by. Before this a serializable prepare validated past a batch already prepared, the batch was decided first, and a reader that saw the batch but not the prepare closed a cycle through two serializable reads.
Its write claims read as future to every validator while it is in doubt. A reader of a key it writes is not refused — it is serialized before the batch, and its read is consistent — while a writer of that key at snapshot or above is, first-committer-wins. Phase two then draws through the same record, so from that draw the claims carry the sequence the batch commits at. A commit drawn above it validates before the batch is applied and finds it below itself in the claims, since the store cannot show it yet. Left reading as future, the batch looked above that commit, its read of a key the batch writes passed against a store that did not hold the batch, and the two committed a write skew. A phase two that fails marks the record future again before it spends the sequence it drew. The claims are dropped once phase two has applied and marked the batch, or rolled it back. Nothing is handed over between the prepare’s sequence and the one phase two commits at, because a claim is held by presence and the record it belongs to is the same one throughout.
An in-doubt batch adopted after a restart claims its keys again, and holds its intervals again, from the entries its PREPARE record carries, and its reads again from the record written immediately ahead of it: at repeatable read and above the prepare appends its read keys and its scanned intervals as a record of their own under the same xid before the PREPARE, so a PREPARE that is durable always has its reads, and recovery holds them for the PREPARE that follows. An interval is an entry flagged and bounded as a range delete is, which is how recovery tells it from a read key. Read keys no PREPARE ever followed — the prepare failed between the two appends — are dropped with the staging map. A prepared handle freed without a decision — abandoned, which the engine allows — leaves its claims with the clock in its place, since the record is durable and a later open may still commit it.
A transient I/O failure in phase two leaves the transaction prepared, not aborted, so the coordinator can retry the same decision. Anything else would let a participant unilaterally abandon a transaction the coordinator had already committed elsewhere.
What an undecided prepare keeps alive
A prepared batch never enters a memtable, so it is durable only in the log its PREPARE record was written to. That generation’s log therefore cannot be unlinked when it flushes, the way an ordinary generation’s is once its data reaches L1 — the flush moved no part of that batch anywhere.
It is that one generation, and no other. The pin is keyed on the generation the record lives in, not on whether some prepare somewhere is undecided. The difference is not academic: an engine driven by a coordinator that always has a transaction in flight — which is what MariaDB’s internal two-phase commit between the engine and the binary log looks like under concurrent load — would otherwise keep every log it ever wrote, since the count is never zero at the moment a flush asks. The store then grows without bound in a way that looks like a compaction failure and is not one.
Once phase two decides, the prepared generation is free immediately, and its log goes. That follows from the commit record carrying the whole write set: replay applies it inline, so nothing needs the original PREPARE any more. A rollback leaves nothing to undo, so the same holds.
The pin is taken by recovery itself, not by whoever adopts the transaction. A database that reopens with a batch in doubt and simply carries on writing — never asking for its in-doubt list — must still keep that log, because it holds the only copy of a batch someone may yet decide.
Not its sequence. The sequence the prepare drew is decided as spent the moment its record is durable, and the commit-status ring may age it out like any other. What keeps the batch’s keys held is its claims, which are held by presence rather than by any sequence, so a prepare left undecided for a ring’s worth of commits refuses exactly what it refused when it was young.
Invariants
| Invariant | Why |
|---|---|
| A sequence is never reused, across restarts included | Reuse would make two different writes indistinguishable |
| A drawn but undecided sequence is invisible | Every reader’s ceiling is the watermark, below which every sequence is decided; otherwise a reader sees half a batch |
| Every drawn sequence is decided, committed or aborted, on every path | The watermark waits on each one; an undecided sequence would hold every later reader’s ceiling down |
| A commit returns only once the watermark has passed its sequence | The caller’s next transaction must see what it just committed; publication is in order |
| No sequence is drawn a ring’s width above the watermark | The slot the watermark has yet to read must not be recycled underneath it |
| A write is validated against the version actually read | Validating against the snapshot alone misses read-modify-write races |
| A claim is compared by its key’s bytes, never by its hash alone | Two keys in one chain are two claims; a hash collision refused a commit that had no conflict |
| Claims are taken before the sequence is drawn | A commit sequenced below mine finished claiming before I drew, so my validation sees it; the other order lets two rivals miss each other |
| A prepare at repeatable read or above holds what it read | Phase two lands it above everything that committed in doubt; a writer of a key it read committing inside that window would leave it a stale read at its final position, and the prepared side cannot yield |
| A prepare holds the intervals it scanned as well as the keys | An insert inside a range its scan found empty is a phantom at the batch’s final position just as a changed key is a stale read |
| Phase two draws through the prepare’s own record | A commit drawn above the batch validates before the batch is applied, so only the claims can show it the batch below; a record still reading as prepared hides it |
| Every writing commit claims, at every level | A validating commit finds a writer below it in the claims until its version is in the store; a writer without claims was in neither between its draw and its apply |
| First-committer-wins counts a write claim below it | A writer without the promise may join a claim taken first and draw below it, landing a version the first-committer never saw |
| A read-committed write is checked against undecided prepares’ reads | It lands below their phase twos, where what they read would be stale |
| A prepare yields to another prepare’s write on what it read | Both are placed by their phase twos, so the batch that voted first may land below the reader |
| An interval is held before the draw and checked both ways | A point writer meets it in the table, and it meets the point writer in the list of commits in flight, so the two find each other whichever was first; without that a range delete and a write inside it could each validate against a set that did not yet hold the other |
| A scan’s footprint is validated like a read | A key another commit put inside the interval a scan covered is a phantom, whether it is in the store above the snapshot or still a claim in flight below this commit; refusing it is what makes serializable hold over predicates and not only over the keys it read |
Compaction may not drop above min_snapshot_seq | A live snapshot must still see what it could see |
| A flush retains against that floor too, not only a merge | A memtable holds the whole chain, so a flush that took the newest version alone would drop what the floor was protecting and a frozen reader would find a live key absent |
| A named snapshot is registered, not just remembered | The floor is the minimum the registry holds; a sequence kept outside it protects nothing, and reading there answers from whatever a merge happened to leave |
| Phase two draws a fresh sequence | The batch must land where decided, not where it voted |
| A prepare’s claims go only with its decision | Held by presence rather than by sequence, they neither age out of the ring nor need handing over to the sequence phase two commits at; one left behind after the decision would refuse every later writer of a finished transaction’s key |
| A failed phase two leaves the transaction prepared | A participant must not abandon a decision unilaterally |
| An undecided prepare pins its own log generation, and only that one | Its PREPARE record is the only copy of the batch. Pinning on a database-wide count instead keeps every log ever written whenever a coordinator always has one in flight |
| A decided prepare frees its generation at once | The commit record carries the write set and replay applies it inline, so nothing needs the original PREPARE |
| Recovery takes the pin, not the caller who adopts the batch | A database that reopens and never asks for its in-doubt list must still keep the only copy of one |