In this post I want to discuss my multiversion concurrency control implementation. Written in Java, it is very straightforward. We use Java threads (which are just native threads) to simulate concurrency in a simple database. See Runner for the scenario that runs. See TransactionC for the transaction that has contention.
When a transaction begins or restarts, it is assigned an identifier which is its timestamp. This number is unique to the transaction and increments for every transaction attempt. Runner will spin up 100 concurrent TransactionC. TransactionC will try to increment two numbers, A and B. A starts at 1 and B starts at 2 at the beginning of the simulation. Of course if you didn’t have multiversion concurrency control, these two numbers would not finish on 101 and 102 due to data races. You have to wait for the addition of the previous number before adding the next number.
When a transaction issues a Read, the fact that a read occurred is tracked. The read will only succeed if there is a committed value that has a version that is at a timestamp less than or equal to the readingg transaction’s timestamp. This essentially means that transactions can see their own writes but can only see old values and cannot see the values that are temporarily created by other transactions.
At commit time, we check the list of transactions that read the key A or B. If there are any that have a timestamp less than the current timestamp, then the current transaction is aborted and restarted. Those younger transactions “win” the chance to commit while everyone else has to restart. There is an exception to this which prevents two transactions committing at the same time – this is that if there is an older transaction that is ahead of us, then we let that transaction win.