You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-commits@jackrabbit.apache.org by ch...@apache.org on 2016/06/21 06:19:17 UTC
svn commit: r1749431 - in /jackrabbit/oak/trunk/oak-core/src:
main/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCache.java
test/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCacheTest.java
Author: chetanm
Date: Tue Jun 21 06:19:17 2016
New Revision: 1749431
URL: http://svn.apache.org/viewvc?rev=1749431&view=rev
Log:
OAK-4180 - Use another NodeStore as a local cache for a remote Document store
Perform a binary search while searching for matching root state in older versions as the array is kept sorted in ascending order
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCache.java
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCacheTest.java
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCache.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCache.java?rev=1749431&r1=1749430&r2=1749431&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCache.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCache.java Tue Jun 21 06:19:17 2016
@@ -48,6 +48,9 @@ class SecondaryStoreCache implements Doc
private final NodeStateDiffer differ;
private final MeterStats unknownPaths;
private final MeterStats knownMissed;
+ private final MeterStats knownMissedOld;
+ private final MeterStats knownMissedNew;
+ private final MeterStats knownMissedInRange;
private final MeterStats headRevMatched;
private final MeterStats prevRevMatched;
private final int maxSize = 10000;
@@ -65,6 +68,10 @@ class SecondaryStoreCache implements Doc
this.pathFilter = pathFilter;
this.unknownPaths = statisticsProvider.getMeter("DOCUMENT_CACHE_SEC_UNKNOWN", StatsOptions.DEFAULT);
this.knownMissed = statisticsProvider.getMeter("DOCUMENT_CACHE_SEC_KNOWN_MISSED", StatsOptions.DEFAULT);
+ this.knownMissedOld = statisticsProvider.getMeter("DOCUMENT_CACHE_SEC_KNOWN_MISSED_OLD", StatsOptions.DEFAULT);
+ this.knownMissedNew = statisticsProvider.getMeter("DOCUMENT_CACHE_SEC_KNOWN_MISSED_NEW", StatsOptions.DEFAULT);
+ this.knownMissedInRange = statisticsProvider.getMeter("DOCUMENT_CACHE_SEC_KNOWN_MISSED_IN_RANGE", StatsOptions
+ .DEFAULT);
this.headRevMatched = statisticsProvider.getMeter("DOCUMENT_CACHE_SEC_HEAD", StatsOptions.DEFAULT);
this.prevRevMatched = statisticsProvider.getMeter("DOCUMENT_CACHE_SEC_OLD", StatsOptions.DEFAULT);
this.queue = EvictingQueue.create(maxSize);
@@ -144,20 +151,30 @@ class SecondaryStoreCache implements Doc
@CheckForNull
private AbstractDocumentNodeState findMatchingRoot(RevisionVector rr) {
- if (previousRoots.length == 0){
+ if (isEmpty()){
return null;
}
- //TODO Binary search
- AbstractDocumentNodeState latest = previousRoots[previousRoots.length - 1];
- AbstractDocumentNodeState oldest = previousRoots[0];
- if (rr.compareTo(latest.getRootRevision()) <= 0
- && rr.compareTo(oldest.getRootRevision()) >= 0){
- for (AbstractDocumentNodeState s : previousRoots){
- if (s.getRootRevision().equals(rr)){
- return s;
- }
- }
+
+ //Use a local variable as the array can get changed in process
+ AbstractDocumentNodeState[] roots = previousRoots;
+ AbstractDocumentNodeState latest = roots[roots.length - 1];
+ AbstractDocumentNodeState oldest = roots[0];
+
+ if (rr.compareTo(latest.getRootRevision()) > 0){
+ knownMissedNew.mark();
+ return null;
+ }
+
+ if (rr.compareTo(oldest.getRootRevision()) < 0){
+ knownMissedOld.mark();
+ return null;
+ }
+
+ AbstractDocumentNodeState result = findMatchingRoot(roots, rr);
+ if (result != null){
+ return result;
}
+ knownMissedInRange.mark();
return null;
}
@@ -169,4 +186,30 @@ class SecondaryStoreCache implements Doc
previousRoots = queue.toArray(EMPTY);
}
}
+
+ private boolean isEmpty() {
+ return previousRoots.length == 0;
+ }
+
+
+ static AbstractDocumentNodeState findMatchingRoot(AbstractDocumentNodeState[] roots, RevisionVector key) {
+ int low = 0;
+ int high = roots.length - 1;
+
+ //Perform a binary search as the array is sorted in ascending order
+ while (low <= high) {
+ int mid = (low + high) >>> 1;
+ AbstractDocumentNodeState midVal = roots[mid];
+ int cmp = midVal.getRootRevision().compareTo(key);
+
+ if (cmp < 0) {
+ low = mid + 1;
+ } else if (cmp > 0) {
+ high = mid - 1;
+ } else {
+ return midVal; // key found
+ }
+ }
+ return null; // key not found.
+ }
}
Modified: jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCacheTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCacheTest.java?rev=1749431&r1=1749430&r2=1749431&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCacheTest.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/secondary/SecondaryStoreCacheTest.java Tue Jun 21 06:19:17 2016
@@ -23,12 +23,13 @@ import java.io.IOException;
import java.util.Collections;
import java.util.List;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Lists;
import org.apache.jackrabbit.oak.plugins.document.AbstractDocumentNodeState;
import org.apache.jackrabbit.oak.plugins.document.DocumentMKBuilderProvider;
import org.apache.jackrabbit.oak.plugins.document.DocumentNodeStateCache;
import org.apache.jackrabbit.oak.plugins.document.DocumentNodeStateCache.NodeStateCacheEntry;
import org.apache.jackrabbit.oak.plugins.document.DocumentNodeStore;
-import org.apache.jackrabbit.oak.plugins.document.NodeStateDiffer;
import org.apache.jackrabbit.oak.plugins.document.Revision;
import org.apache.jackrabbit.oak.plugins.document.RevisionVector;
import org.apache.jackrabbit.oak.plugins.index.PathFilter;
@@ -148,4 +149,41 @@ public class SecondaryStoreCacheTest {
assertTrue(EqualsDiff.equals(a_c_0, result.getState()));
}
+ @Test
+ public void binarySearch() throws Exception{
+ PathFilter pathFilter = new PathFilter(of("/a"), empty);
+ SecondaryStoreCache cache = new SecondaryStoreCache(secondary, pathFilter, DEFAULT_DIFFER);
+ SecondaryStoreObserver observer = new SecondaryStoreObserver(secondary, pathFilter, cache,
+ DEFAULT_DIFFER, StatisticsProvider.NOOP);
+ primary.addObserver(observer);
+
+ List<AbstractDocumentNodeState> roots = Lists.newArrayList();
+ List<RevisionVector> revs = Lists.newArrayList();
+ for (int i = 0; i < 50; i++) {
+ NodeBuilder nb = primary.getRoot().builder();
+ create(nb, "/a/b"+i);
+ AbstractDocumentNodeState r =
+ (AbstractDocumentNodeState) primary.merge(nb, EmptyHook.INSTANCE, CommitInfo.EMPTY);
+ roots.add(r);
+ revs.add(r.getRootRevision());
+ }
+
+ AbstractDocumentNodeState[] rootsArr = Iterables.toArray(roots, AbstractDocumentNodeState.class);
+
+ Collections.shuffle(revs);
+ for (RevisionVector rev : revs){
+ AbstractDocumentNodeState result = SecondaryStoreCache.findMatchingRoot(rootsArr, rev);
+ assertNotNull(result);
+ assertEquals(rev, result.getRootRevision());
+ }
+
+ NodeBuilder nb = primary.getRoot().builder();
+ create(nb, "/a/m");
+ AbstractDocumentNodeState r =
+ (AbstractDocumentNodeState) primary.merge(nb, EmptyHook.INSTANCE, CommitInfo.EMPTY);
+ AbstractDocumentNodeState result = SecondaryStoreCache.findMatchingRoot(rootsArr, r.getRootRevision());
+ assertNull(result);
+
+ }
+
}
\ No newline at end of file