The unique benefit of snapshot isolation is to allow a great concurrency with the execution of multiple transactions. This is because readers do not block writers and writers do not block readers. The rationale behind that is a well-designed mechanism of versioning, including the version generation, visibility, and reclamation.
Version generation
Versioning are applied at the row level. We only maintain versions for updates and deletions because they overwrite the original data content. For most systems (with or without versioning), a deletion does not really overwrite each single bit with a null value, because that’s inefficient and unnecessary (unless the data need to be purged for security). Instead, deleting data simply marks them as deleted (e.g., by updating the metadata). In this sense, deletions always keep the original data version regardless whether versioning is involved.
In contrast, inserting new data does not introduce versions since there are no old data to begin with. One exception is to insert new data over a row that was just deleted. As just mentioned, the original row is only marked as deleted while its content is still there.
Version visibility
Snapshotting-based isolation lets each transaction see the proper version of data. The visibility of each version is determined through the sequence of transactions and their status within a system. For example, we want to know when a transaction starts, reads, writes, and commits. We therefore maintain a global counter that is monotonically increasing. The counter does not need to be persisted (e.g., will be reset over a system restart). Upon the counter, we record timestamps. For version visibility, we maintain two timestamps for each transaction:
-
Start timestamp–When a transaction starts, it’s assigned a timestamp from the current counter value. The counter is then incremented by one.
-
Minimum start timestamp–When a transaction starts, a snapshot of open transactions in the system is taken. It then selects the open transaction in the snapshot that has the lowest start timestamp, and records that as the minimum start timestamp. Such minimum start timestamp indicates the oldest open transaction in the system at that moment.
We also maintain a timestamp for each row inherited from transactions:
- Update timestamp–the start timestamp of the last transaction that updates a row.
Under the snapshot isolation (SI) level, a transaction will access the most recent committed data as of the start of that transaction. The visibility of a row to a transaction \(t\) can be determined as below:
-
If the row has an update timestamp less than the minimum start timestamp of \(t\), it’s visible to \(t\) because the last transaction that updates the row commits before the start of \(t\) (otherwise, that transaction must have been included by the minimum start timestamp of \(t\)).
-
If the row has an update timestamp larger than the start timestamp of \(t\), it’s invisible to \(t\) because the last transaction that updates the row starts after \(t\).
-
If the row has an update timestamp in between the minimum start timestamp and start timestamp (both inclusive) of \(t\), it’s invisible to \(t\) because the last transaction that updates the row starts before \(t\) while being open at the time when \(t\) starts.
Version reclamation
Old versions can be reclaimed if they are not used by any transactions any more. Recall that the reason we keep an old version is to feed it to transactions that are not yet allowed to see the next newer version. Therefore, once the next newer version becomes visible to every transaction, the old version can be discarded. That is, the eligibility of reclaiming a version is equivalent to the visibility of the next newer version to all transactions. With that, we apply two extensions:
The previous session focuses on the version visibility for one specific transaction. Here to determine if a version is visible to all transactions, we further calculate:
- Minimum useful timestamp–the lowest minimum start timestamp of all current open transactions.
Recall that we rely on the update timestamp of a row to determine its visibility. However, when determining the eligibility of reclaiming an old version, we are interested in the visibility of the next newer version while having no idea of its update timestamp. We therefore attach the update timestamp of the next newer version to the old version and name it:
- Version generation timestamp–the start timestamp of the transaction that updates the row from the old version to the next newer version.
Under SI, the minimum useful timestamp represents the upper bound (exclusive) of old versions that can be safely removed:
-
If an old version has a version generation timestamp less than the minimum useful timestamp, it can be reclaimed. The transaction that updates the old version to the next newer version must have been committed before the start timestamp of the oldest open transaction (otherwise, that transaction must have been included by the minimum useful timestamp). With that, the next newer version is thus visible to all open transactions.
-
If an old version has a version generation timestamp larger than the start timestamp of the oldest open transaction, it’s still interesting and can’t be reclaimed. The transaction that updates the old version to the next newer version starts after the oldest open transaction. The next newer version is invisible to at least the oldest open transaction.
-
If an old version has a version generation timestamp in between the minimum useful timestamp and the oldest open transaction (both inclusive), it’s still interesting and can’t be reclaimed. The transaction that updates the old version to the next newer version starts before the oldest open transaction while being open at the time when the oldest open transaction starts. The next newer version is invisible to at least the oldest open transaction.