Generational garbage collection

Oak 1.6 changed the mechanism used to determine reclaimability of segments. Previous versions used reachability through the segment graph starting from a set of GC roots consisting of the segment containing the current head node state and all segments containing records currently referenced by the JVM (i.e. by open sessions).

Oak 1.6 introduced the concept of a GC generation. A GC generation is an integer starting at 0 and increasing with each run of OnRC. Each segment records the current GC generation from the time the segment was created in its segment header. The current GC generation of the repository is just the GC generation of the segment containing the current head state. The compactor reads the current GC generation of the repository and rewrites the head state using the next GC generation number for the segments created in the process. Once the compactor finished rewriting the current head state the newly created, compact head state is atomically set as the new head state of the repository, implicitly and atomically increasing the GC generation of the repository at the same time.

In its default configuration the cleanup phase retains all segments from the current GC generation and the previous one reclaiming all older segments. With the default daily OnRC execution this results in a minimal segment retention time of 24 hours. Sessions that are open at the point in time where OnRC runs will automatically refresh at next access to reduce the risk for them to reference content from segments that were reclaimed.

Since bulk segments do not have a segment header and thus cannot record their GC generation, the cleanup phase still uses reachability through the segment graph to determine whether a bulk segment is reclaimable. That is, a bulk segment is reclaimable if and only if it is not reachable through the segment graph of the non reclaimable data segments starting from an initial set of root segment ids.

Preventing references between segments with different GC generations

The generation based garbage collection approach disallows references between segments from different GC generations as otherwise reclaiming an older generation would render a newer one incomplete potentially causing SegmentNotFoundExceptions subsequently. Unfortunately up to Oak 1.4 references between segments of different GC generations could be introduced by sessions that were acquired before an OnRC cycle completed. Such sessions would reference records in segments of the previous GC generations through their base state. When such a session subsequently saves its changes are written to segments of the new GC generation effectively creating references from this GC generation to the previous one. See (OAK-3348) for the full story.

To prevent reference between segments of different GC generations such references need to be detected and the affected records rewritten into the current GC generation. That is, whenever a node state is written by a SegmentWriter all references to existing records are checked and the records are rewritten if they do not refer to the current generation. Rewriting is potentially expensive as a base state of a NodeBuilder might cover (a previous revision) of the whole repository. Expensive both in terms of CPU and IO cycles and in term of extra disk space to hold the rewritten base state. However when this situation occurs most records of that base state have likely already been rewritten by OnRC: the most recent compacted head state was rewritten by OnRC from a node state of a more recent revision than our base state, both of which are likely sharing many records. To avoid rewriting the same records multiple times the SegmentWriter employs deduplication caches for node records, string records and template records.

The deduplication caches are indexed by the GC generation such that records can be evicted from the caches by generation. Such an eviction happens for older generations that are not needed any more after OnRC succeeded. An eviction happens for the generation created by OnRC in the case of a failure.

For string records and template records the deduplication caches are ultimately backed by a hash map with an LRU eviction policy. For node records the situation is more complicated as determining structural equality for those means traversal of the potentially large subtree rooted at the record. Also relying on the RecordId does not work as equality of RecordIds in only a necessary condition for structural equality of node records but not a sufficient one. That is, when a node record is rewritten during compaction its clone will be structurally equal to the original but yet have a different RecordId. To overcome this problem a stable id that would not change when rewriting a node state was introduced. This stable id is used by the SegmentWriter as cache key when deduplicating node records. Finally the node deduplication cache is backed by the custom PriorityCache implementation. This cache uses efficient rehashing into an array to resolve hash clashes while at the same time using a cost measure to avoid evicting expensive items. The cost of a node increases with its number of child nodes, which increases the chance for such nodes to stay in the cache.

To put everything together OnRC in Oak 1.6 uses a different approach for compaction than OffRC. While the latter uses the Compactor class like in previous versions of Oak, the former passes the current head state to SegmentWriter.writeNode for on a SegmentWriter for the next GC generation. This causes the head state to be rewritten into segments of the next GC generation filling the deduplication caches in the process.

Sequential checkpoint rebasing

The segment store implements checkpoints as links to (previous) root node states from a child node under the checkpoints node of the super root. In Oak 1.6 compaction was not concerned with checkpoints but rather treated them as regular nodes solely relying on the node deduplication cache to prevent them from being exploded. This approach did not scale well and could lead to high IO rates.

Oak 1.8 improved this aspect by considering checkpoints during compaction instead of relying on the node deduplication cache. This is done by using a Compactor to sequentially rebase checkpoints and the repository root on top of each other and subsequently reassembling them into the right super-root structure. As an additional optimisation already compacted checkpoints are cached to prevent them from being passed to the compactor again in the common case where there are no changes between checkpoints.

Tail compaction

Full compaction of the whole repository is the most effective way to remove any accumulated garbage. To achieve this, full compaction rewrites all content regardless whether there have been updates causing fragmentation or not. As a result this approach is very resource intensive (mainly wrt. IO) and can take a lot of time to complete. Oak 1.8 introduced another compaction mode termed tail compaction. In contrast to full compaction, tail compaction does not compact the whole repository but only those revisions that have been updated since the last compaction.

Tail compaction is implemented by compacting the current head state of the repository on top of the previously compacted head state. The range of revisions starting from the previously compacted head state up to the current head state covers all updates since the last compaction, effectively making tail compaction cover only those revisions that have been updated since the last compaction. Tail compaction can also be regarded as a generalisation of full compaction. With the latter the current head state is compacted on top of an empty node state. With the former the current head state is compacted on top of a previously compacted head state.

Since tail compaction relies on the previously compacted head state the subsequent cleanup phase needs to take this into consideration. That is, cleanup needs to be aware of what type of compaction created a certain segment to determine its reclaimability. This required generalising the GC generation from a simple integer into a GCGeneration class that captures the concept of full and tail compaction. Instances of this class represent the garbage collection generation related information of a segment. It consists of the segment's generation, its full generation and its compaction flag. The segment's generation records the number of garbage collection cycles a segment went through and is incremented with every garbage collection regardless of its type. The segment's full generation records the number of full garbage collection cycles a segment went through. It is only incremented on full garbage collection cycles. The segment's compaction flag is set for those segments that have been created by a compaction operation. It is never set for segments created by normal write operations. Segments written by normal repository writes will inherit the generation and full generation of the segment written by the previous compaction process with the compacted flag cleared.

The information recorded in this way allows to determine the reclaimability status of a segment by just looking at the GCGeneration instances of that segment and of the segment containing the repository head: Let S be a segment, H be the segment containing the current repository head and n be the number of retained generations:

• S is old if and only if H.generation - S.generation >= n
• S is in the same compaction tail like H if and only if S.isCompacted && S.fullGeneration == H.fullGeneration
• S is reclaimable if and only if S is old and S is not in the same compaction tail like H.

This logic is captured in the respective implementations of the reclaim predicate in the Reclaimers class.

Note: Oak 1.8.0 had a bug in the implementation of the reclamation mechanism described. The bug was fixed with Oak 1.8.1, which is the version of Oak this section is referring to.

The Compactor strikes back

Oak 1.6 removed the Compactor class in favour of directly rewriting node states with the SegmentWriter solely relying on deduplication caches for deduplicating records. To implement sequential checkpoint rebasing and tail compaction Oak 1.8 reintroduced a new implementation of a Compactor class. This implementation has to deal with two additional requirements compared to the previous implementation: tracking and assigning stable ids and being able to cope with a large number of direct child nodes of a node. This is done by tracking changes with a MemoryNodeBuilder instead of using a NodeBuilder acquired through calling NodeState.builder. The new SegmentWriter.write method with an extra argument for the stable is then used to write compacted node states including their stable id. In addition the number of updates to the MemoryNodeBuilder are tracked and an intermediate node is written to avoid keeping to many updates in memory once an update limit is exceeded. Further updates are tracked in a fresh MemoryNodeBuilder instance that uses this intermediate node as its base.