invalidateAll question

[joanbalaguero]

Hello,

I have a synchronous cache with caffeine 1.3.1 running on a 8-core server. It's working perfectly.

The point is when I try to invalidate all or parts of the cache. This cache can have millions of entries and the user can invalidate all entries or part of them.

Performing an invalidateAll with a 4-millions entry cache locks the entire cache for 4 seconds, or at least this is what it seems, so during this time we don't see incoming traffic registered in our log.

This is the log when the operation starts/ends:
2022-12-09 14:53:25 Deleting all documents for the method "MultiAvailability" ...
2022-12-09 14:53:29 Process of deleting all documents for the method "MultiAvailability" successfully executed.

And this is the access log that traces all incoming requests, Below the first line registered after the invalidateAll finishes:
10.1.0.9,14:53:25.940,S,7,A,90,A,36,A,300,N,,receiver04:8083,g,14194,1601,677,44,,2022-12-09 14:53:29.214

As you can see the operation starts at 14:53:25.940 and ends at 14:53:29.214.

If we add a removal listener (even if it does nothing), then things are getting worse. The same test now takes 16 seconds:
2022-12-09 14:35:52 Deleting all documents for the method "MultiAvailability" ...
2022-12-09 14:36:08 Process of deleting all documents for the method "MultiAvailability" successfully executed.

10.1.0.9,14:35:52.051,S,7,A,90,A,36,A,300,N,,receiver03:8082,g,14194,1601,676,50,,2022-12-09 14:36:08.331

But, in addition to this, we are seeing that all caches are locked, not only the one that receives the invalidateAll. All other caches are differents instances of caffeine caches, and all the incoming traffic also disappears during the invalidateAll operation.

I'm afraid we are misunderstanding something and thus doing something really wrong to get all caches locked.

So we have two questions:

1. This times of 4s (no removalListener) and 18 seconds (with removalListener) are ok? Much more important for us is not the time spent to remove the entries, but the fact the entire cache is locked during this time.

2. is it possible that this operation performed on a caffeine cache instance is also affecting the rest of instances?

Thanks,
Joan.

[ben-manes]

While unfortunately this won't solve your problem, please consider upgrading to a recent release (v2 for Java 8, else v3).

This times of 4s (no removalListener) and 18 seconds (with removalListener) are ok? Much more important for us is not the time spent to remove the entries, but the fact the entire cache is locked during this time.

The removal listener call is delegated to the configured executor, so within the invalidation it should be immediate. You might be suffering if you configured to a direct executor (e.g. Runnable::run) or thread scheduling is causing the invalidation to be deprioritized.

The cache should still accept read/write operations and only locked wrt the eviction policy. Those operations schedule work against the policy through ring buffers, so that batches of events can be replayed under the lock without blocking. In the case of clearing the whole cache, acquiring this lock is generally cheaper than iterating over the map to queue a delete task per entry.

A possible problem might be if you use long computations, as these are performed by ConcurrentHashMap compute methods. That locks the hash bin so a slow load can block the removal of a peer entry, as both require the lock for their writes (whereas reads are lock-free). This is documented as,

Lock contention probability for two threads accessing distinct elements is roughly 1 / (8 * # of elements) under random hashes.

At 4M entries this usually isn't a problem as there should be a good distribution within the table. However if it is, you might consider using AsyncCache so that the mapping is updated immediately and the computation is performed under a per-entry lock (CompletableFuture). The FAQ shows an example of how to do this non-async, if deferring the compute to extra threads is a problem.

is it possible that this operation performed on a caffeine cache instance is also affecting the rest of instances?

The cache itself should not have any cross-instance state that could cause slow downs. If you have callbacks that use shared locks, e.g. in your CacheLoader logic, then that would impact multiple. But the library itself shouldn't have this problem.

[ben-manes]

Thanks, fixed in 68fbff8

[joanbalaguero]

Hi Ben,

Tested, it works, no locks now. 4.5 millions entries removed in 17s. It's a ratio of 265.000 entries /second. It's a bit slow, but I understand there are a lot of processes involved there when removing keys.

Thanks for all,

Joan.

[ben-manes]

that's great and thanks for the feedback!

[ben-manes]

I did some ad hoc benchmarking with jmh to get a feel for the performance. In all cases the throughput was higher than yours, but that is not a running system with competing resources, in-flight computations, etc. The microbenchmark ranged from 0.1s to 10s for 4.5M keys depending on the strategy, cache provider, and if there were concurrent writes (simple puts).

The gist seems to be that iterating over the map to remove one-by-one is a visible cost. This avoids rehashing the key and benefits from data locality by walking the underlying hash table's array. For ConcurrentHashMap the clear() method is 10x faster than a remove(key) loop (or 0.1s vs 1s in this test harness). As Caffeine is built on top of CHM and needs to clear related policy metadata, it must use the iterator method. That further halves the performance due to this extra work, so 20x slower than a CHM clear() (or 2s in this harness).

As you observed, when I add concurrent writes then the iterator method is faster for caches since they typically use a top-level lock and would suffer from lock contention. The newly added detection and fallback should alleviates this, but the baseline throughput is not high and there are no computations (e.g. slow cache loads) so that is hard to observe in this harness.

Ehcache is the only outlier here because they forgo linearizability and notifying listeners by simply dropping the hash table and allocating a new instance. If one wants to notify listeners then the iterator approach is required, where the performance matches Caffeine's. If listeners weren't a concern then naively their approach would be good, but developers often make linearizability assumptions and are surprised by inconsistencies, e.g. a clear would by allow the cache to serve two in-flight computes for the same key and cause side data structures to have stale data. Since the penalty of doing it right is not that high, it's safer to avoid these bad surprises.

There wasn't any obvious ways to make it faster, but I hope you find those extra details interesting.

[ben-manes]

Released in 3.1.3