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 th...@apache.org on 2014/12/01 14:48:25 UTC
svn commit: r1642683 - in /jackrabbit/oak/trunk: oak-core/
oak-core/src/main/java/org/apache/jackrabbit/oak/
oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/
oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/...
Author: thomasm
Date: Mon Dec 1 13:48:24 2014
New Revision: 1642683
URL: http://svn.apache.org/r1642683
Log:
OAK-1907 Better cost estimates for traversal, property, and ordered indexes (work in progress)
Added:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditor.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditorProvider.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounterMBean.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/package-info.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/package-info.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/util/ApproximateCounter.java
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/util/
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/util/ApproximateCounterTest.java
Modified:
jackrabbit/oak/trunk/oak-core/pom.xml
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/Oak.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/IndexStoreStrategy.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/UniqueEntryStoreStrategy.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/nodetype/write/InitialContent.java
jackrabbit/oak/trunk/oak-jcr/src/main/java/org/apache/jackrabbit/oak/jcr/Jcr.java
Modified: jackrabbit/oak/trunk/oak-core/pom.xml
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/pom.xml?rev=1642683&r1=1642682&r2=1642683&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/pom.xml (original)
+++ jackrabbit/oak/trunk/oak-core/pom.xml Mon Dec 1 13:48:24 2014
@@ -65,6 +65,7 @@
org.apache.jackrabbit.oak.plugins.identifier,
org.apache.jackrabbit.oak.plugins.index,
org.apache.jackrabbit.oak.plugins.index.aggregate,
+ org.apache.jackrabbit.oak.plugins.index.counter,
org.apache.jackrabbit.oak.plugins.index.nodetype,
org.apache.jackrabbit.oak.plugins.index.property,
org.apache.jackrabbit.oak.plugins.index.property.jmx,
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/Oak.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/Oak.java?rev=1642683&r1=1642682&r2=1642683&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/Oak.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/Oak.java Mon Dec 1 13:48:24 2014
@@ -64,6 +64,8 @@ import org.apache.jackrabbit.oak.plugins
import org.apache.jackrabbit.oak.plugins.index.IndexConstants;
import org.apache.jackrabbit.oak.plugins.index.IndexEditorProvider;
import org.apache.jackrabbit.oak.plugins.index.IndexUpdateProvider;
+import org.apache.jackrabbit.oak.plugins.index.counter.jmx.NodeCounter;
+import org.apache.jackrabbit.oak.plugins.index.counter.jmx.NodeCounterMBean;
import org.apache.jackrabbit.oak.plugins.index.property.jmx.PropertyIndexAsyncReindex;
import org.apache.jackrabbit.oak.plugins.index.property.jmx.PropertyIndexAsyncReindexMBean;
import org.apache.jackrabbit.oak.plugins.memory.MemoryNodeStore;
@@ -539,6 +541,9 @@ public class Oak {
PropertyIndexAsyncReindexMBean.class, asyncPI,
PropertyIndexAsyncReindexMBean.TYPE, name));
}
+
+ regs.add(registerMBean(whiteboard, NodeCounterMBean.class,
+ new NodeCounter(store), NodeCounterMBean.TYPE, "nodeCounter"));
regs.add(registerMBean(whiteboard, QueryEngineSettingsMBean.class,
queryEngineSettings, QueryEngineSettingsMBean.TYPE, "settings"));
Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditor.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditor.java?rev=1642683&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditor.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditor.java Mon Dec 1 13:48:24 2014
@@ -0,0 +1,154 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.plugins.index.counter;
+
+import javax.annotation.CheckForNull;
+
+import org.apache.jackrabbit.oak.api.CommitFailedException;
+import org.apache.jackrabbit.oak.api.PropertyState;
+import org.apache.jackrabbit.oak.api.Type;
+import org.apache.jackrabbit.oak.plugins.index.IndexUpdateCallback;
+import org.apache.jackrabbit.oak.spi.commit.Editor;
+import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+import org.apache.jackrabbit.oak.util.ApproximateCounter;
+
+/**
+ * An approximate descendant node counter mechanism.
+ */
+public class NodeCounterEditor implements Editor {
+
+ public static final String DATA_NODE_NAME = ":index";
+ public static final String COUNT_PROPERTY_NAME = ":count";
+ private static final int DEFAULT_RESOLUTION = 1000;
+
+ private final NodeCounterRoot root;
+ private final NodeCounterEditor parent;
+ private final String name;
+ private long countOffset;
+
+ public NodeCounterEditor(NodeCounterRoot root, NodeCounterEditor parent, String name) {
+ this.parent = parent;
+ this.root = root;
+ this.name = name;
+ }
+
+ @Override
+ public void enter(NodeState before, NodeState after)
+ throws CommitFailedException {
+ // nothing to do
+ }
+
+ @Override
+ public void leave(NodeState before, NodeState after)
+ throws CommitFailedException {
+ long offset = ApproximateCounter.calculateOffset(
+ countOffset, root.resolution);
+ if (offset == 0) {
+ return;
+ }
+ // only read the value of the property if really needed
+ NodeBuilder builder = getBuilder();
+ PropertyState p = builder.getProperty(COUNT_PROPERTY_NAME);
+ long count = p == null ? 0 : p.getValue(Type.LONG);
+ offset = ApproximateCounter.adjustOffset(count,
+ offset, root.resolution);
+ if (offset == 0) {
+ return;
+ }
+ count += offset;
+ root.callback.indexUpdate();
+ if (count == 0) {
+ if (builder.getChildNodeCount(1) >= 0) {
+ builder.removeProperty(COUNT_PROPERTY_NAME);
+ } else {
+ builder.remove();
+ }
+ } else {
+ builder.setProperty(COUNT_PROPERTY_NAME, count);
+ }
+ }
+
+ private NodeBuilder getBuilder() {
+ if (parent == null) {
+ return root.definition.child(DATA_NODE_NAME);
+ }
+ return parent.getBuilder().child(name);
+ }
+
+ @Override
+ public void propertyAdded(PropertyState after) throws CommitFailedException {
+ // nothing to do
+ }
+
+ @Override
+ public void propertyChanged(PropertyState before, PropertyState after)
+ throws CommitFailedException {
+ // nothing to do
+ }
+
+ @Override
+ public void propertyDeleted(PropertyState before)
+ throws CommitFailedException {
+ // nothing to do
+ }
+
+ @Override
+ @CheckForNull
+ public Editor childNodeChanged(String name, NodeState before, NodeState after)
+ throws CommitFailedException {
+ return getChildIndexEditor(this, name);
+ }
+
+ @Override
+ @CheckForNull
+ public Editor childNodeAdded(String name, NodeState after)
+ throws CommitFailedException {
+ count(1);
+ return getChildIndexEditor(this, name);
+ }
+
+ @Override
+ @CheckForNull
+ public Editor childNodeDeleted(String name, NodeState before)
+ throws CommitFailedException {
+ count(-1);
+ return getChildIndexEditor(this, name);
+ }
+
+ private void count(int offset) {
+ countOffset += offset;
+ if (parent != null) {
+ parent.count(offset);
+ }
+ }
+
+ private Editor getChildIndexEditor(NodeCounterEditor nodeCounterEditor,
+ String name) {
+ return new NodeCounterEditor(root, this, name);
+ }
+
+ public static class NodeCounterRoot {
+ int resolution = DEFAULT_RESOLUTION;
+ NodeBuilder definition;
+ NodeState root;
+ IndexUpdateCallback callback;
+ }
+
+}
Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditorProvider.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditorProvider.java?rev=1642683&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditorProvider.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditorProvider.java Mon Dec 1 13:48:24 2014
@@ -0,0 +1,63 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.plugins.index.counter;
+
+import javax.annotation.CheckForNull;
+import javax.annotation.Nonnull;
+
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Service;
+import org.apache.jackrabbit.oak.api.CommitFailedException;
+import org.apache.jackrabbit.oak.api.PropertyState;
+import org.apache.jackrabbit.oak.api.Type;
+import org.apache.jackrabbit.oak.plugins.index.IndexEditorProvider;
+import org.apache.jackrabbit.oak.plugins.index.IndexUpdateCallback;
+import org.apache.jackrabbit.oak.plugins.index.counter.NodeCounterEditor.NodeCounterRoot;
+import org.apache.jackrabbit.oak.spi.commit.Editor;
+import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+
+@Component
+@Service(IndexEditorProvider.class)
+public class NodeCounterEditorProvider implements IndexEditorProvider {
+
+ public static final String TYPE = "counter";
+
+ public static final String RESOLUTION = "resolution";
+
+ @Override
+ @CheckForNull
+ public Editor getIndexEditor(@Nonnull String type,
+ @Nonnull NodeBuilder definition, @Nonnull NodeState root,
+ @Nonnull IndexUpdateCallback callback) throws CommitFailedException {
+ if (!TYPE.equals(type)) {
+ return null;
+ }
+ NodeCounterRoot rootData = new NodeCounterRoot();
+ rootData.callback = callback;
+ rootData.definition = definition;
+ rootData.root = root;
+ PropertyState s = definition.getProperty(RESOLUTION);
+ if (s != null) {
+ rootData.resolution = s.getValue(Type.LONG).intValue();
+ }
+ return new NodeCounterEditor(rootData, null, "/");
+ }
+
+}
Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java?rev=1642683&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java Mon Dec 1 13:48:24 2014
@@ -0,0 +1,125 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.plugins.index.counter.jmx;
+
+import java.util.Arrays;
+
+import org.apache.jackrabbit.oak.api.PropertyState;
+import org.apache.jackrabbit.oak.api.Type;
+import org.apache.jackrabbit.oak.commons.PathUtils;
+import org.apache.jackrabbit.oak.plugins.index.IndexConstants;
+import org.apache.jackrabbit.oak.plugins.index.counter.NodeCounterEditor;
+import org.apache.jackrabbit.oak.spi.state.ChildNodeEntry;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+import org.apache.jackrabbit.oak.spi.state.NodeStore;
+
+/**
+ * A mechanism to retrieve node counter data.
+ */
+public class NodeCounter implements NodeCounterMBean {
+
+ private final NodeStore store;
+
+ public NodeCounter(NodeStore store) {
+ this.store = store;
+ }
+
+ private static NodeState child(NodeState n, String... path) {
+ return child(n, Arrays.asList(path));
+ }
+
+ private static NodeState child(NodeState n, Iterable<String> path) {
+ for (String p : path) {
+ if (n == null) {
+ break;
+ }
+ if (p.length() > 0) {
+ n = n.getChildNode(p);
+ }
+ }
+ return n;
+ }
+
+ @Override
+ public long getEstimatedNodeCount(String path) {
+ // check if there is a property in the node itself
+ // (for property index nodes)
+ NodeState s = child(store.getRoot(),
+ PathUtils.elements(path));
+ if (s == null) {
+ // node not found
+ return -1;
+ }
+ PropertyState p = s.getProperty(NodeCounterEditor.COUNT_PROPERTY_NAME);
+ if (p != null) {
+ return p.getValue(Type.LONG);
+ }
+
+ // check in the counter index (if it exists)
+ s = child(store.getRoot(),
+ IndexConstants.INDEX_DEFINITIONS_NAME,
+ "counter",
+ NodeCounterEditor.DATA_NODE_NAME);
+ if (s == null) {
+ // no index
+ return -1;
+ }
+ s = child(s, PathUtils.elements(path));
+ if (s == null) {
+ // we have an index, but no data
+ return 0;
+ }
+ p = s.getProperty(NodeCounterEditor.COUNT_PROPERTY_NAME);
+ if (p == null) {
+ // we have an index, but no data
+ return 0;
+ }
+ return p.getValue(Type.LONG);
+ }
+
+ @Override
+ public String getEstimatedChildNodeCounts(String path, int level) {
+ StringBuilder buff = new StringBuilder();
+ collectCounts(buff, path, level);
+ return buff.toString();
+ }
+
+ private void collectCounts(StringBuilder buff, String path, int level) {
+ long count = getEstimatedNodeCount(path);
+ if (count > 0) {
+ if (buff.length() > 0) {
+ buff.append(",\n");
+ }
+ buff.append(path).append(": ").append(count);
+ }
+ if (level <= 0) {
+ return;
+ }
+ NodeState s = child(store.getRoot(),
+ PathUtils.elements(path));
+ if (!s.exists()) {
+ return;
+ }
+ for (ChildNodeEntry c : s.getChildNodeEntries()) {
+ String child = PathUtils.concat(path, c.getName());
+ collectCounts(buff, child, level - 1);
+ }
+ }
+
+}
Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounterMBean.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounterMBean.java?rev=1642683&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounterMBean.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounterMBean.java Mon Dec 1 13:48:24 2014
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.plugins.index.counter.jmx;
+
+/**
+ * An MBean that provides an approximate node count for a given path.
+ */
+public interface NodeCounterMBean {
+
+ String TYPE = "NodeCounter";
+
+ /**
+ * Get the estimated number of nodes below a given path.
+ *
+ * @param path the path
+ * @return the estimated number of nodes, or -1 if unknown (if not index is
+ * available)
+ */
+ long getEstimatedNodeCount(String path);
+
+ /**
+ * Get the estimated number of nodes for the child nodes of a given path.
+ *
+ * @param path the path
+ * @param level the depth of the child nodes to list
+ * @return a comma separated list of child nodes with the respective
+ * estimated counts
+ */
+ String getEstimatedChildNodeCounts(String path, int level);
+
+}
Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/package-info.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/package-info.java?rev=1642683&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/package-info.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/package-info.java Mon Dec 1 13:48:24 2014
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+@Version("1.0")
+@Export(optional = "provide:=true")
+package org.apache.jackrabbit.oak.plugins.index.counter.jmx;
+
+import aQute.bnd.annotation.Version;
+import aQute.bnd.annotation.Export;
\ No newline at end of file
Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/package-info.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/package-info.java?rev=1642683&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/package-info.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/package-info.java Mon Dec 1 13:48:24 2014
@@ -0,0 +1,22 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+@Version("1.0")
+@Export(optional = "provide:=true")
+package org.apache.jackrabbit.oak.plugins.index.counter;
+
+import aQute.bnd.annotation.Version;
+import aQute.bnd.annotation.Export;
\ No newline at end of file
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java?rev=1642683&r1=1642682&r2=1642683&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/ContentMirrorStoreStrategy.java Mon Dec 1 13:48:24 2014
@@ -38,6 +38,7 @@ import org.apache.jackrabbit.oak.spi.sta
import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
import org.apache.jackrabbit.oak.spi.state.NodeState;
import org.apache.jackrabbit.oak.spi.state.NodeStateUtils;
+import org.apache.jackrabbit.oak.util.ApproximateCounter;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -89,8 +90,10 @@ public class ContentMirrorStoreStrategy
}
private void remove(NodeBuilder index, String key, String value) {
+ ApproximateCounter.adjustCount(index, -1);
NodeBuilder builder = index.getChildNode(key);
if (builder.exists()) {
+ ApproximateCounter.adjustCount(builder, -1);
// Collect all builders along the given path
Deque<NodeBuilder> builders = newArrayDeque();
builders.addFirst(builder);
@@ -112,8 +115,10 @@ public class ContentMirrorStoreStrategy
}
private void insert(NodeBuilder index, String key, String value) {
+ ApproximateCounter.adjustCount(index, 1);
// NodeBuilder builder = index.child(key);
NodeBuilder builder = fetchKeyNode(index, key);
+ ApproximateCounter.adjustCount(builder, 1);
for (String name : PathUtils.elements(value)) {
builder = builder.child(name);
}
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/IndexStoreStrategy.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/IndexStoreStrategy.java?rev=1642683&r1=1642682&r2=1642683&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/IndexStoreStrategy.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/IndexStoreStrategy.java Mon Dec 1 13:48:24 2014
@@ -27,7 +27,7 @@ import org.apache.jackrabbit.oak.spi.sta
* index node
*/
public interface IndexStoreStrategy {
-
+
/**
* Updates the index for the given path.
*
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/UniqueEntryStoreStrategy.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/UniqueEntryStoreStrategy.java?rev=1642683&r1=1642682&r2=1642683&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/UniqueEntryStoreStrategy.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/property/strategy/UniqueEntryStoreStrategy.java Mon Dec 1 13:48:24 2014
@@ -30,6 +30,7 @@ import org.apache.jackrabbit.oak.spi.que
import org.apache.jackrabbit.oak.spi.state.ChildNodeEntry;
import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
import org.apache.jackrabbit.oak.spi.state.NodeState;
+import org.apache.jackrabbit.oak.util.ApproximateCounter;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -57,6 +58,7 @@ public class UniqueEntryStoreStrategy im
}
private static void remove(NodeBuilder index, String key, String value) {
+ ApproximateCounter.adjustCount(index, -1);
NodeBuilder builder = index.getChildNode(key);
if (builder.exists()) {
// there could be (temporarily) multiple entries
@@ -77,8 +79,9 @@ public class UniqueEntryStoreStrategy im
}
}
}
-
+
private static void insert(NodeBuilder index, String key, String value) {
+ ApproximateCounter.adjustCount(index, 1);
NodeBuilder k = index.child(key);
ArrayList<String> list = new ArrayList<String>();
list.add(value);
@@ -170,4 +173,5 @@ public class UniqueEntryStoreStrategy im
public long count(final Filter filter, NodeState indexMeta, Set<String> values, int max) {
return count(indexMeta, values, max);
}
+
}
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/nodetype/write/InitialContent.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/nodetype/write/InitialContent.java?rev=1642683&r1=1642682&r2=1642683&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/nodetype/write/InitialContent.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/nodetype/write/InitialContent.java Mon Dec 1 13:48:24 2014
@@ -16,6 +16,9 @@
*/
package org.apache.jackrabbit.oak.plugins.nodetype.write;
+import static org.apache.jackrabbit.oak.api.Type.NAME;
+import static org.apache.jackrabbit.oak.plugins.index.IndexConstants.INDEX_DEFINITIONS_NODE_TYPE;
+import static org.apache.jackrabbit.oak.plugins.index.IndexConstants.TYPE_PROPERTY_NAME;
import static org.apache.jackrabbit.oak.plugins.memory.EmptyNodeState.EMPTY_NODE;
import com.google.common.collect.ImmutableList;
@@ -24,6 +27,7 @@ import org.apache.jackrabbit.oak.api.Typ
import org.apache.jackrabbit.oak.core.SystemRoot;
import org.apache.jackrabbit.oak.plugins.index.IndexConstants;
import org.apache.jackrabbit.oak.plugins.index.IndexUtils;
+import org.apache.jackrabbit.oak.plugins.index.counter.NodeCounterEditorProvider;
import org.apache.jackrabbit.oak.plugins.memory.MemoryNodeStore;
import org.apache.jackrabbit.oak.plugins.memory.ModifiedNodeState;
import org.apache.jackrabbit.oak.plugins.name.NamespaceEditorProvider;
@@ -82,6 +86,12 @@ public class InitialContent implements R
// the cost of using the property index for "@primaryType is not null" is very high
nt.setProperty(IndexConstants.ENTRY_COUNT_PROPERTY_NAME, Long.valueOf(Long.MAX_VALUE));
IndexUtils.createReferenceIndex(index);
+
+ index.child("counter")
+ .setProperty(JCR_PRIMARYTYPE, INDEX_DEFINITIONS_NODE_TYPE, NAME)
+ .setProperty(TYPE_PROPERTY_NAME, NodeCounterEditorProvider.TYPE)
+ .setProperty(IndexConstants.ASYNC_PROPERTY_NAME,
+ IndexConstants.ASYNC_PROPERTY_NAME);
}
NodeState base = builder.getNodeState();
Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/util/ApproximateCounter.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/util/ApproximateCounter.java?rev=1642683&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/util/ApproximateCounter.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/util/ApproximateCounter.java Mon Dec 1 13:48:24 2014
@@ -0,0 +1,122 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.util;
+
+import java.util.Random;
+
+import org.apache.jackrabbit.oak.api.PropertyState;
+import org.apache.jackrabbit.oak.api.Type;
+import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
+
+/**
+ * An approximate counter algorithm.
+ */
+public class ApproximateCounter {
+
+ public static final String COUNT_PROPERTY_NAME = ":count";
+ public static final int COUNT_RESOLUTION = 100;
+
+ private static final Random RANDOM = new Random();
+
+ /**
+ * Calculate the approximate offset from a given offset. The offset is the
+ * number of added or removed entries. The result is 0 in most of the cases,
+ * but sometimes it is a (positive or negative) multiple of the resolution,
+ * such that on average, the sum of the returned value matches the sum of
+ * the passed offsets.
+ *
+ * @param offset the high-resolution input offset
+ * @param resolution the resolution
+ * @return the low-resolution offset (most of the time 0)
+ */
+ public static long calculateOffset(long offset, int resolution) {
+ if (offset == 0 || resolution <= 1) {
+ return offset;
+ }
+ int add = resolution;
+ if (offset < 0) {
+ offset = -offset;
+ add = -add;
+ }
+ long result = 0;
+ for (long i = 0; i < offset; i++) {
+ if (RANDOM.nextInt(resolution) == 0) {
+ result += add;
+ }
+ }
+ return result;
+ }
+
+ /**
+ * This method ensures that the new approximate count (the old count plus
+ * the calculated offset) does not go below 0.
+ *
+ * Also, for large counts and resolutions larger than 10, it reduces the
+ * resolution by a factor of 10 (further reducing the number of updates
+ * needed by a factor of 10).
+ *
+ * @param oldCount the old count
+ * @param calculatedOffset the calculated offset (may not be 0)
+ * @param resolution the new (lower) resolution
+ * @return the new offset
+ */
+ public static long adjustOffset(long oldCount, long calculatedOffset,
+ int resolution) {
+ if (oldCount + calculatedOffset < 0) {
+ return -oldCount;
+ }
+ if (resolution <= 10 || oldCount < resolution * 10) {
+ return calculatedOffset;
+ }
+ return RANDOM.nextInt(10) == 0 ? calculatedOffset * 10 : 0;
+ }
+
+ /**
+ * Set the seed of the random number generator (used for testing).
+ *
+ * @param seed the new seed
+ */
+ static void setSeed(int seed) {
+ RANDOM.setSeed(seed);
+ }
+
+ /**
+ * Adjust a counter in the given node.
+ *
+ * @param builder the node builder
+ * @param offset the offset
+ */
+ public static void adjustCount(NodeBuilder builder, long offset) {
+ offset = ApproximateCounter.calculateOffset(
+ offset, COUNT_RESOLUTION);
+ if (offset == 0) {
+ return;
+ }
+ PropertyState p = builder.getProperty(COUNT_PROPERTY_NAME);
+ long count = p == null ? 0 : p.getValue(Type.LONG);
+ offset = ApproximateCounter.adjustOffset(count,
+ offset, COUNT_RESOLUTION);
+ if (offset == 0) {
+ return;
+ }
+ count += offset;
+ builder.setProperty(COUNT_PROPERTY_NAME, count);
+ }
+
+}
Added: jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/util/ApproximateCounterTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/util/ApproximateCounterTest.java?rev=1642683&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/util/ApproximateCounterTest.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/util/ApproximateCounterTest.java Mon Dec 1 13:48:24 2014
@@ -0,0 +1,117 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.jackrabbit.oak.util;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Random;
+
+import org.junit.Test;
+
+public class ApproximateCounterTest {
+
+ @Test
+ public void veryHighResolution() {
+ for (int i = -100; i < 100; i++) {
+ assertEquals(i, ApproximateCounter.calculateOffset(i, -1));
+ assertEquals(i, ApproximateCounter.calculateOffset(i, 0));
+ assertEquals(i, ApproximateCounter.calculateOffset(i, 1));
+ }
+ }
+
+ @Test
+ public void regularResolution() {
+ ApproximateCounter.setSeed(0);
+ long result = 0;
+ long count = 100000;
+ int nonZero = 0;
+ for (long i = 0; i < count; i++) {
+ long offset = ApproximateCounter.calculateOffset(1, 1000);
+ if (offset != 0) {
+ nonZero++;
+ result += offset;
+ }
+ }
+ // most of the time, 0 needs to be returned
+ assertTrue(nonZero < count / 500);
+ // the expected result is within a certain range
+ assertTrue(Math.abs(result - count) < count / 10);
+ }
+
+ @Test
+ public void addRemove() {
+ ApproximateCounter.setSeed(0);
+ Random r = new Random(1);
+ long result = 0;
+ long exactResult = 0;
+ long count = 100000;
+ long sumChange = 0;
+ int nonZero = 0;
+ for (long i = 0; i < count; i++) {
+ int o = r.nextInt(20) - 10;
+ exactResult += o;
+ sumChange += Math.abs(o);
+ long offset = ApproximateCounter.calculateOffset(o, 1000);
+ if (offset != 0) {
+ nonZero++;
+ result += offset;
+ }
+ }
+ // most of the time, 0 needs to be returned
+ assertTrue(nonZero < count / 50);
+ // the expected result is within a certain range
+ assertTrue(Math.abs(result - exactResult) < sumChange / 10);
+ }
+
+ @Test
+ public void lowResolution() {
+ ApproximateCounter.setSeed(0);
+ long result = 0;
+ long count = 100000;
+ int nonZero = 0;
+ for (long i = 0; i < count; i++) {
+ long offset = ApproximateCounter.calculateOffset(1, 100);
+ if (offset != 0) {
+ offset = ApproximateCounter.adjustOffset(result, offset, 100);
+ }
+ if (offset != 0) {
+ nonZero++;
+ result += offset;
+ }
+ }
+ // most of the time, 0 needs to be returned
+ assertTrue(nonZero < count / 500);
+ // the expected result is within a certain range
+ assertTrue(Math.abs(result - count) < count / 10);
+ }
+
+ @Test
+ public void keepAboveZero() {
+ // adjustOffset ensures that the resulting count is larger or equal to 0
+ assertEquals(1234, ApproximateCounter.adjustOffset(-1234, -100, 10));
+ }
+
+ @Test
+ public void highResolutionAdjust() {
+ // adjustOffset with resolution of 1 should not affect the result
+ for (int i = 0; i < 10; i++) {
+ assertEquals(123, ApproximateCounter.adjustOffset(i, 123, 1));
+ }
+ }
+
+}
Modified: jackrabbit/oak/trunk/oak-jcr/src/main/java/org/apache/jackrabbit/oak/jcr/Jcr.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-jcr/src/main/java/org/apache/jackrabbit/oak/jcr/Jcr.java?rev=1642683&r1=1642682&r2=1642683&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-jcr/src/main/java/org/apache/jackrabbit/oak/jcr/Jcr.java (original)
+++ jackrabbit/oak/trunk/oak-jcr/src/main/java/org/apache/jackrabbit/oak/jcr/Jcr.java Mon Dec 1 13:48:24 2014
@@ -29,6 +29,7 @@ import org.apache.jackrabbit.oak.jcr.rep
import org.apache.jackrabbit.oak.plugins.commit.ConflictValidatorProvider;
import org.apache.jackrabbit.oak.plugins.commit.JcrConflictHandler;
import org.apache.jackrabbit.oak.plugins.index.IndexEditorProvider;
+import org.apache.jackrabbit.oak.plugins.index.counter.NodeCounterEditorProvider;
import org.apache.jackrabbit.oak.plugins.index.nodetype.NodeTypeIndexProvider;
import org.apache.jackrabbit.oak.plugins.index.property.OrderedPropertyIndexEditorProvider;
import org.apache.jackrabbit.oak.plugins.index.property.OrderedPropertyIndexProvider;
@@ -84,6 +85,7 @@ public class Jcr {
with(new ReferenceIndexProvider());
with(new PropertyIndexEditorProvider());
+ with(new NodeCounterEditorProvider());
with(new PropertyIndexProvider());
with(new OrderedPropertyIndexProvider());