Class CacheLongKeyLIRS<V>
- Type Parameters:
V
- the value type
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 LIRS replacement algorithm invented by Xiaodong Zhang and Song Jiang as described in https://web.cse.ohio-state.edu/~zhang.574/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 (8 per segment by default). Write access and moving entries to the top of the stack is synchronized per segment.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
The cache configuration.(package private) static class
A cache entry.private static class
A cache segment -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate long
The maximum memory this cache should use.private final int
private final int
private final int
private final int
private final CacheLongKeyLIRS.Segment<V>[]
private final int
private final int
-
Constructor Summary
ConstructorsConstructorDescriptionCreate a new cache with the given memory size. -
Method Summary
Modifier and TypeMethodDescriptionvoid
clear()
Remove all entries.boolean
containsKey
(long key) Check whether there is a resident entry for the given key.boolean
containsValue
(V value) Check whether the given value is stored.entrySet()
Get the entry set for all resident entries.private CacheLongKeyLIRS.Entry
<V> find
(long key) get
(long key) Get the value for the given key if the entry is cached.(package private) static int
getHash
(long key) Get the hash code for the given key.long
getHits()
Get the number of cache hits.getMap()
Convert this cache to a map.long
Determines max size of the data item size to fit into cachelong
Get the maximum memory to use.int
getMemory
(long key) Get the memory used for the given key.long
Get the number of cache misses.private CacheLongKeyLIRS.Segment
<V> getSegment
(int hash) private int
getSegmentIndex
(int hash) long
Get the currently used memory.boolean
isEmpty()
Check whether the cache is empty.keys
(boolean cold, boolean nonResident) Get the list of keys.keySet()
Get the set of keys for resident entries.peek
(long key) Get the value for the given key if the entry is cached.Add an entry to the cache using the average memory size.Add an entry to the cache.void
Add all elements of the map to this cache.remove
(long key) Remove an entry.private CacheLongKeyLIRS.Segment
<V> resizeIfNeeded
(CacheLongKeyLIRS.Segment<V> s, int segmentIndex) void
setMaxMemory
(long maxMemory) Set the maximum memory this cache should use.int
size()
Get the number of resident entries.int
sizeHot()
Get the number of hot entries in the cache.int
Get the length of the internal map array.int
Get the number of non-resident entries in the cache.protected int
Get the size of the given value.void
Loop through segments, trimming the non resident queue.values()
Get the values for all resident entries.
-
Field Details
-
maxMemory
private long maxMemoryThe maximum memory this cache should use. -
segments
-
segmentCount
private final int segmentCount -
segmentShift
private final int segmentShift -
segmentMask
private final int segmentMask -
stackMoveDistance
private final int stackMoveDistance -
nonResidentQueueSize
private final int nonResidentQueueSize -
nonResidentQueueSizeHigh
private final int nonResidentQueueSizeHigh
-
-
Constructor Details
-
CacheLongKeyLIRS
Create a new cache with the given memory size.- Parameters:
config
- the configuration
-
-
Method Details
-
clear
public void clear()Remove all entries. -
getMaxItemSize
public long getMaxItemSize()Determines max size of the data item size to fit into cache- Returns:
- data items size limit
-
find
-
containsKey
public boolean containsKey(long 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
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
Add an entry to the cache using the average memory size.- Parameters:
key
- the key (may not be null)value
- the value (may not be null)- Returns:
- the old value, or null if there was no resident entry
-
put
Add an entry to the cache. 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
-
resizeIfNeeded
-
sizeOf
Get the size of the given value. The default implementation returns 1.- Parameters:
value
- the value- Returns:
- the size
-
remove
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 if there was no resident entry
-
getMemory
public int getMemory(long 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
-
get
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.- Parameters:
key
- the key (may not be null)- Returns:
- the value, or null if there is no resident entry
-
getSegment
-
getSegmentIndex
private int getSegmentIndex(int hash) -
getHash
static int getHash(long key) Get the hash code for the given key. The hash code is further enhanced to spread the values more evenly.- Parameters:
key
- the key- Returns:
- the hash code
-
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) in bytes
-
getMaxMemory
public long getMaxMemory()Get the maximum memory to use.- Returns:
- the maximum memory
-
entrySet
Get the entry set for all resident entries.- Returns:
- the entry set
-
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
-
getHits
public long getHits()Get the number of cache hits.- Returns:
- the cache hits
-
getMisses
public long getMisses()Get the number of cache misses.- Returns:
- the cache misses
-
size
public int size()Get the number of resident entries.- Returns:
- the number of entries
-
keys
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 returnednonResident
- true for non-resident entries- Returns:
- the key list
-
values
Get the values for all resident entries.- Returns:
- the entry set
-
isEmpty
public boolean isEmpty()Check whether the cache is empty.- Returns:
- true if it is empty
-
containsValue
Check whether the given value is stored.- Parameters:
value
- the value- Returns:
- true if it is stored
-
getMap
Convert this cache to a map.- Returns:
- the map
-
putAll
Add all elements of the map to this cache.- Parameters:
m
- the map
-
trimNonResidentQueue
public void trimNonResidentQueue()Loop through segments, trimming the non resident queue.
-