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/12/12 01:11:39 UTC
svn commit: r1550322 - 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: Thu Dec 12 00:11:39 2013
New Revision: 1550322
URL: http://svn.apache.org/r1550322
Log:
OAK-593: Segment-based MK
Improved handling of map records
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.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/SegmentSizeTest.java
Modified: 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=1550322&r1=1550321&r2=1550322&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/MapRecord.java Thu Dec 12 00:11:39 2013
@@ -17,8 +17,8 @@
package org.apache.jackrabbit.oak.plugins.segment;
import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkState;
import static com.google.common.collect.Iterables.concat;
-import static com.google.common.collect.Iterables.transform;
import static com.google.common.collect.Lists.newArrayListWithCapacity;
import static java.lang.Integer.bitCount;
import static java.lang.Integer.highestOneBit;
@@ -29,36 +29,19 @@ import java.util.Collections;
import java.util.Iterator;
import java.util.List;
-import com.google.common.base.Function;
import com.google.common.base.Objects;
import com.google.common.collect.ComparisonChain;
class MapRecord extends Record {
- private static final long M = 0x5DEECE66DL;
- private static final long A = 0xBL;
+ private static final int M = 0xDEECE66D;
+ private static final int A = 0xB;
static final long HASH_MASK = 0xFFFFFFFFL;
static int getHash(String name) {
- return (int) (((name.hashCode() ^ M) * M + A) >> 16);
+ return (name.hashCode() ^ M) * M + A;
}
- private static final Function<MapRecord, Iterable<String>> GET_KEYS =
- new Function<MapRecord, Iterable<String>>() {
- @Override
- public Iterable<String> apply(MapRecord input) {
- return input.getKeys();
- }
- };
-
- private static final Function<MapRecord, Iterable<MapEntry>> GET_ENTRIES =
- new Function<MapRecord, Iterable<MapEntry>>() {
- @Override
- public Iterable<MapEntry> apply(MapRecord input) {
- return input.getEntries();
- }
- };
-
/**
* Number of bits of the hash code to look at on each level of the trie.
*/
@@ -100,17 +83,15 @@ class MapRecord extends Record {
return !isBranch(getSize(head), getLevel(head));
}
- RecordId[] getBuckets() {
- return getBuckets(getSegment());
- }
-
- private RecordId[] getBuckets(Segment segment) {
- RecordId[] buckets = new RecordId[BUCKETS_PER_LEVEL];
+ MapRecord[] getBuckets() {
+ Segment segment = getSegment();
+ MapRecord[] buckets = new MapRecord[BUCKETS_PER_LEVEL];
int bitmap = segment.readInt(getOffset(4));
int ids = 0;
for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
if ((bitmap & (1 << i)) != 0) {
- buckets[i] = segment.readRecordId(getOffset(8, ids++));
+ buckets[i] = new MapRecord(
+ segment, segment.readRecordId(getOffset(8, ids++)));
} else {
buckets[i] = null;
}
@@ -132,8 +113,8 @@ class MapRecord extends Record {
}
int size() {
- int head = getSegment().readInt(getOffset(0));
- return getSize(head);
+ Segment segment = getSegment();
+ return getSize(segment.readInt(getOffset(0)));
}
MapEntry getEntry(String key) {
@@ -152,9 +133,9 @@ class MapRecord extends Record {
// this is an intermediate branch record
// check if a matching bucket exists, and recurse
int bitmap = segment.readInt(getOffset(4));
- int mask = BUCKETS_PER_LEVEL - 1;
- int shift = 32 - (level + 1) * LEVEL_BITS;
- int index = (int) (hash >> shift) & mask;
+ int mask = (1 << BITS_PER_LEVEL) - 1;
+ int shift = 32 - (level + 1) * BITS_PER_LEVEL;
+ int index = (hash >> shift) & mask;
int bit = 1 << index;
if ((bitmap & bit) != 0) {
int ids = bitCount(bitmap & (bit - 1));
@@ -166,22 +147,35 @@ class MapRecord extends Record {
}
// this is a leaf record; scan the list to find a matching entry
- int d = -1;
- for (int i = 0; i < size && d < 0; i++) {
- d = Long.valueOf(segment.readInt(getOffset(4 + i * 4)) & HASH_MASK)
- .compareTo(Long.valueOf(hash & HASH_MASK));
- if (d == 0) {
+ long h = hash & HASH_MASK;
+ int p = 0;
+ long pH = 0;
+ int q = size - 1;
+ long qH = HASH_MASK;
+ while (p <= q) {
+ checkState(pH <= qH);
+ int i = p + (int) ((q - p) * (h - pH) / (qH - pH));
+ checkState(p <= i && i <= q);
+ long iH = segment.readInt(getOffset(4 + i * 4)) & HASH_MASK;
+ int diff = Long.valueOf(iH).compareTo(Long.valueOf(h));
+ if (diff == 0) {
RecordId keyId = segment.readRecordId(
- getOffset(4 + size * 4, i));
- d = segment.readString(keyId).compareTo(key);
- if (d == 0) {
+ getOffset(4 + size * 4, i * 2));
+ diff = segment.readString(keyId).compareTo(key);
+ if (diff == 0) {
RecordId valueId = segment.readRecordId(
- getOffset(4 + size * 4, size + i));
+ getOffset(4 + size * 4, i * 2 + 1));
return new MapEntry(segment, key, keyId, valueId);
}
}
+ if (diff < 0) {
+ p = i + 1;
+ pH = iH;
+ } else {
+ q = i - 1;
+ qH = iH;
+ }
}
-
return null;
}
@@ -196,12 +190,18 @@ class MapRecord extends Record {
int level = getLevel(head);
if (isBranch(size, level)) {
- return concat(transform(getBucketList(segment), GET_KEYS));
+ List<MapRecord> buckets = getBucketList(segment);
+ List<Iterable<String>> keys =
+ newArrayListWithCapacity(buckets.size());
+ for (MapRecord bucket : buckets) {
+ keys.add(bucket.getKeys());
+ }
+ return concat(keys);
}
RecordId[] ids = new RecordId[size];
for (int i = 0; i < size; i++) {
- ids[i] = segment.readRecordId(getOffset(4 + size * 4, i));
+ ids[i] = segment.readRecordId(getOffset(4 + size * 4, i * 2));
}
String[] keys = new String[size];
@@ -222,17 +222,20 @@ class MapRecord extends Record {
int level = getLevel(head);
if (isBranch(size, level)) {
- return concat(transform(getBucketList(segment), GET_ENTRIES));
+ List<MapRecord> buckets = getBucketList(segment);
+ List<Iterable<MapEntry>> entries =
+ newArrayListWithCapacity(buckets.size());
+ for (MapRecord bucket : buckets) {
+ entries.add(bucket.getEntries());
+ }
+ return concat(entries);
}
RecordId[] keys = new RecordId[size];
- for (int i = 0; i < size; i++) {
- keys[i] = segment.readRecordId(getOffset(4 + size * 4, i));
- }
-
RecordId[] values = new RecordId[size];
for (int i = 0; i < size; i++) {
- values[i] = segment.readRecordId(getOffset(4 + size * 4, size + i));
+ keys[i] = segment.readRecordId(getOffset(4 + size * 4, i * 2));
+ values[i] = segment.readRecordId(getOffset(4 + size * 4, i * 2 + 1));
}
MapEntry[] entries = new MapEntry[size];
@@ -293,32 +296,28 @@ class MapRecord extends Record {
int afterHead = afterSegment.readInt(after.getOffset(0));
if (isBranch(getSize(beforeHead), getLevel(beforeHead))
&& isBranch(getSize(afterHead), getLevel(afterHead))) {
- RecordId[] beforeBuckets = before.getBuckets(beforeSegment);
- RecordId[] afterBuckets = after.getBuckets(afterSegment);
+ MapRecord[] beforeBuckets = before.getBuckets();
+ MapRecord[] afterBuckets = after.getBuckets();
for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
if (Objects.equal(beforeBuckets[i], afterBuckets[i])) {
// do nothing
} else if (beforeBuckets[i] == null) {
- MapRecord bucket =
- new MapRecord(afterSegment, afterBuckets[i]);
+ MapRecord bucket = afterBuckets[i];
for (MapEntry entry : bucket.getEntries()) {
if (!diff.entryAdded(entry)) {
return false;
}
}
} else if (afterBuckets[i] == null) {
- MapRecord bucket =
- new MapRecord(beforeSegment, beforeBuckets[i]);
+ MapRecord bucket = beforeBuckets[i];
for (MapEntry entry : bucket.getEntries()) {
if (!diff.entryDeleted(entry)) {
return false;
}
}
} else {
- MapRecord beforeBucket =
- new MapRecord(beforeSegment, beforeBuckets[i]);
- MapRecord afterBucket =
- new MapRecord(afterSegment, afterBuckets[i]);
+ MapRecord beforeBucket = beforeBuckets[i];
+ MapRecord afterBucket = afterBuckets[i];
if (!compare(beforeBucket, afterBucket, diff)) {
return false;
}
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=1550322&r1=1550321&r2=1550322&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 Thu Dec 12 00:11:39 2013
@@ -23,11 +23,14 @@ import static com.google.common.base.Pre
import static com.google.common.base.Preconditions.checkPositionIndex;
import static com.google.common.base.Preconditions.checkPositionIndexes;
import static com.google.common.base.Preconditions.checkState;
+import static com.google.common.collect.Iterables.addAll;
+import static com.google.common.collect.Lists.newArrayList;
import static com.google.common.collect.Lists.newArrayListWithExpectedSize;
import static com.google.common.collect.Maps.newHashMap;
import static com.google.common.collect.Maps.newLinkedHashMap;
import static com.google.common.collect.Sets.newHashSet;
import static java.util.Collections.emptyMap;
+import static java.util.Collections.nCopies;
import static org.apache.jackrabbit.oak.api.Type.NAME;
import static org.apache.jackrabbit.oak.api.Type.NAMES;
import static org.apache.jackrabbit.oak.plugins.segment.MapRecord.BUCKETS_PER_LEVEL;
@@ -60,7 +63,6 @@ import org.apache.jackrabbit.oak.spi.sta
import org.apache.jackrabbit.oak.spi.state.NodeState;
import com.google.common.base.Charsets;
-import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.io.ByteStreams;
@@ -308,21 +310,19 @@ public class SegmentWriter {
}
for (MapEntry entry : array) {
writeRecordId(entry.getKey());
- }
- for (MapEntry entry : array) {
writeRecordId(entry.getValue());
}
return new MapRecord(dummySegment, id);
}
}
- private MapRecord writeMapBranch(int level, int size, RecordId[] buckets) {
+ private MapRecord writeMapBranch(int level, int size, MapRecord[] buckets) {
int bitmap = 0;
List<RecordId> ids = Lists.newArrayListWithCapacity(buckets.length);
for (int i = 0; i < buckets.length; i++) {
if (buckets[i] != null) {
- bitmap |= 1 << i;
- ids.add(buckets[i]);
+ bitmap |= 1L << i;
+ ids.add(buckets[i].getRecordId());
}
}
@@ -347,117 +347,112 @@ public class SegmentWriter {
}
private synchronized MapRecord writeMapBucket(
- RecordId baseId, Collection<MapEntry> entries, int level) {
- int mask = MapRecord.BUCKETS_PER_LEVEL - 1;
- int shift = 32 - (level + 1) * MapRecord.LEVEL_BITS;
-
+ MapRecord base, Collection<MapEntry> entries, int level) {
+ // when no changed entries, return the base map (if any) as-is
if (entries == null || entries.isEmpty()) {
- if (baseId != null) {
- return dummySegment.readMap(baseId);
+ if (base != null) {
+ return base;
} else if (level == 0) {
synchronized (this) {
- RecordId id = prepare(RecordType.LIST, 4);
+ RecordId id = prepare(RecordType.LEAF, 4);
writeInt(0);
return new MapRecord(dummySegment, id);
}
} else {
return null;
}
- } else if (baseId != null) {
- // FIXME: messy code with lots of duplication
- MapRecord base = dummySegment.readMap(baseId);
- if (base.isLeaf()) {
- Map<String, MapEntry> map = newHashMap();
- for (MapEntry entry : base.getEntries()) {
+ }
+
+ // when no base map was given, write a fresh new map
+ if (base == null) {
+ // use leaf records for small maps or the last map level
+ if (entries.size() <= BUCKETS_PER_LEVEL
+ || level == MapRecord.MAX_NUMBER_OF_LEVELS) {
+ return writeMapLeaf(level, entries);
+ }
+
+ // write a large map by dividing the entries into buckets
+ MapRecord[] buckets = new MapRecord[BUCKETS_PER_LEVEL];
+ List<List<MapEntry>> changes = splitToBuckets(entries, level);
+ for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
+ buckets[i] = writeMapBucket(null, changes.get(i), level + 1);
+ }
+
+ // combine the buckets into one big map
+ return writeMapBranch(level, entries.size(), buckets);
+ }
+
+ // if the base map is small, update in memory and write as a new map
+ if (base.isLeaf()) {
+ Map<String, MapEntry> map = newHashMap();
+ for (MapEntry entry : base.getEntries()) {
+ map.put(entry.getName(), entry);
+ }
+ for (MapEntry entry : entries) {
+ if (entry.getValue() != null) {
map.put(entry.getName(), entry);
- }
- for (MapEntry entry : entries) {
- if (entry.getValue() != null) {
- map.put(entry.getName(), entry);
- } else {
- map.remove(entry.getName());
- }
- }
- if (map.isEmpty()) {
- return null;
} else {
- return writeMapBucket(null, map.values(), level);
- }
- } else {
- List<Collection<MapEntry>> buckets =
- Lists.newArrayListWithCapacity(BUCKETS_PER_LEVEL);
- buckets.addAll(Collections.nCopies(
- BUCKETS_PER_LEVEL, (Collection<MapEntry>) null));
- for (MapEntry entry : entries) {
- int bucketIndex = (entry.getHash() >> shift) & mask;
- Collection<MapEntry> bucket = buckets.get(bucketIndex);
- if (bucket == null) {
- bucket = Lists.newArrayList();
- buckets.set(bucketIndex, bucket);
- }
- bucket.add(entry);
+ map.remove(entry.getName());
}
+ }
+ return writeMapBucket(null, map.values(), level);
+ }
- int newSize = 0;
- List<MapRecord> newBuckets = Lists.newArrayList();
- RecordId[] bucketIds = base.getBuckets();
- for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
- MapRecord newBucket = writeMapBucket(
- bucketIds[i], buckets.get(i), level + 1);
- if (newBucket != null) {
- newBuckets.add(newBucket);
- bucketIds[i] = newBucket.getRecordId();
- newSize += newBucket.size();
- } else {
- bucketIds[i] = null;
- }
- }
+ // finally, the if the base map is large, handle updates per bucket
+ int newSize = 0;
+ int newCount = 0;
+ MapRecord[] buckets = base.getBuckets();
+ List<List<MapEntry>> changes = splitToBuckets(entries, level);
+ for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
+ buckets[i] = writeMapBucket(buckets[i], changes.get(i), level + 1);
+ if (buckets[i] != null) {
+ newSize += buckets[i].size();
+ newCount++;
+ }
+ }
- // OAK-654: what if the updated map is smaller?
- if (newSize > MapRecord.BUCKETS_PER_LEVEL) {
- return writeMapBranch(level, newSize, bucketIds);
- } else if (newSize == 0) {
- if (level == 0) {
- synchronized (this) {
- RecordId id = prepare(RecordType.LIST, 4);
- writeInt(0);
- return new MapRecord(dummySegment, id);
- }
- } else {
- return null;
- }
- } else if (newBuckets.size() == 1) {
- return newBuckets.iterator().next();
- } else {
- List<MapEntry> list = Lists.newArrayList();
- for (MapRecord record : newBuckets) {
- Iterables.addAll(list, record.getEntries());
- }
- return writeMapLeaf(level, list);
+ // OAK-654: what if the updated map is smaller?
+ if (newSize > BUCKETS_PER_LEVEL) {
+ return writeMapBranch(level, newSize, buckets);
+ } else if (newCount <= 1) {
+ // up to one bucket contains entries, so return that as the new map
+ for (int i = 0; i < buckets.length; i++) {
+ if (buckets[i] != null) {
+ return buckets[i];
}
}
- } else if (entries.size() <= MapRecord.BUCKETS_PER_LEVEL
- || level == MapRecord.MAX_NUMBER_OF_LEVELS) {
- return writeMapLeaf(level, entries);
+ // no buckets remaining, return empty map
+ return writeMapBucket(null, null, level);
} else {
- List<MapEntry>[] lists = new List[MapRecord.BUCKETS_PER_LEVEL];
- for (MapEntry entry : entries) {
- int bucketIndex = (entry.getHash() >> shift) & mask;
- if (lists[bucketIndex] == null) {
- lists[bucketIndex] = Lists.newArrayList();
+ // combine all remaining entries into a leaf record
+ List<MapEntry> list = Lists.newArrayList();
+ for (int i = 0; i < buckets.length; i++) {
+ if (buckets[i] != null) {
+ addAll(list, buckets[i].getEntries());
}
- lists[bucketIndex].add(entry);
}
+ return writeMapLeaf(level, list);
+ }
+ }
- RecordId[] buckets = new RecordId[MapRecord.BUCKETS_PER_LEVEL];
- for (int i = 0; i < lists.length; i++) {
- if (lists[i] != null) {
- buckets[i] = writeMapBucket(null, lists[i], level + 1).getRecordId();
- }
- }
+ private static List<List<MapEntry>> splitToBuckets(
+ Collection<MapEntry> entries, int level) {
+ List<MapEntry> empty = null;
+ int mask = (1 << MapRecord.BITS_PER_LEVEL) - 1;
+ int shift = 32 - (level + 1) * MapRecord.BITS_PER_LEVEL;
- return writeMapBranch(level, entries.size(), buckets);
+ List<List<MapEntry>> buckets =
+ newArrayList(nCopies(MapRecord.BUCKETS_PER_LEVEL, empty));
+ for (MapEntry entry : entries) {
+ int index = (entry.getHash() >> shift) & mask;
+ List<MapEntry> bucket = buckets.get(index);
+ if (bucket == null) {
+ bucket = newArrayList();
+ buckets.set(index, bucket);
+ }
+ bucket.add(entry);
}
+ return buckets;
}
private synchronized RecordId writeValueRecord(
@@ -530,15 +525,24 @@ public class SegmentWriter {
public MapRecord writeMap(MapRecord base, Map<String, RecordId> changes) {
List<MapEntry> entries = Lists.newArrayList();
for (Map.Entry<String, RecordId> entry : changes.entrySet()) {
- String name = entry.getKey();
+ String key = entry.getKey();
+
+ RecordId keyId = null;
+ if (base != null) {
+ MapEntry e = base.getEntry(key);
+ if (e != null) {
+ keyId = e.getKey();
+ }
+ }
+ if (keyId == null) {
+ keyId = writeString(key);
+ }
+
entries.add(new MapEntry(
- dummySegment, name, writeString(name), entry.getValue()));
+ dummySegment, key, keyId, entry.getValue()));
}
- RecordId baseId = null;
- if (base != null) {
- baseId = base.getRecordId();
- }
- return writeMapBucket(baseId, entries, 0);
+
+ return writeMapBucket(base, entries, 0);
}
/**
Modified: jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/SegmentSizeTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/SegmentSizeTest.java?rev=1550322&r1=1550321&r2=1550322&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/SegmentSizeTest.java (original)
+++ jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/SegmentSizeTest.java Thu Dec 12 00:11:39 2013
@@ -156,7 +156,7 @@ public class SegmentSizeTest {
SegmentNodeState state = writer.writeNode(builder.getNodeState());
writer.flush();
Segment segment = store.readSegment(state.getRecordId().getSegmentId());
- assertEquals(26752, Segment.WEIGHER.weigh(null, segment));
+ assertEquals(27508, Segment.WEIGHER.weigh(null, segment));
writer.flush(); // force flushing of the previous segment
@@ -165,7 +165,7 @@ public class SegmentSizeTest {
state = writer.writeNode(builder.getNodeState());
writer.flush();
segment = store.readSegment(state.getRecordId().getSegmentId());
- assertEquals(136, Segment.WEIGHER.weigh(null, segment));
+ assertEquals(484, Segment.WEIGHER.weigh(null, segment));
}
private int getSize(NodeBuilder builder) {