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 to...@apache.org on 2016/08/08 10:35:32 UTC
svn commit: r1755490 - in /jackrabbit/oak/branches/1.2/oak-core/src:
main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java
test/java/org/apache/jackrabbit/oak/cache/CacheTest.java
Author: tomekr
Date: Mon Aug 8 10:35:32 2016
New Revision: 1755490
URL: http://svn.apache.org/viewvc?rev=1755490&view=rev
Log:
OAK-3095: Add eviction listener to LIRS cache
Modified:
jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java
jackrabbit/oak/branches/1.2/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/CacheTest.java
Modified: jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java?rev=1755490&r1=1755489&r2=1755490&view=diff
==============================================================================
--- jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java (original)
+++ jackrabbit/oak/branches/1.2/oak-core/src/main/java/org/apache/jackrabbit/oak/cache/CacheLIRS.java Mon Aug 8 10:35:32 2016
@@ -28,6 +28,7 @@ import java.util.concurrent.ConcurrentHa
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ExecutionException;
+import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import org.slf4j.Logger;
@@ -75,6 +76,31 @@ public class CacheLIRS<K, V> implements
private static final Logger LOG = LoggerFactory.getLogger(CacheLIRS.class);
/**
+ * Listener for items that are evicted from the cache. The listener
+ * is called for both, resident and non-resident items. In the
+ * latter case the passed value is {@code null}.
+ * @param <K> type of the key
+ * @param <V> type of the value
+ */
+ public interface EvictionCallback<K, V> {
+
+ /**
+ * Indicates eviction of an item.
+ * <p>
+ * <em>Note:</em> It is not safe to call any of {@code CacheLIRS}'s
+ * method from withing this callback. Any such call might result in
+ * undefined behaviour and Java level deadlocks.
+ * <p>
+ * The method may be called twice for the same key (first if the entry
+ * is resident, and later if the entry is non-resident).
+ *
+ * @param key the evicted item's key
+ * @param value the evicted item's value or {@code null} if non-resident
+ */
+ void evicted(@Nonnull K key, @Nullable V value);
+ }
+
+ /**
* The maximum memory this cache should use.
*/
private long maxMemory;
@@ -94,7 +120,12 @@ public class CacheLIRS<K, V> implements
private final Weigher<K, V> weigher;
private final CacheLoader<K, V> loader;
-
+
+ /**
+ * The eviction listener of this cache or {@code null} if none.
+ */
+ private final EvictionCallback<K, V> evicted;
+
/**
* A concurrent hash map of keys where loading is in progress. Key: the
* cache key. Value: a synchronization object. The threads that wait for the
@@ -112,7 +143,7 @@ public class CacheLIRS<K, V> implements
* @param maxEntries the maximum number of entries
*/
public CacheLIRS(int maxEntries) {
- this(null, maxEntries, 1, 16, maxEntries / 100, null);
+ this(null, maxEntries, 1, 16, maxEntries / 100, null, null);
}
/**
@@ -123,10 +154,12 @@ public class CacheLIRS<K, V> implements
* @param segmentCount the number of cache segments (must be a power of 2)
* @param stackMoveDistance how many other item are to be moved to the top
* of the stack before the current item is moved
+ * @param evicted the eviction listener of this segment or {@code null} if none.
*/
@SuppressWarnings("unchecked")
CacheLIRS(Weigher<K, V> weigher, long maxMemory, int averageMemory,
- int segmentCount, int stackMoveDistance, final CacheLoader<K, V> loader) {
+ int segmentCount, int stackMoveDistance, final CacheLoader<K, V> loader,
+ EvictionCallback<K, V> evicted) {
this.weigher = weigher;
setMaxMemory(maxMemory);
setAverageMemory(averageMemory);
@@ -137,6 +170,7 @@ public class CacheLIRS<K, V> implements
this.segmentMask = segmentCount - 1;
this.stackMoveDistance = stackMoveDistance;
segments = new Segment[segmentCount];
+ this.evicted = evicted;
invalidateAll();
this.segmentShift = Integer.numberOfTrailingZeros(segments[0].entries.length);
this.loader = loader;
@@ -160,7 +194,25 @@ public class CacheLIRS<K, V> implements
s.totalLoadTime = old.totalLoadTime;
s.evictionCount = old.evictionCount;
}
- segments[i] = s;
+ setSegment(i, s);
+ }
+ }
+
+ private void setSegment(int index, Segment<K, V> s) {
+ Segment<K, V> old = segments[index];
+ segments[index] = s;
+ if (evicted != null && old != null && old != s) {
+ old.evictedAll();
+ }
+ }
+
+ void evicted(Entry<K, V> entry) {
+ if (evicted == null) {
+ return;
+ }
+ K key = entry.key;
+ if (key != null) {
+ evicted.evicted(key, entry.value);
}
}
@@ -564,7 +616,12 @@ public class CacheLIRS<K, V> implements
void clear() {
for (Segment<K, V> s : segments) {
- s.clear();
+ synchronized (s) {
+ if (evicted != null) {
+ s.evictedAll();
+ }
+ s.clear();
+ }
}
}
@@ -718,6 +775,22 @@ public class CacheLIRS<K, V> implements
clear();
}
+ public void evictedAll() {
+ for (Entry<K, V> e = stack.stackNext; e != stack; e = e.stackNext) {
+ if (e.value != null) {
+ cache.evicted(e);
+ }
+ }
+ for (Entry<K, V> e = queue.queueNext; e != queue; e = e.queueNext) {
+ if (e.stackNext == null) {
+ cache.evicted(e);
+ }
+ }
+ for (Entry<K, V> e = queue2.queueNext; e != queue2; e = e.queueNext) {
+ cache.evicted(e);
+ }
+ }
+
synchronized void clear() {
// calculate the size of the map array
@@ -1097,17 +1170,18 @@ public class CacheLIRS<K, V> implements
if (e.isHot()) {
// when removing a hot entry, the newest cold entry gets hot,
// so the number of hot entries does not change
- e = queue.queueNext;
- if (e != queue) {
- removeFromQueue(e);
- if (e.stackNext == null) {
- addToStackBottom(e);
+ Entry<K, V> nc = queue.queueNext;
+ if (nc != queue) {
+ removeFromQueue(nc);
+ if (nc.stackNext == null) {
+ addToStackBottom(nc);
}
}
} else {
removeFromQueue(e);
}
pruneStack();
+ cache.evicted(e);
}
/**
@@ -1135,6 +1209,7 @@ public class CacheLIRS<K, V> implements
usedMemory -= e.memory;
evictionCount++;
removeFromQueue(e);
+ cache.evicted(e);
e.value = null;
e.memory = 0;
addToQueue(queue2, e);
@@ -1405,6 +1480,7 @@ public class CacheLIRS<K, V> implements
private int averageWeight = 100;
private int segmentCount = 16;
private int stackMoveDistance = 16;
+ private EvictionCallback<?, ?> evicted;
public Builder<K, V> recordStats() {
return this;
@@ -1449,13 +1525,19 @@ public class CacheLIRS<K, V> implements
return this;
}
+ public Builder evictionCallback(EvictionCallback<?, ?> evicted) {
+ this.evicted = evicted;
+ return this;
+ }
+
public CacheLIRS<K, V> build() {
return build(null);
}
public CacheLIRS<K, V> build(CacheLoader<K, V> cacheLoader) {
+ EvictionCallback<K, V> ec = (EvictionCallback<K, V>) evicted;
return new CacheLIRS<K, V>(weigher, maxWeight, averageWeight,
- segmentCount, stackMoveDistance, cacheLoader);
+ segmentCount, stackMoveDistance, cacheLoader, ec);
}
}
Modified: jackrabbit/oak/branches/1.2/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/CacheTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/branches/1.2/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/CacheTest.java?rev=1755490&r1=1755489&r2=1755490&view=diff
==============================================================================
--- jackrabbit/oak/branches/1.2/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/CacheTest.java (original)
+++ jackrabbit/oak/branches/1.2/oak-core/src/test/java/org/apache/jackrabbit/oak/cache/CacheTest.java Mon Aug 8 10:35:32 2016
@@ -18,6 +18,8 @@
*/
package org.apache.jackrabbit.oak.cache;
+import static com.google.common.collect.Sets.newHashSet;
+import static java.lang.String.valueOf;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNull;
@@ -29,10 +31,12 @@ import java.util.HashSet;
import java.util.List;
import java.util.Map.Entry;
import java.util.Random;
+import java.util.Set;
import java.util.concurrent.Callable;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ExecutionException;
+import org.apache.jackrabbit.oak.cache.CacheLIRS.EvictionCallback;
import org.junit.Test;
import com.google.common.cache.CacheLoader;
@@ -573,7 +577,7 @@ public class CacheTest {
}
private static <K, V> CacheLIRS<K, V> createCache(int maxSize, int averageSize) {
- return new CacheLIRS<K, V>(null, maxSize, averageSize, 1, 0, null);
+ return new CacheLIRS<K, V>(null, maxSize, averageSize, 1, 0, null, null);
}
@Test
@@ -680,5 +684,95 @@ public class CacheTest {
// expected to log a warning, but not fail
cache.refresh(-1);
}
+
+ @Test
+ public void evictionCallback() throws ExecutionException {
+ final Set<String> evictedKeys = newHashSet();
+ final Set<Integer> evictedValues = newHashSet();
+ CacheLIRS<String, Integer> cache = CacheLIRS.newBuilder()
+ .maximumSize(100)
+ .evictionCallback(new EvictionCallback<String, Integer>() {
+ @Override
+ public void evicted(String key, Integer value) {
+ evictedKeys.add(key);
+ if (value != null) {
+ assertEquals(key, valueOf(value));
+ evictedValues.add(value);
+ }
+ }
+ })
+ .build();
+
+ for (int k = 0; k < 200; k++) {
+ cache.put(valueOf(k), k);
+ }
+
+ assertTrue(evictedKeys.size() <= evictedValues.size());
+ for (String key : evictedKeys) {
+ assertFalse(cache.containsKey(key));
+ }
+
+ cache.invalidateAll();
+ assertEquals(200, evictedKeys.size());
+ assertEquals(200, evictedValues.size());
+ }
+ @Test
+ public void evictionCallbackRandomized() throws ExecutionException {
+ final HashMap<Integer, Integer> evictedMap = new HashMap<Integer, Integer>();
+ final HashSet<Integer> evictedNonResidentSet = new HashSet<Integer>();
+ CacheLIRS<Integer, Integer> cache = CacheLIRS.newBuilder()
+ .maximumSize(10)
+ .evictionCallback(new EvictionCallback<Integer, Integer>() {
+ @Override
+ public void evicted(Integer key, Integer value) {
+ if (value == null) {
+ assertTrue(evictedNonResidentSet.add(key));
+ } else {
+ assertEquals(null, evictedMap.put(key, value));
+ }
+ }
+ })
+ .build();
+ Random r = new Random(1);
+ for (int k = 0; k < 10000; k++) {
+ if (r.nextInt(20) == 0) {
+ evictedMap.clear();
+ evictedNonResidentSet.clear();
+ long size = cache.size();
+ long sizeNonResident = cache.sizeNonResident();
+ cache.invalidateAll();
+ assertEquals(evictedMap.size(), size);
+ assertEquals(evictedNonResidentSet.size(), sizeNonResident);
+ }
+ evictedMap.clear();
+ evictedNonResidentSet.clear();
+ int key = r.nextInt(20);
+ if (r.nextBoolean()) {
+ cache.put(key, k);
+ } else {
+ cache.get(key);
+ }
+ for (Entry<Integer, Integer> ev : evictedMap.entrySet()) {
+ int ek = ev.getKey();
+ if (ek == key) {
+ // the same key was inserted just now
+ } else {
+ assertFalse(cache.containsKey(ek));
+ }
+ }
+ for (Entry<Integer, Integer> ev : evictedMap.entrySet()) {
+ int ek = ev.getKey();
+ Integer v = ev.getValue();
+ // an old value
+ assertTrue(v < k);
+ if (ek == key) {
+ // the same key was inserted just now
+ } else {
+ assertFalse(cache.containsKey(ek));
+ }
+ }
+ }
+ }
+
}