Author: jukka
Date: Sat Mar 15 16:26:05 2014
New Revision: 1577891
URL: http://svn.apache.org/r1577891
Log:
OAK-1526: Lock contention in SegmentIdFactory
Maintain a lazily initialized array of refids
Optimize the SemgentId hash tables
Added:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentIdTable.java
(with props)
Modified:
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/SegmentTracker.java
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentWriter.java
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=1577891&r1=1577890&r2=1577891&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
Sat Mar 15 16:26:05 2014
@@ -103,6 +103,12 @@ public class Segment {
private final ByteBuffer data;
/**
+ * Referenced segment identifiers. Entries are initialized lazily in
+ * {@link #getRefId(int)}. Set to {@code null} for bulk segments.
+ */
+ private final SegmentId[] refids;
+
+ /**
* String records read from segment. Used to avoid duplicate
* copies and repeated parsing of the same strings.
*/
@@ -118,6 +124,22 @@ public class Segment {
this.tracker = checkNotNull(tracker);
this.id = checkNotNull(id);
this.data = checkNotNull(data);
+
+ if (id.isDataSegmentId()) {
+ this.refids = new SegmentId[getRefCount()];
+ refids[0] = id;
+ } else {
+ this.refids = null;
+ }
+ }
+
+ Segment(SegmentTracker tracker, byte[] buffer) {
+ this.tracker = checkNotNull(tracker);
+ this.id = tracker.newDataSegmentId();
+ this.data = ByteBuffer.wrap(checkNotNull(buffer));
+
+ this.refids = new SegmentId[SEGMENT_REFERENCE_LIMIT + 1];
+ refids[0] = id;
}
/**
@@ -137,22 +159,28 @@ public class Segment {
}
public SegmentId getSegmentId() {
- return id;
+ return refids[0];
}
int getRefCount() {
return (data.get(REF_COUNT_OFFSET) & 0xff) + 1;
}
- SegmentId getRefId(int refid) {
- if (refid == 0) {
- return id;
- } else {
- int refpos = data.position() + refid * 16;
- long msb = data.getLong(refpos);
- long lsb = data.getLong(refpos + 8);
- return tracker.getSegmentId(msb, lsb);
+ SegmentId getRefId(int index) {
+ SegmentId refid = refids[index];
+ if (refid == null) {
+ synchronized (this) {
+ refid = refids[index];
+ if (refid == null) {
+ int refpos = data.position() + index * 16;
+ long msb = data.getLong(refpos);
+ long lsb = data.getLong(refpos + 8);
+ refid = tracker.getSegmentId(msb, lsb);
+ refids[index] = refid;
+ }
+ }
}
+ return refid;
}
public List<SegmentId> getReferencedIds() {
@@ -169,11 +197,14 @@ public class Segment {
}
public long getCacheSize() {
- if (data.isDirect()) {
- return 1024 + data.remaining();
- } else {
- return 1024 + 2 * data.remaining();
+ int size = 1024;
+ if (!data.isDirect()) {
+ size += size();
+ }
+ if (id.isDataSegmentId()) {
+ size += size();
}
+ return size;
}
/**
Added:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentIdTable.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentIdTable.java?rev=1577891&view=auto
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentIdTable.java
(added)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentIdTable.java
Sat Mar 15 16:26:05 2014
@@ -0,0 +1,140 @@
+/*
+ * 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.collect.Lists.newArrayList;
+import static com.google.common.collect.Maps.newHashMapWithExpectedSize;
+import static java.util.Collections.nCopies;
+
+import java.lang.ref.WeakReference;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Map;
+
+/**
+ * Hash table of weak references to segment identifiers.
+ */
+public class SegmentIdTable {
+
+ /**
+ * Hash table of weak references to segment identifiers that are
+ * currently being accessed. The size of the table is always a power
+ * of two, which optimizes the {@link #expand()} operation. The table is
+ * indexed by the random identifier bits, which guarantees uniform
+ * distribution of entries. Each table entry is either {@code null}
+ * (when there are no matching identifiers) or a list of weak references
+ * to the matching identifiers.
+ */
+ private final ArrayList<WeakReference<SegmentId>> references =
+ newArrayList(nCopies(1024, (WeakReference<SegmentId>) null));
+
+ private final SegmentTracker tracker;
+
+ SegmentIdTable(SegmentTracker tracker) {
+ this.tracker = tracker;
+ }
+
+ /**
+ *
+ * @param msb
+ * @param lsb
+ * @return
+ */
+ synchronized SegmentId getSegmentId(long msb, long lsb) {
+ int first = getIndex(lsb);
+ int index = first;
+
+ WeakReference<SegmentId> reference = references.get(index);
+ while (reference != null) {
+ SegmentId id = reference.get();
+ if (id != null
+ && id.getMostSignificantBits() == msb
+ && id.getLeastSignificantBits() == lsb) {
+ return id;
+ }
+ index = (index + 1) % references.size();
+ reference = references.get(index);
+ }
+
+ SegmentId id = new SegmentId(tracker, msb, lsb);
+ references.set(index, new WeakReference<SegmentId>(id));
+ if (index != first) {
+ refresh();
+ }
+ return id;
+ }
+
+ /**
+ * Returns all segment identifiers that are currently referenced in memory.
+ *
+ * @return referenced segment identifiers
+ */
+ void collectReferencedIds(Collection<SegmentId> ids) {
+ ids.addAll(refresh());
+ }
+
+ private synchronized Collection<SegmentId> refresh() {
+ int size = references.size();
+ Map<SegmentId, WeakReference<SegmentId>> ids =
+ newHashMapWithExpectedSize(size);
+
+ boolean hashCollisions = false;
+ boolean emptyReferences = false;
+ for (int i = 0; i < size; i++) {
+ WeakReference<SegmentId> reference = references.get(i);
+ if (reference != null) {
+ SegmentId id = reference.get();
+ if (id != null) {
+ ids.put(id, reference);
+ hashCollisions = hashCollisions || (i != getIndex(id));
+ } else {
+ references.set(i, null);
+ emptyReferences = true;
+ }
+ }
+ }
+
+ while (2 * ids.size() > size) {
+ size *= 2;
+ }
+
+ if ((hashCollisions && emptyReferences) || size != references.size()) {
+ references.clear();
+ references.addAll(nCopies(size, (WeakReference<SegmentId>) null));
+
+ for (Map.Entry<SegmentId, WeakReference<SegmentId>> entry
+ : ids.entrySet()) {
+ int index = getIndex(entry.getKey());
+ while (references.get(index) != null) {
+ index = (index + 1) % size;
+ }
+ references.set(index, entry.getValue());
+ }
+ }
+
+ return ids.keySet();
+ }
+
+ private int getIndex(SegmentId id) {
+ return getIndex(id.getLeastSignificantBits());
+ }
+
+ private int getIndex(long lsb) {
+ return ((int) lsb) & (references.size() - 1);
+ }
+
+}
Propchange:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentIdTable.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified:
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentTracker.java
URL:
http://svn.apache.org/viewvc/jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentTracker.java?rev=1577891&r1=1577890&r2=1577891&view=diff
==============================================================================
---
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentTracker.java
(original)
+++
jackrabbit/oak/trunk/oak-core/src/main/java/org/apache/jackrabbit/oak/plugins/segment/SegmentTracker.java
Sat Mar 15 16:26:05 2014
@@ -16,17 +16,11 @@
*/
package org.apache.jackrabbit.oak.plugins.segment;
-import static com.google.common.collect.Lists.newArrayList;
import static com.google.common.collect.Lists.newLinkedList;
-import static com.google.common.collect.Sets.newHashSetWithExpectedSize;
+import static com.google.common.collect.Sets.newHashSet;
-import java.lang.ref.WeakReference;
import java.security.SecureRandom;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Iterator;
import java.util.LinkedList;
-import java.util.List;
import java.util.Set;
/**
@@ -54,6 +48,12 @@ public class SegmentTracker {
*/
private final SecureRandom random = new SecureRandom();
+ private final SegmentStore store;
+
+ private final SegmentWriter writer;
+
+ private final long cacheSize;
+
/**
* Hash table of weak references to segment identifiers that are
* currently being accessed. The size of the table is always a power
@@ -63,20 +63,17 @@ public class SegmentTracker {
* (when there are no matching identifiers) or a list of weak references
* to the matching identifiers.
*/
- private final ArrayList<List<WeakReference<SegmentId>>> uuids =
newArrayList(
- Collections.<List<WeakReference<SegmentId>>>nCopies(1024, null));
+ private final SegmentIdTable[] tables = new SegmentIdTable[32];
private final LinkedList<Segment> segments = newLinkedList();
- private final SegmentStore store;
-
- private final SegmentWriter writer;
-
- private final long cacheSize;
-
private long currentSize = 0;
public SegmentTracker(SegmentStore store, int cacheSizeMB) {
+ for (int i = 0; i < tables.length; i++) {
+ tables[i] = new SegmentIdTable(this);
+ }
+
this.store = store;
this.writer = new SegmentWriter(store, this);
this.cacheSize = cacheSizeMB * MB;
@@ -118,27 +115,11 @@ public class SegmentTracker {
* @return referenced segment identifiers
*/
public synchronized Set<SegmentId> getReferencedSegmentIds() {
- Set<SegmentId> set = newHashSetWithExpectedSize(uuids.size());
-
- for (int i = 0; i < uuids.size(); i++) {
- List<WeakReference<SegmentId>> list = uuids.get(i);
- if (list != null) {
- Iterator<WeakReference<SegmentId>> iterator = list.iterator();
- while (iterator.hasNext()) {
- SegmentId id = iterator.next().get();
- if (id == null) {
- iterator.remove();
- } else {
- set.add(id);
- }
- }
- if (list.isEmpty()) {
- uuids.set(i, null);
- }
- }
+ Set<SegmentId> ids = newHashSet();
+ for (SegmentIdTable table : tables) {
+ table.collectReferencedIds(ids);
}
-
- return set;
+ return ids;
}
/**
@@ -147,33 +128,9 @@ public class SegmentTracker {
* @param lsb
* @return
*/
- public synchronized SegmentId getSegmentId(long msb, long lsb) {
- int index = ((int) lsb) & (uuids.size() - 1);
-
- List<WeakReference<SegmentId>> list = uuids.get(index);
- if (list == null) {
- list = newLinkedList();
- uuids.set(index, list);
- }
-
- Iterator<WeakReference<SegmentId>> iterator = list.iterator();
- while (iterator.hasNext()) {
- SegmentId id = iterator.next().get();
- if (id == null) {
- iterator.remove();
- } else if (id.equals(msb, lsb)) {
- return id;
- }
- }
-
- SegmentId id = new SegmentId(this, msb, lsb);
- list.add(new WeakReference<SegmentId>(id));
-
- if (list.size() > 5) {
- expand();
- }
-
- return id;
+ public SegmentId getSegmentId(long msb, long lsb) {
+ int index = ((int) msb) & (tables.length - 1);
+ return tables[index].getSegmentId(msb, lsb);
}
SegmentId newDataSegmentId() {
@@ -190,39 +147,4 @@ public class SegmentTracker {
return getSegmentId(msb, lsb);
}
- private synchronized void expand() {
- int n = uuids.size();
- uuids.ensureCapacity(n * 2);
- for (int i = 0; i < n; i++) {
- List<WeakReference<SegmentId>> list = uuids.get(i);
- if (list == null) {
- uuids.add(null);
- } else {
- List<WeakReference<SegmentId>> newList = newLinkedList();
-
- Iterator<WeakReference<SegmentId>>iterator = list.iterator();
- while (iterator.hasNext()) {
- WeakReference<SegmentId> reference = iterator.next();
- SegmentId 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=1577891&r1=1577890&r2=1577891&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 Mar 15 16:26:05 2014
@@ -141,8 +141,7 @@ public class SegmentWriter {
public SegmentWriter(SegmentStore store, SegmentTracker tracker) {
this.store = store;
this.tracker = tracker;
- this.segment = new Segment(
- tracker, tracker.newDataSegmentId(), ByteBuffer.wrap(buffer));
+ this.segment = new Segment(tracker, buffer);
segment.getSegmentId().setSegment(segment);
}
@@ -189,9 +188,7 @@ public class SegmentWriter {
roots.clear();
length = 0;
position = buffer.length;
- segment = new Segment(
- tracker, tracker.newDataSegmentId(),
- ByteBuffer.wrap(buffer));
+ segment = new Segment(tracker, buffer);
segment.getSegmentId().setSegment(segment);
}
}
