svn commit: r1856909 - /jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/onrc-memoirs.md

[md...@apache.org]

Author: mduerig
Date: Thu Apr  4 09:05:46 2019
New Revision: 1856909

URL: http://svn.apache.org/viewvc?rev=1856909&view=rev
Log:
OAK-301: Document Oak
Memoirs in Garbage Collection (WIP):
- Describe checkpoint rebasing and tail compaction in Oak 1.8

Modified:
    jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/onrc-memoirs.md

Modified: jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/onrc-memoirs.md
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/onrc-memoirs.md?rev=1856909&r1=1856908&r2=1856909&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/onrc-memoirs.md (original)
+++ jackrabbit/oak/trunk/oak-doc/src/site/markdown/nodestore/segment/onrc-memoirs.md Thu Apr  4 09:05:46 2019
@@ -57,7 +57,7 @@ Oak 1.6 was the first version with worka
 ### 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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/Segment.java#L380). GC generations are numbered 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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/SegmentBufferWriter.java#L200-L203). The current GC generation of the repository is just the GC generation of the segment containing the current head state. The compactor [reads](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/FileStore.java#L845) the current GC generation of the repository and [rewrites](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segment-
 tar/src/main/java/org/apache/jackrabbit/oak/segment/file/FileStore.java#L864) 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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/FileStore.java#L876) as the new head state of the repository, implicitly and atomically increasing the GC generation of the repository at the same time. 
+Oak 1.6 introduced the concept of a [GC generation](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/Segment.java#L380). 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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/SegmentBufferWriter.java#L200-L203). The current GC generation of the repository is just the GC generation of the segment containing the current head state. The compactor [reads](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/FileStore.java#L845) the current GC generation of the repository and [rewrites](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segmen
 t-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/FileStore.java#L864) 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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/FileStore.java#L876) 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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.6.0/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/FileStore.java#L1055) 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](https://issues.apache.org/jira/browse/OAK-2407) at next access to reduce the risk for them to reference content from segments that were reclaimed.
 
@@ -77,5 +77,35 @@ To put everything together OnRC in Oak 1
 
 Oak 1.8
 -------
-TODO
+Oak 1.8 introduced two main improvements on top of the GC generation based garbage collection approach from Oak 1.6: sequential rebasing of checkpoints on top of each other and tail compaction, a lighter variant of compaction roughly comparable to the JVM's young generation garbage collection.
+
+### Sequential checkpoint rebasing
+The segment store implements checkpoints as links to (previous) root node states from a [child node](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/scheduler/LockBasedScheduler.java#L383) 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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/DefaultSegmentWriter.java#L967) to prevent them from being exploded. This approach did not scale well and could lead to [high IO rates](https://issues.apache.org/jira/browse/OAK-6984).
+
+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`](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/Compactor.java#L56) to sequentially rebase [checkpoints and the repository root](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/CheckpointCompactor.java#L119) on [top of each other](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/CheckpointCompactor.java#L160) and subsequently reassembling them into the right [super-root structure](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/CheckpointCompactor.java#L128-L138). As an additional optimisation alr
 eady compacted checkpoints are [cached](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/CheckpointCompactor.java#L249) 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](https://issues.apache.org/jira/browse/OAK-3349). 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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/FileStore.java#L730). 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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/FileStore.java#L723). With the former the current head state is [compacted on top of a previously compacted head state](https://github.com/apache/ja
 ckrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/FileStore.java#L730). 
+
+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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/GCGeneration.java#L52) 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 col
 lection 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](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/Reclaimers.java#L61) in  the [`Reclaimers` class](https://github.com/apache/jackrabbit-oak/blob/jackrabbit-oak-1.8.1/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/Reclaimers.java#L33). 
+
+> *Note:* Oak 1.8.0 had a [bug](https://issues.apache.org/jira/browse/OAK-7132) 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.  
+
+* TODO: describe usage of MemoryNodeBuilder and modCount in Compactor
+* TODO: describe usage and implementation of stableIds in Compactor
+
+
+Oak 1.10
+--------
+* TODO: describe fixes, improvements and backports