Package org.apache.jackrabbit.oak.cache

Class CacheLIRS<K,​V>

  • Type Parameters:
    K - the key type
    V - the value type
    All Implemented Interfaces:
    Function<K,​V>, Cache<K,​V>, LoadingCache<K,​V>
    @Internal(since="1.1.1")
public class CacheLIRS<K,​V>
extends java.lang.Object
implements 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 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 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

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      V apply​(K key)
      Discouraged.
      java.util.concurrent.ConcurrentMap<K,​V> asMap()
      Returns a view of the entries stored in this cache as a thread-safe map.
      void cleanUp()
      Performs any pending maintenance operations needed by the cache.
      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)
      Returns the value associated with key in this cache, obtaining that value from valueLoader if necessary.
      ImmutableMap<K,​V> getAll​(java.lang.Iterable<? extends K> keys)
      Returns a map of the values associated with keys, creating or retrieving those values if necessary.
      ImmutableMap<K,​V> getAllPresent​(java.lang.Iterable<?> keys)
      Returns a map of the values associated with keys in this cache.
      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)
      Discards any cached values for keys 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)
      Copies all of the mappings from the specified map to the cache.
      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.
      CacheStats stats()
      Returns a current snapshot of this cache's cumulative statistics.

      • Methods inherited from class java.lang.Object

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

    • 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 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 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
        Description copied from interface: Cache
        Returns the value associated with key in this cache, obtaining that value from valueLoader if necessary. No observable state associated with this cache is modified until loading completes. This method provides a simple substitute for the conventional "if cached, return; otherwise create, cache and return" pattern.

        Warning: as with CacheLoader.load(K), valueLoader must not return null; it may either return a non-null value or throw an exception.

        Specified by:
        get in interface Cache<K,​V>
        Throws:
        java.util.concurrent.ExecutionException - if a checked exception was thrown while loading the value

      • 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 LoadingCache<K,​V>
        Parameters:
        key - the key
        Returns:
        the value
        Throws:
        UncheckedExecutionException

      • get

        public V get​(K key)
      throws java.util.concurrent.ExecutionException
        Get the value, loading it if needed.
        Specified by:
        get in interface 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 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 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 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)
        Description copied from interface: Cache
        Discards any cached values for keys keys.
        Specified by:
        invalidateAll in interface 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 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 CacheStats stats()
        Description copied from interface: Cache
        Returns a current snapshot of this cache's cumulative statistics. All stats are initialized to zero, and are monotonically increasing over the lifetime of the cache.
        Specified by:
        stats in interface Cache<K,​V>

      • newBuilder

        public static <K,​V> CacheLIRS.Builder<K,​V> newBuilder()
        Create a builder.
        Returns:
        the builder

      • getAllPresent

        public ImmutableMap<K,​V> getAllPresent​(java.lang.Iterable<?> keys)
        Description copied from interface: Cache
        Returns a map of the values associated with keys in this cache. The returned map will only contain entries which are already present in the cache.
        Specified by:
        getAllPresent in interface Cache<K,​V>

      • asMap

        public java.util.concurrent.ConcurrentMap<K,​V> asMap()
        Description copied from interface: LoadingCache
        Returns a view of the entries stored in this cache as a thread-safe map. Modifications made to the map directly affect the cache.

        Note that although the view is modifiable, no method on the returned map will ever cause entries to be automatically loaded.

        Specified by:
        asMap in interface Cache<K,​V>
        Specified by:
        asMap in interface LoadingCache<K,​V>

      • cleanUp

        public void cleanUp()
        Description copied from interface: Cache
        Performs any pending maintenance operations needed by the cache. Exactly which activities are performed -- if any -- is implementation-dependent.
        Specified by:
        cleanUp in interface Cache<K,​V>

      • putAll

        public void putAll​(java.util.Map<? extends K,​? extends V> m)
        Description copied from interface: Cache
        Copies all of the mappings from the specified map to the cache. The effect of this call is equivalent to that of calling put(k, v) on this map once for each mapping from key k to value v in the specified map. The behavior of this operation is undefined if the specified map is modified while the operation is in progress.
        Specified by:
        putAll in interface Cache<K,​V>

      • isEmpty

        public boolean isEmpty()