Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 79 ยท Concurrency Control

MVCC and Optimistic Concurrency Control

Learn multiversion concurrency control: version chains, visibility rules, snapshot isolation, write skew and optimistic validation, with live Python simulations.

Locking makes readers and writers wait for each other. Timestamp ordering aborts whoever arrives too late. Multiversion concurrency control (MVCC) avoids both problems with a simple trick: do not overwrite data, add a new version of it. A reader keeps looking at the versions that existed when it started, a writer creates new ones, and the two never block each other. Most modern engines (PostgreSQL, MySQL's InnoDB, Oracle, SQL Server in snapshot mode) are built on this idea.

Optimistic concurrency control (OCC) is a close relative. Instead of preventing conflicts while a transaction runs, it assumes conflicts are rare, lets the transaction work on private copies, and checks at the end whether anything went wrong. In this lesson you will build both ideas in Python and see exactly where they can go wrong.

Do not overwrite, append

Version chain Each item keeps several versions.
Snapshot A transaction sees the world as of its start.
Readers never block Writers add versions instead of waiting.

The price: old versions must be cleaned up later.

1 / 2

Versions and visibility

In an MVCC store, each write to item X creates a new version instead of changing the old one. A version records the value and which transactions it is visible to, usually through the commit timestamps of its creator and of whoever replaced it:

TEXT
X: [ v1: value 10, created at 1 ] -> [ v2: value 15, created at 4 ] -> [ v3: value 20, created at 9 ]

When transaction T starts, it receives a snapshot: in the simplest scheme, the number of the last transaction that had committed. The visibility rule is then:

T reads the newest version that was committed at or before its snapshot, plus the versions T created itself.

So a transaction that started at time 5 reads v2 of X (15) even after v3 has been committed at time 9. It sees a stable, consistent picture for its whole life. This gives you repeatable reads and removes the classic read anomalies without any read locks.

Writers do not wait for readers either: they just append a version. Two writers of the same item are the one case that still needs a rule, as you will see in a moment.

Snapshot isolation

An MVCC store with the rules "read from your snapshot" and "if two concurrent transactions write the same item, only one may commit" is said to provide snapshot isolation (SI). The second rule is usually called first committer wins: when T tries to commit, the system checks whether any item in T's write set received a newer committed version after T's snapshot. If so, T has a write-write conflict and is aborted.

The simulator below keeps a version chain per item. Run it and look at the printed chains and at the lost-update case.

Python A tiny MVCC store with snapshot isolation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the second scenario both transactions read 100 and both wanted to add to it. Without protection one increment would be silently lost. Under snapshot isolation T2 is aborted and the application retries it, which then reads 110 and writes 130.

Write skew: what snapshot isolation does not prevent

Snapshot isolation is strong, but it is not serializable. Its blind spot is write skew: two transactions read overlapping data, then write different items. Because their write sets are disjoint, first-committer-wins sees no conflict, yet together they can break a rule that spans both items. (You met this anomaly in Isolation Levels and Concurrency Anomalies.)

The standard story is a hospital rule: at least one doctor must stay on call. Ana and Ben are both on call. Each checks that the other is on call and then takes themselves off.

Python Write skew under snapshot isolation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both commits succeed and nobody is on call. In a serial execution the second doctor would have seen the first one off duty and refused. Engines that offer true SERIALIZABLE on top of MVCC (PostgreSQL's SSI, for example) detect these dangerous read-write dependency patterns and abort one of the transactions. Another practical fix is to make the conflict visible: have both transactions write the same "guard" row, or lock the rows they read (SELECT ... FOR UPDATE in server databases).

Optimistic concurrency control

OCC divides each transaction into three phases:

  1. Read phase. The transaction reads items and does all its writes on private copies. Nothing is visible to others. The system records the read set and the write set.
  2. Validation phase. At commit time, the system checks whether the transaction can be serialized. In the common backward validation, it asks: did any transaction that committed after I started write something I read? If yes, my reads are stale and I must abort.
  3. Write phase. If validation succeeded, the private writes are installed and become visible.

This is the same bet as timestamp ordering: conflicts are rare, so check at the end instead of paying a locking cost all the time. A practical version, widely used in web applications, stores a version number on each row and writes with a condition: UPDATE ... SET ..., version = version + 1 WHERE id = ? AND version = ?. If zero rows are updated, someone else got there first and the application re-reads and retries.

Python Optimistic validation with retry

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three clients read version 0, but only the first commit validates. The other two are aborted and retried, and the counter ends at 3 with no lost update. Notice the cost model: with three conflicting clients two did their work twice. If most transactions collide on the same hot row, OCC wastes more effort than waiting on a lock would. OCC is best for read-mostly workloads and short transactions.

The cost of versions

Keeping old versions is not free:

  • Garbage collection. A version can be removed only when no running transaction can still see it. A long-running transaction therefore prevents cleanup and makes tables bloat. PostgreSQL calls its cleaner VACUUM; InnoDB purges old row versions from its undo log.
  • Write amplification. An update may write a whole new row version and touch indexes.
  • Snapshot management. The system has to track which transactions are active to decide visibility.

Different engines store the chain differently: some keep all versions in the table and mark old ones dead, others keep the newest in the table and rebuild older versions from an undo log. The details are engine-specific and are not something you can run here; the principle (newest version in the chain, older ones for readers who need them) is the same.

SQLite: WAL mode is not full MVCC

SQLite deserves a precise description because people often assume "it supports snapshots, so it is MVCC". SQLite allows one writer at a time for the whole database. In its default rollback-journal mode, a writer blocks readers while it commits. In WAL mode (write-ahead log, see Logging and Write-Ahead Logging), new pages are appended to a separate log file, so readers can continue using the unmodified database file plus the part of the log that was committed when they started. Readers see a consistent snapshot and do not block the writer, and the writer does not block readers. But there is still only one writer, so write-write conflicts show up as "database is locked" errors, never as snapshot-isolation aborts. Compared to a server engine, you get snapshot reads with a very simple concurrency model.

You turn WAL on for a file-based database with this statement (read-only here, because the browser database lives in memory and there is no file to log):

SQL
PRAGMA journal_mode = WAL;

The next example shows the idea of versions in plain SQL. It keeps a history table where each row has a validity interval, and an "as of version N" query plays the role of a snapshot.

SQL Versions as validity intervals in SQL

Press Run (or Ctrl + Enter) to see the result here.

Engines are more sophisticated, but this is the heart of the visibility rule: pick the version whose validity interval contains the snapshot number.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A transaction T starts at snapshot 5. Item X has versions committed at times 2, 4 and 8. Which version does T read?

    T sees the newest version committed at or before its snapshot. Time 4 is the latest that is not after 5. Readers do not wait.
  2. 2. Two concurrent transactions each read two accounts and then each update a different one, breaking a rule that involves both. Snapshot isolation allows it because

    This is write skew. The conflict is between a read of one transaction and a write of the other, which snapshot isolation does not check.
  3. 3. In optimistic concurrency control, when is a conflict detected?

    OCC lets transactions run on private copies and checks whether their reads are still valid when they ask to commit.
  4. 4. Why can one very long-running transaction hurt an MVCC database?

    A version can be removed only when no transaction can still need it. A long snapshot keeps many old versions alive, so tables and undo logs grow.
  5. 5. SQLite in WAL mode lets readers and a writer work at the same time. What is still true?

    WAL gives readers a stable snapshot, but SQLite still allows a single writer for the database, so writers queue behind one another.

Summary

  • MVCC keeps several versions per item; a transaction reads the newest version committed at or before its snapshot, so readers and writers do not block each other.
  • Snapshot isolation adds first-committer-wins for write-write conflicts, which prevents lost updates but still permits write skew.
  • Optimistic concurrency control works in read, validation and write phases; it wins when conflicts are rare and loses when many transactions fight over the same rows.
  • Old versions must be garbage collected, and long-running transactions delay that cleanup.
  • SQLite WAL mode gives snapshot reads next to a single writer; it is not the multi-writer MVCC of server databases.

Next: Failure Classification and Recovery Goals.