Recursive cache loading never terminates

[theangrydev]

Caffeine seems to exhibit the same kind of behaviour as described in this post, I guess because it uses ConcurrentHashMap under the hood.

Is there any way to specify an alternative backing map other than ConcurrentHashMap to work around this?

[ben-manes]

Unfortunately a different map implementation would either be deadlock prone, use non-atomic computes, or a single exclusive lock. There would be the case of (A) => (B) and (B) => (A), so at best an ordered set of computations might complete. As noted in your link, I worked with Doug to detect and fail fast because its an easy mistake to make. The cache's JavaDoc do warn that recursive computations are prohibited.

A workaround for ordered computations is to use AsyncLoadingCache and its synchronous() view. In that the map's computation is merely inserting a CompletableFuture, which computes asynchronously. A deadlock may still occur due to unordered computes, but you can recover by adding a timeout to fail the computation (built-in to JDK9 futures).

[theangrydev]

As you pointed out, this kind of thing only really makes sense for ordered computations, such as a tree structure that shares subtrees.

I didn't spot the JavaDoc, it could be worth adding your comments about ordered computations there to help point anyone else that stumbles across this kind of problem in the right direction.

Your tip about using AsyncLoadingCache and its synchronous() view looks promising, I'll see how that goes for my problem. If I understand you correctly, are you saying that solution is deadlock free if I can guarantee that there are no unordered computes?

[ben-manes]

Yes, it should be deadlock free when ordered.

In the regular case, an unordered computation might deadlock due to the computation. The ordered case would also be prone due to the hash table resizing during the operations. The latter case is why HashMap was updated to restrict recursion as otherwise it corrupted itself.

In the asynchronous case the map operations are immediate with no dependencies. The futures may deadlock on each other when unordered. But if ordered then it is a linear dependency chain and shouldn't cause a problem. The synchronous view is merely a helper that blocks on the returned futures so that the calling code isn't forced into being written in an asynchronous fashion.

[theangrydev]

Great, thanks for your comments, it's nice to see a library maintained by someone who clearly knows their domain very well!

[protogenes]

I just encountered this problem when looking for a replacement because of google/guava#1881
I assume you need an unbounded executor for the asynchronous workaround to operate?
Please consider to document this behaviour more prominently.
An attempt to perform a recursive should not lead into an infinite loop within computeIfAbsent, but throw an exception if it is not supported.

[ben-manes]

I agree it shouldn't result in an infinite loop, but it is not something I can fix locally without a penalty. It is a bug within ConcurrentHashMap that we are exposed to.

I brought this issue up and had it fixed in the 2011 preview and, after discovering it regressed, worked with Doug to fix it in 2014. Unfortunately that was never brought into a Java 8 release, so we have to wait for 9. Until then I'd need to embed the corrected hash table, which I've been holding off on. (Note that I also fixed recursion in Guava's loading and reported it as regressed in their new compute() support).

All of the computing methods are documented, e.g. CacheLoader states,

<b>Warning:</b> loading <b>must not</b> attempt to update any mappings of this cache directly.

Yes, an unbounded pool is ideal for async recursion. It relies on decoupling the map operation from the computation so that the future is inserted and then executed, rather than executed during the insert. This means that a caller-runs policy cannot be used (e.g. same-thread executor), which is ensured by an unbounded pool.