Package com.github.benmanes.caffeine.cache

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>, java.util.concurrent.ConcurrentMap<K,​V>, java.util.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 Detail

      • logger

        static final java.util.logging.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:
        Constant Field Values

      • 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:
        Constant Field Values

      • MAXIMUM_CAPACITY

        static final long MAXIMUM_CAPACITY
        The maximum weighted capacity of the map.
        See Also:
        Constant Field Values

      • PERCENT_MAIN

        static final double PERCENT_MAIN
        The percent of the maximum weighted capacity dedicated to the main space.
        See Also:
        Constant Field Values

      • 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:
        Constant Field Values

      • EXPIRE_WRITE_TOLERANCE

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

      • data

        final java.util.concurrent.ConcurrentHashMap<java.lang.Object,​Node<K,​V>> data

      • accessPolicy

        final java.util.function.Consumer<Node<K,​V>> accessPolicy

      • evictionLock

        final java.util.concurrent.locks.Lock evictionLock

      • executor

        final java.util.concurrent.Executor executor

      • isAsync

        final boolean isAsync

      • keySet

        transient java.util.Set<K> keySet

      • values

        transient java.util.Collection<V> values

      • entrySet

        transient java.util.Set<java.util.Map.Entry<K,​V>> entrySet

    • Constructor Detail

      • BoundedLocalCache

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

    • Method Detail

      • ceilingPowerOfTwo

        static int ceilingPowerOfTwo​(int x)

      • isComputingAsync

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

      • buffersWrites

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

      • executor

        public final java.util.concurrent.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>

      • 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 java.lang.ref.ReferenceQueue<K> keyReferenceQueue()

      • valueReferenceQueue

        @Nullable
protected java.lang.ref.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>

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

      • 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,
                java.lang.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.

      • performCleanUp

        void performCleanUp​(@Nullable
                    java.lang.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
                 java.lang.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 java.util.Map<K,​V>
        Overrides:
        isEmpty in class java.util.AbstractMap<K,​V>

      • size

        public int size()
        Specified by:
        size in interface java.util.Map<K,​V>
        Overrides:
        size in class java.util.AbstractMap<K,​V>

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<K,​V>
        Overrides:
        clear in class java.util.AbstractMap<K,​V>

      • removeNode

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

      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K,​V>

      • containsValue

        public boolean containsValue​(java.lang.Object value)
        Specified by:
        containsValue in interface java.util.Map<K,​V>
        Overrides:
        containsValue in class java.util.AbstractMap<K,​V>

      • get

        public V get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>

      • getIfPresent

        public V getIfPresent​(java.lang.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​(java.lang.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>

      • put

        public V put​(K key,
             V value)
        Specified by:
        put in interface java.util.Map<K,​V>
        Overrides:
        put in class java.util.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 java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        putIfAbsent in interface java.util.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​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<K,​V>
        Overrides:
        remove in class java.util.AbstractMap<K,​V>

      • removeNoWriter

        V removeNoWriter​(java.lang.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​(java.lang.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​(java.lang.Object key,
                      java.lang.Object value)
        Specified by:
        remove in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        remove in interface java.util.Map<K,​V>

      • replace

        public V replace​(K key,
                 V value)
        Specified by:
        replace in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        replace in interface java.util.Map<K,​V>

      • replace

        public boolean replace​(K key,
                       V oldValue,
                       V newValue)
        Specified by:
        replace in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        replace in interface java.util.Map<K,​V>

      • replaceAll

        public void replaceAll​(java.util.function.BiFunction<? super K,​? super V,​? extends V> function)
        Specified by:
        replaceAll in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        replaceAll in interface java.util.Map<K,​V>

      • computeIfAbsent

        public V computeIfAbsent​(K key,
                         java.util.function.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,
                    java.lang.Object keyRef,
                    java.util.function.Function<? super K,​? extends V> mappingFunction,
                    long now)
        Returns the current value from a computeIfAbsent invocation.

      • computeIfPresent

        public V computeIfPresent​(K key,
                          java.util.function.BiFunction<? super K,​? super V,​? extends V> remappingFunction)
        Specified by:
        computeIfPresent in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        computeIfPresent in interface java.util.Map<K,​V>

      • compute

        public V compute​(K key,
                 java.util.function.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,
               java.util.function.BiFunction<? super V,​? super V,​? extends V> remappingFunction)
        Specified by:
        merge in interface java.util.concurrent.ConcurrentMap<K,​V>
        Specified by:
        merge in interface java.util.Map<K,​V>

      • remap

        V remap​(K key,
        java.lang.Object keyRef,
        java.util.function.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 java.util.Set<K> keySet()
        Specified by:
        keySet in interface java.util.Map<K,​V>
        Overrides:
        keySet in class java.util.AbstractMap<K,​V>

      • values

        public java.util.Collection<V> values()
        Specified by:
        values in interface java.util.Map<K,​V>
        Overrides:
        values in class java.util.AbstractMap<K,​V>

      • entrySet

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

      • evictionOrder

        java.util.Map<K,​V> evictionOrder​(int limit,
                                       java.util.function.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

        java.util.Map<K,​V> expireAfterAcessOrder​(int limit,
                                               java.util.function.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

        java.util.Map<K,​V> expireAfterWriteOrder​(int limit,
                                               java.util.function.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

        java.util.Map<K,​V> snapshot​(java.util.function.Supplier<java.util.Iterator<Node<K,​V>>> iteratorSupplier,
                                  java.util.function.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.