How does Guava Cache implement "if cached, return; otherwise create, cache and return" pattern?

Question

I am trying to understand how Guava Cache achieves thread-safety in its get() method and also ensures that if 2 threads simultaneously invoke the get method and the value is not present only one thread will calculate the value and the rest will wait. Also, when the thread is done with calculating the value the rest of the threads can use that value.

This SO answer says Guava does this via a combination of ReentrantLock and ConcurrentHashMap.

I can intuitively understand how to achieve mutual exclusion via the use of locks.

But what I can't understand is that how after the value is calculated the other threads will not lock and use that value. The only way I can implement this is via double-checked locking, but that seems too slow since after the value is calculated all threads will have to lock once.

What I mean is the following:

1. Check to see if Item X is cached.
2. If missing tryForLock() on underlying data-structure (most likely some sort of HashMap)
3. If lock acquired check to see value computed (If already computed by another thread)
4. If not, Compute Value
5. Put in underlying cache data structure.
6. Release lock.

Now let's say the above Code is invoked by 3 Threads A,B,C : only one thread can get the lock when it tries for it. Rest will be waiting for lock. Once the thread that got the lock, computes the value, releases the lock.

All the other 2 threads will also be acquiring the lock in a sequential way. And all will check if the value is computed or not, but not compute it themselves. And release the lock. This will all happen sequentially.

Is this what Guava Cache does? Or is there a better way to implement this pattern?

Answer 1

Yes, that is basically the pattern except that no locking is needed if present. The cost of the computation is much greater than the penalty of locking (millis or seconds, vs nanos).

A lookup for the entry is lock-free so this quickly identifies if it is absent, present, or in-flight.

• If absent then the threads race for the segment lock to insert an in-flight entry
  • if winner, then insert an in-flight entry, unlock, and compute
  • otherwise find the entry, unlock, and wait on it
• If the entry is found,
  • if in-flight then a thread will block on it waiting for the result.
  • Otherwise the entry's value is returned immediately.

A lock is cheap if not on the hot path that serializes all of the threads. Since the in-flight entry is quickly visible in the map and looked up lock-free, the segment holding multiple entries is not locked excessively. The descheduling of the entry's waiting threads can free resources for other application work.

ConcurrentHashMap added native functionality with computeIfAbsent. It reuses the hashbin's lock (a fine-grained segment), and does a similar pattern. Since a computing thread locks the hashbin which holds multiple entries, there is a higher chance of collisions causing unnecessary stalls. Their approach has nice linearization and memory efficiency benefits, but it can be more problematic for long-running computations. In those cases one can emulate Guava's approach by storing a Future<V> value as the map's entry. Caffeine, a rewrite of Guava's cache, offers that through its AsyncCache.