Visibility Checker
What it is
Real databases let many readers and writers work on the same data at the same time, without one blocking the other. The trick behind this is called multi-version concurrency control, or MVCC: instead of keeping one copy of each value and locking it while someone reads or changes it, the database keeps several versions of each value, stamped with when they were committed. A transaction reads a snapshot, not whatever the latest value happens to be at that exact instant.
This way of reading is called snapshot isolation. It means: each transaction sees the data as it was when it started, no matter what anyone else does afterward.
The core idea
When a transaction begins, its view is fixed from that moment on. A read from that transaction follows three rules, in order:
- If this transaction has written this key itself, even without committing yet, it sees its own write.
- Otherwise, it sees the newest value that was committed before it began. Never something still open (not yet committed or cancelled) in another transaction, and never something committed after it began.
- If a write was later cancelled (aborted), it is as if that write never happened. It is never visible to anyone, not even after the cancelling transaction is long gone.
Example: three transactions, one key
| action | who | committed? |
|---|---|---|
| writes "red" | transaction A | yes, first |
| writes "ghost" | transaction X | no, X cancelled this write |
| writes "blue" | transaction C | yes, most recently |
A transaction that begins after all three of these finish reads "blue", the newest committed value. "ghost" is never visible to anyone, since X cancelled it. A transaction that had already begun right after A committed, but before C committed, still reads "red", even once C's "blue" exists, because its view was fixed earlier. Different transactions, reading at different moments, can correctly see different versions of the exact same key.
Why real databases do this
Picture a transaction reading from a key while another transaction is in the middle of writing to it. If the reader just read "whatever is there right now", it could see half a change, or a value that gets cancelled a moment later. The usual fix is to make the reader wait with a lock until the writer finishes, but that makes every reader wait on every writer, which gets slow fast.
Keeping old versions around solves this without any waiting: a reader just picks the version that matches when it began, and carries on, while writers keep adding new versions. Nobody has to block anybody. The two things actually in tension are speed (locks are simple but slow everyone down) and memory (every version you keep costs space), and this design trades a bit of the second for a lot of the first.
Real databases often track this with two hidden numbers on each row, usually called xmin and xmax, for the transaction that created that row's version and the one that deleted or replaced it. The idea is the same one at work here: a value's write and its cancellation play the same role.
Where you meet this
- PostgreSQL: "each SQL statement sees a snapshot of data", and for those MVCC locks "reading never blocks writing and writing never blocks reading". Reads that lock rows on purpose (
SELECT ... FOR UPDATE) and table locks still wait. (PostgreSQL MVCC) - MySQL's InnoDB keeps old row versions in undo logs and uses them to build the version a reader should see. (InnoDB multi-versioning)
- The cost: old versions must be cleaned up later. PostgreSQL does it with
VACUUM. (Routine vacuuming) InnoDB cannot clean up versions that an open transaction might still need, so its docs ask you to commit transactions regularly.
When to choose it: many readers and writers work on the same data at the same time, and readers must not wait for writers.
When not to: almost all work is writes to the same few rows. Versions do not help there, because two writers to one row still have to take turns. Long-running transactions are also a problem, because they keep old versions alive and the storage keeps growing.
Common bugs
- Ignoring a transaction's own writes, so it can't read back what it just wrote.
- Letting a reader see another transaction's write before that transaction commits (a dirty read).
- Returning the newest committed value, ignoring when the reader began, so a reader sees something committed after it started.
- Letting a cancelled transaction's writes leak through as if they had committed.
- Picking the wrong version right at the edge: a version committed at the exact same moment a reader began needs a careful, consistent rule, not a guess.
Check it yourself
Write down every write and every commit or cancel, in the order they happened, with a running number for "when". Then, for any transaction, find its own begin number and ask: what is the newest write to this key, committed strictly before that number, counting the transaction's own writes separately? That answer is what Read must return. Try it with three versions of the same key and readers that began at different points between the commits.
Keep it fast
Keep each key's versions in the order they were committed, newest last. A read can then start at the end and stop as soon as it finds a version it is allowed to see, which is usually one of the first few it checks. Scanning from the oldest version every time gets slower the longer a key has been written to, for no reason.
Learn more
PostgreSQL's own documentation on transaction isolation is a clear read once you have built this yourself. "A Critique of ANSI SQL Isolation Levels" is the classic paper on what different databases promise, and don't promise, about what a transaction can see.