Commutative Updates and GC

In MVCC a version can be flat or commutative. Both flat and commutative versions can be in PENDING, COMMITTED, or ABORTED states.

Commutative version may turn into a flat version once a flattening operation occur (currently triggered by a read, or in general during some background cleanup process not yet implemented). Every time we introduce a flat, COMMITTED version, either by installing it directly or via flattening, we should mark everything following the flat version down the version chain as GCed.

Without loss of generality, we consider one MVCC record only. We call the oldest non-garbage flat COMMITTED version of this record PV.

1. Versions newer than PV can be flat ABORTED/PENDING or commutative (any state).
2. PV and versions newer than PV are not marked garbage.
3. All versions older than PV should be (eventually) marked garbage.

In particular let's discuss how to guarantee (3) (no leak).

When PV is introduced, the installation/flattening procedure will traverse down the version chain and mark all subsequent versions at garbage. This is however not sufficient to guarantee (3) because of concurrent pending version installations. The traversal down the chain might miss concurrently inserted versions older than PV. So we will potentially need multiple traversals. We need to make sure:

1. All versions installed under PV are always reachable via a traversal from PV at any given time after their insertion to the version chain.
2. All versions installed under PV at any possible time will be visited at least once by a traversal to mark it as garbage.

The proposed GC enqueue protocol:

At pending version installation (STO lock) time:

1. Find the MVCC version V at which pending version insertion should occur.
2. Perform CAS on &V->prev_ to install the pending version. If fail, go back to 1.
3. If succeeds, check if V is a flat COMMITTED version or if V is already marked GCed. If true, mark the inserted version as GCed and all subsequent versions in the version chain as GCed.

The argument is that this would satisfy the no leak property.

Claim 1: It is not possible to construct a version chain that contains a leak without a boundary link. A boundary link is a link from a flat COMMITTED version to any non-GCed version (type A), or a link from any GCed version to any non-GCed version (type B).

A leaky chain is a version chain where a flat COMMITTED version is followed by one or more non-GCed version in the steady state.

In a version chain without boundary links:

1. GCed versions must be followed by GCed versions.
2. Flat COMMITTED versions must be followed by GCed versions.

By 1 and 2, flat COMMITTED versions must be followed by only GCed versions all the way down in a non-leaky chain. This proves Claim 1.

Claim 2: In a leaky chain, the GC enqueuing protocol transforms the chain into a non-leaky one. Or equivalently, given a leaky chain, the GC enqueuing protocol erases all boundary links.

For type A boundary links PV->NV: NV will detect a flat COMMITTED version and mark itself as GCed, erasing the type A link. This might create a type B link from NV to the older version. However, any such type B link is erased by a traversal down the chain initiated at NV.

For type B boundary links NNV->NV: NV will detect a GCed version and mark itself as GCed, erasing the type B link. This again might create another type B link from NV to the older version. Any such newly created type B link are erased by a traversal down the chain by NV.

This proves Claim 2.

If we change the traversal procedure to terminate at a version already marked GCed or a flat COMMITTED version, the two proofs above still hold. (Because additional boundary links are only created if the pointed-to version is a non-GCed version. Marking a version GCed won't introduce any boundary links if the older version is already marked GCed.)

This termination condition also means that the downward version chain traversal never accesses beyond the next older flat COMMITTED version, which in turn guarantees that it never access a freed/recycled version.