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 2016/05/03 13:38:18 UTC
svn commit: r1742102 - in
/jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak:
plugins/index/counter/ plugins/index/counter/jmx/ util/
Author: thomasm
Date: Tue May 3 11:38:18 2016
New Revision: 1742102
URL: http://svn.apache.org/viewvc?rev=1742102&view=rev
Log:
OAK-4275 Backport OAK-4065 (Counter index can get out of sync) to 1.2 and 1.4
Added:
jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/util/SipHash.java
Modified:
jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditor.java
jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditorProvider.java
jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java
Modified: jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditor.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditor.java?rev=1742102&r1=1742101&r2=1742102&view=diff
==============================================================================
--- jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditor.java (original)
+++ jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditor.java Tue May 3 11:38:18 2016
@@ -24,10 +24,12 @@ import org.apache.jackrabbit.oak.api.Com
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.plugins.index.counter.jmx.NodeCounter;
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;
+import org.apache.jackrabbit.oak.util.SipHash;
/**
* An approximate descendant node counter mechanism.
@@ -35,18 +37,40 @@ import org.apache.jackrabbit.oak.util.Ap
public class NodeCounterEditor implements Editor {
public static final String DATA_NODE_NAME = ":index";
+
+ // the property that is used with the "old" (pseudo-random number generator based) method
public static final String COUNT_PROPERTY_NAME = ":count";
+
+ // the property that is used with the "new" (hash of the path based) method
+ public static final String COUNT_HASH_PROPERTY_NAME = ":cnt";
+
public static final int DEFAULT_RESOLUTION = 1000;
private final NodeCounterRoot root;
private final NodeCounterEditor parent;
private final String name;
private long countOffset;
+ private SipHash hash;
- public NodeCounterEditor(NodeCounterRoot root, NodeCounterEditor parent, String name) {
+ public NodeCounterEditor(NodeCounterRoot root, NodeCounterEditor parent, String name, SipHash hash) {
this.parent = parent;
this.root = root;
this.name = name;
+ this.hash = hash;
+ }
+
+ private SipHash getHash() {
+ if (hash != null) {
+ return hash;
+ }
+ SipHash h;
+ if (parent == null) {
+ h = new SipHash(root.seed);
+ } else {
+ h = new SipHash(parent.getHash(), name.hashCode());
+ }
+ this.hash = h;
+ return h;
}
@Override
@@ -58,6 +82,15 @@ public class NodeCounterEditor implement
@Override
public void leave(NodeState before, NodeState after)
throws CommitFailedException {
+ if (NodeCounter.COUNT_HASH) {
+ leaveNew(before, after);
+ return;
+ }
+ leaveOld(before, after);
+ }
+
+ private void leaveOld(NodeState before, NodeState after)
+ throws CommitFailedException {
long offset = ApproximateCounter.calculateOffset(
countOffset, root.resolution);
if (offset == 0) {
@@ -84,6 +117,27 @@ public class NodeCounterEditor implement
builder.setProperty(COUNT_PROPERTY_NAME, count);
}
}
+
+ public void leaveNew(NodeState before, NodeState after)
+ throws CommitFailedException {
+ if (countOffset == 0) {
+ return;
+ }
+ NodeBuilder builder = getBuilder();
+ PropertyState p = builder.getProperty(COUNT_HASH_PROPERTY_NAME);
+ long count = p == null ? 0 : p.getValue(Type.LONG);
+ count += countOffset;
+ root.callback.indexUpdate();
+ if (count <= 0) {
+ if (builder.getChildNodeCount(1) >= 0) {
+ builder.removeProperty(COUNT_HASH_PROPERTY_NAME);
+ } else {
+ builder.remove();
+ }
+ } else {
+ builder.setProperty(COUNT_HASH_PROPERTY_NAME, count);
+ }
+ }
private NodeBuilder getBuilder() {
if (parent == null) {
@@ -113,23 +167,41 @@ public class NodeCounterEditor implement
@CheckForNull
public Editor childNodeChanged(String name, NodeState before, NodeState after)
throws CommitFailedException {
- return getChildIndexEditor(this, name);
+ return getChildIndexEditor(name, null);
}
@Override
@CheckForNull
public Editor childNodeAdded(String name, NodeState after)
throws CommitFailedException {
+ if (NodeCounter.COUNT_HASH) {
+ SipHash h = new SipHash(getHash(), name.hashCode());
+ // with bitMask=1024: with a probability of 1:1024,
+ if ((h.hashCode() & root.bitMask) == 0) {
+ // add 1024
+ count(root.bitMask + 1);
+ }
+ return getChildIndexEditor(name, h);
+ }
count(1);
- return getChildIndexEditor(this, name);
+ return getChildIndexEditor(name, null);
}
@Override
@CheckForNull
public Editor childNodeDeleted(String name, NodeState before)
throws CommitFailedException {
+ if (NodeCounter.COUNT_HASH) {
+ SipHash h = new SipHash(getHash(), name.hashCode());
+ // with bitMask=1024: with a probability of 1:1024,
+ if ((h.hashCode() & root.bitMask) == 0) {
+ // subtract 1024
+ count(-(root.bitMask + 1));
+ }
+ return getChildIndexEditor(name, h);
+ }
count(-1);
- return getChildIndexEditor(this, name);
+ return getChildIndexEditor(name, null);
}
private void count(int offset) {
@@ -139,16 +211,27 @@ public class NodeCounterEditor implement
}
}
- private Editor getChildIndexEditor(NodeCounterEditor nodeCounterEditor,
- String name) {
- return new NodeCounterEditor(root, this, name);
+ private Editor getChildIndexEditor(String name, SipHash hash) {
+ return new NodeCounterEditor(root, this, name, hash);
}
public static class NodeCounterRoot {
- int resolution = DEFAULT_RESOLUTION;
- NodeBuilder definition;
- NodeState root;
- IndexUpdateCallback callback;
+ final int resolution;
+ final long seed;
+ final int bitMask;
+ final NodeBuilder definition;
+ final NodeState root;
+ final IndexUpdateCallback callback;
+
+ NodeCounterRoot(int resolution, long seed, NodeBuilder definition, NodeState root, IndexUpdateCallback callback) {
+ this.resolution = resolution;
+ this.seed = seed;
+ // if resolution is 1000, then the bitMask is 1023 (bits 0..9 set)
+ this.bitMask = (Integer.highestOneBit(resolution) * 2) - 1;
+ this.definition = definition;
+ this.root = root;
+ this.callback = callback;
+ }
}
}
Modified: jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditorProvider.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditorProvider.java?rev=1742102&r1=1742101&r2=1742102&view=diff
==============================================================================
--- jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditorProvider.java (original)
+++ jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/NodeCounterEditorProvider.java Tue May 3 11:38:18 2016
@@ -18,6 +18,8 @@
*/
package org.apache.jackrabbit.oak.plugins.index.counter;
+import java.util.UUID;
+
import javax.annotation.CheckForNull;
import javax.annotation.Nonnull;
@@ -29,6 +31,7 @@ import org.apache.jackrabbit.oak.api.Typ
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.plugins.index.counter.jmx.NodeCounter;
import org.apache.jackrabbit.oak.spi.commit.Editor;
import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
import org.apache.jackrabbit.oak.spi.state.NodeState;
@@ -41,6 +44,8 @@ public class NodeCounterEditorProvider i
public static final String RESOLUTION = "resolution";
+ public static final String SEED = "seed";
+
@Override
@CheckForNull
public Editor getIndexEditor(@Nonnull String type,
@@ -49,15 +54,28 @@ public class NodeCounterEditorProvider i
if (!TYPE.equals(type)) {
return null;
}
- NodeCounterRoot rootData = new NodeCounterRoot();
- rootData.callback = callback;
- rootData.definition = definition;
- rootData.root = root;
+ int resolution;
PropertyState s = definition.getProperty(RESOLUTION);
+ if (s == null) {
+ resolution = NodeCounterEditor.DEFAULT_RESOLUTION;
+ } else {
+ resolution = s.getValue(Type.LONG).intValue();
+ }
+ long seed;
+ s = definition.getProperty(SEED);
if (s != null) {
- rootData.resolution = s.getValue(Type.LONG).intValue();
+ seed = s.getValue(Type.LONG).intValue();
+ } else {
+ seed = 0;
+ if (NodeCounter.COUNT_HASH) {
+ // create a random number (that way we can also check if this feature is enabled)
+ seed = UUID.randomUUID().getMostSignificantBits();
+ definition.setProperty(SEED, seed);
+ }
}
- return new NodeCounterEditor(rootData, null, "/");
+ NodeCounterRoot rootData = new NodeCounterRoot(
+ resolution, seed, definition, root, callback);
+ return new NodeCounterEditor(rootData, null, "/", null);
}
}
Modified: jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java?rev=1742102&r1=1742101&r2=1742102&view=diff
==============================================================================
--- jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java (original)
+++ jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/index/counter/jmx/NodeCounter.java Tue May 3 11:38:18 2016
@@ -37,6 +37,13 @@ import org.apache.jackrabbit.oak.util.Ap
*/
public class NodeCounter implements NodeCounterMBean {
+ /**
+ * Approximate count using the hashed name (deterministically, so that after
+ * adding a removing all nodes the count goes back to zero).
+ */
+ public final static boolean COUNT_HASH =
+ Boolean.parseBoolean(System.getProperty("oak.countHashed", "true"));
+
private final NodeStore store;
public NodeCounter(NodeStore store) {
@@ -90,6 +97,14 @@ public class NodeCounter implements Node
return syncCount;
}
}
+ if (COUNT_HASH) {
+ return getCombinedCount(root, path, s, max);
+ }
+ return getEstimatedNodeCountOld(root, s, path, max);
+ }
+
+ private static long getEstimatedNodeCountOld(NodeState root, NodeState s, String path, boolean max) {
+ // old code from here
PropertyState p = s.getProperty(NodeCounterEditor.COUNT_PROPERTY_NAME);
if (p != null) {
long x = p.getValue(Type.LONG);
@@ -135,6 +150,47 @@ public class NodeCounter implements Node
return x;
}
+ private static long getCombinedCount(NodeState root, String path, NodeState s, boolean max) {
+ Long value = getCombinedCountIfAvailable(s);
+ if (value != null) {
+ return value + (max ? ApproximateCounter.COUNT_RESOLUTION : 0);
+ }
+ // check in the counter index (if it exists)
+ s = child(root,
+ IndexConstants.INDEX_DEFINITIONS_NAME,
+ "counter");
+ if (s == null || !s.exists()) {
+ // no index
+ return -1;
+ }
+ s = child(s, NodeCounterEditor.DATA_NODE_NAME);
+ s = child(s, PathUtils.elements(path));
+ if (s != null && s.exists()) {
+ value = getCombinedCountIfAvailable(s);
+ if (value != null) {
+ return value + (max ? ApproximateCounter.COUNT_RESOLUTION : 0);
+ }
+ }
+ // we have an index, but no data
+ return max ? ApproximateCounter.COUNT_RESOLUTION * 20 : 0;
+ }
+
+ private static Long getCombinedCountIfAvailable(NodeState s) {
+ boolean found = false;
+ long x = 0;
+ PropertyState p = s.getProperty(NodeCounterEditor.COUNT_HASH_PROPERTY_NAME);
+ if (p != null) {
+ found = true;
+ x = p.getValue(Type.LONG);
+ }
+ p = s.getProperty(NodeCounterEditor.COUNT_PROPERTY_NAME);
+ if (p != null) {
+ found = true;
+ x += p.getValue(Type.LONG);
+ }
+ return found ? x : null;
+ }
+
@Override
public String getEstimatedChildNodeCounts(String path, int level) {
StringBuilder buff = new StringBuilder();
Added: jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/util/SipHash.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/util/SipHash.java?rev=1742102&view=auto
==============================================================================
--- jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/util/SipHash.java (added)
+++ jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/util/SipHash.java Tue May 3 11:38:18 2016
@@ -0,0 +1,70 @@
+/*
+ * 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;
+
+/**
+ * An implementation of the SipHash-2-2 function, to prevent hash flooding.
+ */
+public class SipHash {
+
+ private final long v0, v1, v2, v3;
+
+ public SipHash(long seed) {
+ long k0 = seed;
+ long k1 = Long.rotateLeft(seed, 32);
+ v0 = k0 ^ 0x736f6d6570736575L;
+ v1 = k1 ^ 0x646f72616e646f6dL;
+ v2 = k0 ^ 0x6c7967656e657261L;
+ v3 = k1 ^ 0x7465646279746573L;
+ }
+
+ public SipHash(SipHash parent, long m) {
+ long v0 = parent.v0;
+ long v1 = parent.v1;
+ long v2 = parent.v2;
+ long v3 = parent.v3;
+ int repeat = 2;
+ for (int i = 0; i < repeat; i++) {
+ v0 += v1;
+ v2 += v3;
+ v1 = Long.rotateLeft(v1, 13);
+ v3 = Long.rotateLeft(v3, 16);
+ v1 ^= v0;
+ v3 ^= v2;
+ v0 = Long.rotateLeft(v0, 32);
+ v2 += v1;
+ v0 += v3;
+ v1 = Long.rotateLeft(v1, 17);
+ v3 = Long.rotateLeft(v3, 21);
+ v1 ^= v2;
+ v3 ^= v0;
+ v2 = Long.rotateLeft(v2, 32);
+ }
+ v0 ^= m;
+ this.v0 = v0;
+ this.v1 = v1;
+ this.v2 = v2;
+ this.v3= v3;
+ }
+
+ @Override
+ public int hashCode() {
+ long x = v0 ^ v1 ^ v2 ^ v3;
+ return (int) (x ^ (x >>> 16));
+ }
+
+}