jackrabbit-oak-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ju...@apache.org
Subject svn commit: r1449271 - in /jackrabbit/oak/trunk/oak-core/src: main/java/org/apache/jackrabbit/oak/plugins/segment/ test/java/org/apache/jackrabbit/oak/plugins/segment/
Date Sat, 23 Feb 2013 05:45:53 GMT
Author: jukka
Date: Sat Feb 23 05:45:53 2013
New Revision: 1449271

URL: http://svn.apache.org/r1449271
Log:
OAK-632: SegmentMK: Efficient updates of flat nodes

Fix handling of worst-case scenario where all map keys have the same hash
Move duplicate code for writing map branches to a separate method

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/RecordTest.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=1449271&r1=1449270&r2=1449271&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
Sat Feb 23 05:45:53 2013
@@ -18,11 +18,14 @@ package org.apache.jackrabbit.oak.plugin
 
 import static com.google.common.base.Preconditions.checkElementIndex;
 import static com.google.common.base.Preconditions.checkNotNull;
+import static com.google.common.base.Preconditions.checkPositionIndex;
 import static java.lang.Integer.highestOneBit;
 import static java.lang.Integer.numberOfTrailingZeros;
 
 import java.util.UUID;
 
+import com.google.common.base.Preconditions;
+
 abstract class MapRecord extends Record {
 
     /**
@@ -65,7 +68,6 @@ abstract class MapRecord extends Record 
         int head = segment.readInt(id.getOffset());
         int level = head >>> SIZE_BITS;
         int size = head & ((1 << SIZE_BITS) - 1);
-        System.out.println("R: " + size + " " + level);
         if (size > BUCKETS_PER_LEVEL && level < MAX_NUMBER_OF_LEVELS) {
             int bitmap = segment.readInt(id.getOffset() + 4);
             return new MapBranch(store, id, size, level, bitmap);
@@ -84,7 +86,7 @@ abstract class MapRecord extends Record 
         super(checkNotNull(id));
         this.store = checkNotNull(store);
         this.size = checkElementIndex(size, MAX_SIZE);
-        this.level = checkElementIndex(level, MAX_NUMBER_OF_LEVELS);
+        this.level = checkPositionIndex(level, MAX_NUMBER_OF_LEVELS);
     }
 
     protected Segment getSegment() {

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=1449271&r1=1449270&r2=1449271&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
Sat Feb 23 05:45:53 2013
@@ -175,7 +175,7 @@ public class SegmentWriter {
         writeInt((int) value);
     }
 
-    private synchronized MapLeaf writeLeaf(
+    private synchronized MapLeaf writeMapLeaf(
             int level, Collection<MapEntry> entries) {
         checkNotNull(entries);
 
@@ -208,6 +208,26 @@ public class SegmentWriter {
         return new MapLeaf(store, id, size, level);
     }
 
+    private MapRecord writeMapBranch(int level, int size, RecordId[] 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]);
+            }
+        }
+
+        RecordId mapId = prepare(8, ids);
+        writeInt((level << MapRecord.SIZE_BITS) | size);
+        writeInt(bitmap);
+        for (RecordId id : ids) {
+            writeRecordId(id);
+        }
+        return new MapBranch(store, mapId, size, level, bitmap);
+    }
+
+
     private synchronized RecordId writeListBucket(List<RecordId> bucket) {
         RecordId bucketId = prepare(0, bucket);
         for (RecordId id : bucket) {
@@ -243,7 +263,11 @@ public class SegmentWriter {
                         map.remove(entry.getName());
                     }
                 }
-                return writeMapBucket(null, map.values(), level);
+                if (map.isEmpty()) {
+                    return null;
+                } else {
+                    return writeMapBucket(null, map.values(), level);
+                }
             } else {
                 List<Collection<MapEntry>> buckets =
                         Lists.newArrayListWithCapacity(BUCKETS_PER_LEVEL);
@@ -272,51 +296,29 @@ public class SegmentWriter {
                     }
                 }
                 
-                List<RecordId> ids = Lists.newArrayList();
-                int bucketMap = 0;
-                for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
-                    if (bucketIds[i] != null) {
-                        ids.add(bucketIds[i]);
-                        bucketMap |= 1 << i;
-                    }
-                }
-
-                RecordId bucketId = prepare(12, ids);
-                writeInt((level << MapRecord.SIZE_BITS) | newSize);
-                writeInt(bucketMap);
-                for (RecordId id : ids) {
-                    writeRecordId(id);
-                }
-                return new MapBranch(store, bucketId, newSize, level, bucketMap);
+                return writeMapBranch(level, newSize, bucketIds);
             }
-        } else if (entries.size() <= MapRecord.BUCKETS_PER_LEVEL) {
-            return writeLeaf(level, entries);
+        } else if (entries.size() <= MapRecord.BUCKETS_PER_LEVEL
+                || level == MapRecord.MAX_NUMBER_OF_LEVELS) {
+            return writeMapLeaf(level, entries);
         } else {
-            List<MapEntry>[] buckets = new List[MapRecord.BUCKETS_PER_LEVEL];
+            List<MapEntry>[] lists = new List[MapRecord.BUCKETS_PER_LEVEL];
             for (MapEntry entry : entries) {
                 int bucketIndex = (entry.hashCode() >> shift) & mask;
-                if (buckets[bucketIndex] == null) {
-                    buckets[bucketIndex] = Lists.newArrayList();
+                if (lists[bucketIndex] == null) {
+                    lists[bucketIndex] = Lists.newArrayList();
                 }
-                buckets[bucketIndex].add(entry);
+                lists[bucketIndex].add(entry);
             }
 
-            List<RecordId> bucketIds = Lists.newArrayList();
-            int bucketMap = 0;
-            for (int i = 0; i < buckets.length; i++) {
-                if (buckets[i] != null) {
-                    bucketIds.add(writeMapBucket(null, buckets[i], level + 1).getRecordId());
-                    bucketMap |= 1 << i;
+            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();
                 }
             }
 
-            RecordId bucketId = prepare(8, bucketIds);
-            writeInt((level << MapRecord.SIZE_BITS) | entries.size());
-            writeInt(bucketMap);
-            for (RecordId id : bucketIds) {
-                writeRecordId(id);
-            }
-            return new MapBranch(store, bucketId, entries.size(), level, bucketMap);
+            return writeMapBranch(level, entries.size(), buckets);
         }
     }
 

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=1449271&r1=1449270&r2=1449271&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
Sat Feb 23 05:45:53 2013
@@ -213,7 +213,6 @@ public class RecordTest {
 
         assertEquals(1000, many.size());
         iterator = many.getEntries().iterator();
-        System.out.println(MapRecord.readMap(store, many.getRecordId()));
         for (int i = 0; i < 1000; i++) {
             assertTrue(iterator.hasNext());
             assertEquals(blockId, iterator.next().getValue());
@@ -239,6 +238,29 @@ public class RecordTest {
     }
 
     @Test
+    public void testWorstCaseMap() {
+        RecordId blockId = writer.writeBlock(bytes, 0, bytes.length);
+        Map<String, RecordId> map = Maps.newHashMap();
+        char[] key = new char[2];
+        for (int i = 0; i <= MapRecord.BUCKETS_PER_LEVEL; i++) {
+            key[0] = (char) ('A' + i);
+            key[1] = (char) ('\u1000' - key[0] * 31);
+            map.put(new String(key), blockId);
+        }
+
+        MapRecord bad = writer.writeMap(null, map);
+        writer.flush();
+
+        assertEquals(map.size(), bad.size());
+        Iterator<MapEntry> iterator = bad.getEntries().iterator();
+        for (int i = 0; i < map.size(); i++) {
+            assertTrue(iterator.hasNext());
+            assertEquals('\u1000', iterator.next().getName().hashCode());
+        }
+        assertFalse(iterator.hasNext());
+    }
+
+    @Test
     public void testEmptyNode() {
         NodeState before = MemoryNodeState.EMPTY_NODE;
         NodeState after = writer.writeNode(before);

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=1449271&r1=1449270&r2=1449271&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
Sat Feb 23 05:45:53 2013
@@ -163,7 +163,7 @@ public class SegmentSizeTest {
         state = writer.writeNode(builder.getNodeState());
         writer.flush();
         segment = store.readSegment(state.getRecordId().getSegmentId());
-        assertEquals(260, segment.getData().length);
+        assertEquals(252, segment.getData().length);
     }
 
     private int getSize(NodeBuilder builder) {



Mime
View raw message