Chapter 07

Timestamps, Multiversion & Snapshot Isolation

The optimistic answer to concurrency: order transactions by birth date and kill whoever arrives out of order. RTM/WTM bookkeeping, Thomas rule, multiversion timestamps in the exact variant the exercises use, snapshot isolation and write skew — plus where each class sits against 2PL, CSR and VSR.

Reading: ~40 min Interactive: 1 widgets Source: Polimi Data Base 2 2025/26 — Lecture 3.2 (Concurrency Control), slides 103–124 · Atzeni, Ceri, Fraternali, Paraboschi, Torlone — Basi di dati (2023)

01 · Mechanism

Timestamp concurrency control

Locking is pessimistic: it assumes collisions and prevents them. The optimistic alternative assumes collisions are rare — run the transaction, and validate as you go.

A timestamp is an identifier defining a total ordering of events. Each transaction gets one at birth, so transactions can be ordered by age: a smaller index means an older transaction. The principle is then blunt:

✓

The timestamp principle

A schedule is accepted only if it reflects the serial ordering of the transactions induced by their timestamps.

The scheduler keeps two counters per object:

$\mathrm{RTM}(x)$ — the highest timestamp among transactions that have read $x$ ;
$\mathrm{WTM}(x)$ — the timestamp of the transaction that performed the last write on $x$ .

and applies two rules to every incoming request, tagged with its transaction’s timestamp $ts$ :

Request	Rejected when	Otherwise
$r_{ts}(x)$	$ts < \mathrm{WTM}(x)$	grant; $\mathrm{RTM}(x) \leftarrow \max(\mathrm{RTM}(x), ts)$
$w_{ts}(x)$	$ts < \mathrm{RTM}(x)$ or $ts < \mathrm{WTM}(x)$	grant; $\mathrm{WTM}(x) \leftarrow ts$

Rejected means the transaction is killed — not delayed. Read the rules as: you may not read something a younger transaction has already overwritten, and you may not write something a younger transaction has already read or written. Either would mean the schedule contradicts the birth order.

The worked example the lectures use, starting from $\mathrm{RTM}(x) = 7$ , $\mathrm{WTM}(x) = 4$ :

request   response                      RTM(x)  WTM(x)
                                          7       4
r6(x)     ok   (6 > 4)                    7
r8(x)     ok   (8 > 4)                    8
r9(x)     ok   (9 > 4)                    9
w8(x)     NO   (8 < RTM = 9) → T8 killed
w11(x)    ok   (11 > 9 and 11 > 4)                11
r10(x)    NO   (10 < WTM = 11) → T10 killed

Note how a single young writer, w11, retroactively invalidates any older reader that has not yet arrived — r10 dies for having been born before a transaction that has already written. Many transactions are killed, and that is the method’s defining weakness.

Read the two rules asymmetrically

A read is checked against WTM only; a write is checked against both RTM and WTM. Forgetting the RTM half of the write rule is the single most common error in these tables — it is the clause that kills a writer arriving after a younger reader, which feels counter-intuitive until you remember that the reader has already committed to seeing an older value.

02 · Comparison

TS versus 2PL — incomparable, with witnesses

Neither class contains the other. Exams ask for the witness schedules, so learn all three.

In TS but not 2PL:      r1(x) w1(x) r2(x) w2(x) r0(y) w1(y)
In 2PL but not TS:      r2(x) w2(x) r1(x) w1(x)          ← and this one is serial!
In both, and not serial: r1(x) r2(y) w2(y) w1(x) r2(x) w2(x)

The second is the striking one: a serial schedule that timestamps reject, because T2 ran before T1 despite being younger. Timestamps enforce the birth order, not merely an order — which is exactly why they kill so much.

Where TS does sit is inside CSR:

Deep dive Why TS ⊆ CSR

Let $S$ be a TS schedule of $T_1$ and $T_2$ and suppose it is not conflict-serializable. Then its conflict graph has a cycle, so $S$ contains $op_1(x), op_2(x)$ with at least one a write, and later $op_2(y), op_1(y)$ with at least one a write.

Consider what happens when $op_1(y)$ arrives, after $op_2(y)$ :

If $op_1(y)$ is a read, it tries to read a value written by the younger $T_2$ , so $ts = 1 < \mathrm{WTM}(y) = 2$ and $T_1$ is killed.
If $op_1(y)$ is a write, it tries to write an object already read or written by the younger $T_2$ , so $ts = 1 < \mathrm{RTM}(y)$ or $ts < \mathrm{WTM}(y)$ , and $T_1$ is killed again.

Either way the schedule contains a killed transaction and is not in TS — contradiction.

Two practical notes complete the comparison. Basic TS also assumes commit projection, so dirty reads are still possible; the fix is to delay an acceptable read until the transaction that wrote the value has committed or aborted — the same effect as long-duration write locks, at the cost of buffering. And the verdict from the lectures on which mechanism wins in practice:

	2PL	Timestamps
Serialization order imposed by	conflicts	the timestamps
Blocked transactions	wait	are killed and restarted
Deadlocks	possible	impossible (but wound-wait/wait-die borrow the idea)
Cost of the failure mode	waiting	restarting — more expensive

Restarting costs more than waiting, so 2PL wins for the general case. Commercial systems mix the two: strict 2PL for writes, multiversion timestamps for reads.

03 · Refinement

Thomas rule: skip, do not kill

A cheap improvement to the kill rate, built on one observation: some rejected writes did not need to happen at all.

If a write arrives with $ts < \mathrm{WTM}(x)$ — a younger transaction has already written $x$ — then this write is obsolete. Nobody will ever read its value, because the newer value already sits there. So instead of killing the transaction, simply skip the write:

Request	Basic TS	With Thomas rule
$r_{ts}(x)$	kill if $ts < \mathrm{WTM}$	unchanged
$w_{ts}(x)$	kill if $ts < \mathrm{RTM}$ or $ts < \mathrm{WTM}$	kill if $ts < \mathrm{RTM}$ ; skip if $ts < \mathrm{WTM}$ ; else grant

The RTM clause survives untouched — a write that a younger transaction has already read past cannot be skipped, because that reader saw the old value and the write would have changed what it should have seen.

Thomas rule does not enlarge the class within VSR

It is tempting to file TS-with-Thomas as “TS but better”. The lectures show it escapes the hierarchy instead. Take w2(x) w1(x) r2(x): Thomas skips w1(x) as obsolete, and the resulting behaviour matches neither serial order — against T1 T2 the final write differs, against T2 T1 the reads-from for r2(x) differs. So the schedule is not even in VSR. Skipping a write changes what the schedule means, which is precisely what view equivalence tracks.

2025-07-02-q12025Q01Schedule classificationhard12 pts

Consider the schedule $$S = r_1(X)\; w_2(X)\; w_3(Z)\; w_1(X)\; w_5(X)\; r_6(Z)\; r_5(Y)\; r_3(Y)\; r_3(Z)\; r_5(X)\; r_2(Y)\; w_5(Y)\; r_5(Z)$$ Establish membership of S in VSR, CSR, 2PL, TS Mono, TS Mono with Thomas Rule, and TS Multi (usual conventions used in the exercises). Justify tersely, using class inclusion whenever possible.

04 · Mechanism

Multiversion timestamps — and the variant the exam uses

The best idea in the chapter: writes create new versions instead of overwriting, so a late reader can still be served the value it should have seen. Reads never fail.

Each object $x$ keeps $N \ge 1$ active versions. The $i$ -th has its own write timestamp $\mathrm{WTM}_i(x)$ ; there is a single global $\mathrm{RTM}(x)$ . Old versions are discarded once no transaction can still need them.

The read rule — always accepted — selects the version that was current at the reader’s birth:

✓

Version selection

For $r_{ts}(x)$ : if $ts \ge \mathrm{WTM}_N(x)$ take the newest version $N$ ; otherwise take the $k$ with $\mathrm{WTM}_k(x) \le ts < \mathrm{WTM}_{k+1}(x)$ .

For writes there are two variants, and the difference matters enormously for the exam.

Variant A — 'in theory'

$w_{ts}(x)$ is rejected only if $ts < \mathrm{RTM}(x)$ . A write older than the newest version is still accepted: a new version is inserted and the list is re-sorted. The lectures label this “what can be done in theory” and say plainly it is not the one used in the exercises.

Variant B — snapshot isolation (use this one)

$w_{ts}(x)$ is rejected if $ts < \mathrm{RTM}(x)$ or $ts < \mathrm{WTM}_N(x)$ . Writes must arrive in timestamp order; a late writer is killed. This is what real systems based on snapshot isolation do, and the slide states it is the variant used in the exercises.

Run the same request stream through both, from $\mathrm{RTM}(x) = 7$ , $N = 1$ , $\mathrm{WTM}_1(x) = 4$ :

request    Variant A (theory)              Variant B (exam)
r6(x)      ok                              ok
r8(x)      ok, RTM=8                       ok, RTM=8
r9(x)      ok, RTM=9                       ok, RTM=9
w8(x)      NO — 8 < RTM=9, T8 killed       NO — 8 < RTM=9, T8 killed
w11(x)     ok, WTM2=11, N=2                ok, WTM2=11, N=2
r10(x)     ok on version x1 (not killed)   ok on version x1
r12(x)     ok on version x2                ok on version x2
w14(x)     ok, WTM3=14, N=3                ok, WTM3=14, N=3
w13(x)     ok — insert and re-sort         NO — 13 < WTM_N=14, T13 killed

The streams agree until the final request. Note what multiversioning bought in both: r10(x) — which basic TS killed — is now served the old version and survives. Versions rescue readers, never writers.

TS Multi is graded in every classification exercise — and exempted most often

The classification question asks for TS Multi in all 8 of the papers that set it, and the marking is per class. It is also the item the professors most frequently allow reduced-workload students to omit — 5 of the 14 sessions (2024-01-24, 2025-07-02, 2025-09-05, 2026-01-22, 2026-06-12), more than any other topic, which is a fair signal of its difficulty. Use variant B: every published solution applies it, and the phrase in the exam text — “with the conventions adopted for TS Multi under Snapshot Isolation, used for the exercises” — is telling you so directly.

Worked exam Filling a TS-Multi table (exam 2026-01-22)

The schedule

S = r1(y) w2(x) r1(x) r1(z) w1(x) r2(z) r3(x) w1(z) w3(y). All counters start at 0. We track RTM and WTM per object and note every kill.

r1(y) — a read, always accepted

Version selection is trivial (only the initial version exists). RTM(y) ← 1.

w2(x) — first write on x

$ts = 2 \ge \mathrm{RTM}(x) = 0$ and $\ge \mathrm{WTM}_N(x) = 0$ . Accepted: a new version with WTM = 2.

r1(x), r1(z) — reads survive

r1(x) is accepted and served the version visible at timestamp 1, i.e. the initial one — not T2’s. RTM(x) ← max(0, 1). r1(z) likewise.

w1(x) — the kill

$ts = 1 < \mathrm{WTM}_N(x) = 2$ . Under variant B this is rejected and T1 is killed. Its later w1(z) belongs to an already-killed transaction and needs no separate analysis.

The rest, and the verdict

r2(z), r3(x) and w3(y) all pass. Because a transaction was killed, S ∉ TS Multi — and that is the whole answer for this class. Under variant A the same write would have been inserted and re-sorted, giving the wrong verdict.

Object x has RTM(x)=5 and a single version with WTM=3. Request w4(x) arrives. Under the exam's TS-Multi conventions, what happens?

05 · Practice

Snapshot isolation and write skew

Multiversioning made a new isolation level possible, and Oracle, MySQL, PostgreSQL, SQL Server and MongoDB all ship it. It is not serializable, and it is worth knowing exactly how it fails.

Under snapshot isolation there is no RTM at all — only write timestamps. Every transaction reads the version consistent with its own start time (its snapshot) and defers its writes to the end. When it tries to write a row, it first checks whether anyone else has modified that row since it began; if so, the snapshot view is stale and the transaction is rolled back or retried. This is first-committer-wins, and it is another optimistic method.

The benefit is large: reads never block writes and writes never block reads, so read-heavy workloads run without lock contention.

The cost is that snapshot isolation does not guarantee serializability, and the counter-example is elegant:

T1: update Balls set Color = 'White' where Color = 'Black';
T2: update Balls set Color = 'Black' where Color = 'White';

Any serial execution ends with all balls one colour: run T1 then T2 and everything is black; run T2 then T1 and everything is white. Under snapshot isolation, if both start from the same snapshot, neither sees the other’s changes, and they simply swap the two colours. That final state is reachable by no serial order at all. The anomaly is called write skew, and it arises because the two transactions write disjoint rows — so the first-committer-wins check never fires.

06 · Distributed

Assigning timestamps without a global clock

Everything above assumed timestamps could be compared. In a distributed system there is no global time, so they have to be manufactured.

The syntax is timestamp = event-id.node-id, with event ids unique at each node, and the ordering is lexical: 5.1 occurs before 5.2. Synchronization comes from messages — for any message $m$ , $\mathrm{send}(m)$ precedes $\mathrm{receive}(m)$ .

The Lamport method enforces that with a bumping rule: you cannot receive a message from the future, so if a message arrives carrying a timestamp greater than your last emitted one, you advance your local timestamp past it. Mnemonically: if I receive a message from you whose timestamp exceeds my last one, I update my current timestamp to exceed yours.

Messages received “from the present or past” need no adjustment and the local sequence continues normally; messages “from the future” force a bump, leaving a gap in the local event numbering. In the lectures’ two-node trace, a receive event at node 1 is stamped 8.1 precisely so that it exceeds the send event 7.2 that caused it.

Load-bearing ideas

Timestamps order by birth date. Read killed if $ts < \mathrm{WTM}$ ; write killed if $ts < \mathrm{RTM}$ or $ts < \mathrm{WTM}$ . The asymmetry — reads check one counter, writes two — is the most common slip.
TS ⊂ CSR, but TS and 2PL are incomparable. Learn all three witness schedules, including the serial schedule that timestamps reject.
2PL wins in practice because restarting costs more than waiting; real systems combine strict 2PL on writes with multiversion timestamps on reads.
Thomas rule skips an obsolete write ( $ts < \mathrm{WTM}$ , passing the RTM test) instead of killing — and the resulting class is not inside VSR.
Multiversion rescues readers, never writers. Reads are always accepted and served the version visible at their timestamp; a late write still dies.
Use variant B (snapshot isolation) in exercises — reject when $ts < \mathrm{RTM}(x)$ or $ts < \mathrm{WTM}_N(x)$ . The slides and every exam text say so explicitly.
Snapshot isolation drops RTM entirely, defers writes, and resolves conflicts first-committer-wins — permitting write skew, where two transactions writing disjoint rows reach a state no serial order produces.
Exam radar. Re-derive before the exam: the RTM/WTM table for a full schedule under variant B, naming each kill and its clause; the three witness schedules for TS versus 2PL; and Thomas rule’s skip-versus-kill boundary.