CSE Roadmap

Common tier · about 3 hours · 6 parts

Part 5 of 6 · 4 min read

Serializable snapshot isolation

Run on snapshots, then check at commit whether a premise went stale.

Serializable snapshot isolation

Think of a team who all draft plans on their own copies of a document. Nobody waits. At the deadline an editor checks: did anyone act on a fact that someone else has since changed? If so, that plan is sent back.

The book presents serializable snapshot isolation (SSI) as promising: full serializability with only a small penalty compared with plain snapshot isolation. It was first described in 2008. It is the serializable level in PostgreSQL since version 9.1, and FoundationDB uses a similar algorithm. It is young, so its performance is still being proven in practice.

The core idea is optimistic concurrency control: continue even when something may be dangerous, hope it turns out fine, and at commit check whether isolation was violated. If so, abort and retry. Two-phase locking is pessimistic: if anything might go wrong, wait.

Optimistic concurrency control

Optimistic concurrency control lets transactions run without blocking and checks at commit time whether they conflicted, aborting those that did.

Example: two clerks edit separate copies. At commit, the system finds that clerk 2 relied on a value clerk 1 changed, and sends clerk 2's work back.

The book's reasoning: a transaction acts on a premise, a fact true when it read (two doctors are on call). By commit the fact may have changed. The database cannot know how the application uses a query result, so it must treat any change in the result as a threat to the writes. SSI detects two cases.

  1. Stale reads of an MVCC snapshot. Transaction 43 reads and ignores a write by transaction 42 because 42 had not committed. If 42 commits before 43 does, 43's premise is wrong. The database tracks ignored writes and, at 43's commit, aborts it if any of them has committed since. It waits until commit rather than aborting at once: a read-only transaction need not abort, 42 may still abort, and so unnecessary aborts are avoided.
  2. Writes that change something already read. Using records similar to index-range locks (but not blocking), the database notes which transactions read a range. When another transaction writes into that range, the database notifies the readers that what they read may be outdated. Unlike 2PL, it does not block anyone. When a transaction commits, the database checks whether any such notice shows a conflict; if so, abort.

Performance. SSI cost depends on how much the database tracks. The book notes it tolerates long read-only queries well, because they run on a consistent snapshot, and that it can scale across machines. Optimistic methods suffer under high contention, since many aborts follow, and when the system is near its maximum, retries add load. Commutative atomic operations, like counters, reduce contention because their order does not matter. The abort rate also limits long read-write transactions, so SSI wants fairly short ones.

A worked example with the doctors. Alice and Bob are on call. T1 (Alice) and T2 (Bob) both start. Both read "count of doctors on call" = 2. T1 sets Alice off call and commits first. T2 sets Bob off call and tries to commit. The database sees that T2's read (count where on_call) was changed by T1's write. It aborts T2. On retry, T2 reads 1 and refuses to go off call. Result: one doctor stays. If T1 and T2 had touched different shifts, no notice would arise and both would commit.

Recipe Waits? Strength Weakness
Serial execution No, one at a time Simple and fast for short work One core, data in RAM, stored procedures
2PL Yes, readers and writers block Mature, precise Unstable latency, deadlocks
SSI No blocking, aborts at commit Fast read-only, no blocking Aborts under contention, newer

Common mistake

Treating serializable as free. It can mean waits (2PL) or retries (SSI). Code must be ready to retry an aborted transaction.

Interview angle

Answer in your head first, then open it.

What does serializable mean?

The result equals some one-at-a-time order. Mention that it stops write skew.

How would you get it?

Serial execution for small in-memory work, 2PL for mature locking, SSI for low-contention mixed work.

Why not always use serializable?

Cost: waits, deadlocks or aborts. Many systems accept weaker levels plus targeted safeguards.

Pessimistic versus optimistic?

Pessimistic waits when a conflict is possible; optimistic proceeds and checks. Optimism wins when contention is low.

Is 2PL the same as 2PC?

No. 2PL is about locks in one database; 2PC is about agreeing across nodes (module 9).

Check yourself:

  • Why does SSI wait until commit to abort a stale reader?
  • When does optimistic control perform badly?

Words you will meet

Word Plain meaning
Serializable Same result as some one-at-a-time order
Actual serial execution One transaction at a time on one thread
Stored procedure Transaction code submitted to the database ahead of time
Two-phase locking Shared and exclusive locks held until commit or abort
Shared lock Lock that allows other readers
Exclusive lock Lock that allows no one else
Deadlock Transactions each waiting for the other
Predicate lock Lock on all rows matching a condition, even future ones
Index-range lock Cheaper approximation of a predicate lock
Pessimistic Wait if a conflict is possible
Optimistic Proceed, check at commit
SSI Snapshot isolation plus commit-time conflict checks
Premise A fact a transaction relied on when it decided to write