A high performance caching library for Java

Under heavy load of JVM, we are experiencing deadlocks in caffeine version 2.5.6.

Here is the threaddump of the two threads in deadlock:

"ajp-0.0.0.0-8109-59 (P6V7aMaZbbXkfaYzYzXxID0tvHylFQJumanAAABmA)":
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x000000032a600bb8> (a com.github.benmanes.caffeine.cache.NonReentrantLock$Sync)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:836)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:870)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1199)
        at com.github.benmanes.caffeine.cache.NonReentrantLock$Sync.lock(NonReentrantLock.java:315)
        at com.github.benmanes.caffeine.cache.NonReentrantLock.lock(NonReentrantLock.java:78)
        at com.github.benmanes.caffeine.cache.BoundedLocalCache.performCleanUp(BoundedLocalCache.java:1096)
        at com.github.benmanes.caffeine.cache.BoundedLocalCache.afterWrite(BoundedLocalCache.java:1017)
        at com.github.benmanes.caffeine.cache.BoundedLocalCache.put(BoundedLocalCache.java:1655)
        at com.github.benmanes.caffeine.cache.BoundedLocalCache.put(BoundedLocalCache.java:1602)
        at com.github.benmanes.caffeine.cache.LocalManualCache.put(LocalManualCache.java:64)

and

"ajp-0.0.0.0-8109-78 (-jIkyghhBePEsLll9i5dnGr65Dx8PfahGe2gAABxE)":
        at sun.misc.Unsafe.park(Native Method)
        - parking to wait for  <0x000000032a600bb8> (a com.github.benmanes.caffeine.cache.NonReentrantLock$Sync)
        at java.util.concurrent.locks.LockSupport.park(LockSupport.java:175)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.parkAndCheckInterrupt(AbstractQueuedSynchronizer.java:836)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquireQueued(AbstractQueuedSynchronizer.java:870)
        at java.util.concurrent.locks.AbstractQueuedSynchronizer.acquire(AbstractQueuedSynchronizer.java:1199)
        at com.github.benmanes.caffeine.cache.NonReentrantLock$Sync.lock(NonReentrantLock.java:315)
        at com.github.benmanes.caffeine.cache.NonReentrantLock.lock(NonReentrantLock.java:78)
        at com.github.benmanes.caffeine.cache.BoundedLocalCache.performCleanUp(BoundedLocalCache.java:1096)
        at com.github.benmanes.caffeine.cache.BoundedLocalCache.afterWrite(BoundedLocalCache.java:1017)
        at com.github.benmanes.caffeine.cache.BoundedLocalCache.put(BoundedLocalCache.java:1655)
        at com.github.benmanes.caffeine.cache.BoundedLocalCache.put(BoundedLocalCache.java:1602)
        at com.github.benmanes.caffeine.cache.LocalManualCache.put(LocalManualCache.java:64)

Looking at the code, I can't imagine a scenario this could occur, but it does occur under heavy load of our JVMs.

Any ideas what we could do? For now, as a workaround, I've added a synchronized() block around the cache.put() methods to make sure only 1 thread is adding new values to the cache at a time.

I noticed that concurrentlinkedhashmap originally planned on having LIRS eviction for v2.x according to the google code page [1].

Is this still planned for caffeine the successor to concurrentlinkedhashmap ?

I also am quite happy to see you have custom weighting for entries :+1:

[1] https://code.google.com/p/concurrentlinkedhashmap/

I observed a very high false positive rate with the current implementation of BloomFilter, at times as high as 100%. My test code and results are given below. I also found out what can be changed to fix it, although not completely sure why my fix worked. I thought maybe bitmask method's output has some bias, but upon further inspection it seems alright. I hope I am using the APIs correctly and don't have some other bug in my test code. Would be great if someone can review and let me know. tks! P.S.: I understand that BloomFilter code might be internal to caffeine, but just want to highlight my observation.

Line: https://github.com/ben-manes/caffeine/blob/master/simulator/src/main/java/com/github/benmanes/caffeine/cache/simulator/admission/bloom/BloomFilter.java#L166

Current code:

static long bitmask(int hash) {
    return 1L << ((hash >>> 8) & INDEX_MASK);
  }

| Number of Insertions | False positives(% ) | True positives | | --- | --- | --- | | 1024 | 27 (2.636719%) | 1024 | | 4096 | 640 (15.625000%) | 4096 | | 16384 | 15213 (92.852783%) | 16384 | | 65536 | 65536 (100.000000%) | 65536 | | 262144 | 262144 (100.000000%) | 262144 | | 1048576 | 1048576 (100.000000%) | 1048576 |

New implementation:

static long bitmask(int hash) {
    return 1L << ((hash >>> 24) & INDEX_MASK);
  }

| Number of Insertions | False positives(%) | True positives | | --- | --- | --- | | 1024 | 15 (1.464844%) | 1024 | | 4096 | 96 (2.343750%) | 4096 | | 16384 | 391 (2.386475%) | 16384 | | 65536 | 1598 (2.438354%) | 65536 | | 262144 | 6326 (2.413177%) | 262144 | | 1048576 | 25600 (2.441406%) | 1048576 |

Test method:

    public void bloomFilterTest() {
        System.out.println("Number of Insertions\tFalse positives(%)\tTrue positives");
        for (int capacity = 2 << 10; capacity < 2 << 22; capacity = capacity << 2) {
            long[] input = new Random().longs(capacity).distinct().toArray();
            BloomFilter bf = new BloomFilter(input.length / 2, new Random().nextInt());
            int truePositives = 0;
            int falsePositives = 0;
            int i = 0;
            // Add only first half of input array to bloom filter
            for (; i < (input.length / 2); i++) {
                bf.put(input[i]);
            }
            // First half should be part of the bloom filter
            for (int k = 0; k < i; k++) {
                truePositives += bf.mightContain(input[k]) ? 1 : 0;
            }
            // Second half shouldn't be part of the bloom filter
            for (; i < input.length; i++) {
                falsePositives += bf.mightContain(input[i]) ? 1 : 0;
            }
            System.out.format("%d\t\t%d(%f%%)\t\t%d\n",
                input.length / 2, falsePositives,
                ((float) falsePositives / (input.length / 2)) * 100, truePositives);
        }
    }

We recently upgraded from 2.7.0 to 2.8.8 and noticed that our putIfAbsent code-paths are contending more heavily than before (at least that's our observation):

   java.lang.Thread.State: BLOCKED (on object monitor)
	at com.github.benmanes.caffeine.cache.BoundedLocalCache.put(BoundedLocalCache.java:2030)
	- waiting to lock <0x00007f00ba087828> (a com.github.benmanes.caffeine.cache.PSWMS)
	at com.github.benmanes.caffeine.cache.BoundedLocalCache.putIfAbsent(BoundedLocalCache.java:1965)

We are aware of the commit https://github.com/ben-manes/caffeine/commit/614fe6053e343481c15c55f1d696517d73baae0d that should have improved putIfAbsent but we are somehow seeing the opposite. This is a bounded (1M) synchronous cache with a 1-day expiration.

I'm using Modeshape JCR implementation, and it internally uses caffeine cache configured on the following way: Caffeine.newBuilder().maximumSize(workspaceCacheSize).executor(Runnable::run).build(); I noticed that for each read operation is trying to perform some cleaning up operations, represented on this method: scheduleDrainBuffers(). It internally performs the operation on the current thread. The problem that I see is that when Modeshape calls many times to read the cache, and each scheduleDrainBuffers is taking in one example about 128 ms, which seems to be high. Why is this operation required when reading the cache? I attached some images showing the time spent on executing clean up tasks:

I appreciate your help.

Thanks

Hi @ben-manes,

I have created a trace from a production system where I see Caffeine underperforming a simple LRU strategy (with a cache size of 100k items, Caffeine hit rate is 72.35% vs 75.91% with LRU): scarab-recs.trace.gz

The format is a series of longs (can be decoded with DataInputStream#readLong)

Any thoughts if this could be improved upon?

Thanks, Viktor

Hi Ben,

I was pleasantly surprised by CheckerFramework annotations on the caffeine code, since we also switched a while back, it makes life easier. :+1:

A pattern I saw and I wanted to check your opinion on is for example Cache::get:

  @Nullable
  V get(@NonNull K key, @NonNull Function<? super K, ? extends V> mappingFunction);

Now reading the documentation, if the mapping function never returns null, neither should the get function, right?

If that is so, than I think the @Nullable should be removed from the return type. Since CF will just propagate the nullability of the V type parameter. If V is @Nullable, then the result will be, but if you provide a mapping function that has a @NonNull return type, it's a bit strange to still have to handle the null case.

I hope this question makes sense?

Hi,

I have a use-case where I need to maintain several caches that basically store the same value, but have different keys. So, I want to update both caches whenever i actually get the data for one of them, and so want to be notified whenever a load was called. It's basically similar to the removalListener. Is there any particular reason why it's not support for updates and only removal.

Thanks.

I saw this problem in version 2.3.1, via VisualVm, when after a few hours that a bunch of ForkJoinWorkers would be stuck on the WriteBuffer.poll() function in RUNNABLE state. Even hit an OOM when the cpu utilization became too high and my events started to get backed up. I recently upgraded to 2.3.3 and thought the problem was fixed until the below screenshots.

When I started up the application (10/19, 7:34 am) there is one FJW in the writebuffer.poll, which is fine.

This morning (10/20, 9:34am) and this is in constant RUNNABLE state. The number of workers that will be in this stuck runnable state will slowly grow over time too because I have seen this behavior happen with 2.3.1.

The cpu utilization and cpu load metrics in Grafana support an overall increase work as if the workers are busy waiting/spinlooping or something.

There are maybe 1k or so instances of the cache data structure in the application. This server has the most instances of the cache and the issue appears to manifest faster than the other servers. All of the servers have a 64GB heap.

I will have to switch back to Guava considering this is a production application.

Thanks for your effort though!

Hi @ben-manes,

I could not find a better place to ask the following, therefore I am opening the current issue.

My question is regarding a maintenance clean up approach that I am thinking to implement. This approach does not make use of a maintenance thread.

I want to make use of CacheWriter and cache's notification mechanism by acting on RemovalCause.EXPIRED events to perform a maintenance clean up. Consider the following interface:

Implementations of this interface would construct instances of the Cache<String, T> by invoking the build(long). At runtime, when a cache entry expires and the delete handler is invoked, a reference to the respective cache instance is obtained by invoking nativeCache() and then calling cleanUp() on it to clean up. The idea here is to call cleanUp() after N entries have expired.

Do you see any issues with this approach?

public interface MyCache<T> {
    
    default Cache<String, T> build(final long expireAfterWriteSeconds) {

        final Cache<String, T> nativeCache = Caffeine.newBuilder()
                .expireAfterWrite(expireAfterWriteSeconds, TimeUnit.SECONDS)
                .writer(new CacheWriter<String, T>() {

                    private static final int CACHE_CLEANUP_THRESHOLD = <SOME_VALUE>; 
                    private final AtomicInteger expiredEntryCounter = new AtomicInteger(0);

                    @Override
                    public void write(String key, T value) {
                        //NO-OP
                    }

                    @Override
                    public void delete(final String key, final T value, final RemovalCause removalCause) {
                        if (removalCause == RemovalCause.EXPIRED) {
                            if (expiredEntryCounter.incrementAndGet() == CACHE_CLEANUP_THRESHOLD) {
                                nativeCache().cleanUp();
                                expiredEntryCounter.set(0);
                            }
                        }
                    }
                })
                .build();

        return nativeCache;
    }

    Cache<String, T> nativeCache();
}

I'm a newbie to threadsafety. Let's say i have a Cache<K, List> where V is a recursive key of the cache. Users can request all children of a key K. The children will have their sub-children retrieved, and the sub-children have their sub-sub-children retrieved until no more nodes can be located. This works adequately with a loading function which, upon not having a value for K, will request a database for only the immediate children, and stays within the cache function's expected atomic operation. However, i want to reduce the amount of queries to the database, since if a key is missing, potentially a query must be run for every single child and their descendants. I'd like to perform a modified get function that has the power to update multiple keys at once, but that breaks the expected contract of the get operation. Will it still function safely?

Currently a fixed duration in refreshAfterWrite is supported. An evaluation per entry, similar to expireAfter(Expiry), would provide a more flexible approach. In #261 this would evaluate on create, read, and update. In #498, it was also requested to evaluate on the exceptional case, where the entry remains unchanged.

Implementation notes

A quirk in Guava (and replicated in Caffeine for compatibility) is that expireAfterWrite and expireAfterAccess may both be set and honored. As refreshAfterWrite piggybacks on the write timestamp, we would have to extend the codegen to 3 timestamps. That isn't desirable or useful, so instead we should restrict this specific combination and reuse the 2 timestamp variations already generated (e.g. for expireAfter and refreshAfterWrite). Setting both fixed and variable refresh should be disallowed. This approach only requires retrofitting methods onto existing generated cache entries to map to the correct timestamp field.

This issue consolidates #261, #272, #360, and #498. @denghongcai @eugenemiretsky, @anuraaga, @musiKk, @minwoox, @ikhoon, @barkanido, @wcpan

This Guava issue identified an expected optimization not being implemented. A getAll where some of the entries should be refreshed due to refreshAfterWrite schedules each key as an independent asynchronous operation. Due to the provided CacheLoader supporting bulk loads, it is reasonable to expect that the refresh is performed as a single batch operation.

This optimization may be invasive and deals with complex interactions for both the synchronous and asynchronous cache implementations. Or, it could be as simple as using getAllPresent and enhancing it to support batch read post-processing.