Class 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  
    • 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.
      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
    • Method Detail

      • 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
      • 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