jackrabbit-oak-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ju...@apache.org
Subject svn commit: r1559709 - in /jackrabbit/oak/trunk/oak-core/src: main/java/org/apache/jackrabbit/oak/plugins/segment/ main/java/org/apache/jackrabbit/oak/plugins/segment/file/ main/java/org/apache/jackrabbit/oak/plugins/segment/memory/ main/java/org/apach...
Date Mon, 20 Jan 2014 14:31:53 GMT
Author: jukka
Date: Mon Jan 20 14:31:53 2014
New Revision: 1559709

URL: http://svn.apache.org/r1559709
Log:
OAK-631: SegmentMK: Implement garbage collection

Make the SegmentIdFactory keep weak references to all segment identifiers,
so we can tell which ones are still being accessed by existing sessions.

Modified:
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/AbstractStore.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/SegmentIdFactory.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/file/FileStore.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/memory/MemoryStore.java
    jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/mongo/MongoStore.java
    jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/CheckpointTest.java
    jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/RecordTest.java

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/AbstractStore.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/AbstractStore.java?rev=1559709&r1=1559708&r2=1559709&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/AbstractStore.java
(original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/AbstractStore.java
Mon Jan 20 14:31:53 2014
@@ -19,6 +19,7 @@ package org.apache.jackrabbit.oak.plugin
 import static com.google.common.collect.Sets.newHashSet;
 import static org.apache.jackrabbit.oak.plugins.segment.SegmentIdFactory.isBulkSegmentId;
 
+import java.nio.ByteBuffer;
 import java.util.Set;
 import java.util.UUID;
 
@@ -45,9 +46,12 @@ public abstract class AbstractStore impl
      */
     private int currentlyWaiting = 0;
 
-    private final SegmentWriter writer = new SegmentWriter(this);
+    private final SegmentIdFactory factory = new SegmentIdFactory();
+
+    private final SegmentWriter writer;
 
     protected AbstractStore(int cacheSizeMB) {
+        this.writer = new SegmentWriter(this, factory);
         if (cacheSizeMB > 0) {
             this.segments = CacheLIRS.newBuilder()
                     .weigher(Segment.WEIGHER)
@@ -58,6 +62,10 @@ public abstract class AbstractStore impl
         }
     }
 
+    protected Segment createSegment(UUID segmentId, ByteBuffer data) {
+        return new Segment(this, factory, segmentId, data);
+    }
+
     @Nonnull
     protected abstract Segment loadSegment(UUID id);
 

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=1559709&r1=1559708&r2=1559709&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
Mon Jan 20 14:31:53 2014
@@ -127,7 +127,9 @@ public class Segment {
 
     private final byte[] recentCacheHits;
 
-    public Segment(SegmentStore store, UUID uuid, ByteBuffer data) {
+    public Segment(
+            SegmentStore store, SegmentIdFactory factory,
+            UUID uuid, ByteBuffer data) {
         this.store = checkNotNull(store);
         this.uuid = checkNotNull(uuid);
         this.data = checkNotNull(data);
@@ -139,7 +141,7 @@ public class Segment {
             refpos += align(3 + roots * 3);
             refids = new UUID[refs];
             for (int i = 0; i < refs; i++) {
-                refids[i] = new UUID(
+                refids[i] = factory.getSegmentId(
                         data.getLong(refpos + i * 16),
                         data.getLong(refpos + i * 16 + 8));
             }

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentIdFactory.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentIdFactory.java?rev=1559709&r1=1559708&r2=1559709&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentIdFactory.java
(original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentIdFactory.java
Mon Jan 20 14:31:53 2014
@@ -16,13 +16,24 @@
  */
 package org.apache.jackrabbit.oak.plugins.segment;
 
+import static com.google.common.collect.Lists.newArrayList;
+import static com.google.common.collect.Lists.newLinkedList;
+
+import java.lang.ref.WeakReference;
 import java.security.SecureRandom;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
 import java.util.UUID;
 
+/**
+ * Factory for creating the UUID objects used to identify segments.
+ * Weak references are used to keep track of all currently referenced
+ * UUIDs, so that we can avoid garbage-collecting those segments.
+ */
 public class SegmentIdFactory {
 
-    private static final SecureRandom random = new SecureRandom();
-
     private static final long MSB_MASK = ~(0xfL << 12);
 
     private static final long VERSION = (0x4L << 12);
@@ -33,26 +44,125 @@ public class SegmentIdFactory {
 
     private static final long BULK = 0xBL << 60;
 
-    private static UUID newSegmentId(long type) {
-        long msb = (random.nextLong() & MSB_MASK) | VERSION;
-        long lsb = (random.nextLong() & LSB_MASK) | type;
-        return new UUID(msb, lsb);
+    /**
+     * Checks whether the given UUID identifies a data segment.
+     *
+     * @param id segment identifier
+     * @return {@code true} for a data segment, {@code false} for bulk
+     */
+    public static boolean isDataSegmentId(UUID id) {
+        return (id.getLeastSignificantBits() & ~LSB_MASK) == DATA; 
+    }
+
+    /**
+     * Checks whether the given UUID identifies a bulk segment.
+     *
+     * @param id segment identifier
+     * @return {@code true} for a bulk segment, {@code false} for data
+     */
+    public static boolean isBulkSegmentId(UUID id) {
+        return (id.getLeastSignificantBits() & ~LSB_MASK) == BULK; 
     }
 
-    static UUID newDataSegmentId() {
+    /**
+     * The random number source for generating new segment identifiers.
+     */
+    private final SecureRandom random = new SecureRandom();
+
+    /**
+     * Hash table of weak references to UUIDs that are currently referenced.
+     * The size of the table is always a power of two, which optimizes the
+     * {@link #expand()} operation. The table is indexed by the random UUID
+     * bits, which guarantees uniform distribution of entries. Each table
+     * entry is either {@code null} (when there are no matching UUIDs) or
+     * a list of weak references to the matching UUIDs.
+     */
+    private final ArrayList<List<WeakReference<UUID>>> uuids = newArrayList(
+            Collections.<List<WeakReference<UUID>>>nCopies(1024, null));
+
+    /**
+     * 
+     * @param msb
+     * @param lsb
+     * @return
+     */
+    synchronized UUID getSegmentId(long msb, long lsb) {
+        int index = ((int) lsb) & (uuids.size() - 1);
+
+        List<WeakReference<UUID>> list = uuids.get(index);
+        if (list == null) {
+            list = newLinkedList();
+            uuids.set(index, list);
+        }
+
+        Iterator<WeakReference<UUID>> iterator = list.iterator();
+        while (iterator.hasNext()) {
+            UUID uuid = iterator.next().get();
+            if (uuid == null) {
+                iterator.remove();
+            } else if (uuid.getMostSignificantBits() == msb
+                    && uuid.getLeastSignificantBits() == lsb) {
+                return uuid;
+            }
+        }
+
+        UUID uuid = new UUID(msb, lsb);
+        list.add(new WeakReference<UUID>(uuid));
+
+        if (list.size() > 5) {
+            expand();
+        }
+
+        return uuid;
+    }
+
+    UUID newDataSegmentId() {
         return newSegmentId(DATA);
     }
 
-    static UUID newBulkSegmentId() {
+    UUID newBulkSegmentId() {
         return newSegmentId(BULK);
     }
 
-    public static boolean isDataSegmentId(UUID id) {
-        return (id.getLeastSignificantBits() & ~LSB_MASK) == DATA; 
+    private UUID newSegmentId(long type) {
+        long msb = (random.nextLong() & MSB_MASK) | VERSION;
+        long lsb = (random.nextLong() & LSB_MASK) | type;
+        return getSegmentId(msb, lsb);
     }
 
-    public static boolean isBulkSegmentId(UUID id) {
-        return (id.getLeastSignificantBits() & ~LSB_MASK) == BULK; 
+    private synchronized void expand() {
+        int n = uuids.size();
+        uuids.ensureCapacity(n * 2);
+        for (int i = 0; i < n; i++) {
+            List<WeakReference<UUID>> list = uuids.get(i);
+            if (list == null) {
+                uuids.add(null);
+            } else {
+                List<WeakReference<UUID>> newList = newLinkedList();
+
+                Iterator<WeakReference<UUID>>iterator = list.iterator();
+                while (iterator.hasNext()) {
+                    WeakReference<UUID> reference = iterator.next();
+                    UUID uuid = reference.get();
+                    if (uuid == null) {
+                        iterator.remove();
+                    } else if ((uuid.getLeastSignificantBits() & n) != 0) {
+                        iterator.remove();
+                        newList.add(reference);
+                    }
+                }
+
+                if (list.isEmpty()) {
+                    uuids.set(i, null);
+                }
+
+                if (newList.isEmpty()) {
+                    uuids.add(null);
+                } else {
+                    uuids.add(newList);
+                }
+            }
+        }
     }
 
 }

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=1559709&r1=1559708&r2=1559709&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
Mon Jan 20 14:31:53 2014
@@ -37,8 +37,6 @@ import static org.apache.jackrabbit.oak.
 import static org.apache.jackrabbit.oak.plugins.segment.MapRecord.BUCKETS_PER_LEVEL;
 import static org.apache.jackrabbit.oak.plugins.segment.Segment.MAX_SEGMENT_SIZE;
 import static org.apache.jackrabbit.oak.plugins.segment.Segment.align;
-import static org.apache.jackrabbit.oak.plugins.segment.SegmentIdFactory.newBulkSegmentId;
-import static org.apache.jackrabbit.oak.plugins.segment.SegmentIdFactory.newDataSegmentId;
 
 import java.io.IOException;
 import java.io.InputStream;
@@ -86,6 +84,8 @@ public class SegmentWriter {
 
     private final SegmentStore store;
 
+    private final SegmentIdFactory factory;
+
     /**
      * Cache of recently stored string and template records, used to
      * avoid storing duplicates of frequently occurring data.
@@ -99,7 +99,7 @@ public class SegmentWriter {
             }
         };
 
-    private UUID uuid = newDataSegmentId();
+    private UUID uuid;
 
     /**
      * Insertion-ordered map from the UUIDs of referenced segments to the
@@ -136,10 +136,13 @@ public class SegmentWriter {
 
     private final Segment dummySegment;
 
-    public SegmentWriter(SegmentStore store) {
+    public SegmentWriter(SegmentStore store, SegmentIdFactory factory) {
         this.store = store;
-        this.dummySegment =
-                new Segment(store, newBulkSegmentId(), ByteBuffer.allocate(0));
+        this.factory = factory;
+        this.uuid = factory.newDataSegmentId();
+        this.dummySegment = new Segment(
+                store, factory,
+                factory.newBulkSegmentId(), ByteBuffer.allocate(0));
     }
 
     private void writeSegmentHeader(ByteBuffer b) {
@@ -197,7 +200,7 @@ public class SegmentWriter {
 
             store.writeSegment(uuid, buffer, buffer.length - length, length);
 
-            uuid = newDataSegmentId();
+            uuid = factory.newDataSegmentId();
             buffer = new byte[MAX_SEGMENT_SIZE];
             refids.clear();
             roots.clear();
@@ -621,7 +624,7 @@ public class SegmentWriter {
 
         // write as many full bulk segments as possible
         while (pos + MAX_SEGMENT_SIZE <= data.length) {
-            UUID uuid = newBulkSegmentId();
+            UUID uuid = factory.newBulkSegmentId();
             store.writeSegment(uuid, data, pos, MAX_SEGMENT_SIZE);
             for (int i = 0; i < MAX_SEGMENT_SIZE; i += BLOCK_SIZE) {
                 blockIds.add(new RecordId(uuid, i));
@@ -686,7 +689,7 @@ public class SegmentWriter {
 
         // Write the data to bulk segments and collect the list of block ids
         while (n != 0) {
-            UUID id = newBulkSegmentId();
+            UUID id = factory.newBulkSegmentId();
             int len = align(n);
             store.writeSegment(id, data, 0, len);
 

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/file/FileStore.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/file/FileStore.java?rev=1559709&r1=1559708&r2=1559709&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/file/FileStore.java
(original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/file/FileStore.java
Mon Jan 20 14:31:53 2014
@@ -280,7 +280,7 @@ public class FileStore extends AbstractS
             try {
                 ByteBuffer buffer = file.readEntry(id);
                 if (buffer != null) {
-                    return new Segment(FileStore.this, id, buffer);
+                    return createSegment(id, buffer);
                 }
             } catch (IOException e) {
                 throw new RuntimeException(
@@ -292,7 +292,7 @@ public class FileStore extends AbstractS
             try {
                 ByteBuffer buffer = file.readEntry(id);
                 if (buffer != null) {
-                    return new Segment(FileStore.this, id, buffer);
+                    return createSegment(id, buffer);
                 }
             } catch (IOException e) {
                 throw new RuntimeException(

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/memory/MemoryStore.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/memory/MemoryStore.java?rev=1559709&r1=1559708&r2=1559709&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/memory/MemoryStore.java
(original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/memory/MemoryStore.java
Mon Jan 20 14:31:53 2014
@@ -81,7 +81,7 @@ public class MemoryStore extends Abstrac
         ByteBuffer buffer = ByteBuffer.allocate(length);
         buffer.put(data, offset, length);
         buffer.rewind();
-        Segment segment = new Segment(this, segmentId, buffer);
+        Segment segment = createSegment(segmentId, buffer);
         if (segments.putIfAbsent(segment.getSegmentId(), segment) != null) {
             throw new IllegalStateException(
                     "Segment override: " + segment.getSegmentId());

Modified: jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/mongo/MongoStore.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/mongo/MongoStore.java?rev=1559709&r1=1559708&r2=1559709&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/mongo/MongoStore.java
(original)
+++ jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/mongo/MongoStore.java
Mon Jan 20 14:31:53 2014
@@ -106,7 +106,7 @@ public class MongoStore extends Abstract
         }
 
         byte[] data = (byte[]) segment.get("data");
-        return new Segment(this, segmentId, ByteBuffer.wrap(data));
+        return createSegment(segmentId, ByteBuffer.wrap(data));
     }
 
     @Override

Modified: jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/CheckpointTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/CheckpointTest.java?rev=1559709&r1=1559708&r2=1559709&view=diff
==============================================================================
--- jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/CheckpointTest.java
(original)
+++ jackrabbit/oak/trunk/oak-core/src/test/java/org/apache/jackrabbit/oak/plugins/segment/CheckpointTest.java
Mon Jan 20 14:31:53 2014
@@ -41,7 +41,7 @@ public class CheckpointTest {
         verifyNS(store, false);
 
         // gc?
-        store.retrieve(SegmentIdFactory.newDataSegmentId().toString());
+        store.retrieve(new SegmentIdFactory().newDataSegmentId().toString());
     }
 
     private static void verifyNS(SegmentNodeStore store, boolean exists) {

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=1559709&r1=1559708&r2=1559709&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
Mon Jan 20 14:31:53 2014
@@ -20,7 +20,6 @@ import static com.google.common.collect.
 import static junit.framework.Assert.fail;
 import static org.apache.jackrabbit.oak.plugins.memory.EmptyNodeState.EMPTY_NODE;
 import static org.apache.jackrabbit.oak.plugins.segment.ListRecord.LEVEL_SIZE;
-import static org.apache.jackrabbit.oak.plugins.segment.SegmentIdFactory.newBulkSegmentId;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNull;
@@ -125,9 +124,10 @@ public class RecordTest {
 
     @Test
     public void testListWithLotsOfReferences() { // OAK-1184
+        SegmentIdFactory factory = new SegmentIdFactory();
         List<RecordId> list = newArrayList();
         for (int i = 0; i < 1000; i++) {
-            list.add(new RecordId(newBulkSegmentId(), 0));
+            list.add(new RecordId(factory.newBulkSegmentId(), 0));
         }
         writer.writeList(list);
     }



Mime
View raw message