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 md...@apache.org on 2018/04/03 14:50:24 UTC
svn commit: r1828244 - in /jackrabbit/oak/trunk/oak-segment-tar/src:
main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/
test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/
Author: mduerig
Date: Tue Apr 3 14:50:24 2018
New Revision: 1828244
URL: http://svn.apache.org/viewvc?rev=1828244&view=rev
Log:
OAK-5655: TarMK: Analyse locality of reference
Depth first trace
Added:
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/DepthFirstTrace.java
- copied, changed from r1828237, jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/BreadthFirstTrace.java
jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/DepthFirstTraceTest.java
Modified:
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/BreadthFirstTrace.java
jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/IOTracerRunner.java
jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/IOTracerTest.java
Modified: jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/BreadthFirstTrace.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/BreadthFirstTrace.java?rev=1828244&r1=1828243&r2=1828244&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/BreadthFirstTrace.java (original)
+++ jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/BreadthFirstTrace.java Tue Apr 3 14:50:24 2018
@@ -40,7 +40,7 @@ import org.apache.jackrabbit.oak.spi.sta
* A breadth first traversal trace.
* <p>
* When {@link Trace#run(NodeState) run} this trace performs a breadth first traversal starting
- * from the passed node up to a certain depth. It logs the current depth and the number of
+ * from the passed node down to a certain depth. It logs the current depth and the number of
* traversed nodes as additional {@link IOTracer#setContext(List) context}.
*/
public class BreadthFirstTrace implements Trace {
@@ -92,7 +92,7 @@ public class BreadthFirstTrace implement
return node;
}
- private void traverse(Queue<NodeState> nodes, int depth) {
+ private void traverse(@Nonnull Queue<NodeState> nodes, int depth) {
if (!nodes.isEmpty()) {
Queue<NodeState> children = newLinkedList();
while (!nodes.isEmpty()) {
Copied: jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/DepthFirstTrace.java (from r1828237, jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/BreadthFirstTrace.java)
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/DepthFirstTrace.java?p2=jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/DepthFirstTrace.java&p1=jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/BreadthFirstTrace.java&r1=1828237&r2=1828244&rev=1828244&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/BreadthFirstTrace.java (original)
+++ jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/tool/iotrace/DepthFirstTrace.java Tue Apr 3 14:50:24 2018
@@ -19,14 +19,12 @@
package org.apache.jackrabbit.oak.segment.tool.iotrace;
import static com.google.common.base.Preconditions.checkArgument;
-import static com.google.common.collect.Lists.newLinkedList;
import static java.lang.String.valueOf;
-import static java.util.Collections.singleton;
+import static org.apache.jackrabbit.oak.commons.PathUtils.concat;
import static org.apache.jackrabbit.oak.commons.PathUtils.elements;
import java.io.Writer;
import java.util.List;
-import java.util.Queue;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Consumer;
import java.util.function.Function;
@@ -37,20 +35,20 @@ import com.google.common.collect.Immutab
import org.apache.jackrabbit.oak.spi.state.NodeState;
/**
- * A breadth first traversal trace.
+ * A depth first traversal trace.
* <p>
- * When {@link Trace#run(NodeState) run} this trace performs a breadth first traversal starting
- * from the passed node up to a certain depth. It logs the current depth and the number of
- * traversed nodes as additional {@link IOTracer#setContext(List) context}.
+ * When {@link Trace#run(NodeState) run} this trace performs a depth first traversal starting
+ * from the passed node down to a certain depth. It logs the current depth, the number of traversed
+ * nodes and the current path as additional {@link IOTracer#setContext(List) context}.
*/
-public class BreadthFirstTrace implements Trace {
+public class DepthFirstTrace implements Trace {
/**
* The context specification of this trace.
* @see IOTracer#newIOTracer(Function, Writer, String)
*/
@Nonnull
- public static final String CONTEXT_SPEC = "depth,count";
+ public static final String CONTEXT_SPEC = "depth,count,path";
private final int depth;
@@ -64,12 +62,12 @@ public class BreadthFirstTrace implement
private final AtomicInteger nodeCount = new AtomicInteger();
/**
- * Create a new instance of a breadth first traversal trace.
+ * Create a new instance of a depth first traversal trace.
* @param depth maximal depth of the nodes to traverse
* @param path path of the root node where to start traversing
* @param context consumer to pass the additional context to
*/
- public BreadthFirstTrace(int depth, @Nonnull String path, @Nonnull Consumer<List<String>> context) {
+ public DepthFirstTrace(int depth, @Nonnull String path, @Nonnull Consumer<List<String>> context) {
checkArgument(depth >= 0);
this.depth = depth;
@@ -79,8 +77,7 @@ public class BreadthFirstTrace implement
@Override
public void run(@Nonnull NodeState node) {
- updateContext(context, 0, nodeCount.incrementAndGet());
- traverse(newLinkedList(singleton(getNode(node, path))), 0);
+ traverse(getNode(node, path), 0, path);
}
@Nonnull
@@ -92,30 +89,19 @@ public class BreadthFirstTrace implement
return node;
}
- private void traverse(Queue<NodeState> nodes, int depth) {
- if (!nodes.isEmpty()) {
- Queue<NodeState> children = newLinkedList();
- while (!nodes.isEmpty()) {
- NodeState head = nodes.poll();
- assert head != null;
- if (depth < this.depth) {
- head.getChildNodeEntries().forEach(
- cse -> {
- updateContext(context, depth + 1, nodeCount.incrementAndGet());
- NodeState child = cse.getNodeState();
- if (depth + 1 < this.depth) {
- // Only add to children queue if not at last level to save memory
- children.offer(child);
- }
- });
- }
- }
- traverse(children, depth + 1);
+ private void traverse(NodeState node, int depth, @Nonnull String path) {
+ updateContext(context, depth, nodeCount.incrementAndGet(), path);
+ if (depth < this.depth) {
+ node.getChildNodeEntries().forEach(cse -> {
+ String childPath = concat(path, cse.getName());
+ traverse(cse.getNodeState(), depth + 1, childPath);
+ });
}
}
- private static void updateContext(@Nonnull Consumer<List<String>> context, int depth, int count) {
- context.accept(ImmutableList.of(valueOf(depth), valueOf(count)));
+ private static void updateContext(
+ @Nonnull Consumer<List<String>> context, int depth, int count, @Nonnull String path) {
+ context.accept(ImmutableList.of(valueOf(depth), valueOf(count), path));
}
}
Added: jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/DepthFirstTraceTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/DepthFirstTraceTest.java?rev=1828244&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/DepthFirstTraceTest.java (added)
+++ jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/DepthFirstTraceTest.java Tue Apr 3 14:50:24 2018
@@ -0,0 +1,83 @@
+/*
+ * 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.segment.tool.iotrace;
+
+import static com.google.common.collect.Lists.newArrayList;
+import static org.apache.jackrabbit.oak.plugins.memory.EmptyNodeState.EMPTY_NODE;
+import static org.junit.Assert.assertEquals;
+
+import java.util.List;
+
+import javax.annotation.Nonnull;
+
+import com.google.common.collect.ImmutableList;
+import org.apache.jackrabbit.oak.spi.state.NodeBuilder;
+import org.apache.jackrabbit.oak.spi.state.NodeState;
+import org.junit.Test;
+
+public class DepthFirstTraceTest {
+
+ @Nonnull
+ private static NodeState createTree(int depth) {
+ NodeBuilder root = EMPTY_NODE.builder();
+ NodeBuilder child = root;
+ for (int k = 0 ; k < depth; k++) {
+ child = child.setChildNode("node-" + k);
+ }
+ return root.getNodeState();
+ }
+
+ @Test
+ public void testTraverseEmptyTree() {
+ List<List<String>> trace = newArrayList();
+ new DepthFirstTrace(4, "/", trace::add).run(createTree(0));
+ assertEquals(1, trace.size());
+ assertEquals(ImmutableList.of("0", "1", "/"), trace.get(0));
+ }
+
+ @Test
+ public void testTraverseDepth1Tree() {
+ List<List<String>> trace = newArrayList();
+ new DepthFirstTrace(4, "/", trace::add).run(createTree(1));
+ assertEquals(2, trace.size());
+ assertEquals(ImmutableList.of("0", "1", "/"), trace.get(0));
+ assertEquals(ImmutableList.of("1", "2", "/node-0"), trace.get(1));
+ }
+
+ @Test
+ public void testTraverseDepth2Tree() {
+ List<List<String>> trace = newArrayList();
+ new DepthFirstTrace(4, "/", trace::add).run(createTree(2));
+ assertEquals(3, trace.size());
+ assertEquals(ImmutableList.of("0", "1", "/"), trace.get(0));
+ assertEquals(ImmutableList.of("1", "2", "/node-0"), trace.get(1));
+ assertEquals(ImmutableList.of("2", "3", "/node-0/node-1"), trace.get(2));
+ }
+
+ @Test
+ public void testTraverseDepth3TreeWithLimit2() {
+ List<List<String>> trace = newArrayList();
+ new DepthFirstTrace(2, "/", trace::add).run(createTree(3));
+ assertEquals(3, trace.size());
+ assertEquals(ImmutableList.of("0", "1", "/"), trace.get(0));
+ assertEquals(ImmutableList.of("1", "2", "/node-0"), trace.get(1));
+ assertEquals(ImmutableList.of("2", "3", "/node-0/node-1"), trace.get(2));
+ }
+
+}
Modified: jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/IOTracerRunner.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/IOTracerRunner.java?rev=1828244&r1=1828243&r2=1828244&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/IOTracerRunner.java (original)
+++ jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/IOTracerRunner.java Tue Apr 3 14:50:24 2018
@@ -51,6 +51,7 @@ import org.junit.Test;
* <br>
* The test accepts the following properties:<br>
* {@code -Dinput=/path/to/segmentstore}. Required.<br>
+ * {{@code -Dtrace=breadth|depth}}. Required. <br>
* {@code -Doutput=/path/to/trace.cvs}. Default: {@code iotrace.csv}<br>
* {@code -Dmmap=true|false}. Default {@code true}<br>
* {@code -Dsegment-cache=n}. Default {@code 256}<br>
@@ -63,10 +64,12 @@ public class IOTracerRunner extends IOMo
private static final boolean ENABLED =
IOTracerRunner.class.getSimpleName().equals(getProperty("test"));
- private static final String OUTPUT = getProperty("output", "iotrace.csv");
-
private static final String INPUT = getProperty("segmentstore");
+ private static final String TRACE = getProperty("trace");
+
+ private static final String OUTPUT = getProperty("output", "iotrace.csv");
+
private static final boolean MMAP = parseBoolean(getProperty("mmap", "true"));
private static final int SEGMENT_CACHE = getInteger("segment-cache", 256);
@@ -85,16 +88,25 @@ public class IOTracerRunner extends IOMo
@Test
public void collectTrace() throws IOException, InvalidFileStoreVersionException {
checkArgument(INPUT != null, "No segment store directory specified");
+ checkArgument("breadth".equalsIgnoreCase(TRACE) || "depth".equalsIgnoreCase(TRACE),
+ "No trace specified");
+
System.out.println(format(
- "Breadth first traversing %d levels of %s starting at %s", DEPTH, INPUT, PATH));
+ "%s first traversing %d levels of %s starting at %s", TRACE, DEPTH, INPUT, PATH));
System.out.println(
format("mmap=%b, segment cache=%d", MMAP, SEGMENT_CACHE));
System.out.println(format("Writing trace to %s", OUTPUT));
- collectTrace(INPUT, MMAP, SEGMENT_CACHE, PATH, DEPTH, OUTPUT);
+ if ("depth".equals(TRACE)) {
+ collectDepthFirstTrace(INPUT, MMAP, SEGMENT_CACHE, PATH, DEPTH, OUTPUT);
+ } else if ("breadth".equals(TRACE)) {
+ collectBreadthFirstTrace(INPUT, MMAP, SEGMENT_CACHE, PATH, DEPTH, OUTPUT);
+ } else {
+ throw new IllegalStateException();
+ }
}
- public void collectTrace(
+ public void collectBreadthFirstTrace(
@Nonnull String segmentStore,
boolean mmap,
int segmentCacheSize,
@@ -120,6 +132,33 @@ public class IOTracerRunner extends IOMo
}
}
+ public void collectDepthFirstTrace(
+ @Nonnull String segmentStore,
+ boolean mmap,
+ int segmentCacheSize,
+ @Nonnull String path,
+ int depth,
+ @Nonnull String output)
+ throws IOException, InvalidFileStoreVersionException {
+ checkNotNull(segmentStore);
+ checkNotNull(path);
+ checkNotNull(output);
+
+ try (PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(output, true)))) {
+ Function<IOMonitor, FileStore> factory = ioMonitor ->
+ newFileStore(
+ fileStoreBuilder(new File(segmentStore))
+ .withMemoryMapping(mmap)
+ .withSegmentCacheSize(segmentCacheSize)
+ .withIOMonitor(ioMonitor));
+
+ IOTracer ioTracer = newIOTracer(factory, out, DepthFirstTrace.CONTEXT_SPEC);
+ ioTracer.collectTrace(
+ new DepthFirstTrace(depth, path, ioTracer::setContext));
+ }
+ }
+
+
@Nonnull
private static FileStore newFileStore(FileStoreBuilder fileStoreBuilder) {
try {
Modified: jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/IOTracerTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/IOTracerTest.java?rev=1828244&r1=1828243&r2=1828244&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/IOTracerTest.java (original)
+++ jackrabbit/oak/trunk/oak-segment-tar/src/test/java/org/apache/jackrabbit/oak/segment/tool/iotrace/IOTracerTest.java Tue Apr 3 14:50:24 2018
@@ -63,17 +63,17 @@ public class IOTracerTest extends IOMoni
try (FileStore fileStore = fileStoreBuilder(folder.getRoot()).build()) {
SegmentNodeState currentHead = fileStore.getHead();
SegmentNodeBuilder root = currentHead.builder();
- root.setChildNode("0a");
- root.setChildNode("0b");
- NodeBuilder builder = root.setChildNode("0c");
-
- builder.setChildNode("0d");
- builder.setChildNode("0e");
- builder = builder.setChildNode("0f");
-
- builder.setChildNode("0g");
- builder.setChildNode("0h");
- builder.setChildNode("0i").setChildNode("0j");
+ root.setChildNode("1a");
+ root.setChildNode("1b");
+ NodeBuilder builder = root.setChildNode("1c");
+
+ builder.setChildNode("2d");
+ builder.setChildNode("2e");
+ builder = builder.setChildNode("2f");
+
+ builder.setChildNode("3g");
+ builder.setChildNode("3h");
+ builder.setChildNode("3i").setChildNode("4j");
SegmentNodeState newHead = root.getNodeState();
fileStore.getRevisions().setHead(currentHead.getRecordId(), newHead.getRecordId());
}
@@ -91,7 +91,7 @@ public class IOTracerTest extends IOMoni
}
@Test
- public void collectTrace() throws IOException, InvalidFileStoreVersionException {
+ public void collectBreadthFirstTrace() throws IOException, InvalidFileStoreVersionException {
try (StringWriter out = new StringWriter()) {
Function<IOMonitor, FileStore> factory = this::createFileStore;
@@ -119,6 +119,46 @@ public class IOTracerTest extends IOMoni
entries.stream()
.map(row -> parseInt(row[5])) // depth
.distinct().collect(toSet()));
+
+ assertEquals("Expected max 10 nodes",
+ Optional.of(true),
+ entries.stream()
+ .map(row -> parseInt(row[6])) // count
+ .max(Comparator.naturalOrder())
+ .map(max -> max <= 10));
+ }
+ }
+ }
+
+ @Test
+ public void collectDepthFirstTrace() throws IOException, InvalidFileStoreVersionException {
+ try (StringWriter out = new StringWriter()) {
+ Function<IOMonitor, FileStore> factory = this::createFileStore;
+
+ IOTracer ioTracer = newIOTracer(factory, out, DepthFirstTrace.CONTEXT_SPEC);
+ ioTracer.collectTrace(
+ new DepthFirstTrace(2, "/", ioTracer::setContext));
+
+ try (BufferedReader reader = new BufferedReader(new StringReader(out.toString()))) {
+ Optional<String> header = reader.lines().findFirst();
+ List<String[]> entries = reader.lines()
+ .map(line -> line.split(","))
+ .collect(toList());
+
+ assertTrue(header.isPresent());
+ assertEquals("timestamp,file,segmentId,length,elapsed,depth,count,path", header.get());
+
+ long now = currentTimeMillis();
+ assertTrue("The timestamps of all entries must be in the past",
+ entries.stream()
+ .map(row -> parseLong(row[0])) // ts
+ .allMatch(ts -> ts <= now));
+
+ assertEquals("Expected depths 0 and 1",
+ ImmutableSet.of(0, 1),
+ entries.stream()
+ .map(row -> parseInt(row[5])) // depth
+ .distinct().collect(toSet()));
assertEquals("Expected max 10 nodes",
Optional.of(true),