Efficient way to use Caffeine as a Set

[koikahin]

I have a use-case where I want to track which keys have already been computed recently. The number of keys will be huge so I want some time-based eviction policy. Caffeine fits the bill, except there is no corresponding value to be cached for each key. I can of course build a cache with a dummy object for values but I was wondering if there exists a more efficient way to do this? Does getting an instance of cache.asMap().keySet() and manipulating that work correctly and efficiently and will evictions happen correctly in that case?

[ben-manes]

All of Java's Set implementations use a dummy value with a Map, where Boolean.TRUE is idiomatic. The Cache.policy() can provide a best effort ordered view, such as by hot/cold or young/old. However, this is mostly for cases like persisting for a warm restart so it is meant for infrequent usage as it requires obtaining the eviction lock, meaning excessively long hold times could impact eviction. Also since it is a concurrent data structure, we are less concerned about exactness as caching is fundamentally a probabilistic problem. If you need something more precise then you might maintain a secondary data structure that is written into by your compute.

[ben-manes]

One gotcha to be aware of is if you use expireAfterAccess policy to reset the ttl on a read. Otherwise I think your plan is solid.

cache.asMap().keySet().contains(key) uses Map.containsKey, which is an existence check. It will verify the entry is not expired, but does not treat this as a cache read (cache hit). It won’t reset the expiration time, trigger evictions, or increment statistics. If you want those you can use getIfPresent(key) != null, or else rely on the next write to handle any pending evictions which is likely fine.

[koikahin]

In my use-case there is no need for expireAfterAccess, just expireAfterWrite. But is there any difference in terms of space usage between using a dummy value for the map with, say Boolean.TRUE vs just the key management with the key-set view of cache.asMap().keySet()? Will adding a key to this set anyway add a corresponding dummy value? Likely yes as you point out that Sets are internally modeled as Map anyway.

My use-case is to track a bunch of UUIDs as having been recently handled. They are 16 bytes raw data. All the structures needed to even hold dummy value objects seem very wasteful. At the very least there will be 1 word worth of address information to hold that which is 50% additional data.

[ben-manes]

Yes, there is small waste because there would be an additional field in the entry, 4 or 8 bytes depending on your JVM configuration. We shave that off in the implementation details of Interner which is a set of weakly held keys. That is a well-defined subset of features (no refresh, no listeners, etc) and we fake the value getters to return the internal constant. We generate entry classes to minimize fields to those needed, but only this case discards the value as we don't have a Set-only builder to constrain by. I don't think that would likely happen just to reduce a field as those concerned might be prefer a highly packed data structure like those in fastutil and trade off high concurrency/flexibility to do that. Or they might use a time-bounded data sketch to probabilistically determine membership if that is still too sparse. So you actually have a lot of options depending on your needs, where Caffeine with Collections#newSetFromMap might be the convenient most general purpose solution, but you can use might prefer more specialized approaches if you have tighter resource constraints.