Visibility Checker
Track: Data consistency. 6 stages. Languages: Go, Python, JavaScript, Rust.
Real databases let many readers and writers work at the same time without locking each other out. The trick behind that: every transaction gets its own fixed view of the data, decided the moment it starts. Build the piece that decides what a transaction can see. It is a small, simple function: given the history of what was written, committed, and cancelled so far, and which transaction is asking, work out the answer to a read. No threads, no timers, no real clock. Your code just looks at the actions it is given, in order, and decides what each read should return.
Implement New(), Begin() -> txID to start a transaction, Write(txID, key, value) to record a change, Commit(txID) to make those changes stick, Abort(txID) to cancel them, and Read(txID, key) -> (value, ok) to read a key the way that transaction should see it.
The rule for Read: a transaction always sees its own writes first, even before it commits. Other than that, it sees the data as it was when it started, meaning the newest value that was committed before it began. It never sees a write that is still open (not yet committed or cancelled) in another transaction, never a value committed after it began, and never a write that was later cancelled.
Example: transaction A begins, writes color = "red", and reads color back before committing.
| write | by | committed? | Read("color") from A sees |
|---|---|---|---|
| "red" | A | not yet | "red" (its own write, even though A has not committed) |
For help with the ideas behind this, read the notes.
Where it is used
- PostgreSQL gives each statement or transaction a snapshot of the data, so a normal read does not wait for a write to the same row, and a write does not wait for a read. Reads that lock rows on purpose, like
SELECT ... FOR UPDATE, are the exception. - MySQL's InnoDB keeps old versions of rows in its undo logs and rebuilds the version each transaction should see.
If a reader can see another transaction's unfinished write, it can act on money or stock that is later cancelled. This is called a dirty read, and it is the mistake the rules in this challenge prevent.
Stages
mv1: see your own writes before you commit (very easy)
A transaction writes a key and reads it back before it commits. It must see its own write.
The tester will verify: a transaction that has not committed yet still sees the value it just wrote.
mv2: only see what was committed before you began (easy)
One transaction commits a value. Later, after a second transaction has already begun, a third transaction writes and commits a new value for the same key. The second transaction must still see the first value, never the newer one.
| write | by | committed? | Read("color") from the second transaction sees |
|---|---|---|---|
| "red" | A | yes, before the reader began | "red" |
| "blue" | C | yes, but after the reader began | never this one |
Then the mirror case. A fourth transaction D begins and writes "green". A fifth transaction E begins while D is still open. Then D commits. D began before E, but it committed after E began, so E must still see "blue", never "green". What counts is when a transaction committed, not when it began.
The tester will verify: a value committed after a transaction began is invisible to it, even when the writer began first, and the value committed before it began is what it reads.
mv3: never see another transaction's unfinished write (medium)
Another transaction writes a key but has not committed or cancelled it yet. A transaction reading that key right now must not see that unfinished write.
| write | by | committed? | Read("color") from a third transaction sees |
|---|---|---|---|
| "red" | A | yes | "red" |
| "green" | C | still open, not committed | never this one, even though it happened more recently |
The tester will verify: an unfinished write from another open transaction is invisible to every other transaction.
mv4: cancelled writes stay invisible, and each reader gets its own version (hard)
A transaction writes a key and then cancels (aborts). That write must never become visible to anyone, including later readers. Separately, when a key has been committed more than once, each transaction must see the version that matches when it began, not always the newest one.
| write | by | committed? | visible to a reader that began right after? |
|---|---|---|---|
| "red" | A | yes | no, a newer version exists |
| "ghost" | X | no, X cancelled this write | never, to anyone |
| "blue" | C | yes, most recent | yes, this is the newest committed value |
The tester will verify: a cancelled write is never visible, and a transaction that began between two commits sees the one that was already committed, never one that came later.
mv5: many transactions mixed together (hard)
We run 200 actions in one long sequence over 3 keys named a, b, and c: starting transactions, writing values, reading values, committing, and cancelling, all mixed together, with several transactions open at once. Your code does not need threads, since the actions happen one at a time, in order, but it does need to get every rule above right at the same time.
The tester will verify: every answer your Read calls give, all the way through the 200 actions, matches our solution.
mv6: make reading fast even on long chains (hard)
Keep Read quick even after a key has been written and committed many times. Looking through every old version starting from the oldest shows up here. Starting from the newest version and stopping as soon as you find the one you can see does not. Example: if our solution takes 100 ms for a batch of calls, the limit is 150 ms, which is 1.5 times as long. Your solution must also make no more than 2 times as many memory allocations as our solution.
The tester will verify: your code takes at most 1.5 times as long and makes at most 2 times as many memory allocations as our solution, with every answer still correct.
Rules
- Standard library only. No third-party packages.
- A read sees the reading transaction's own writes first. Otherwise, it sees the newest value that was committed before that transaction began: never something still open, never something committed later, never something cancelled.
- Your store does not need threads, locks, or a real clock. It only has to look at the actions it is given, in order, and work out what each read should return.
- Keep reads fast on a key with many old versions: start from the newest version and stop as soon as you find one you can see, instead of scanning from the oldest.