Class BoundedLocalCache<K,V>

Type Parameters:
K - the type of keys maintained by this cache
V - the type of mapped values
All Implemented Interfaces:
LocalCache<K,V>, ConcurrentMap<K,V>, Map<K,V>
Direct Known Subclasses:
LocalCacheFactory.SI, LocalCacheFactory.SS, LocalCacheFactory.WI, LocalCacheFactory.WS

@ThreadSafe abstract class BoundedLocalCache<K,V> extends BLCHeader.DrainStatusRef<K,V> implements LocalCache<K,V>
An in-memory cache implementation that supports full concurrency of retrievals, a high expected concurrency for updates, and multiple ways to bound the cache.

This class is abstract and code generated subclasses provide the complete implementation for a particular configuration. This is to ensure that only the fields and execution paths necessary for a given configuration are used.

  • Field Details

    • logger

      static final Logger logger
    • NCPU

      static final int NCPU
      The number of CPUs
    • WRITE_BUFFER_MIN

      static final int WRITE_BUFFER_MIN
      The initial capacity of the write buffer.
      See Also:
    • WRITE_BUFFER_MAX

      static final int WRITE_BUFFER_MAX
      The maximum capacity of the write buffer.
    • WRITE_BUFFER_RETRIES

      static final int WRITE_BUFFER_RETRIES
      The number of attempts to insert into the write buffer before yielding.
      See Also:
    • MAXIMUM_CAPACITY

      static final long MAXIMUM_CAPACITY
      The maximum weighted capacity of the map.
      See Also:
    • PERCENT_MAIN

      static final double PERCENT_MAIN
      The percent of the maximum weighted capacity dedicated to the main space.
      See Also:
    • PERCENT_MAIN_PROTECTED

      static final double PERCENT_MAIN_PROTECTED
      The percent of the maximum weighted capacity dedicated to the main's protected space.
      See Also:
    • EXPIRE_WRITE_TOLERANCE

      static final long EXPIRE_WRITE_TOLERANCE
      The maximum time window between entry updates before the expiration must be reordered.
    • data

    • drainBuffersTask

      final BoundedLocalCache<K,V>.PerformCleanupTask drainBuffersTask
    • accessPolicy

      final Consumer<Node<K,V>> accessPolicy
    • cacheLoader

      final CacheLoader<K,V> cacheLoader
    • readBuffer

      final Buffer<Node<K,V>> readBuffer
    • writer

      final CacheWriter<K,V> writer
    • nodeFactory

      final NodeFactory nodeFactory
    • weigher

      final Weigher<K,V> weigher
    • evictionLock

      final Lock evictionLock
    • executor

      final Executor executor
    • isAsync

      final boolean isAsync
    • keySet

      transient Set<K> keySet
    • values

      transient Collection<V> values
    • entrySet

      transient Set<Map.Entry<K,V>> entrySet
  • Constructor Details

    • BoundedLocalCache

      protected BoundedLocalCache(Caffeine<K,V> builder, @Nullable CacheLoader<K,V> cacheLoader, boolean isAsync)
      Creates an instance based on the builder's configuration.
  • Method Details

    • ceilingPowerOfTwo

      static int ceilingPowerOfTwo(int x)
    • isComputingAsync

      final boolean isComputingAsync(Node<?,?> node)
      Returns if the node's value is currently being computed, asynchronously.
    • accessOrderEdenDeque

      protected AccessOrderDeque<Node<K,V>> accessOrderEdenDeque()
    • accessOrderProbationDeque

      protected AccessOrderDeque<Node<K,V>> accessOrderProbationDeque()
    • accessOrderProtectedDeque

      protected AccessOrderDeque<Node<K,V>> accessOrderProtectedDeque()
    • writeOrderDeque

      protected WriteOrderDeque<Node<K,V>> writeOrderDeque()
    • buffersWrites

      protected boolean buffersWrites()
      If the page replacement policy buffers writes.
    • writeBuffer

      protected MpscGrowableArrayQueue<Runnable> writeBuffer()
    • executor

      public final Executor executor()
      Description copied from interface: LocalCache
      Returns the Executor used by this cache.
      Specified by:
      executor in interface LocalCache<K,V>
    • hasWriter

      protected boolean hasWriter()
      Returns whether this cache notifies a writer when an entry is modified.
    • isRecordingStats

      public boolean isRecordingStats()
      Description copied from interface: LocalCache
      Returns whether this cache has statistics enabled.
      Specified by:
      isRecordingStats in interface LocalCache<K,V>
    • statsCounter

      public StatsCounter statsCounter()
      Description copied from interface: LocalCache
      Returns the StatsCounter used by this cache.
      Specified by:
      statsCounter in interface LocalCache<K,V>
    • statsTicker

      public Ticker statsTicker()
      Description copied from interface: LocalCache
      Returns the Ticker used by this cache for statistics.
      Specified by:
      statsTicker in interface LocalCache<K,V>
    • removalListener

      public RemovalListener<K,V> removalListener()
      Description copied from interface: LocalCache
      Returns the RemovalListener used by this cache or null if not used.
      Specified by:
      removalListener in interface LocalCache<K,V>
    • hasRemovalListener

      public boolean hasRemovalListener()
      Description copied from interface: LocalCache
      Returns whether this cache notifies when an entry is removed.
      Specified by:
      hasRemovalListener in interface LocalCache<K,V>
    • notifyRemoval

      public void notifyRemoval(@Nullable K key, @Nullable V value, RemovalCause cause)
      Description copied from interface: LocalCache
      Asynchronously sends a removal notification to the listener.
      Specified by:
      notifyRemoval in interface LocalCache<K,V>
    • collectKeys

      protected boolean collectKeys()
      Returns if the keys are weak reference garbage collected.
    • collectValues

      protected boolean collectValues()
      Returns if the values are weak or soft reference garbage collected.
    • keyReferenceQueue

      @Nullable protected ReferenceQueue<K> keyReferenceQueue()
    • valueReferenceQueue

      @Nullable protected ReferenceQueue<V> valueReferenceQueue()
    • expiresAfterAccess

      protected boolean expiresAfterAccess()
      Returns if the cache expires entries after an access time threshold.
    • expiresAfterAccessNanos

      protected long expiresAfterAccessNanos()
      How long after the last access to an entry the map will retain that entry.
    • setExpiresAfterAccessNanos

      protected void setExpiresAfterAccessNanos(long expireAfterAccessNanos)
    • expiresAfterWrite

      protected boolean expiresAfterWrite()
      Returns if the cache expires entries after an write time threshold.
    • expiresAfterWriteNanos

      protected long expiresAfterWriteNanos()
      How long after the last write to an entry the map will retain that entry.
    • setExpiresAfterWriteNanos

      protected void setExpiresAfterWriteNanos(long expireAfterWriteNanos)
    • refreshAfterWrite

      protected boolean refreshAfterWrite()
      Returns if the cache refreshes entries after an write time threshold.
    • refreshAfterWriteNanos

      protected long refreshAfterWriteNanos()
      How long after the last write an entry becomes a candidate for refresh.
    • setRefreshAfterWriteNanos

      protected void setRefreshAfterWriteNanos(long refreshAfterWriteNanos)
    • hasWriteTime

      public boolean hasWriteTime()
      Description copied from interface: LocalCache
      Returns whether the cache captures the write time of the entry.
      Specified by:
      hasWriteTime in interface LocalCache<K,V>
    • expirationTicker

      public Ticker expirationTicker()
      Description copied from interface: LocalCache
      Returns the Ticker used by this cache for expiration.
      Specified by:
      expirationTicker in interface LocalCache<K,V>
    • evicts

      protected boolean evicts()
      Returns if the cache evicts entries due to a maximum size or weight threshold.
    • isWeighted

      protected boolean isWeighted()
      Returns if entries may be assigned different weights.
    • frequencySketch

      protected FrequencySketch<K> frequencySketch()
    • fastpath

      protected boolean fastpath()
      Returns if an access to an entry can skip notifying the eviction policy.
    • maximum

      protected long maximum()
      Returns the maximum weighted size.
    • edenMaximum

      protected long edenMaximum()
      Returns the maximum weighted size of the eden space.
    • mainProtectedMaximum

      protected long mainProtectedMaximum()
      Returns the maximum weighted size of the main's protected space.
    • lazySetMaximum

      protected void lazySetMaximum(long maximum)
    • lazySetEdenMaximum

      protected void lazySetEdenMaximum(long maximum)
    • lazySetMainProtectedMaximum

      protected void lazySetMainProtectedMaximum(long maximum)
    • setMaximum

      void setMaximum(long maximum)
      Sets the maximum weighted size of the cache. The caller may need to perform a maintenance cycle to eagerly evicts entries until the cache shrinks to the appropriate size.
    • adjustedWeightedSize

      long adjustedWeightedSize()
      Returns the combined weight of the values in the cache.
    • weightedSize

      protected long weightedSize()
      Returns the uncorrected combined weight of the values in the cache.
    • edenWeightedSize

      protected long edenWeightedSize()
      Returns the uncorrected combined weight of the values in the eden space.
    • mainProtectedWeightedSize

      protected long mainProtectedWeightedSize()
      Returns the uncorrected combined weight of the values in the main's protected space.
    • lazySetWeightedSize

      protected void lazySetWeightedSize(long weightedSize)
    • lazySetEdenWeightedSize

      protected void lazySetEdenWeightedSize(long weightedSize)
    • lazySetMainProtectedWeightedSize

      protected void lazySetMainProtectedWeightedSize(long weightedSize)
    • evictEntries

      void evictEntries()
      Evicts entries if the cache exceeds the maximum.
    • evictFromEden

      int evictFromEden()
      Evicts entries from the eden space into the main space while the eden size exceeds a maximum.
      Returns:
      the number of candidate entries evicted from the eden space
    • evictFromMain

      void evictFromMain(int candidates)
      Evicts entries from the main space if the cache exceeds the maximum capacity. The main space determines whether admitting an entry (coming from the eden space) is preferable to retaining the eviction policy's victim. This is decision is made using a frequency filter so that the least frequently used entry is removed. The eden space candidates were previously placed in the MRU position and the eviction policy's victim is at the LRU position. The two ends of the queue are evaluated while an eviction is required. The number of remaining candidates is provided and decremented on eviction, so that when there are no more candidates the victim is evicted.
      Parameters:
      candidates - the number of candidate entries evicted from the eden space
    • admit

      boolean admit(K candidateKey, K victimKey)
      Determines if the candidate should be accepted into the main space, as determined by its frequency relative to the victim. A small amount of randomness is used to protect against hash collision attacks, where the victim's frequency is artificially raised so that no new entries are admitted.
      Parameters:
      candidateKey - the key for the entry being proposed for long term retention
      victimKey - the key for the entry chosen by the eviction policy for replacement
      Returns:
      if the candidate should be admitted and the victim ejected
    • expireEntries

      void expireEntries()
      Expires entries that have expired in the access and write queues.
    • expireAfterAccessEntries

      void expireAfterAccessEntries(long now)
      Expires entries in the access-order queue.
    • expireAfterAccessEntries

      void expireAfterAccessEntries(AccessOrderDeque<Node<K,V>> accessOrderDeque, long expirationTime, long now)
      Expires entries in an access-order queue.
    • expireAfterWriteEntries

      void expireAfterWriteEntries(long now)
      Expires entries on the write-order queue.
    • hasExpired

      boolean hasExpired(Node<K,V> node, long now)
      Returns if the entry has expired.
    • evictEntry

      void evictEntry(Node<K,V> node, RemovalCause cause, long now)
      Attempts to evict the entry based on the given removal cause. A removal due to expiration or size may be ignored if the entry was updated and is no longer eligible for eviction.
      Parameters:
      node - the entry to evict
      cause - the reason to evict
      now - the current time, used only if expiring
    • afterRead

      void afterRead(Node<K,V> node, long now, boolean recordHit)
      Performs the post-processing work required after a read.
      Parameters:
      node - the entry in the page replacement policy
      now - the current expiration time, in nanoseconds
      recordHit - if the hit count should be incremented
    • skipReadBuffer

      boolean skipReadBuffer()
      Returns if the cache should bypass the read buffer.
    • refreshIfNeeded

      void refreshIfNeeded(Node<K,V> node, long now)
      Asynchronously refreshes the entry if eligible.
      Parameters:
      node - the entry in the cache to refresh
      now - the current time, in nanoseconds
    • afterWrite

      void afterWrite(@Nullable Node<K,V> node, Runnable task, long now)
      Performs the post-processing work required after a write.
      Parameters:
      node - the node that was written to
      task - the pending operation to be applied
      now - the current expiration time, in nanoseconds
    • scheduleAfterWrite

      void scheduleAfterWrite()
      Conditionally schedules the asynchronous maintenance task after a write operation. If the task status was IDLE or REQUIRED then the maintenance task is scheduled immediately. If it is already processing then it is set to transition to REQUIRED upon completion so that a new execution is triggered by the next operation.
    • scheduleDrainBuffers

      void scheduleDrainBuffers()
      Attempts to schedule an asynchronous task to apply the pending operations to the page replacement policy. If the executor rejects the task then it is run directly.
    • cleanUp

      public void cleanUp()
      Description copied from interface: LocalCache
      Specified by:
      cleanUp in interface LocalCache<K,V>
    • performCleanUp

      void performCleanUp(@Nullable Runnable task)
      Performs the maintenance work, blocking until the lock is acquired. Any exception thrown, such as by CacheWriter#delete(), is propagated to the caller.
      Parameters:
      task - an additional pending task to run, or null if not present
    • maintenance

      void maintenance(@Nullable Runnable task)
      Performs the pending maintenance work and sets the state flags during processing to avoid excess scheduling attempts. The read buffer, write buffer, and reference queues are drained, followed by expiration, and size-based eviction.
      Parameters:
      task - an additional pending task to run, or null if not present
    • drainKeyReferences

      void drainKeyReferences()
      Drains the weak key references queue.
    • drainValueReferences

      void drainValueReferences()
      Drains the weak / soft value references queue.
    • drainReadBuffer

      void drainReadBuffer()
      Drains the read buffer.
    • onAccess

      void onAccess(Node<K,V> node)
      Updates the node's location in the page replacement policy.
    • reorderProbation

      void reorderProbation(Node<K,V> node)
      Promote the node from probation to protected on an access.
    • reorder

      static <K, V> void reorder(LinkedDeque<Node<K,V>> deque, Node<K,V> node)
      Updates the node's location in the policy's deque.
    • drainWriteBuffer

      void drainWriteBuffer()
      Drains the write buffer.
    • makeDead

      void makeDead(Node<K,V> node)
      Atomically transitions the node to the dead state and decrements the weightedSize.
      Parameters:
      node - the entry in the page replacement policy
    • isEmpty

      public boolean isEmpty()
      Specified by:
      isEmpty in interface Map<K,V>
      Overrides:
      isEmpty in class AbstractMap<K,V>
    • size

      public int size()
      Specified by:
      size in interface Map<K,V>
      Overrides:
      size in class AbstractMap<K,V>
    • estimatedSize

      public long estimatedSize()
      Description copied from interface: LocalCache
      Specified by:
      estimatedSize in interface LocalCache<K,V>
    • clear

      public void clear()
      Specified by:
      clear in interface Map<K,V>
      Overrides:
      clear in class AbstractMap<K,V>
    • removeNodes

      void removeNodes(LinkedDeque<Node<K,V>> deque, long now)
    • removeNode

      void removeNode(Node<K,V> node, long now)
    • containsKey

      public boolean containsKey(Object key)
      Specified by:
      containsKey in interface Map<K,V>
      Overrides:
      containsKey in class AbstractMap<K,V>
    • containsValue

      public boolean containsValue(Object value)
      Specified by:
      containsValue in interface Map<K,V>
      Overrides:
      containsValue in class AbstractMap<K,V>
    • get

      public V get(Object key)
      Specified by:
      get in interface Map<K,V>
      Overrides:
      get in class AbstractMap<K,V>
    • getIfPresent

      public V getIfPresent(Object key, boolean recordStats)
      Description copied from interface: LocalCache
      See Cache.getIfPresent(Object). This method differs by accepting a parameter of whether to record the hit and miss statistics based on the success of this operation.
      Specified by:
      getIfPresent in interface LocalCache<K,V>
    • getIfPresentQuietly

      public V getIfPresentQuietly(Object key, long[] writeTime)
      Description copied from interface: LocalCache
      See Cache.getIfPresent(Object). This method differs by not recording the access with the statistics nor the eviction policy, and populates the write time if known.
      Specified by:
      getIfPresentQuietly in interface LocalCache<K,V>
    • getAllPresent

      public Map<K,V> getAllPresent(Iterable<?> keys)
      Description copied from interface: LocalCache
      Specified by:
      getAllPresent in interface LocalCache<K,V>
    • put

      public V put(K key, V value)
      Specified by:
      put in interface Map<K,V>
      Overrides:
      put in class AbstractMap<K,V>
    • put

      public V put(K key, V value, boolean notifyWriter)
      Description copied from interface: LocalCache
      See Cache.put(Object, Object). This method differs by allowing the operation to not notify the writer when an entry was inserted or updated.
      Specified by:
      put in interface LocalCache<K,V>
    • putIfAbsent

      public V putIfAbsent(K key, V value)
      Specified by:
      putIfAbsent in interface ConcurrentMap<K,V>
      Specified by:
      putIfAbsent in interface Map<K,V>
    • putFast

      V putFast(K key, V value, int newWeight, boolean notifyWriter, boolean onlyIfAbsent)
      Adds a node to the policy and the data store. If an existing node is found, then its value is updated if allowed. This implementation is optimized for writing values with a non-zero weight. A zero weight is incompatible due to the potential for the update to race with eviction, where the entry should no longer be eligible if the update was successful. This implementation is ~50% faster than putSlow(K, V, int, boolean, boolean) due to not incurring the penalty of a compute and lambda in the common case.
      Parameters:
      key - key with which the specified value is to be associated
      value - value to be associated with the specified key
      notifyWriter - if the writer should be notified for an inserted or updated entry
      onlyIfAbsent - a write is performed only if the key is not already associated with a value
      Returns:
      the prior value in or null if no mapping was found
    • putSlow

      V putSlow(K key, V value, int newWeight, boolean notifyWriter, boolean onlyIfAbsent)
      Adds a node to the policy and the data store. If an existing node is found, then its value is updated if allowed. This implementation is strict by using a compute to block other writers to that entry. This guards against an eviction trying to discard an entry concurrently (and successfully) updated to have a zero weight. The penalty is 50% of the throughput when compared to putFast(K, V, int, boolean, boolean).
      Parameters:
      key - key with which the specified value is to be associated
      value - value to be associated with the specified key
      notifyWriter - if the writer should be notified for an inserted or updated entry
      onlyIfAbsent - a write is performed only if the key is not already associated with a value
      Returns:
      the prior value or null if no mapping was found
    • remove

      public V remove(Object key)
      Specified by:
      remove in interface Map<K,V>
      Overrides:
      remove in class AbstractMap<K,V>
    • removeNoWriter

      V removeNoWriter(Object key)
      Removes the mapping for a key without notifying the writer.
      Parameters:
      key - key whose mapping is to be removed
      Returns:
      the removed value or null if no mapping was found
    • removeWithWriter

      V removeWithWriter(Object key)
      Removes the mapping for a key after notifying the writer.
      Parameters:
      key - key whose mapping is to be removed
      Returns:
      the removed value or null if no mapping was found
    • remove

      public boolean remove(Object key, Object value)
      Specified by:
      remove in interface ConcurrentMap<K,V>
      Specified by:
      remove in interface Map<K,V>
    • replace

      public V replace(K key, V value)
      Specified by:
      replace in interface ConcurrentMap<K,V>
      Specified by:
      replace in interface Map<K,V>
    • replace

      public boolean replace(K key, V oldValue, V newValue)
      Specified by:
      replace in interface ConcurrentMap<K,V>
      Specified by:
      replace in interface Map<K,V>
    • replaceAll

      public void replaceAll(BiFunction<? super K,? super V,? extends V> function)
      Specified by:
      replaceAll in interface ConcurrentMap<K,V>
      Specified by:
      replaceAll in interface Map<K,V>
    • computeIfAbsent

      public V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction, boolean recordStats, boolean recordLoad)
      Description copied from interface: LocalCache
      See ConcurrentMap.computeIfAbsent(K, java.util.function.Function<? super K, ? extends V>). This method differs by accepting parameters indicating how to record statistics.
      Specified by:
      computeIfAbsent in interface LocalCache<K,V>
    • doComputeIfAbsent

      V doComputeIfAbsent(K key, Object keyRef, Function<? super K,? extends V> mappingFunction, long now)
      Returns the current value from a computeIfAbsent invocation.
    • computeIfPresent

      public V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)
      Specified by:
      computeIfPresent in interface ConcurrentMap<K,V>
      Specified by:
      computeIfPresent in interface Map<K,V>
    • compute

      public V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction, boolean recordMiss, boolean recordLoad)
      Description copied from interface: LocalCache
      See ConcurrentMap.compute(K, java.util.function.BiFunction<? super K, ? super V, ? extends V>). This method differs by accepting parameters indicating whether to record miss and load statistics based on the success of this operation.
      Specified by:
      compute in interface LocalCache<K,V>
    • merge

      public V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)
      Specified by:
      merge in interface ConcurrentMap<K,V>
      Specified by:
      merge in interface Map<K,V>
    • remap

      V remap(K key, Object keyRef, BiFunction<? super K,? super V,? extends V> remappingFunction, long now, boolean computeIfAbsent)
      Attempts to compute a mapping for the specified key and its current mapped value (or null if there is no current mapping).

      An entry that has expired or been reference collected is evicted and the computation continues as if the entry had not been present. This method does not pre-screen and does not wrap the remappingFuntion to be statistics aware.

      Parameters:
      key - key with which the specified value is to be associated
      keyRef - the key to associate with or a lookup only key if not computeIfAbsent
      remappingFunction - the function to compute a value
      now - the current time, according to the ticker
      computeIfAbsent - if an absent entry can be computed
      Returns:
      the new value associated with the specified key, or null if none
    • keySet

      public Set<K> keySet()
      Specified by:
      keySet in interface Map<K,V>
      Overrides:
      keySet in class AbstractMap<K,V>
    • values

      public Collection<V> values()
      Specified by:
      values in interface Map<K,V>
      Overrides:
      values in class AbstractMap<K,V>
    • entrySet

      public Set<Map.Entry<K,V>> entrySet()
      Specified by:
      entrySet in interface Map<K,V>
      Specified by:
      entrySet in class AbstractMap<K,V>
    • evictionOrder

      Map<K,V> evictionOrder(int limit, Function<V,V> transformer, boolean hottest)
      Returns an unmodifiable snapshot map ordered in eviction order, either ascending or descending. Beware that obtaining the mappings is NOT a constant-time operation.
      Parameters:
      limit - the maximum number of entries
      transformer - a function that unwraps the value
      hottest - the iteration order
      Returns:
      an unmodifiable snapshot in a specified order
    • expireAfterAcessOrder

      Map<K,V> expireAfterAcessOrder(int limit, Function<V,V> transformer, boolean oldest)
      Returns an unmodifiable snapshot map ordered in access expiration order, either ascending or descending. Beware that obtaining the mappings is NOT a constant-time operation.
      Parameters:
      limit - the maximum number of entries
      transformer - a function that unwraps the value
      oldest - the iteration order
      Returns:
      an unmodifiable snapshot in a specified order
    • expireAfterWriteOrder

      Map<K,V> expireAfterWriteOrder(int limit, Function<V,V> transformer, boolean oldest)
      Returns an unmodifiable snapshot map ordered in write expiration order, either ascending or descending. Beware that obtaining the mappings is NOT a constant-time operation.
      Parameters:
      limit - the maximum number of entries
      transformer - a function that unwraps the value
      oldest - the iteration order
      Returns:
      an unmodifiable snapshot in a specified order
    • snapshot

      Map<K,V> snapshot(Supplier<Iterator<Node<K,V>>> iteratorSupplier, Function<V,V> transformer, int limit)
      Returns an unmodifiable snapshot map ordered by the provided iterator. Beware that obtaining the mappings is NOT a constant-time operation.
      Parameters:
      iteratorSupplier - the iterator
      limit - the maximum number of entries
      transformer - a function that unwraps the value
      Returns:
      an unmodifiable snapshot in the iterator's order
    • makeSerializationProxy

      static <K, V> SerializationProxy<K,V> makeSerializationProxy(BoundedLocalCache<?,?> cache, boolean isWeighted)
      Creates a serialization proxy based on the common configuration shared by all cache types.