Author: mreutegg
Date: Thu Aug 25 09:27:40 2016
New Revision: 1757639
URL: http://svn.apache.org/viewvc?rev=1757639&view=rev
Log:
OAK-4697: Optimize read of old node state
Improved implementation and enabled test
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/NodeDocument.java
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/NodeDocumentTest.java
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/NodeDocument.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/NodeDocument.java?rev=1757639&r1=1757638&r2=1757639&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/NodeDocument.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/document/NodeDocument.java
Thu Aug 25 09:27:40 2016
@@ -18,6 +18,7 @@ package org.apache.jackrabbit.oak.plugin
import java.util.ArrayList;
import java.util.Collections;
+import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
@@ -37,10 +38,12 @@ import javax.annotation.Nullable;
import com.google.common.base.Function;
import com.google.common.base.Predicate;
+import com.google.common.base.Predicates;
import com.google.common.collect.AbstractIterator;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterators;
import com.google.common.collect.Lists;
+import com.google.common.collect.Ordering;
import com.google.common.collect.Queues;
import org.apache.jackrabbit.oak.api.PropertyState;
import org.apache.jackrabbit.oak.cache.CacheValue;
@@ -61,7 +64,9 @@ import com.google.common.collect.Sets;
import static com.google.common.base.Objects.equal;
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.collect.Iterables.concat;
import static com.google.common.collect.Iterables.filter;
+import static com.google.common.collect.Iterables.mergeSorted;
import static com.google.common.collect.Iterables.transform;
import static org.apache.jackrabbit.oak.plugins.document.Collection.NODES;
import static
org.apache.jackrabbit.oak.plugins.document.StableRevisionComparator.REVERSE;
@@ -967,7 +972,8 @@ public final class NodeDocument extends
continue;
}
// first check local map, which contains most recent values
- Value value = getLatestValue(nodeStore, local, readRevision,
validRevisions, lastRevs);
+ Value value = getLatestValue(nodeStore, local.entrySet(),
+ readRevision, validRevisions, lastRevs);
// check if there may be more recent values in a previous document
if (value != null
@@ -986,8 +992,9 @@ public final class NodeDocument extends
}
if (value == null && !getPreviousRanges().isEmpty()) {
- // check complete revision history
- value = getLatestValue(nodeStore, getValueMap(key),
readRevision, validRevisions, lastRevs);
+ // check revision history
+ value = getLatestValue(nodeStore, getVisibleChanges(key,
readRevision),
+ readRevision, validRevisions, lastRevs);
}
String propertyName = Utils.unescapePropertyName(key);
String v = value != null ? value.value : null;
@@ -1070,10 +1077,10 @@ public final class NodeDocument extends
Map<Revision, String> validRevisions,
LastRevs lastRevs) {
// check local deleted map first
- Value value = getLatestValue(context, getLocalDeleted(), readRevision,
validRevisions, lastRevs);
+ Value value = getLatestValue(context, getLocalDeleted().entrySet(),
readRevision, validRevisions, lastRevs);
if (value == null && !getPreviousRanges().isEmpty()) {
// need to check complete map
- value = getLatestValue(context, getDeleted(), readRevision,
validRevisions, lastRevs);
+ value = getLatestValue(context, getDeleted().entrySet(),
readRevision, validRevisions, lastRevs);
}
return value != null && "false".equals(value.value) ? value.revision :
null;
@@ -1519,6 +1526,70 @@ public final class NodeDocument extends
}
/**
+ * Returns all changes for the given property that are visible from the
+ * {@code readRevision} vector. The revisions include committed as well as
+ * uncommitted changes. The returned revisions are sorted in reverse order
+ * (newest first).
+ *
+ * @param property the name of the property.
+ * @param readRevision the read revision vector.
+ * @return property changes visible from the given read revision vector.
+ */
+ @Nonnull
+ Iterable<Map.Entry<Revision, String>> getVisibleChanges(@Nonnull final
String property,
+ @Nonnull final
RevisionVector readRevision) {
+ Predicate<Map.Entry<Revision, String>> p = new
Predicate<Map.Entry<Revision, String>>() {
+ @Override
+ public boolean apply(Map.Entry<Revision, String> input) {
+ return !readRevision.isRevisionNewer(input.getKey());
+ }
+ };
+ List<Iterable<Map.Entry<Revision, String>>> changes =
Lists.newArrayList();
+ changes.add(filter(getLocalMap(property).entrySet(), p));
+
+ boolean overlapping = false;
+ List<Range> ranges = Lists.newArrayList();
+ long lowStamp = Long.MAX_VALUE;
+ for (Map.Entry<Revision, Range> e : getPreviousRanges().entrySet()) {
+ Range range = e.getValue();
+ if (!readRevision.isRevisionNewer(range.low)) {
+ ranges.add(range);
+ // check if overlapping
+ if (!overlapping) {
+ overlapping = range.high.getTimestamp() >= lowStamp;
+ }
+ lowStamp = Math.min(lowStamp, range.low.getTimestamp());
+ }
+ }
+
+ if (!ranges.isEmpty()) {
+ Iterable<Iterable<Map.Entry<Revision, String>>> revs =
transform(filter(transform(ranges,
+ new Function<Range, NodeDocument>() {
+ @Override
+ public NodeDocument apply(Range input) {
+ return getPreviousDoc(input.high, input);
+ }
+ }), Predicates.notNull()), new Function<NodeDocument,
Iterable<Map.Entry<Revision, String>>>() {
+ @Override
+ public Iterable<Map.Entry<Revision, String>>
apply(NodeDocument prev) {
+ return prev.getVisibleChanges(property, readRevision);
+ }
+ });
+ if (overlapping) {
+ changes.add(mergeSorted(revs, ValueComparator.REVERSE));
+ } else {
+ changes.add(concat(revs));
+ }
+ }
+
+ if (changes.size() == 1) {
+ return changes.get(0);
+ } else {
+ return mergeSorted(changes, ValueComparator.REVERSE);
+ }
+ }
+
+ /**
* Returns the local value map for the given key.
*
* @param key the key.
@@ -1965,11 +2036,11 @@ public final class NodeDocument extends
*/
@CheckForNull
private Value getLatestValue(@Nonnull RevisionContext context,
- @Nonnull Map<Revision, String> valueMap,
+ @Nonnull Iterable<Map.Entry<Revision,
String>> valueMap,
@Nonnull RevisionVector readRevision,
@Nonnull Map<Revision, String> validRevisions,
@Nonnull LastRevs lastRevs) {
- for (Map.Entry<Revision, String> entry : valueMap.entrySet()) {
+ for (Map.Entry<Revision, String> entry : valueMap) {
Revision propRev = entry.getKey();
String commitValue = validRevisions.get(propRev);
if (commitValue == null) {
@@ -2188,4 +2259,24 @@ public final class NodeDocument extends
this.value = value;
}
}
+
+ private static final class ValueComparator implements
+ Comparator<Entry<Revision, String>> {
+
+ static final Comparator<Entry<Revision, String>> INSTANCE = new
ValueComparator();
+
+ static final Comparator<Entry<Revision, String>> REVERSE =
Collections.reverseOrder(INSTANCE);
+
+ private static final Ordering<String> STRING_ORDERING =
Ordering.natural().nullsFirst();
+
+ @Override
+ public int compare(Entry<Revision, String> o1,
+ Entry<Revision, String> o2) {
+ int cmp = StableRevisionComparator.INSTANCE.compare(o1.getKey(),
o2.getKey());
+ if (cmp != 0) {
+ return cmp;
+ }
+ return STRING_ORDERING.compare(o1.getValue(), o2.getValue());
+ }
+ }
}
Modified:
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/NodeDocumentTest.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/NodeDocumentTest.java?rev=1757639&r1=1757638&r2=1757639&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/NodeDocumentTest.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/document/NodeDocumentTest.java
Thu Aug 25 09:27:40 2016
@@ -39,7 +39,6 @@ import org.apache.jackrabbit.oak.spi.com
import org.apache.jackrabbit.oak.spi.commit.EmptyHook;
import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
import org.apache.jackrabbit.oak.spi.state.NodeStore;
-import org.junit.Ignore;
import org.junit.Test;
import static com.google.common.collect.Sets.newHashSet;
@@ -491,26 +490,8 @@ public class NodeDocumentTest {
DocumentNodeStore ns2 = createTestStore(store, 2, 0);
List<DocumentNodeStore> nodeStores = Lists.newArrayList(ns1, ns2);
- List<RevisionVector> headRevisions = Lists.newArrayList();
- for (int i = 0; i < numChanges; i++) {
- DocumentNodeStore ns =
nodeStores.get(random.nextInt(nodeStores.size()));
- ns.runBackgroundOperations();
- NodeBuilder builder = ns.getRoot().builder();
- builder.setProperty("p", i);
- merge(ns, builder);
- headRevisions.add(ns.getHeadRevision());
- ns.runBackgroundOperations();
- if (random.nextDouble() < 0.2) {
- RevisionVector head = ns.getHeadRevision();
- for (UpdateOp op : SplitOperations.forDocument(
- getRootDocument(store), ns, head,
- Predicates.<String>alwaysFalse(), 2)) {
- store.createOrUpdate(NODES, op);
- }
- }
- }
-
- headRevisions = Lists.reverse(headRevisions);
+ List<RevisionVector> headRevisions = Lists.reverse(
+ createTestData(nodeStores, random, numChanges));
NodeDocument doc = getRootDocument(store);
for (int i = 0; i < 10; i++) {
int idx = random.nextInt(numChanges);
@@ -636,7 +617,6 @@ public class NodeDocumentTest {
ns.dispose();
}
- @Ignore("OAK-4697")
@Test
public void tooManyReadsOnGetNodeAtRevision() throws Exception {
final int numChanges = 200;
@@ -671,6 +651,47 @@ public class NodeDocumentTest {
ns.dispose();
}
+ @Test
+ public void getVisibleChanges() throws Exception {
+ final int numChanges = 200;
+ Random random = new Random();
+ DocumentNodeStore ns = createTestStore(numChanges);
+ DocumentStore store = ns.getDocumentStore();
+ NodeDocument doc = getRootDocument(store);
+ for (int i = 0; i < 10; i++) {
+ int idx = random.nextInt(numChanges);
+ Revision r = Iterables.get(doc.getValueMap("p").keySet(), idx);
+ Iterable<Map.Entry<Revision, String>> revs =
doc.getVisibleChanges("p", new RevisionVector(r));
+ assertEquals(idx, numChanges - Iterables.size(revs));
+ }
+ ns.dispose();
+ }
+
+ @Test
+ public void getVisibleChangesMixedClusterIds() throws Exception {
+ final int numChanges = 200;
+ Random random = new Random();
+ MemoryDocumentStore store = new MemoryDocumentStore();
+ DocumentNodeStore ns1 = createTestStore(store, 1, 0);
+ DocumentNodeStore ns2 = createTestStore(store, 2, 0);
+ List<DocumentNodeStore> nodeStores = Lists.newArrayList(ns1, ns2);
+
+ List<RevisionVector> headRevisions = Lists.reverse(
+ createTestData(nodeStores, random, numChanges));
+ NodeDocument doc = getRootDocument(store);
+ for (int i = 0; i < 10; i++) {
+ int idx = random.nextInt(numChanges);
+ RevisionVector r = headRevisions.get(idx);
+ Iterable<Map.Entry<Revision, String>> revs1 =
doc.getVisibleChanges("p", r);
+ Iterable<Map.Entry<Revision, String>> revs2 =
doc.getVisibleChanges("p", r);
+ assertEquals(Iterables.size(revs1), Iterables.size(revs2));
+ assertEquals(idx, numChanges - Iterables.size(revs1));
+ }
+
+ ns1.dispose();
+ ns2.dispose();
+ }
+
private DocumentNodeStore createTestStore(int numChanges) throws Exception
{
return createTestStore(new MemoryDocumentStore(), 0, numChanges);
}
@@ -697,6 +718,32 @@ public class NodeDocumentTest {
return ns;
}
+ private List<RevisionVector> createTestData(List<DocumentNodeStore>
nodeStores,
+ Random random,
+ int numChanges)
+ throws CommitFailedException {
+ List<RevisionVector> headRevisions = Lists.newArrayList();
+ for (int i = 0; i < numChanges; i++) {
+ DocumentNodeStore ns =
nodeStores.get(random.nextInt(nodeStores.size()));
+ ns.runBackgroundOperations();
+ NodeBuilder builder = ns.getRoot().builder();
+ builder.setProperty("p", i);
+ merge(ns, builder);
+ headRevisions.add(ns.getHeadRevision());
+ ns.runBackgroundOperations();
+ if (random.nextDouble() < 0.2) {
+ DocumentStore store = ns.getDocumentStore();
+ RevisionVector head = ns.getHeadRevision();
+ for (UpdateOp op : SplitOperations.forDocument(
+ getRootDocument(store), ns, head,
+ Predicates.<String>alwaysFalse(), 2)) {
+ store.createOrUpdate(NODES, op);
+ }
+ }
+ }
+ return headRevisions;
+ }
+
private void merge(NodeStore store, NodeBuilder builder)
throws CommitFailedException {
store.merge(builder, EmptyHook.INSTANCE, CommitInfo.EMPTY);
