We are mostly following the Multi-Version Concurrency Control system described in thtransactionsis HyperDB related paper.

MVCC version maintenance and access

The goal of this chapter is to give a brief explanation about how the MVCC works. For detailed explanation and reasoning, please consult the paper.

Timestamps

When a transaction starts, it gets a start timestamp. The start timestamp indicate when a transaction is started regarding to other transactions commit timestamp. Each transaction receives a commit timestamp when it is committed. The two timestamps are generated using a single counter. This mean using the timestamps we can always decide which transaction is started before or whether any of them committed before the other started. On top of the two mentioned timestamps, each transaction has a transaction id. It is always true that all of the transaction ids are greater than all of the start and commit timestamps. The transaction id is somewhat different than the start and commit timestamps, but because it is often used in the same manner, let’s consider it also to be a timestamp.

In our implementation (and also in the paper) start and commit timestamps start from 0 and transaction ids are start from 2^63.

Deltas

When a transaction modifies an object, then on top modifying the object in place, it also creates a delta object which described how to undo the changes of the transaction. These delta object can be used for multiple things:

1. When the transaction is aborted, the changes done by the transaction can be easily reverted using the deltas.
2. When another transaction wants to read the data, then the transaction can figure out the exact state of the object it should see it based on the delta chain of the object.
3. When another transaction wants to modify the data, then delta chain can be used to detect conflicts between transactions.

Each delta consists of three important part in theory:

1. A numerical value that identifies the transaction. For transactions that are not committed, this id is the transaction id. For committed transactions this id is the commit timestamp. Let’s call this numerical value the timestamp of the delta.
2. The information about how to revert the change (this is quite specific to vertex/edge, but you can image this part “setting x property to original_value” and similar things)
3. A pointer to the next delta of that object

Access a specific version

When a transaction wants to read an object, it has to check its delta chain to make sure it recover the correct version of the object. To achieve this in snapshot isolation mode, a transactions needs to apply the deltas that are committed before the transaction started. This can be checked easily by comparing the timestamp of a delta and the start timestamp of a transaction. For deltas that are not committed, the timestamp is a transaction id, which is always bigger than any start timestamp. For deltas that are committed, the timestamp is the commit timestamp of the transaction, which can be used to determine the order of the start of current transaction and the commit of the transaction that created the delta. Based on these, if a delta’s timestamp is larger than the start timestamp of the transaction, then the delta has to be applied to revert back the changes of the object to the state when it should be at start time of the transaction. This functionality is described in mvcc.hpp in the ApplyDeltasForRead function.

Similarly, for read committed isolation level, all the uncommitted deltas has to be applied (delta’s timestamp greater or equal than the smallest transaction id). For read uncommitted isolation level, none of the deltas should be applied.

When a transaction wants to write an object using any isolation level, a very similar thing has to done to figure out whether the transaction is allowed to modify the object or not. The transaction is free to modify the object, when the object