Serializability, two-phase locking and timestamps

Part of the free LogicWiz SQL & Databases course, Module 16: Inside the DBMS. The queries and practice run in the app on real Postgres.

Two Tatkal bookings run at once. Each reads "1 seat left", each books it, and the train is overbooked. Running them one after the other would have been safe. When is mixing their steps just as safe as running them in order?

You'll learn to

• Find conflicting operations and draw the precedence graph of a schedule
• Decide whether a schedule is conflict serializable, and find an equal serial order
• Apply 2PL, strict 2PL and timestamp ordering rules to a schedule

Learn

Schedules and conflicts

A schedule is the order in which the steps of several transactions actually run. We write R1(A) for "T1 reads A" and W2(A) for "T2 writes A".

• A serial schedule runs one transaction completely, then the next. Always safe, but slow.
• A schedule is serializable if it has the same effect as some serial order.

Two operations conflict when all three hold:

1. they belong to different transactions,
2. they touch the same item,
3. at least one is a write.

Swapping two conflicting operations can change the result. Swapping non-conflicting ones never does.

Which pairs conflict? (same item, different transactions)

The precedence graph

To test a schedule, draw a precedence graph:

• one node per transaction;
• an edge Ti → Tj whenever an operation of Ti conflicts with a later operation of Tj.

The edge means "Ti must come before Tj in any equal serial order".

• No cycle: the schedule is conflict serializable. A topological order of the graph is an equal serial schedule.
• A cycle: it is not conflict serializable. T1 would have to come both before and after T2.

The lost update, as a table

-- R1(A) R2(A) W1(A) W2(A)
SELECT DISTINCT a.txn AS from_txn, b.txn AS to_txn
FROM schedule a
JOIN schedule b
  ON a.item = b.item
 AND a.txn <> b.txn
 AND a.step < b.step
 AND (a.op = 'W' OR b.op = 'W')
ORDER BY from_txn, to_txn;

A self-join lists every conflicting pair in time order. R1(A) before W2(A) gives T1 → T2; R2(A) before W1(A) gives T2 → T1. A cycle: this schedule is not conflict serializable, and indeed one of the two updates is lost.

Interleaved, yet serializable

-- R1(A) W1(A) R2(A) R1(B) W2(A) W1(B) R2(B) W2(B)
SELECT DISTINCT a.txn AS from_txn, b.txn AS to_txn
FROM schedule a
JOIN schedule b
  ON a.item = b.item
 AND a.txn <> b.txn
 AND a.step < b.step
 AND (a.op = 'W' OR b.op = 'W')
ORDER BY from_txn, to_txn;

Every conflict points T1 → T2, so there is no cycle. The schedule is conflict serializable and equal to the serial order T1, T2, even though their steps are mixed.

Common slips when drawing the graph: adding an edge for two reads, or for operations on different items; drawing the arrow backwards (it goes from the earlier operation's transaction to the later one's); and stopping at the first edge per pair. One edge in each direction between the same two transactions is already a cycle.

Two-phase locking (2PL)

Locks: S (shared) to read, X (exclusive) to write. S is compatible with S; X is compatible with nothing.

2PL splits each transaction into two phases:

1. Growing: it may acquire locks, never release.
2. Shrinking: once it releases any lock, it may never acquire another.

2PL guarantees conflict serializability, but it can deadlock and it allows cascading aborts (T2 reads what T1 wrote, then T1 aborts).

Strict 2PL holds every X lock until commit or abort, so nobody reads uncommitted data: no cascading aborts. Rigorous 2PL holds all locks until the end. Postgres row locks work the strict way.

Timestamp ordering

No locks: each transaction gets a timestamp TS(T) when it starts, and the schedule must behave like the timestamp order. Each item X remembers R-TS(X) and W-TS(X), the largest timestamps that read and wrote it.

• T reads X: if TS(T) < W-TS(X), a younger transaction already wrote X, so abort T. Otherwise read, and set R-TS(X) = max(R-TS(X), TS(T)).
• T writes X: if TS(T) < R-TS(X) or TS(T) < W-TS(X), abort T. Otherwise write, and set W-TS(X) = TS(T).
• Thomas write rule: if TS(T) < W-TS(X) but not < R-TS(X), just skip the outdated write and carry on.

Aborted transactions restart with a new timestamp. There is no waiting, so no deadlock.

Also asked: view serializability is wider than conflict serializability. Every conflict-serializable schedule is view serializable; a view-serializable one that is not conflict serializable always has a blind write (a write without a read first). Testing view serializability is NP-complete. Recoverable schedule: a transaction commits only after every transaction it read from has committed. Cascadeless: it reads only committed data. Strict 2PL gives both.

In one line

Conflict = different transactions, same item, at least one write; precedence graph with no cycle = conflict serializable; 2PL guarantees it (but can deadlock), strict 2PL also stops cascading aborts.

Interview corner

How do you test whether a schedule is conflict serializable?

Draw the precedence graph: one node per transaction and an edge Ti → Tj for each conflicting pair where Ti's operation comes first. If the graph has no cycle, the schedule is conflict serializable, and any topological order is an equivalent serial schedule.

What is two-phase locking, and what problem does strict 2PL fix?

Under 2PL a transaction acquires all its locks before releasing any (growing, then shrinking phase), which guarantees conflict serializability. Basic 2PL may release a write lock before commit, so another transaction can read uncommitted data and must abort if the first one does (cascading abort). Strict 2PL holds write locks until commit or abort, which prevents that.

Locking vs timestamp ordering?

Locking makes conflicting transactions wait, which can cause deadlocks. Timestamp ordering never waits: a transaction that arrives too late for an item is aborted and restarted, so there are no deadlocks but more restarts. MVCC databases like Postgres mostly avoid both costs for reads by keeping several versions of each row.