How do I implement MVCC?

Question

I have located many resources on the web giving general overviews of MVCC (multi-version concurrency control) concepts, but no detailed technical references on exactly how it should work or be implemented. Are there any documents online, or books offline, that contain enough theory (and a bit of practical help, ideally) on which to base an implementation? I wish to emulate more or less what PostgreSQL does.

(For info I will be implementing it in SAS using SAS/Share - which provides some locking primitives and concurrent read/write access to the underlying data store, but nothing in the way of transaction isolation or proper DBMS features. If anyone is familiar with SAS/Share and thinks this is an impossible task, please shout!)

Answer 1

Transaction Processing: Concepts and Techniques and Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery are authoritative source of transaction processing.

Both these books are also mentioned in PostgreSQL Wiki.

Answer 2

A table in PostgreSQL can store multiple versions of the same row.

More, there are two additional columns:

• tmin - marking the transaction id that inserted the row
• tmax - marking the transaction id that deleted the row

The update is done by deleting and inserting a new record, and the VACUUM process collects the old versions that are no longer in use.

Answer 3

I wrote a blog post about this:

https://elliot.land/post/implementing-your-own-transactions-with-mvcc

Answer 4

I implemented MVCC in Java. See transaction, runner and mvcc code.

Imagine each transaction gets a number timestamp that goes up for each transaction. We have transactions 1 and 2 in this example.

Transaction 1 reads A and writes value (A + 1). The snapshot isolation creates a temporary version of (A) which transaction 1 owns. The read timestamp of A is set to Transaction 1.

If transaction 2 comes along at the same time and reads A, it will also read the committed A -- it wont see A + 1 because it hasn't been committed. Transaction 2 can see versions of A that are == lastCommittedA and <= transaction 2.

At the time transaction 2 reads A, it will also check the read timestamp of A and see that a transaction 1 is there and check transaction 1 timestamp < transaction 2 timestamp. Because 1 < 2 then the transaction 2 will be aborted because it already depends on an old value of A.