You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jackrabbit.apache.org by th...@apache.org on 2012/01/18 13:40:17 UTC
svn commit: r1232860 - in /jackrabbit/sandbox/microkernel/src:
main/java/org/apache/jackrabbit/mk/mem/
test/java/org/apache/jackrabbit/mk/large/
test/java/org/apache/jackrabbit/mk/mem/
Author: thomasm
Date: Wed Jan 18 12:40:16 2012
New Revision: 1232860
URL: http://svn.apache.org/viewvc?rev=1232860&view=rev
Log:
More efficient revision data structure (similar to a skip list)
Modified:
jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/MemoryKernelImpl.java
jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java
jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java
jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/LargeNodeTest.java
jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/mem/MemoryNodeTest.java
Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/MemoryKernelImpl.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/MemoryKernelImpl.java?rev=1232860&r1=1232859&r2=1232860&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/MemoryKernelImpl.java (original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/MemoryKernelImpl.java Wed Jan 18 12:40:16 2012
@@ -38,23 +38,22 @@ import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
-import java.util.Iterator;
/*
Node structure:
/head/rev = 100
-/head/time = now()
-/head/commit/diff = "+ "/test ..."
+/head/time = millis
+/head/commit/diff = [+ "/test"{}]
/head/commit/msg = "hello ..."
-/head/data/<user root>
-/old/90/rev = 90
-/old/90/data/<user root of revision 90>
-/old/91/rev = 91
-/old/99/rev = 99
-/old/old/80/rev = 80
-/old/old/89/rev = 89
+/head/config/ (optional)
+/head/data/
+/99/head/time = millis
+/99/98/head
+/99/98/97/head
+/99/90/head
+/99/90/89/head
*/
@@ -64,14 +63,16 @@ Node structure:
*/
public class MemoryKernelImpl extends WrapperBase implements MicroKernel {
- private static final int MAX_REVISIONS_PER_NODE = 5;
private static final HashMap<String, MemoryKernelImpl> INSTANCES = new HashMap<String, MemoryKernelImpl>();
+ private static final int REV_SKIP_OFFSET = 20;
+
private final String name;
private final AbstractBlobStore ds;
private final NonDescendingClock clock = new NonDescendingClock(System.currentTimeMillis());
private final CommitGate gate = new CommitGate();
private final Cache<Long, Revision> revisionCache = Cache.newInstance(null, 1024 * 1024);
+
private volatile long headRevId;
private volatile String headRevision;
private NodeMap nodeMap;
@@ -102,10 +103,8 @@ public class MemoryKernelImpl extends Wr
Revision revNode = new Revision(0, 0, "", "");
head = revNode.store(head, new NodeImpl(nodeMap, 0));
head.addChildNode("data", new NodeImpl(nodeMap, 0));
- head.addChildNode("config", new NodeImpl(nodeMap, 0));
NodeImpl root = new NodeImpl(nodeMap, 0);
root.addChildNode("head", head);
- root.addChildNode("old", new NodeImpl(nodeMap, 0));
nodeMap.commit(root);
} else {
NodeImpl head = getRoot().getNode("head");
@@ -161,9 +160,12 @@ public class MemoryKernelImpl extends Wr
}
private void applyConfig(NodeImpl head) {
- NodeImpl config = head.getNode("config");
- for (int i = 0, size = config.getPropertyCount(); i < size; i++) {
- nodeMap.setSetting(config.getProperty(i), config.getPropertyValue(i));
+ // /head/config doesn't always exist
+ if (head.exists("config")) {
+ NodeImpl config = head.getNode("config");
+ for (int i = 0, size = config.getPropertyCount(); i < size; i++) {
+ nodeMap.setSetting(config.getProperty(i), config.getPropertyValue(i));
+ }
}
}
@@ -242,6 +244,9 @@ public class MemoryKernelImpl extends Wr
}
if (isConfigChange) {
String p = PathUtils.relativize(":root/head", from);
+ if (!head.exists("config")) {
+ head = head.setChild("config", new NodeImpl(nodeMap, rev), rev);
+ }
head = head.cloneAndSetProperty(p, value, rev);
applyConfig(head);
} else {
@@ -340,13 +345,24 @@ public class MemoryKernelImpl extends Wr
revisionCache.put(rev, revNode);
head = revNode.store(head, new NodeImpl(nodeMap, rev));
root = root.setChild("head", head, rev);
- NodeImpl old = root.getNode("old");
- if (old.getChildCount() > MAX_REVISIONS_PER_NODE) {
- NodeImpl newOld = new NodeImpl(nodeMap, rev);
- old = newOld.setChild("old", old, rev);
+ String old = Revision.formatId(oldRevision);
+ NodeImpl oldRev = new NodeImpl(nodeMap, rev);
+ oldRev.addChildNode("head", oldHead);
+ String lastRev = Revision.formatId(oldRevision - 1);
+ if (root.exists(lastRev)) {
+ NodeImpl lastRevNode = root.getNode(lastRev);
+ root = root.cloneAndRemoveChildNode(lastRev, rev);
+ oldRev.setChild(lastRev, lastRevNode, rev);
+ if (oldRevision % REV_SKIP_OFFSET == 0) {
+ long skip = oldRevision - REV_SKIP_OFFSET;
+ NodeImpl n = getRevisionNode(getRoot(), skip, skip);
+ if (n != null) {
+ oldRev.setChild(Revision.formatId(skip), n, rev);
+ // TODO remove old link to reduce descendant count
+ }
+ }
}
- old = old.setChild(Revision.formatId(oldRevision), oldHead, rev);
- root = root.setChild("old", old, rev);
+ root = root.setChild(old, oldRev, rev);
nodeMap.commit(root);
headRevId = rev;
headRevision = Revision.formatId(rev);
@@ -368,16 +384,24 @@ public class MemoryKernelImpl extends Wr
Revision r = Revision.get(node.getNode("head"));
if (since < r.getTime() && maxEntries > 0) {
revisions.add(r);
- while (node.exists("old") && revisions.size() < maxEntries) {
- node = node.getNode("old");
- for (Iterator<String> it = node.getChildNodeNames(Integer.MAX_VALUE); it.hasNext();) {
- r = Revision.get(node.getNode(it.next()));
- if (r != null) {
- revisions.add(r);
+ while (revisions.size() < maxEntries) {
+ String newest = null;
+ for (int i = 0;; i++) {
+ String next = node.getChildNodeName(i);
+ if (next == null) {
+ break;
+ } else if (!next.equals("head") && !next.equals("config")) {
+ if (newest == null || next.compareTo(newest) >= 0) {
+ newest = next;
+ }
}
}
- if (since >= r.getTime()) {
- break;
+ if (newest != null) {
+ r = Revision.get(node);
+ if (r == null) {
+ break;
+ }
+ revisions.add(r);
}
}
}
@@ -401,29 +425,67 @@ public class MemoryKernelImpl extends Wr
NodeImpl node = getRoot();
ArrayList<Revision> revisions = new ArrayList<Revision>();
Revision r = Revision.get(node.getNode("head"));
- if (r.getId() >= fromRev) {
+ if (r.getId() >= fromRev && r.getId() <= toRev) {
revisions.add(r);
}
- while (r.getId() > fromRev && node.exists("old")) {
- node = node.getNode("old");
- for (Iterator<String> it = node.getChildNodeNames(Integer.MAX_VALUE); it.hasNext();) {
- r = Revision.get(node.getNode(it.next()));
- if (r != null && r.getId() >= fromRev && r.getId() <= toRev) {
+ if (r.getId() > fromRev) {
+ node = getRevisionNode(node, fromRev, toRev);
+ while (node != null) {
+ r = Revision.get(node.getNode("head"));
+ if (r.getId() >= fromRev && r.getId() <= toRev) {
r = revisionCache.replace(r.getId(), r);
revisions.add(r);
}
+ String next = Revision.formatId(r.getId() - 1);
+ if (!node.exists(next)) {
+ break;
+ }
+ node = node.getNode(next);
}
}
- Collections.sort(revisions);
JsopStream buff = new JsopStream().array().newline();
- for (Revision rev : revisions) {
+ for (int i = revisions.size() - 1; i >= 0; i--) {
+ Revision rev = revisions.get(i);
if (rev.getId() >= fromRev && rev.getId() <= toRev) {
rev.appendJournal(buff);
}
}
return buff.endArray();
+ }
+
+ private NodeImpl getRevisionNode(NodeImpl node, long fromRev, long toRev) {
+ while (true) {
+ long next = -1;
+ String nextRev = null;
+ for (int i = 0;; i++) {
+ String n = node.getChildNodeName(i);
+ if (n == null) {
+ break;
+ }
+ if ("head".equals(n)) {
+ continue;
+ }
+ long rev = Revision.parseId(n);
+ if (next == -1 || (rev >= toRev && rev < next)) {
+ next = rev;
+ nextRev = n;
+ }
+ }
+ if (next == -1 || fromRev > next) {
+ if (!node.exists("head")) {
+ return null;
+ }
+ node = node.getNode("head");
+ } else {
+ node = node.getNode(nextRev);
+ if (next <= toRev) {
+ return node;
+ }
+ }
+ }
}
+
public JsopReader diffStream(String fromRevisionId, String toRevisionId, String path) {
// TODO implement if required
return new JsopStream();
@@ -458,10 +520,10 @@ public class MemoryKernelImpl extends Wr
} else if (path.startsWith("/:info")) {
n = nodeMap.getInfo(PathUtils.relativize("/:info", path));
} else {
- n = getRevision(revisionId).getNode(path.substring(1));
+ n = getRevisionDataRoot(revisionId).getNode(path.substring(1));
}
} else {
- n = getRevision(revisionId).getNode(path.substring(1));
+ n = getRevisionDataRoot(revisionId).getNode(path.substring(1));
}
if (n == null) {
throw ExceptionFactory.get("Path not found: " + path);
@@ -471,27 +533,27 @@ public class MemoryKernelImpl extends Wr
return json;
}
- private NodeImpl getRevision(String revisionId) {
+ private NodeImpl getRevisionDataRoot(String revisionId) {
+ NodeImpl rev = getRevisionIfExists(revisionId);
+ if (rev == null) {
+ throw ExceptionFactory.get("Revision not found: " + revisionId);
+ }
+ return rev.getNode("data");
+ }
+
+ private NodeImpl getRevisionIfExists(String revisionId) {
NodeImpl node = getRoot();
NodeImpl head = node.getNode("head");
- String headRev = head.getProperty("rev");
+ String headRev;
+ headRev = head.getProperty("rev");
headRev = headRev == null ? null : JsopTokenizer.decodeQuoted(headRev);
// we can't rely on headRevId, as it's a volatile field
if (revisionId.equals(headRev)) {
- node = head;
+ return head;
} else {
- while (true) {
- if (!node.exists("old")) {
- throw ExceptionFactory.get("Revision not found: " + revisionId);
- }
- node = node.getNode("old");
- if (node.exists(revisionId)) {
- node = node.getNode(revisionId);
- break;
- }
- }
+ long rev = Revision.parseId(revisionId);
+ return getRevisionNode(node, rev, rev).getNode("head");
}
- return node.getNode("data");
}
public boolean nodeExists(String path, String revisionId) {
@@ -504,7 +566,7 @@ public class MemoryKernelImpl extends Wr
return true;
}
// TODO possibly use a cache / a bloom filter
- return getRevision(revisionId).exists(path.substring(1));
+ return getRevisionDataRoot(revisionId).exists(path.substring(1));
}
public long getLength(String blobId) {
Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java?rev=1232860&r1=1232859&r2=1232860&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java (original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/NodeImpl.java Wed Jan 18 12:40:16 2012
@@ -47,12 +47,12 @@ public class NodeImpl implements Cache.V
/**
* The total number of child nodes.
*/
- public static final String DESCENDANT_COUNT = ":descendantCount";
+ public static final String DESCENDANT_COUNT = ":size";
/**
* The total number of child nodes that are stored inline.
*/
- public static final String DESCENDANT_INLINE_COUNT = ":descendantInlineCount";
+ public static final String DESCENDANT_INLINE_COUNT = ":sizeInline";
/**
* The content hash.
@@ -570,11 +570,15 @@ public class NodeImpl implements Cache.V
}
public String asString() {
+ // TODO ALLOW_UNQUOTED_FIELD_NAMES to safe space
+ // (check what Javascript supports and what are the keywords)
JsopWriter json = new JsopBuilder();
json.setLineLength(120);
+ boolean inline = true;
if (id != null && !id.isInline()) {
String nodeId = map.formatId(id);
if (nodeId != null) {
+ inline = false;
json.encodedValue(nodeId).tag('=');
}
}
@@ -590,12 +594,18 @@ public class NodeImpl implements Cache.V
json.key(HASH).value(StringUtils.convertBytesToHex(hash));
}
if (childNodes != null && childNodes.size() > 0) {
- if (descendantCount > childNodes.size()) {
- json.key(DESCENDANT_COUNT).value(descendantCount);
+ if (map.getDescendantCount()) {
+ if (descendantCount > childNodes.size()) {
+ json.key(DESCENDANT_COUNT).value(descendantCount);
+ }
}
childNodes.append(json, map);
}
- return json.endObject().toString();
+ json.endObject();
+ if (!inline) {
+ json.tag(';');
+ }
+ return json.toString();
}
public static NodeImpl fromString(NodeMap map, String s) {
Modified: jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java?rev=1232860&r1=1232859&r2=1232860&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java (original)
+++ jackrabbit/sandbox/microkernel/src/main/java/org/apache/jackrabbit/mk/mem/Revision.java Wed Jan 18 12:40:16 2012
@@ -65,14 +65,24 @@ public class Revision implements Compara
private String getDiff() {
if (diff == null) {
- diff = getCommitValue("diff");
+ String s = getCommitValue("diff");
+ if (s.length() == 0) {
+ s = "";
+ } else if (s.charAt(0) == '[') {
+ // remove the surrounding "[" and "]"
+ s = s.substring(1, s.length() - 1);
+ } else {
+ s = JsopTokenizer.decodeQuoted(s);
+ }
+ diff = s;
}
return diff;
}
private String getMsg() {
if (msg == null) {
- msg = getCommitValue("msg");
+ String m = getCommitValue("msg");
+ msg = m.length() == 0 ? "" : JsopTokenizer.decodeQuoted(m);
}
return msg;
}
@@ -81,7 +91,7 @@ public class Revision implements Compara
if (node.exists("commit")) {
String v = node.getNode("commit").getProperty(s);
if (v != null) {
- return JsopTokenizer.decodeQuoted(v);
+ return v;
}
}
return "";
@@ -109,7 +119,11 @@ public class Revision implements Compara
NodeImpl store(NodeImpl head, NodeImpl commit) {
head = head.cloneAndSetProperty("rev", JsopBuilder.encode(formatId(id)), id);
head = head.cloneAndSetProperty("time", Long.toString(time), id);
- commit.setProperty("diff", JsopBuilder.encode(diff));
+ if (diff.indexOf(";\n") >= 0) {
+ commit.setProperty("diff", JsopBuilder.encode(diff));
+ } else {
+ commit.setProperty("diff", "[" + diff + "]");
+ }
if (msg != null) {
commit.setProperty("msg", JsopBuilder.encode(msg));
}
Modified: jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/LargeNodeTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/LargeNodeTest.java?rev=1232860&r1=1232859&r2=1232860&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/LargeNodeTest.java (original)
+++ jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/large/LargeNodeTest.java Wed Jan 18 12:40:16 2012
@@ -73,7 +73,6 @@ public class LargeNodeTest extends Multi
return;
}
int max = 90;
- Assert.assertEquals("{\":childNodeCount\":0}", mk.getNodes("/:root/head/config", head));
head = mk.commit("/:root/head/config", "^ \"maxMemoryChildren\":" + max, head, "");
Assert.assertEquals("{\"maxMemoryChildren\":"+max+",\":childNodeCount\":0}", mk.getNodes("/:root/head/config", head));
head = mk.commit("/", "+ \"t\": {}", head, "");
@@ -88,7 +87,6 @@ public class LargeNodeTest extends Multi
public void veryLargeNodeList() {
if (isMemoryKernel(mk)) {
int max = 2000;
- Assert.assertEquals("{\":childNodeCount\":0}", mk.getNodes("/:root/head/config", head));
head = mk.commit("/:root/head/config", "^ \"maxMemoryChildren\":" + max, head, "");
Assert.assertEquals("{\"maxMemoryChildren\":"+max+",\":childNodeCount\":0}", mk.getNodes("/:root/head/config", head));
}
@@ -127,7 +125,6 @@ public class LargeNodeTest extends Multi
return;
}
- Assert.assertEquals("{\":childNodeCount\":0}", mk.getNodes("/:root/head/config", head));
head = mk.commit("/:root/head/config", "^ \"maxMemoryChildren\": 10", head, "");
Assert.assertEquals("{\"maxMemoryChildren\":10,\":childNodeCount\":0}", mk.getNodes("/:root/head/config", head));
for (int i = 0; i < 100; i++) {
Modified: jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/mem/MemoryNodeTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/mem/MemoryNodeTest.java?rev=1232860&r1=1232859&r2=1232860&view=diff
==============================================================================
--- jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/mem/MemoryNodeTest.java (original)
+++ jackrabbit/sandbox/microkernel/src/test/java/org/apache/jackrabbit/mk/mem/MemoryNodeTest.java Wed Jan 18 12:40:16 2012
@@ -34,9 +34,9 @@ public class MemoryNodeTest {
NodeImpl n = new NodeImpl(map, 0);
Assert.assertEquals("{}", n.asString());
n.setId(NodeId.get(255));
- Assert.assertEquals("nff={}", n.asString());
+ Assert.assertEquals("nff={};", n.asString());
n.setPath("/test");
- Assert.assertEquals("nff={}/* /test */", n.toString());
+ Assert.assertEquals("nff={};/* /test */", n.toString());
n = n.createClone(10);
Assert.assertEquals("{}", n.asString());
NodeImpl a = new NodeImpl(map, 0);
@@ -50,9 +50,9 @@ public class MemoryNodeTest {
n = n.cloneAndAddChildNode("a", false, null, a, 11);
n = n.cloneAndSetProperty("x", "1", 12);
n.setId(NodeId.get(3));
- Assert.assertEquals("n3={\"x\":1,\"a\":n1}", n.asString());
+ Assert.assertEquals("n3={\"x\":1,\"a\":n1};", n.asString());
NodeImpl n2 = NodeImpl.fromString(map, n.asString());
- Assert.assertEquals("n3={\"x\":1,\"a\":n1}", n2.asString());
+ Assert.assertEquals("n3={\"x\":1,\"a\":n1};", n2.asString());
n = new NodeImpl(map, 0);
n = n.cloneAndAddChildNode("a", false, null, a, 1);
@@ -97,9 +97,9 @@ public class MemoryNodeTest {
n = n.cloneAndAddChildNode("a", false, null, a, 11);
n = n.cloneAndSetProperty("x", "1", 12);
n.setId(NodeId.get(3));
- Assert.assertEquals("n3={\"x\":1,\"a\":{\"name\":\"a\"}}", n.asString());
+ Assert.assertEquals("n3={\"x\":1,\"a\":{\"name\":\"a\"}};", n.asString());
NodeImpl n2 = NodeImpl.fromString(map, n.asString());
- Assert.assertEquals("n3={\"x\":1,\"a\":{\"name\":\"a\"}}", n2.asString());
+ Assert.assertEquals("n3={\"x\":1,\"a\":{\"name\":\"a\"}};", n2.asString());
n = new NodeImpl(map, 0);
n = n.cloneAndAddChildNode("a", false, null, a, 1);
@@ -121,13 +121,13 @@ public class MemoryNodeTest {
NodeImpl root = new NodeImpl(map, 0);
root = root.cloneAndAddChildNode("test", false, null, n2, 1);
- Assert.assertEquals("{\":descendantCount\":4,\"test\":n1}", root.asString());
+ Assert.assertEquals("{\":size\":4,\"test\":n1}", root.asString());
Assert.assertEquals(0, root.getDescendantInlineCount());
n2 = n2.cloneAndRemoveChildNode("c", 4);
root = new NodeImpl(map, 0);
root = root.cloneAndAddChildNode("test", false, null, n2, 1);
- Assert.assertEquals("{\":descendantCount\":3,\"test\":" + ab + "}", root.asString());
+ Assert.assertEquals("{\":size\":3,\"test\":" + ab + "}", root.asString());
}