Interface WeakCARCache<K,​V>

  • All Known Implementing Classes:
    WeakCARCacheImpl

    public interface WeakCARCache<K,​V>
    A cache that uses the CAR algorithm to remove entries.

    As a quick review, the CAR algorithm maintains four lists:

    1. t1 - A clock of recently used keys with values
    2. t2 - A clock of frequently used keys with values
    3. b1 - A LRU of keys removed from t1 with no values
    4. b2 - A LRU of keys removed from t2 with no values
    The sum of entries in t1 and t2 will never be higher than maxSize (c). The sum of entries in all four lists will never be higher than 2c. There is an adaptive parameter p which is the target size of the t1 list which gets modified when a key is found on either the b1 or b2 list. This adaptive parameter essentially allows the algorithm to adapt to the pattern of keys, whether there be more frequently used keys or there be a pattern of keys used quickly but not again.
    Author:
    jwells
    • Method Summary

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method Description
      void clear()
      Clears the current cache, making the current size zero
      void clearStaleReferences()
      Causes stale references to be cleared from the data structures.
      V compute​(K key)
      The method used to get or add values to this cache
      String dumpAllLists()
      Returns a string that will contain all the elements of the four lists
      int getB1Size()
      Returns the number of items in the B1 LRU
      int getB2Size()
      Returns the number of items in the B2 LRU
      Computable<K,​V> getComputable()
      The computable associated with this cache
      double getHitRate()
      Returns the hit rate from the last time clear was called
      int getKeySize()
      Returns the current number of keys in the cache.
      int getMaxSize()
      Gets the current maximum size of the cache (the maximum number of values that will be kept by the cache).
      int getP()
      Returns the value of p from the CAR algorithm, which is the target size of the t1 clock
      int getT1Size()
      Returns the number of items in the T1 clock
      int getT2Size()
      Returns the number of items in the T2 clock
      int getValueSize()
      Returns the current number of values in the cache.
      void releaseMatching​(CacheKeyFilter<K> filter)
      Releases all key/value pairs that match the filter
      boolean remove​(K key)
      Used to remove a single key and value from the cache (if the value is available)
    • Method Detail

      • compute

        V compute​(K key)
        The method used to get or add values to this cache
        Parameters:
        key - The key to add to the cache. If the value is not found, then the computable will be called to get the value. May not be null
        Returns:
        The calculated return value. May not be null
      • getKeySize

        int getKeySize()
        Returns the current number of keys in the cache. Note that the number of keys can be up to 2x the maximum size of the cache
        Returns:
        The current number of key entries in the cache
      • getValueSize

        int getValueSize()
        Returns the current number of values in the cache. Note that the number of values can be up the maximum size of the cache
        Returns:
        The current number of value entries in the cache
      • getT1Size

        int getT1Size()
        Returns the number of items in the T1 clock
        Returns:
        The current number of items in the T1 clock
      • getT2Size

        int getT2Size()
        Returns the number of items in the T2 clock
        Returns:
        The current number of items in the T2 clock
      • getB1Size

        int getB1Size()
        Returns the number of items in the B1 LRU
        Returns:
        The current number of items in the B1 LRU
      • getB2Size

        int getB2Size()
        Returns the number of items in the B2 LRU
        Returns:
        The current number of items in the B2 LRU
      • clear

        void clear()
        Clears the current cache, making the current size zero
      • getMaxSize

        int getMaxSize()
        Gets the current maximum size of the cache (the maximum number of values that will be kept by the cache). Note that the number of keys kept will be 2x, where x is the maximum size of the cache (see CAR algorithm which keeps a key history)
        Returns:
        The maximum size of the cache
      • getComputable

        Computable<K,​V> getComputable()
        The computable associated with this cache
        Returns:
        The computable associated with this cache
      • remove

        boolean remove​(K key)
        Used to remove a single key and value from the cache (if the value is available)
        Parameters:
        key - The key to remove. May not be null
        Returns:
        true if a key was found and removed
      • releaseMatching

        void releaseMatching​(CacheKeyFilter<K> filter)
        Releases all key/value pairs that match the filter
        Parameters:
        filter - A non-null filter that can be used to delete every key/value pair that matches the filter
      • clearStaleReferences

        void clearStaleReferences()
        Causes stale references to be cleared from the data structures. Since this is a weak cache the references can go away at any time, which happens whenever any operation has been performed. However, it may be the case that no operation will be performed for a while and so this method is provided to have a no-op operation to call in order to clear out any stale references
      • getP

        int getP()
        Returns the value of p from the CAR algorithm, which is the target size of the t1 clock
        Returns:
        The current value of P
      • dumpAllLists

        String dumpAllLists()
        Returns a string that will contain all the elements of the four lists
        Returns:
        A String containing the values of T1, T2, B1 and B2
      • getHitRate

        double getHitRate()
        Returns the hit rate from the last time clear was called
        Returns:
        The Hit rate from the last time clear was called or 0 if there is no data