Garbage collection

Purpose of garbage collection includes removing old versions and removing unreferenced pages. The GC is the most "dangerous" component in the system, as its functionality to permanently delete data.

The GC is designed to be correct with no assumptions on external dependencies. Things like the system clock are used as heuristics to prevent transaction interruptions, but consistency and correctness are never sacrificed.

Invariants

• Pages that have been committed must not be deleted
• Pages that have been deleted must not be committed

Process

GC task (GT)

1. Fetch read version RAW-RV.

2. Collect inconsistent snapshot of hashes.

   1. Scan the page index incrementally and collect all hashes.
   2. Scan the delta referrer index incrementally and collect all hashes.

3. Scan the CAM index incrementally. For each batch (scanned with TXN1), transaction TXN2:

   1. Filter out those hashes seen in step 2.
   2. Filter out those hashes added within a time duration.
   3. Filter out those CAM entries modified after RAW-RV.
   4. Set TXN2.RV to TXN1.RV.
   5. Add the CAM index of the remaining pages to the conflict set.
   6. Delete the remaining pages from the CAM.
   7. Delete COMMIT-TOKEN.

Commit task (CT)

1. Transaction:

   1. Check the existence of each page. If any page is missing, abort.
   2. Insert COMMIT-TOKEN.

2. Transaction:

   1. Check COMMIT-TOKEN. If not matching step 1, abort.
   2. Insert each hash to the CAM index.
   3. Insert each hash to the page index.
   4. Insert metadata, if any.

Note: In a previous version step 2c and 2d was split into their own transaction (with commit-token check). This is incorrect. Consider this order:

1. CT, step 1.
2. CT, step 2a-2b.
3. GT, step 1 and 2.
4. CT, step 2c-3d.
5. GT, step 3.

In this case, the newly committed page index entries will be deleted.