Garbage collection

Copyright 2010-2011 © Gabriel Zs. K. Horvath

So far all the versions of the versioned variables have been kept in the variables’ history. This is obviously not a viable option and an unnecessary one as most of the versions are likely to become quickly unreachable. Let me first define what a reachable version is. Consider the following versioned variables:

The important point to remember is that any new transaction will always see only the most recent value of a versioned variable. So a transaction which starts after version 6 has been created will see version 5 of the integer transactional box and version 6 of the set transactional box. Version 2 of the integer variable will only ever be visible to a transaction which has started after that version has been created and before version 5 has been committed. On the left I have drawn rectangles to depict the lifetime of the transactions which are responsible for the newly created versions. We see that at the time defined by the dotted line, all transactions, with the exception of X, have committed their changes and any new transaction will see only versions 5 and 6. These and versions 2 and 3, via transaction X, are the only other versions which are reachable . No other version is reachable by any legal means. This implies that we can get rid of them, i.e. garbage collect them.

Simplification

We can consider a very useful simplification to our model [1]. Consider the oldest live transaction, in our example that would be transaction X. That transaction can still access versions 2 and 3, but since it is the oldest live transaction no older version is reachable. This gives us a simpler way to determine what versions are actually reachable. The downside of this approach is that version 4 which is not reachable would not be garbage collected. More importantly, were an old transaction to never end, no garbage collection would take place… so this simplification will require us to include a way of timing out old transactions. Not doing so would result in some serious memory leaks.

[1] “Versioned boxes as the basis for memory transactions“, J. Cachopo and A. Rito-Silva, 2006, http://portal.acm.org/citation.cfm?id=1228566