org.apache.jackrabbit.oak.cache

Class CacheLIRS<K,V>

java.lang.Object

org.apache.jackrabbit.oak.cache.CacheLIRS<K,V>

Type Parameters:

K - the key type

V - the value type

All Implemented Interfaces:

com.google.common.base.Function<K,V>, com.google.common.cache.Cache<K,V>, com.google.common.cache.LoadingCache<K,V>

@Internal(since="1.1.1")
public class CacheLIRS<K,V>
extends java.lang.Object
implements com.google.common.cache.LoadingCache<K,V>

For Oak internal use only. Do not use outside Oak components.

A scan resistant cache. It is meant to cache objects that are relatively costly to acquire, for example file content.

This implementation is multi-threading safe and supports concurrent access. Null keys or null values are not allowed. The map fill factor is at most 75%.

Each entry is assigned a distinct memory size, and the cache will try to use at most the specified amount of memory. The memory unit is not relevant, however it is suggested to use bytes as the unit.

This class implements an approximation of the the LIRS replacement algorithm invented by Xiaodong Zhang and Song Jiang as described in http://www.cse.ohio-state.edu/~zhang/lirs-sigmetrics-02.html with a few smaller changes: An additional queue for non-resident entries is used, to prevent unbound memory usage. The maximum size of this queue is at most the size of the rest of the stack. About 6.25% of the mapped entries are cold.

Internally, the cache is split into a number of segments, and each segment is an individual LIRS cache.

Accessed entries are only moved to the top of the stack if at least a number of other entries have been moved to the front (1% by default). Write access and moving entries to the top of the stack is synchronized per segment.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	CacheLIRS.Builder<K,V> A builder for the cache.
static interface	CacheLIRS.EvictionCallback<K,V> Listener for items that are evicted from the cache.

Constructor Summary

Constructors

Constructor and Description
CacheLIRS(int maxEntries) Create a new cache with the given number of entries, and the default settings (an average size of 1 per entry, 16 segments, and stack move distance equals to the maximum number of entries divided by 100).

Method Summary

Modifier and Type	Method and Description
V	apply(K key)
java.util.concurrent.ConcurrentMap<K,V>	asMap()
void	cleanUp()
boolean	containsKey(java.lang.Object key) Check whether there is a resident entry for the given key.
java.util.Set<java.util.Map.Entry<K,V>>	entrySet() Get the entry set for all resident entries.
V	get(K key) Get the value, loading it if needed.
V	get(K key, java.util.concurrent.Callable<? extends V> valueLoader)
com.google.common.collect.ImmutableMap<K,V>	getAll(java.lang.Iterable<? extends K> keys)
com.google.common.collect.ImmutableMap<K,V>	getAllPresent(java.lang.Iterable<?> keys)
int	getAverageMemory() Get the average memory used per entry.
V	getIfPresent(java.lang.Object key) Get the value for the given key if the entry is cached.
long	getMaxMemory() Get the maximum memory to use.
int	getMemory(K key) Get the memory used for the given key.
V	getUnchecked(K key) Get the value, loading it if needed.
long	getUsedMemory() Get the currently used memory.
void	invalidate(java.lang.Object key) Remove an entry.
void	invalidateAll() Remove all entries.
void	invalidateAll(java.lang.Iterable<?> keys)
boolean	isEmpty()
java.util.List<K>	keys(boolean cold, boolean nonResident) Get the list of keys.
java.util.Set<K>	keySet() Get the set of keys for resident entries.
static <K,V> CacheLIRS.Builder<K,V>	newBuilder() Create a builder.
V	peek(K key) Get the value for the given key if the entry is cached.
void	put(K key, V value) Add an entry to the cache.
V	put(K key, V value, int memory) Add an entry to the cache.
void	putAll(java.util.Map<? extends K,? extends V> m)
void	refresh(K key) Re-load the value for the given key.
V	remove(java.lang.Object key) Remove an entry.
void	setAverageMemory(int averageMemory) Set the average memory used per entry.
void	setMaxMemory(long maxMemory) Set the maximum memory this cache should use.
long	size() Get the number of resident entries.
int	sizeHot() Get the number of hot entries in the cache.
int	sizeMapArray() Get the length of the internal map array.
int	sizeNonResident() Get the number of non-resident entries in the cache.
com.google.common.cache.CacheStats	stats()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.google.common.base.Function

equals

Constructor Detail

CacheLIRS

public CacheLIRS(int maxEntries)

Create a new cache with the given number of entries, and the default settings (an average size of 1 per entry, 16 segments, and stack move distance equals to the maximum number of entries divided by 100).

Parameters:

maxEntries - the maximum number of entries

Method Detail

invalidateAll

public void invalidateAll()

Remove all entries.

Specified by:

invalidateAll in interface com.google.common.cache.Cache<K,V>

containsKey

public boolean containsKey(java.lang.Object key)

Check whether there is a resident entry for the given key. This method does not adjust the internal state of the cache.

Parameters:

key - the key (may not be null)

Returns:

true if there is a resident entry

peek

public V peek(K key)

Get the value for the given key if the entry is cached. This method does not modify the internal state.

Parameters:

key - the key (may not be null)

Returns:

the value, or null if there is no resident entry

put

public V put(K key,
             V value,
             int memory)

Add an entry to the cache. This method is an explicit memory size (weight), and not using the weigher even if configured. The entry may or may not exist in the cache yet. This method will usually mark unknown entries as cold and known entries as hot.

Parameters:

key - the key (may not be null)

value - the value (may not be null)

memory - the memory used for the given entry

Returns:

the old value, or null if there was no resident entry

put

public void put(K key,
                V value)

Add an entry to the cache. If a weigher is specified, it is used, otherwise the average memory size is used.

Specified by:

put in interface com.google.common.cache.Cache<K,V>

Parameters:

key - the key (may not be null)

value - the value (may not be null)

get

public V get(K key,
             java.util.concurrent.Callable<? extends V> valueLoader)
      throws java.util.concurrent.ExecutionException

Specified by:

get in interface com.google.common.cache.Cache<K,V>

Throws:

java.util.concurrent.ExecutionException

getUnchecked

public V getUnchecked(K key)

Get the value, loading it if needed.

If there is an exception loading, an UncheckedExecutionException is thrown.

Specified by:

getUnchecked in interface com.google.common.cache.LoadingCache<K,V>

Parameters:

key - the key

Returns:

the value

Throws:

com.google.common.util.concurrent.UncheckedExecutionException

get

public V get(K key)
      throws java.util.concurrent.ExecutionException

Get the value, loading it if needed.

Specified by:

get in interface com.google.common.cache.LoadingCache<K,V>

Parameters:

key - the key

Returns:

the value

Throws:

java.util.concurrent.ExecutionException

refresh

public void refresh(K key)

Re-load the value for the given key.

If there is an exception while loading, it is logged and ignored. This method calls CacheLoader.reload, but synchronously replaces the old value.

Specified by:

refresh in interface com.google.common.cache.LoadingCache<K,V>

Parameters:

key - the key

getIfPresent

@Nullable
public V getIfPresent(java.lang.Object key)

Get the value for the given key if the entry is cached. This method adjusts the internal state of the cache sometimes, to ensure commonly used entries stay in the cache.

Specified by:

getIfPresent in interface com.google.common.cache.Cache<K,V>

Parameters:

key - the key (may not be null)

Returns:

the value, or null if there is no resident entry

invalidate

public void invalidate(java.lang.Object key)

Remove an entry. Both resident and non-resident entries can be removed.

Specified by:

invalidate in interface com.google.common.cache.Cache<K,V>

Parameters:

key - the key (may not be null)

remove

public V remove(java.lang.Object key)

Remove an entry. Both resident and non-resident entries can be removed.

Parameters:

key - the key (may not be null)

Returns:

the old value or null

invalidateAll

public void invalidateAll(java.lang.Iterable<?> keys)

Specified by:

invalidateAll in interface com.google.common.cache.Cache<K,V>

getMemory

public int getMemory(K key)

Get the memory used for the given key.

Parameters:

key - the key (may not be null)

Returns:

the memory, or 0 if there is no resident entry

getUsedMemory

public long getUsedMemory()

Get the currently used memory.

Returns:

the used memory

setMaxMemory

public void setMaxMemory(long maxMemory)

Set the maximum memory this cache should use. This will not immediately cause entries to get removed however; it will only change the limit. To resize the internal array, call the clear method.

Parameters:

maxMemory - the maximum size (1 or larger)

setAverageMemory

public void setAverageMemory(int averageMemory)

Set the average memory used per entry. It is used to calculate the length of the internal array.

Parameters:

averageMemory - the average memory used (1 or larger)

getAverageMemory

public int getAverageMemory()

Get the average memory used per entry.

Returns:

the average memory

getMaxMemory

public long getMaxMemory()

Get the maximum memory to use.

Returns:

the maximum memory

entrySet

public java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Get the entry set for all resident entries.

Returns:

the entry set

keySet

public java.util.Set<K> keySet()

Get the set of keys for resident entries.

Returns:

the set of keys

sizeNonResident

public int sizeNonResident()

Get the number of non-resident entries in the cache.

Returns:

the number of non-resident entries

sizeMapArray

public int sizeMapArray()

Get the length of the internal map array.

Returns:

the size of the array

sizeHot

public int sizeHot()

Get the number of hot entries in the cache.

Returns:

the number of hot entries

size

public long size()

Get the number of resident entries.

Specified by:

size in interface com.google.common.cache.Cache<K,V>

Returns:

the number of entries

keys

public java.util.List<K> keys(boolean cold,
                              boolean nonResident)

Get the list of keys. This method allows to read the internal state of the cache.

Parameters:

cold - if true, only keys for the cold entries are returned

nonResident - true for non-resident entries

Returns:

the key list

stats

public com.google.common.cache.CacheStats stats()

Specified by:

stats in interface com.google.common.cache.Cache<K,V>

newBuilder

public static <K,V> CacheLIRS.Builder<K,V> newBuilder()

Create a builder.

Returns:

the builder

getAllPresent

public com.google.common.collect.ImmutableMap<K,V> getAllPresent(java.lang.Iterable<?> keys)

Specified by:

getAllPresent in interface com.google.common.cache.Cache<K,V>

asMap

public java.util.concurrent.ConcurrentMap<K,V> asMap()

Specified by:

asMap in interface com.google.common.cache.Cache<K,V>

Specified by:

asMap in interface com.google.common.cache.LoadingCache<K,V>

cleanUp

public void cleanUp()

Specified by:

cleanUp in interface com.google.common.cache.Cache<K,V>

putAll

public void putAll(java.util.Map<? extends K,? extends V> m)

Specified by:

putAll in interface com.google.common.cache.Cache<K,V>

getAll

public com.google.common.collect.ImmutableMap<K,V> getAll(java.lang.Iterable<? extends K> keys)
                                                   throws java.util.concurrent.ExecutionException

Specified by:

getAll in interface com.google.common.cache.LoadingCache<K,V>

Throws:

java.util.concurrent.ExecutionException

apply

public V apply(K key)

Specified by:

apply in interface com.google.common.base.Function<K,V>

Specified by:

apply in interface com.google.common.cache.LoadingCache<K,V>

isEmpty

public boolean isEmpty()