LocalCache deadlock in Guava 22

[dima5rr]

Throwing exception in compute function of Cache ConcurrentMap and computing the same key after makes deadlock in LocalCache.java:2387

@test
public void testCacheLoaderException() {
Map cache = CacheBuilder.newBuilder().build().asMap();

    Integer n = 1;
    try {
        cache.computeIfAbsent(n,k->{
            throw new IllegalStateException("make deadlock");
        });
    } catch (Exception e) {
    }
    int v = (int)cache.computeIfAbsent(n, k->k); //deadlock here
    Assert.assertEquals(1, v);
}

[ben-manes]

All recursive operations on a map are undefined behavior, so this works as intended. When the cache was a feature of MapMaker it had this behavior for computations on get, but I switched it to fail fast by detecting the lock was already held. Ideally the computations would emulate that for consistency and friendliness, but it isn't required.

Java 8's ConcurrentHashMap will live-lock on this call and HashMap may corrupt itself. In Java 9 it will fail fast in both cases, if detected.

So this works as intended, but could be a tad nicer.

[lowasser]

I'm not sure I see the recursion here?

[ben-manes]

Oh shoot, I misread. I've seen the recursion issues raised so many times across hash tables that, on seeing multiple computeIfAbsent calls, I saw the imagined pattern.

It does appear that LocalCache.compute fails to handle exceptions from loadingValueReference.compute and leaves the failed entry in the cache. The subsequent call waits for a future that has never been finalized.

[andrewparmet]

Isn't this the behavior referenced in #2799?

[slovdahl]

I'm also observing some strange behaviour with guava caches under contention. Not sure if these two issues are related. If they aren't, I'm happy to open a separate issue.

While I was doing some JMH benchmarks I noticed that benchmarks that were using guava caches stalled completely and/or had very erratic performance during thread contention. Benchmark iterations very often stalled for seconds, minutes or sometimes seemingly indefinitely. It turned out that the cache was the culprit in all cases.

The issue is very easy to trigger. I published a sample project on https://github.com/hibox-systems/guava-cache-test that demonstrates the issue. In my environment it works fine with 1, 2 and 3 threads. Using 4 threads or more always stalls the benchmark at some point. I have tried the benchmark with all published guava versions that are compatible with the sample code, i.e. guava 11.0 and newer. Tested with these JVM versions on Ubuntu 16.04 with a Intel Core i7-3770 CPU:

• OpenJDK 1.8.0_131-8u131-b11-2ubuntu1.16.04.3-b11
• Oracle 1.8.0_151-b12
• Oracle 9.0.1+11

FWIW, I tried replacing the guava caches in the benchmarks with caffeine caches, and all kinds of stalling and erratic performance went away.

[ben-manes]

It should be unrelated due to this bug dealing with new code for Java 8. Your benchmark touches prior code.

Note that by default there are 4 hash segments, each having its own queue and counter for replaying reads. The queue is uncapped and draining is amortized across readers. There should be a per drain threshold to avoid over penalizing any thread. In a stress test like yours, one could imagine a memory issue, hang ups for the penalized callers, and contention adding to the read buffer. Caffeine uses a lossy ring buffer which avoids all of this. My guess is you are hitting the worst case which wouldn’t be expected in practice, or at least not with the hardware available when the cache was designed.