Contended cache access causes deadlock

[slovdahl]

I'm also observing some strange behaviour with guava caches under contention. According to @ben-manes, this is unrelated to #2863. Motivation for opening this issue: #2863 (comment)

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]

I ran your benchmark and the problem is due to GC / allocation rate. When using the default settings, in JDK8, a small maximum heap is used with the parallel collector. That defers collection for overall throughput, resulting in a long pause during an iteration. Due to the allocation rate vastly exceeding the drain rate, the entries are promoted to old generation and may cause a GC death spiral.

When using G1 and an 8gb heap instead, the pauses mostly disappeared. It did hang, but jstack showed no benchmark threads running. Instead JMH was blocked waiting for the runner to complete, indicating a missed signal. My guess is that the constant GC pressure exposed a race in JMH, which is not typically under memory pressure.

In LRU every read is a write by mutating a doubly-linked list. If guarded by a lock for concurrency, then this creates significant contention. Guava solves this by delaying the LRU reorder and batching it, using a read buffer as an intermediary. For simplicity, this was a ConcurrentLinkedQueue and an AtomicInteger counter. This creates an allocation, but overall is cheaper than a lock. The work is then amortized on callers to drain the read buffer and catch-up the LRU.

This was intended to eventually be optimized with a ring buffer to remove allocations, do less work, and favor performance over strict LRU order. Unfortunately this improvement never occurred, though it was proven out in the predecessor (CLHM) and further optimized in its successor (Caffeine). After Caffeine began getting some traction, I tried once again to float the idea and provided a patch as a proof-of-concept.

Using that patch and your original JMH command, no issues occurs during benchmarking. The ns/op is relatively tight at 5-50ns, with the variance due to whether JMH is observing the amortized drain penalty. After 10 forks with the 20 warmup iterations and 20 actual iterations, there is no stalling.

Thus while Guava's cache degrades poorly under synthetic pressure, it does not deadlock.