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 fr...@apache.org on 2017/08/03 15:14:44 UTC
svn commit: r1804011 - in
/jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar:
TarReader.java index/Index.java index/IndexEntry.java index/IndexLoader.java
Author: frm
Date: Thu Aug 3 15:14:44 2017
New Revision: 1804011
URL: http://svn.apache.org/viewvc?rev=1804011&view=rev
Log:
OAK-6518 - Introduce a data type to encapsulate the index representation
Added:
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/Index.java (with props)
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexEntry.java (with props)
Modified:
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/TarReader.java
jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexLoader.java
Modified: jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/TarReader.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/TarReader.java?rev=1804011&r1=1804010&r2=1804011&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/TarReader.java (original)
+++ jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/TarReader.java Thu Aug 3 15:14:44 2017
@@ -26,7 +26,6 @@ import static com.google.common.collect.
import static com.google.common.collect.Maps.newLinkedHashMap;
import static com.google.common.collect.Maps.newTreeMap;
import static com.google.common.collect.Sets.newHashSet;
-import static com.google.common.collect.Sets.newHashSetWithExpectedSize;
import static java.nio.ByteBuffer.wrap;
import static java.util.Collections.singletonList;
import static org.apache.jackrabbit.oak.segment.file.tar.GCGeneration.newGCGeneration;
@@ -62,6 +61,8 @@ import com.google.common.base.Predicate;
import com.google.common.base.Stopwatch;
import com.google.common.collect.Sets;
import org.apache.commons.io.FileUtils;
+import org.apache.jackrabbit.oak.segment.file.tar.index.Index;
+import org.apache.jackrabbit.oak.segment.file.tar.index.IndexEntry;
import org.apache.jackrabbit.oak.segment.file.tar.index.IndexLoader;
import org.apache.jackrabbit.oak.segment.file.tar.index.InvalidIndexException;
import org.slf4j.Logger;
@@ -276,7 +277,7 @@ class TarReader implements Closeable {
try {
RandomAccessFile access = new RandomAccessFile(file, "r");
try {
- ByteBuffer index = loadAndValidateIndex(access, name);
+ Index index = loadAndValidateIndex(access, name);
if (index == null) {
log.info("No index found in tar file {}, skipping...", name);
} else {
@@ -291,11 +292,6 @@ class TarReader implements Closeable {
if (memoryMapping) {
try {
FileAccess mapped = new FileAccess.Mapped(access);
- // re-read the index, now with memory mapping
- int indexSize = index.remaining();
- index = mapped.read(
- mapped.length() - indexSize - 16 - 1024,
- indexSize);
return new TarReader(file, mapped, index, ioMonitor);
} catch (IOException e) {
log.warn("Failed to mmap tar file {}. Falling back to normal file " +
@@ -338,7 +334,7 @@ class TarReader implements Closeable {
* the index. If the TAR doesn't contain any index, {@code null} is returned
* instead.
*/
- private static ByteBuffer loadAndValidateIndex(RandomAccessFile file, String name) throws IOException {
+ private static Index loadAndValidateIndex(RandomAccessFile file, String name) throws IOException {
try {
return indexLoader.loadIndex(file);
} catch (InvalidIndexException e) {
@@ -443,13 +439,13 @@ class TarReader implements Closeable {
private final FileAccess access;
- private final ByteBuffer index;
+ private final Index index;
private volatile boolean hasGraph;
private final IOMonitor ioMonitor;
- private TarReader(File file, FileAccess access, ByteBuffer index, IOMonitor ioMonitor) {
+ private TarReader(File file, FileAccess access, Index index, IOMonitor ioMonitor) {
this.file = file;
this.access = access;
this.index = index;
@@ -467,15 +463,7 @@ class TarReader implements Closeable {
* @return An instance of {@link Set}.
*/
Set<UUID> getUUIDs() {
- Set<UUID> uuids = newHashSetWithExpectedSize(index.remaining() / TarEntry.SIZE);
- int position = index.position();
- while (position < index.limit()) {
- uuids.add(new UUID(
- index.getLong(position),
- index.getLong(position + 8)));
- position += TarEntry.SIZE;
- }
- return uuids;
+ return index.getUUIDs();
}
/**
@@ -487,7 +475,7 @@ class TarReader implements Closeable {
* otherwise.
*/
boolean containsEntry(long msb, long lsb) {
- return findEntry(msb, lsb) != -1;
+ return findEntry(msb, lsb) != null;
}
/**
@@ -502,14 +490,11 @@ class TarReader implements Closeable {
* @return the byte buffer, or null if not in this file.
*/
ByteBuffer readEntry(long msb, long lsb) throws IOException {
- int position = findEntry(msb, lsb);
- if (position != -1) {
- int pos = index.getInt(position + 16);
- int len = index.getInt(position + 20);
- return readSegment(msb, lsb, pos, len);
- } else {
+ IndexEntry entry = findEntry(msb, lsb);
+ if (entry == null) {
return null;
}
+ return readSegment(msb, lsb, entry.getPosition(), entry.getLength());
}
/**
@@ -520,48 +505,8 @@ class TarReader implements Closeable {
* @return The position of the entry in the TAR file, or {@code -1} if the
* entry is not found.
*/
- private int findEntry(long msb, long lsb) {
- // The segment identifiers are randomly generated with uniform
- // distribution, so we can use interpolation search to find the
- // matching entry in the index. The average runtime is O(log log n).
-
- int lowIndex = 0;
- int highIndex = index.remaining() / TarEntry.SIZE - 1;
- float lowValue = Long.MIN_VALUE;
- float highValue = Long.MAX_VALUE;
- float targetValue = msb;
-
- while (lowIndex <= highIndex) {
- int guessIndex = lowIndex + Math.round(
- (highIndex - lowIndex)
- * (targetValue - lowValue)
- / (highValue - lowValue));
- int position = index.position() + guessIndex * TarEntry.SIZE;
- long m = index.getLong(position);
- if (msb < m) {
- highIndex = guessIndex - 1;
- highValue = m;
- } else if (msb > m) {
- lowIndex = guessIndex + 1;
- lowValue = m;
- } else {
- // getting close...
- long l = index.getLong(position + 8);
- if (lsb < l) {
- highIndex = guessIndex - 1;
- highValue = m;
- } else if (lsb > l) {
- lowIndex = guessIndex + 1;
- lowValue = m;
- } else {
- // found it!
- return position;
- }
- }
- }
-
- // not found
- return -1;
+ private IndexEntry findEntry(long msb, long lsb) {
+ return index.findEntry(msb, lsb);
}
/**
@@ -571,21 +516,20 @@ class TarReader implements Closeable {
*/
@Nonnull
TarEntry[] getEntries() {
- TarEntry[] entries = new TarEntry[index.remaining() / TarEntry.SIZE];
- int position = index.position();
- for (int i = 0; position < index.limit(); i++) {
+ TarEntry[] entries = new TarEntry[index.entryCount()];
+ for (int i = 0; i < entries.length; i++) {
+ IndexEntry e = index.entry(i);
entries[i] = new TarEntry(
- index.getLong(position),
- index.getLong(position + 8),
- index.getInt(position + 16),
- index.getInt(position + 20),
+ e.getMsb(),
+ e.getLsb(),
+ e.getPosition(),
+ e.getLength(),
newGCGeneration(
- index.getInt(position + 24),
- index.getInt(position + 28),
- index.get(position + 32) != 0
+ e.getFullGeneration(),
+ e.getTailGeneration(),
+ e.isTail()
)
);
- position += TarEntry.SIZE;
}
Arrays.sort(entries, TarEntry.OFFSET_ORDER);
return entries;
@@ -885,7 +829,7 @@ class TarReader implements Closeable {
}
private int getIndexEntrySize() {
- return getEntrySize(index.remaining() + 16);
+ return getEntrySize(index.size());
}
private int getGraphEntrySize() {
Added: jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/Index.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/Index.java?rev=1804011&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/Index.java (added)
+++ jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/Index.java Thu Aug 3 15:14:44 2017
@@ -0,0 +1,100 @@
+/*
+ * 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.file.tar.index;
+
+import static com.google.common.collect.Sets.newHashSetWithExpectedSize;
+
+import java.nio.ByteBuffer;
+import java.util.Set;
+import java.util.UUID;
+
+public class Index {
+
+ private final ByteBuffer index;
+
+ Index(ByteBuffer index) {
+ this.index = index;
+ }
+
+ public Set<UUID> getUUIDs() {
+ Set<UUID> uuids = newHashSetWithExpectedSize(index.remaining() / IndexLoader.ENTRY_SIZE);
+ int position = index.position();
+ while (position < index.limit()) {
+ long msb = index.getLong(position);
+ long lsb = index.getLong(position + 8);
+ uuids.add(new UUID(msb, lsb));
+ position += IndexLoader.ENTRY_SIZE;
+ }
+ return uuids;
+ }
+
+ public IndexEntry findEntry(long msb, long lsb) {
+ // The segment identifiers are randomly generated with uniform
+ // distribution, so we can use interpolation search to find the
+ // matching entry in the index. The average runtime is O(log log n).
+
+ int lowIndex = 0;
+ int highIndex = index.remaining() / IndexLoader.ENTRY_SIZE - 1;
+ float lowValue = Long.MIN_VALUE;
+ float highValue = Long.MAX_VALUE;
+ float targetValue = msb;
+
+ while (lowIndex <= highIndex) {
+ int guessIndex = lowIndex + Math.round(
+ (highIndex - lowIndex)
+ * (targetValue - lowValue)
+ / (highValue - lowValue));
+ int position = index.position() + guessIndex * IndexLoader.ENTRY_SIZE;
+ long m = index.getLong(position);
+ if (msb < m) {
+ highIndex = guessIndex - 1;
+ highValue = m;
+ } else if (msb > m) {
+ lowIndex = guessIndex + 1;
+ lowValue = m;
+ } else {
+ // getting close...
+ long l = index.getLong(position + 8);
+ if (lsb < l) {
+ highIndex = guessIndex - 1;
+ highValue = m;
+ } else if (lsb > l) {
+ lowIndex = guessIndex + 1;
+ lowValue = m;
+ } else {
+ return new IndexEntry(index, position);
+ }
+ }
+ }
+
+ return null;
+ }
+
+ public int size() {
+ return index.remaining() + 16;
+ }
+
+ public int entryCount() {
+ return index.remaining() / IndexLoader.ENTRY_SIZE;
+ }
+
+ public IndexEntry entry(int i) {
+ return new IndexEntry(index, index.position() + i * IndexLoader.ENTRY_SIZE);
+ }
+
+}
Propchange: jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/Index.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexEntry.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexEntry.java?rev=1804011&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexEntry.java (added)
+++ jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexEntry.java Thu Aug 3 15:14:44 2017
@@ -0,0 +1,61 @@
+/*
+ * 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.file.tar.index;
+
+import java.nio.ByteBuffer;
+
+public class IndexEntry {
+
+ private final ByteBuffer index;
+
+ private final int position;
+
+ IndexEntry(ByteBuffer index, int position) {
+ this.index = index;
+ this.position = position;
+ }
+
+ public long getMsb() {
+ return index.getLong(position);
+ }
+
+ public long getLsb() {
+ return index.getLong(position + 8);
+ }
+
+ public int getPosition() {
+ return index.getInt(position + 16);
+ }
+
+ public int getLength() {
+ return index.getInt(position + 20);
+ }
+
+ public int getFullGeneration() {
+ return index.getInt(position + 24);
+ }
+
+ public int getTailGeneration() {
+ return index.getInt(position + 28);
+ }
+
+ public boolean isTail() {
+ return index.get(position + 32) != 0;
+ }
+
+}
Propchange: jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexEntry.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexLoader.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexLoader.java?rev=1804011&r1=1804010&r2=1804011&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexLoader.java (original)
+++ jackrabbit/oak/trunk/oak-segment-tar/src/main/java/org/apache/jackrabbit/oak/segment/file/tar/index/IndexLoader.java Thu Aug 3 15:14:44 2017
@@ -29,7 +29,7 @@ public class IndexLoader {
private static final int MAGIC = ('\n' << 24) + ('0' << 16) + ('K' << 8) + '\n';
- private static final int ENTRY_SIZE = 33;
+ static final int ENTRY_SIZE = 33;
public static IndexLoader newIndexLoader(int blockSize) {
checkArgument(blockSize > 0, "Invalid block size");
@@ -42,7 +42,7 @@ public class IndexLoader {
this.blockSize = blockSize;
}
- public ByteBuffer loadIndex(RandomAccessFile file) throws IOException, InvalidIndexException {
+ public Index loadIndex(RandomAccessFile file) throws IOException, InvalidIndexException {
long length = file.length();
if (length % blockSize != 0 || length < 6 * blockSize || length > Integer.MAX_VALUE) {
@@ -110,7 +110,8 @@ public class IndexLoader {
}
index.reset();
- return index;
+
+ return new Index(index);
}
}