Class Cache<K,​V>

java.lang.Object
org.elasticsearch.common.cache.Cache<K,​V>
Type Parameters:
K - The type of the keys
V - The type of the values

public class Cache<K,​V>
extends java.lang.Object
A simple concurrent cache.

Cache is a simple concurrent cache that supports time-based and weight-based evictions, with notifications for all evictions. The design goals for this cache were simplicity and read performance. This means that we are willing to accept reduced write performance in exchange for easy-to-understand code. Cache statistics for hits, misses and evictions are exposed.

The design of the cache is relatively simple. The cache is segmented into 256 segments which are backed by HashMaps. Each segment is protected by a re-entrant read/write lock. The read/write locks permit multiple concurrent readers without contention, and the segments gives us write throughput without impacting readers (so readers are blocked only if they are reading a segment that a writer is writing to).

The LRU functionality is backed by a single doubly-linked list chaining the entries in order of insertion. This LRU list is protected by a lock that serializes all writes to it. There are opportunities for improvements here if write throughput is a concern.

  1. LRU list mutations could be inserted into a blocking queue that a single thread is reading from and applying to the LRU list.
  2. Promotions could be deferred for entries that were "recently" promoted.
  3. Locks on the list could be taken per node being modified instead of globally.

Evictions only occur after a mutation to the cache (meaning an entry promotion, a cache insertion, or a manual invalidation) or an explicit call to refresh().

  • Nested Class Summary

    Nested Classes
    Modifier and Type Class Description
    static class  Cache.CacheStats  
  • Field Summary

    Fields
    Modifier and Type Field Description
    static int NUMBER_OF_SEGMENTS  
  • Method Summary

    Modifier and Type Method Description
    V computeIfAbsent​(K key, CacheLoader<K,​V> loader)
    If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null.
    int count()
    The number of entries in the cache.
    void forEach​(java.util.function.BiConsumer<K,​V> consumer)
    Performs an action for each cache entry in the cache.
    V get​(K key)
    Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
    void invalidate​(K key)
    Invalidate the association for the specified key.
    void invalidate​(K key, V value)
    Invalidate the entry for the specified key and value.
    void invalidateAll()
    Invalidate all cache entries.
    java.lang.Iterable<K> keys()
    An LRU sequencing of the keys in the cache that supports removal.
    protected long now()
    The relative time used to track time-based evictions.
    void put​(K key, V value)
    Associates the specified value with the specified key in this map.
    void refresh()
    Force any outstanding size-based and time-based evictions to occur
    Cache.CacheStats stats()
    The cache statistics tracking hits, misses and evictions.
    java.lang.Iterable<V> values()
    An LRU sequencing of the values in the cache.
    long weight()
    The weight of the entries in the cache.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

  • Method Details

    • now

      protected long now()
      The relative time used to track time-based evictions.
      Returns:
      the current relative time
    • get

      public V get​(K key)
      Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
      Parameters:
      key - the key whose associated value is to be returned
      Returns:
      the value to which the specified key is mapped, or null if this map contains no mapping for the key
    • computeIfAbsent

      public V computeIfAbsent​(K key, CacheLoader<K,​V> loader) throws java.util.concurrent.ExecutionException
      If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null. The load method for a given key will be invoked at most once. Use of different CacheLoader implementations on the same key concurrently may result in only the first loader function being called and the second will be returned the result provided by the first including any exceptions thrown during the execution of the first.
      Parameters:
      key - the key whose associated value is to be returned or computed for if non-existent
      loader - the function to compute a value given a key
      Returns:
      the current (existing or computed) non-null value associated with the specified key
      Throws:
      java.util.concurrent.ExecutionException - thrown if loader throws an exception or returns a null value
    • put

      public void put​(K key, V value)
      Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.
      Parameters:
      key - key with which the specified value is to be associated
      value - value to be associated with the specified key
    • invalidate

      public void invalidate​(K key)
      Invalidate the association for the specified key. A removal notification will be issued for invalidated entries with RemovalNotification.RemovalReason INVALIDATED.
      Parameters:
      key - the key whose mapping is to be invalidated from the cache
    • invalidate

      public void invalidate​(K key, V value)
      Invalidate the entry for the specified key and value. If the value provided is not equal to the value in the cache, no removal will occur. A removal notification will be issued for invalidated entries with RemovalNotification.RemovalReason INVALIDATED.
      Parameters:
      key - the key whose mapping is to be invalidated from the cache
      value - the expected value that should be associated with the key
    • invalidateAll

      public void invalidateAll()
      Invalidate all cache entries. A removal notification will be issued for invalidated entries with RemovalNotification.RemovalReason INVALIDATED.
    • refresh

      public void refresh()
      Force any outstanding size-based and time-based evictions to occur
    • count

      public int count()
      The number of entries in the cache.
      Returns:
      the number of entries in the cache
    • weight

      public long weight()
      The weight of the entries in the cache.
      Returns:
      the weight of the entries in the cache
    • keys

      public java.lang.Iterable<K> keys()
      An LRU sequencing of the keys in the cache that supports removal. This sequence is not protected from mutations to the cache (except for Iterator.remove(). The result of iteration under any other mutation is undefined.
      Returns:
      an LRU-ordered Iterable over the keys in the cache
    • values

      public java.lang.Iterable<V> values()
      An LRU sequencing of the values in the cache. This sequence is not protected from mutations to the cache (except for Iterator.remove(). The result of iteration under any other mutation is undefined.
      Returns:
      an LRU-ordered Iterable over the values in the cache
    • forEach

      public void forEach​(java.util.function.BiConsumer<K,​V> consumer)
      Performs an action for each cache entry in the cache. While iterating over the cache entries this method is protected from mutations that occurs within the same cache segment by acquiring the segment's read lock during all the iteration. As such, the specified consumer should not try to modify the cache. Modifications that occur in already traveled segments won't been seen by the consumer but modification that occur in non yet traveled segments should be.
      Parameters:
      consumer - the Consumer
    • stats

      public Cache.CacheStats stats()
      The cache statistics tracking hits, misses and evictions. These are taken on a best-effort basis meaning that they could be out-of-date mid-flight.
      Returns:
      the current cache statistics