CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 3 of 7 · 4 min read

Read skew and snapshot isolation

Seeing a changing database at two different moments, and the fix of a consistent snapshot.

Think of counting the cash in two tills while a cashier moves money from one to the other. You count till 1 before the money arrives and till 2 after it has left. The total comes out 100 short, although every count was correct at the moment it was made.

The book describes this with Alice's accounts: $500 in each of two accounts. A transfer of $100 happens while she looks. She sees one account before the incoming payment (500) and the other after the outgoing transfer (400), so $900 in total. If she reloaded, she would see consistent balances. This anomaly is a non-repeatable read or read skew: reading the same account again would give a different value. The book notes the word "skew" has two uses; here it means a timing anomaly.

Read skew is allowed under read committed, since each balance was committed when read. Some situations cannot tolerate it:

  • Backups. A backup of a large database may take hours. If it copies some parts before a change and some after, restoring it makes the inconsistency permanent.
  • Analytic queries and integrity checks. A query that scans a large part of the database gives nonsense if the data changes during the scan.

Snapshot isolation

Snapshot isolation gives each transaction a consistent snapshot of the database: everything committed at the moment the transaction started. Later changes by other transactions are invisible to it.

Example: a backup starts at 10:00. It sees the database as of 10:00 throughout, however long it takes.

It is a boon for long read-only queries. It is supported by PostgreSQL, MySQL with InnoDB, Oracle and SQL Server. Its key principle: readers never block writers, and writers never block readers. Writes still use locks to prevent dirty writes, but reads need no locks.

How it works: multi-version concurrency control (MVCC). The database keeps several committed versions of each object side by side, since different transactions may need to see different points in time.

MVCC (multi-version concurrency control)

MVCC keeps several versions of each row, each tagged with the transaction that created it and the transaction that deleted it, so that every transaction can read the version that was current at its snapshot.

Example: when a transaction changes a balance from 500 to 400, the old row is marked deleted by that transaction and a new row of 400 is created by it. Both exist until nobody needs the old one.

The book describes PostgreSQL's way. Each transaction gets a unique, always-increasing transaction id (txid). A row has a created_by field and a deleted_by field. An update is a delete plus a create. A garbage collector later removes old versions that no transaction can see.

Visibility rules. When a transaction reads, it sees a row only if:

  1. The creating transaction had committed before this transaction began; and
  2. The row is not marked deleted, or the deleting transaction had not committed when this one began.

Put the book's four rules more simply: at the start, the database lists the transactions in progress, and ignores their writes even if they commit later. Writes of aborted transactions are ignored. Writes by transactions with a later id are ignored. All other writes are visible.

A worked example. Account 2 holds 500 (row created by txid 5). Transaction 12 starts. Transaction 13 starts and reduces account 2 to 400, then commits.

Row created_by deleted_by
balance 500 5 13
balance 400 13 (empty)

Transaction 12 reads account 2. The row "400" was created by 13, a later id, so it is invisible. The row "500" is marked deleted by 13, a later transaction, so the deletion is invisible and the row stays visible. Transaction 12 sees 500, as of its start. A new transaction 14 sees 400.

Names differ: the book notes that snapshot isolation is called repeatable read in PostgreSQL and MySQL, and "serializable" in Oracle, which is confusing. The SQL standard's definitions are ambiguous, so one must read the documentation of the database used. Read committed typically uses a new snapshot for each query, and snapshot isolation uses one snapshot for the whole transaction.

Check yourself:

  • A backup runs for 3 hours under read committed. What can be wrong with the copy?
  • Which rule lets a transaction ignore a change committed after it started?