Handling reentrant computations

[msevcenko]

The fact that reentrant computations are not allowed in caffeine is kind of blocker for me, can't be avoided, so I needed to downgrade to guava cache that allows them.

I had an idea to work around this limitation at the expense of not caching the reentrant computations. That is, instead of failing, the reentring computation is simply evaluated without being cached. Only when the computation is evaluated again as top level, can be cached. It seems to me as better approach than just failing. What do you think?

The implementation is to wrap the cache into a wrapper (I use wrapper anyway, to decouple caching from actual implementation)

class MyCache<K, V>(
    private val cache: Cache<K, V>
) {
    private val inLoader = ThreadLocal()

    fun <K: Any, V: Any> get(key: K, compute: () -> V): V =
        if (inLoader.get() == true) {
            // return cached value if present
            cache.getIfPresent(key)?.let { return it }
            // recursion detected, compute without caching
            compute()
        } else {
            // top-level load
            inLoader.set(true)
            try {
                cache.get(key) { compute() }
            } finally {
                inLoader.remove()
            }
        }
}

[ben-manes]

The limitation comes from ConcurrentHashMap. Guava handles it better because it used to deadlock until I added detection using Thread.holdsLock when the same key was applied. This was for LoadingCache style where Guava inserts a future and unlocks the segment, so it does not hold a lock throughout. If you use their grafted on compute then it locks the segment, but a recursive call might lock a different segment and deadlock again. It is a fundamental problem if you want linearizability, which Guava does not provide and often isn't needed.

Have you tried the future-style approach in the FAQ? That would let you cache the results while also recursing outside of any map locks.

[msevcenko]

I have read the FAQ entry, I am not sure if it is applicable for my case. First, I'd like a solution that is, if possible, transparent, built-in my wrapper, that doesn't burden the client code. Also, I do not know in advance whether the reentrancy is possible or not, so I would need to do this check always. Second, I might not be able to offload a computation to a different thread (it may use dependency injection that works only in single thread).

So what am I looking for is a guava drop-in replacement that "just works" (under assuptions and with tradeoffs), never fails due to reentrancy. What do you think about the proposed solution? Or would you recommend to stick to guava cache?

[ben-manes]

The proposal seems reasonable. I don’t have much of an opinion on it vs guava, both would be fine imho.

The faq example should work within your facade and compute on the calling thread. It uses futures as just a memorizing supplier for shorter code.

but lgtm if you just wanted the code review

[msevcenko]

Ah, looks like I misunderstood the proposed solution in the FAQ. So the trick is not to offload the computation, but only to postpone it and evaluate it outside the cache lock. The generalized solution (universal wrapper) could then be

fun get(key: K, compute: () -> V): V {
    val future = CompletableFuture<V>()
    cache.asMap().putIfAbsent(key, future)?.let { return it.join() /* computing or already cached, join and return */}
    return compute().also { future.complete(it) }
}

The tradeoff here is that the CompletableFuture is always instantiated, providing some overhead. So I might as well combine the two approaches, and use reentrancy detection, and create the future only when needed. Because, if I understand it correctly, if the cache contains large number of long-living values, they will stay wrapped in the future wrapper, so the overhead may be noticeable. So the detection would create the wrapper only in (hopefully rare) situations of reentrancy.

On a second thought, I still like my first approach better, as it avoids the computable overhead altogether, and it seems to me that not caching the conflicting computation is not a big price to pay. Also the reentrancy detection doesn't seem to be a big overhead.

Anyway, many thanks for your insights and clarifications, @ben-manes !

[msevcenko]

I also missed the point what an AsyncCache is, which is basically a Cache of CompletableFuture values, with some built-in support. So maybe whether the values actually stay wrapped forewer, is an implementation detail of the AsyncCache.

[ben-manes]

Exactly.

AsyncCache is just a convenience that handles a few minor quirks of a CompletableFuture valued cache, like not evicting an in-flight future by size/expiration or removing if failed. Unfortunately we cannot transparently store the unwrapped version because CompletableFuture uses reference identity (no equality defined), and if you wanted to manage it in a complex concurrent flow then using CAS-style methods that rely on value equality would break (making coordination across multiple data structures harder and disallowing an async asMap view). CompletableFuture is not that heavy, but you can use a lighter weight Suppliers.memoizingSupplier(...) as a thinner wrapper given the caveats of being opaque to the cache.

Guava doesn't expose an async interface even though the internals is a future value (LoadingValueReference). Since its not exposed, upon completion it swaps that with a lighter StrongValueReference. ConcurrentHashMap does similar with ReservationNode replaced by a TreeNode, but its not a full future as it holds the lock and is just a placeholder to detect recursion.