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 ju...@apache.org on 2013/02/07 00:54:40 UTC
svn commit: r1443278 - in /jackrabbit/oak/trunk/oak-core/src:
main/java/org/apache/jackrabbit/oak/plugins/segment/
test/java/org/apache/jackrabbit/oak/plugins/segment/
Author: jukka
Date: Wed Feb 6 23:54:40 2013
New Revision: 1443278
URL: http://svn.apache.org/viewvc?rev=1443278&view=rev
Log:
OAK-593: Segment-based MK
Initial implementation of map records
Added:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java (with props)
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Record.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/RecordId.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Segment.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentReader.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java
jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java
Added: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java?rev=1443278&view=auto
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java (added)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java Wed Feb 6 23:54:40 2013
@@ -0,0 +1,74 @@
+/*
+ * 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.segment;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+class MapRecord extends Record {
+
+ static final int LEVEL_BITS = 6;
+
+ MapRecord(SegmentReader reader, RecordId id) {
+ super(reader, id);
+ }
+
+ public int size() {
+ return readInt(0);
+ }
+
+ public RecordId getEntry(String key) {
+ checkNotNull(key);
+ return getEntry(key, 0);
+ }
+
+ private RecordId getEntry(String key, int level) {
+ int size = 1 << LEVEL_BITS;
+ int mask = size - 1;
+ int shift = level * LEVEL_BITS;
+
+ int code = key.hashCode();
+ int bucketSize = readInt(0);
+ if (bucketSize == 0) {
+ return null;
+ } else if (bucketSize <= size) {
+ int offset = 0;
+ while (offset < bucketSize && readInt(4 + offset * 4) < code) {
+ offset++;
+ }
+ while (offset < bucketSize && readInt(4 + offset * 4) == code) {
+ RecordId keyId = readRecordId(4 + (bucketSize + offset) * 4);
+ if (key.equals(getReader().readString(keyId))) {
+ return readRecordId(4 + (2 * bucketSize + offset) * 4);
+ }
+ offset++;
+ }
+ return null;
+ } else {
+ long bucketMap = readLong(4);
+ int bucketIndex = (code >> shift) & mask;
+ long bucketBit = 1L << bucketIndex;
+ if ((bucketMap & bucketBit) != 0) {
+ bucketIndex = Long.bitCount(bucketMap & (bucketBit - 1));
+ RecordId bucketId = readRecordId(12 + bucketIndex * 4);
+ return new MapRecord(getReader(), bucketId).getEntry(key, level + 1);
+ } else {
+ return null;
+ }
+ }
+ }
+
+}
Propchange: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Record.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Record.java?rev=1443278&r1=1443277&r2=1443278&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Record.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Record.java Wed Feb 6 23:54:40 2013
@@ -35,6 +35,14 @@ class Record {
return reader.readRecordId(id, position);
}
+ protected int readInt(int position) {
+ return reader.readInt(id, position);
+ }
+
+ protected long readLong(int position) {
+ return reader.readLong(id, position);
+ }
+
public RecordId getRecordId() {
return id;
}
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/RecordId.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/RecordId.java?rev=1443278&r1=1443277&r2=1443278&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/RecordId.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/RecordId.java Wed Feb 6 23:54:40 2013
@@ -20,7 +20,7 @@ import java.util.UUID;
import com.google.common.base.Preconditions;
-public final class RecordId {
+public final class RecordId implements Comparable<RecordId> {
public static RecordId[] EMPTY_ARRAY = new RecordId[0];
@@ -41,6 +41,17 @@ public final class RecordId {
return offset;
}
+ //--------------------------------------------------------< Comparable >--
+
+ @Override
+ public int compareTo(RecordId that) {
+ int diff = segmentId.compareTo(that.segmentId);
+ if (diff == 0) {
+ diff = offset - that.offset;
+ }
+ return diff;
+ }
+
//------------------------------------------------------------< Object >--
@Override
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Segment.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Segment.java?rev=1443278&r1=1443277&r2=1443278&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Segment.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/Segment.java Wed Feb 6 23:54:40 2013
@@ -16,6 +16,7 @@
*/
package org.apache.jackrabbit.oak.plugins.segment;
+import static com.google.common.base.Preconditions.checkElementIndex;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkPositionIndexes;
@@ -50,6 +51,11 @@ class Segment {
return data.length;
}
+ public byte readByte(int position) {
+ checkElementIndex(position, data.length);
+ return data[position];
+ }
+
/**
* Reads the given number of bytes starting from the given position
* in this segment.
@@ -75,7 +81,12 @@ class Segment {
| (data[offset + 3] & 0xff));
}
- public long readLength(int offset) {
+ public int readInt(int offset) {
+ checkPositionIndexes(offset, offset + 4, data.length);
+ return ByteBuffer.wrap(data).getInt(offset);
+ }
+
+ public long readLong(int offset) {
checkPositionIndexes(offset, offset + 8, data.length);
return ByteBuffer.wrap(data).getLong(offset);
}
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentReader.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentReader.java?rev=1443278&r1=1443277&r2=1443278&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentReader.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentReader.java Wed Feb 6 23:54:40 2013
@@ -54,13 +54,27 @@ public class SegmentReader {
public SegmentStream readStream(RecordId recordId) {
Segment segment = store.readSegment(recordId.getSegmentId());
int offset = recordId.getOffset();
- long length = segment.readLength(offset);
+ long length = segment.readLong(offset);
int size = (int) ((length + BLOCK_SIZE - 1) / BLOCK_SIZE);
ListRecord list = new ListRecord(
this, segment.readRecordId(offset + 8), size);
return new SegmentStream(this, list, length);
}
+ public int readInt(RecordId recordId, int position) {
+ checkNotNull(recordId);
+ checkArgument(position >= 0);
+ Segment segment = store.readSegment(recordId.getSegmentId());
+ return segment.readInt(recordId.getOffset() + position);
+ }
+
+ public long readLong(RecordId recordId, int position) {
+ checkNotNull(recordId);
+ checkArgument(position >= 0);
+ Segment segment = store.readSegment(recordId.getSegmentId());
+ return segment.readLong(recordId.getOffset() + position);
+ }
+
public void readBytes(
RecordId recordId, int position,
byte[] buffer, int offset, int length) {
Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java?rev=1443278&r1=1443277&r2=1443278&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java Wed Feb 6 23:54:40 2013
@@ -27,6 +27,7 @@ import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
+import java.util.Map;
import java.util.Set;
import java.util.UUID;
@@ -144,6 +145,83 @@ public class SegmentWriter {
return bucketId;
}
+ class MapEntry implements Comparable<MapEntry> {
+ private final int hashCode;
+ private final RecordId key;
+ private final RecordId value;
+
+ MapEntry(int hashCode, RecordId key, RecordId value) {
+ this.hashCode = hashCode;
+ this.key = key;
+ this.value = value;
+ }
+
+ @Override
+ public int compareTo(MapEntry that) {
+ int diff = hashCode - that.hashCode;
+ if (diff == 0) {
+ diff = key.compareTo(that.key);
+ }
+ return diff;
+ }
+ }
+
+ private synchronized RecordId writeMapBucket(
+ List<MapEntry> entries, int level) {
+ int size = 1 << MapRecord.LEVEL_BITS;
+ int mask = size - 1;
+ int shift = level * MapRecord.LEVEL_BITS;
+
+ if (entries.size() <= size) {
+ Collections.sort(entries);
+
+ List<RecordId> ids = Lists.newArrayList();
+ for (MapEntry entry : entries) {
+ ids.add(entry.key);
+ ids.add(entry.value);
+ }
+
+ RecordId bucketId = prepare(4 + entries.size() * 12, ids);
+ buffer.putInt(entries.size());
+ for (MapEntry entry : entries) {
+ buffer.putInt(entry.hashCode);
+ }
+ for (MapEntry entry : entries) {
+ writeRecordId(entry.key);
+ }
+ for (MapEntry entry : entries) {
+ writeRecordId(entry.value);
+ }
+ return bucketId;
+ } else {
+ List<MapEntry>[] buckets = new List[size];
+ for (MapEntry entry : entries) {
+ int bucketIndex = (entry.hashCode >> shift) & mask;
+ if (buckets[bucketIndex] == null) {
+ buckets[bucketIndex] = Lists.newArrayList();
+ }
+ buckets[bucketIndex].add(entry);
+ }
+
+ List<RecordId> bucketIds = Lists.newArrayList();
+ long bucketMap = 0L;
+ for (int i = 0; i < buckets.length; i++) {
+ if (buckets[i] != null) {
+ bucketIds.add(writeMapBucket(buckets[i], level + 1));
+ bucketMap |= 1L << i;
+ }
+ }
+
+ RecordId bucketId = prepare(12 + bucketIds.size() * 4, bucketIds);
+ buffer.putInt(entries.size());
+ buffer.putLong(bucketMap);
+ for (RecordId id : bucketIds) {
+ writeRecordId(id);
+ }
+ return bucketId;
+ }
+ }
+
private synchronized RecordId writeValueRecord(
long length, RecordId blocks) {
RecordId valueId = prepare(8, Collections.singleton(blocks));
@@ -173,27 +251,36 @@ public class SegmentWriter {
/**
* Writes a list record containing the given list of record identifiers.
*
- * @param ids list of record identifiers
+ * @param list list of record identifiers
* @return list record identifier
*/
- public RecordId writeList(List<RecordId> ids) {
- checkNotNull(ids);
+ public RecordId writeList(List<RecordId> list) {
+ checkNotNull(list);
- int size = ids.size();
- if (size == 0) {
- return prepare(0);
- } else {
- List<RecordId> thisLevel = ids;
- while (thisLevel.size() > 1) {
- List<RecordId> nextLevel = new ArrayList<RecordId>();
- for (List<RecordId> bucket :
- Lists.partition(thisLevel, ListRecord.LEVEL_SIZE)) {
- nextLevel.add(writeListBucket(bucket));
- }
- thisLevel = nextLevel;
+ if (list.isEmpty()) {
+ return prepare(0); // special case
+ }
+
+ List<RecordId> thisLevel = list;
+ while (thisLevel.size() > 1) {
+ List<RecordId> nextLevel = Lists.newArrayList();
+ for (List<RecordId> bucket :
+ Lists.partition(thisLevel, ListRecord.LEVEL_SIZE)) {
+ nextLevel.add(writeListBucket(bucket));
}
- return thisLevel.iterator().next();
+ thisLevel = nextLevel;
+ }
+ return thisLevel.iterator().next();
+ }
+
+ public RecordId writeMap(Map<String, RecordId> map) {
+ List<MapEntry> entries = Lists.newArrayList();
+ for (Map.Entry<String, RecordId> entry : map.entrySet()) {
+ String key = entry.getKey();
+ entries.add(new MapEntry(
+ key.hashCode(), writeString(key), entry.getValue()));
}
+ return writeMapBucket(entries, 0);
}
/**
Modified: jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java?rev=1443278&r1=1443277&r2=1443278&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java Wed Feb 6 23:54:40 2013
@@ -18,6 +18,7 @@ package org.apache.jackrabbit.oak.plugin
import static org.apache.jackrabbit.oak.plugins.segment.ListRecord.LEVEL_SIZE;
import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNull;
import java.io.ByteArrayInputStream;
import java.io.IOException;
@@ -25,11 +26,14 @@ import java.io.InputStream;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
+import java.util.Map;
import java.util.Random;
import org.junit.Test;
import com.google.common.base.Charsets;
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Maps;
public class RecordTest {
@@ -158,4 +162,38 @@ public class RecordTest {
assertEquals(builder.toString(), reader.readString(large));
}
+ @Test
+ public void testMapRecord() {
+ RecordId blockId = writer.writeBlock(bytes, 0, bytes.length);
+
+ MapRecord zero = new MapRecord(reader, writer.writeMap(
+ ImmutableMap.<String, RecordId>of()));
+ MapRecord one = new MapRecord(reader, writer.writeMap(
+ ImmutableMap.of("one", blockId)));
+ MapRecord two = new MapRecord(reader, writer.writeMap(
+ ImmutableMap.of("one", blockId, "two", blockId)));
+ Map<String, RecordId> map = Maps.newHashMap();
+ for (int i = 0; i < 1000; i++) {
+ map.put("key" + i, blockId);
+ }
+ MapRecord many = new MapRecord(reader, writer.writeMap(map));
+
+ writer.flush();
+
+ assertEquals(0, zero.size());
+ assertNull(zero.getEntry("one"));
+ assertEquals(1, one.size());
+ assertEquals(blockId, one.getEntry("one"));
+ assertNull(one.getEntry("two"));
+ assertEquals(2, two.size());
+ assertEquals(blockId, two.getEntry("one"));
+ assertEquals(blockId, two.getEntry("two"));
+ assertNull(two.getEntry("three"));
+ assertEquals(1000, many.size());
+ for (int i = 0; i < 1000; i++) {
+ assertEquals(blockId, many.getEntry("key" + i));
+ }
+ assertNull(many.getEntry("foo"));
+ }
+
}