MVCC
Two transactions can each read a consistent picture of the database, each write something the other did not, and both be allowed to commit, leaving a state that no order of running them one after another could have produced. That is not a fault in an implementation. It is what the design costs, and what it buys is the property that makes it worth having: a reader never waits for a writer and a writer never waits for a reader. Every one of the 252 ways two transactions can interleave is run here, and the number that come out unaccountable is not small.
New to how a database keeps transactions apart? Start here
When two pieces of work touch the same data at once, something has to stop them from seeing each other half-finished. The old answer is a lock: whoever gets there first holds the row, and everybody else waits. It is correct and it is slow, and the slowest case is the common one, a long report reading rows that a short update wants to change.
The other answer is to stop overwriting. A change writes a new version of the row and leaves the old one alone, so a reader that started earlier can carry on reading the version that was current when it began. Nobody waits for anybody. What that costs is the subject of this page: the readers are each looking at a consistent past, and two of them can act on facts that were never true at the same moment.
Two things at once
A program you write reads top to bottom, one step after the last. Once two of them run at the same time, that stops being true of the pair: their steps interleave, in an order nobody chose and nothing wrote down.
The hard part is that the order is not random so much as unconstrained. Any interleaving the hardware permits is one you will eventually get, on someone else's machine, months later, on the run you were not watching. So the machines in this topic are not about making the right order happen. They are about which orders are possible, which of those are wrong, and what it costs to rule them out.
The machine for this idea on its own is Race, if you would rather press it than read about it.
The reader never waits, because it is reading a version nobody is writing
1 Two readers and a writer on one row, and which version of it each of them is entitled to see
Three workloads, each two transactions over two rows. Step through the schedule one operation at a time and watch what each transaction is entitled to see. Nothing here is stored: every value in the table is worked out from the versions that exist at that instant.
| at | who | does | and gets |
|---|
before:
after:
2 What those versions let the scheduler permit: the commits snapshot rules accept, and the one they refuse
Two transactions of five operations interleave in exactly 252 ways, and every one of them is run. The scheduler makes one test and one only: at commit, did anything this transaction wrote get written by somebody who committed after it started?
| outcome | how many | share |
|---|
3 Whether the result could have come from any serial order at all, decided by a mechanism that shares no code with the scheduler
A different question, asked by different code: could what happened have happened in some order where the transactions ran one after another? It is answered twice over, by looking for a cycle in the serialisation graph and by running every serial order and comparing.
| question | answer |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every way two five-step transactions can interleave is generated, not sampled | yes | 252 interleavings, which is C(10,5); each one is run through the scheduler and then judged twice more |
| snapshot isolation lets both transactions commit and the result is not serialisable | yes | 250 of 252 interleavings of the write-skew workload commit both transactions and produce a history no serial order can account for; the scheduler tested the only thing it tests, which is whether the write sets overlap, and they do not |
| the graph and the definition are asked separately and agree on every one | yes | a cycle in the serialisation graph and the absence of any equivalent serial order are computed by different code from the same history: 250 and 250 on write skew, 0 and 0 on lost update, 0 and 0 on the read-only workload |
| the anomaly it is praised for stopping really is stopped | yes | on the lost-update workload the two write sets overlap, so 250 of 252 interleavings abort a transaction outright and none of the rest is unserialisable |
| the reader is never made to wait and never sees a half-finished write | yes | on the read-only workload no interleaving aborts anything and none is unserialisable: the reader takes no locks, blocks nobody and reads a version that is finished and cannot change under it |
| in the broken case each transaction read a row the other was replacing | yes | the cycle is T1 -> T2 -> T1, which is what having no serial order looks like when it is drawn |
| serialisable snapshot isolation is not offered here as the fix | yes | it exists, it works, and it works by detecting exactly the structure drawn above and aborting one of the transactions, which costs the property this page opened with -- that nobody waits and nobody is turned away; naming it as a free repair would be the overclaim this page is written to avoid |
| two rows and two transactions is a model, and the anomaly is not confined to it | yes | the enumeration is complete for the model it states and says nothing about three transactions, predicates or phantom rows; what generalises is the shape, which is a cycle of reads against writes, and not the count |
What is real here, and what is not
Two rows and two transactions is a model, and the count is a property of the model
252 is C(10,5), the number of ways two five-operation transactions can interleave. Three transactions, or predicates instead of single rows, or phantom rows appearing mid-transaction, all change the arithmetic and none of them changes the shape. What generalises is the structure -- a cycle of reads against writes with nothing in the scheduler that looks for it -- and not the number.
Snapshot isolation and MVCC are not the same thing
MVCC is keeping several versions of a row. Snapshot isolation is a rule about which version a transaction may see and when it may commit. They are almost always paired and they are not the same, and a system can keep versions and offer something stronger. This page models the common pairing and says so rather than letting the two words stand in for each other.
First-committer-wins is one of two implementations, and the other aborts earlier
The scheduler modelled here detects a write-write conflict when the second transaction tries to commit. Several real systems detect it when the second transaction tries to WRITE, and abort it there instead. The set of outcomes is the same and the moment of the abort is not, so a schedule that commits here can fail earlier in a real system. Nothing on this page rests on which of the two it is.
Serialisable snapshot isolation is not offered as the fix
It exists and it works, by detecting the structure this page draws and aborting one of the transactions. That is the right answer for a database and it costs the property the page opened with: under it, transactions do wait to be turned away. Presenting it as a free repair would be the same overclaim as offering three-phase commit as the repair for a blocking commit protocol, which this site also declines to do.
The graph is a sufficient test and the brute force is the definition
A cycle in the multiversion serialisation graph proves there is no equivalent serial order. The absence of a cycle is the practical test that real systems approximate, and it is not in general the same question. So the page asks both, from the same history, in code that shares nothing: the definition is answered by running every serial order and comparing what was read and what was left behind. On every one of the 756 histories here they agree, and if they ever stopped agreeing the page would say the graph was wrong, not the definition.
1978 is the dissertation, and the anomaly was not named for another seventeen years
Reed's dissertation is September 1978 and describes keeping several versions rather than overwriting. Snapshot isolation as a named level, and write skew as a named anomaly, arrive with Berenson and his co-authors in 1995, which is where the term on this page comes from. Seventeen years separate the mechanism from the careful account of what it does not guarantee, and that gap is the ordinary shape of this kind of work rather than a lapse.
Sources
- David P. Reed, Naming and Synchronization in a Decentralized Computer System, MIT dissertation, September 1978.
- Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil and Patrick O'Neil, A Critique of ANSI SQL Isolation Levels, Microsoft Research Technical Report MSR-TR-95-51, June 1995; also SIGMOD 1995.
- Logical Art, the studio this belongs to.