[FeatureRequest] support set a different exprie time when add a cache entry

[jiming]

Hi Ben,

Sometime, we need set the exprie time for certain cache entry, such as to an NullObject entry, I want it's expired time is one tenth of the global cache setting. Could you please consider add a method to support it?

And another feature useful is to change ttl of a cache, which is useful when I wanted to gracefully upgrade or downgrade system setting. I hope the ttl of cache can be longer or shorter

Thanks.
Jiming

[ben-manes]

Hi Jiming,

You can modify the expiration times at runtime using Cache.policy().

The reason why per-entry expiration times isn't provided is that it is difficult to implement efficiently. The fixed expiration times is performed as O(1) operations by moving nodes in a linked list to maintain order. This works because we know the accessed entry is the least likely to expire, so its pushed to the end of the list. We can then peek at the front knowing that if it hasn't expired, no entries behind it have too.

We can't use that trick if an entry's expiration time varies. This leads to a few common approaches which are each problematic.

• Use a sorted priority queue, O(lg n). This adds a high penalty on every operation to reorder.
• Use a periodic O(n) sweep. This is expensive and undesirable.
• Use a timestamp and rely on size eviction. This is O(1) and used by memcached. However, it is easily doable in user code and I'd prefer a solution that is flexible to more configurations.
• Use a hash timer wheel. This is amortized O(1) and used by OS kernels and network stacks for scheduling timers. However it can degrade to O(n), so it requires care to minimize the penalties.

Of the choices, I'm prone to using a timer wheel. But that requires experimentation and understanding how implementors have resolved performance issues. I've never seen it used for caches and its not a widely known technique, so contributions exploring this would be helpful.

For the time being, I'd recommend using your own timestamp and relying on size eviction. That should be simple to code.

[jiming]

Hi Ben,

Got it, thanks a lot for the detailed answer!

Best regards!
Jiming

[costimuraru]

@ben-manes, when you're saying I'd recommend using your own timestamp and relying on size eviction. do you think you could help with an example?
I'm trying to achieve the exact same thing in my application: have an expire time of X seconds, but for empty values have an expire time of X/10 seconds. The use case is the following: I'm querying the data store in order to retrieve a value. If the value is present then ok, cache it. However, if no entry is found, then it's ok to cache it, but I want to retry it more often.

[ben-manes]

That idea is called negative caching, where you use a placeholder to indicate its absence to avoid query storms. If you use your own timestamp, then you can check if the entry is expired and, if so, use cache.remove(key, absent) followed by another cache.get(key) to force a reload. Alternatively if absent is okay, you can use refresh(key) to do it asynchronously.

I started working on variable expiration over the weekend. That would support your use-case naturally and operates in amortized O(1) time. The timer wheel needs more tests and bug fixes, and it needs to be integrated into the cache. Please take a look at the interface and let me know your thoughts.

[ben-manes]

2.5.0 is released and provides variable caching using the timer wheel, as described above. You can enable it using the new Expiry interface, e.g.

Caffeine.newBuilder()
    .expireAfter(new Expiry<Key, Graph>() {
      public long expireAfterCreate(Key key, Graph graph, long currentTime) {
        return (graph instanceof NullGraph)
            ? TimeUnit.MINUTES.toNanos(1)
            : TimeUnit.MINUTES.toNanos(10);
      }
      public long expireAfterUpdate(Key key, Graph graph, 
          long currentTime, long currentDuration) {
        return currentDuration;
      }
      public long expireAfterRead(Key key, Graph graph,
          long currentTime, long currentDuration) {
        return currentDuration;
      }
    })
    .build(key -> createExpensiveGraph(key));

Note that the other methods return currentDuration to indicate no change. If you want to disable expiration it would return a large duration, e.g. Long.MAX_VALUE is over 200 years. Some runtime inspection is provided by cache.policy().expireVariably().

[costimuraru]

Thanks @ben-manes, you're the man!
Will plug this in and see how it goes. Do you happen to know if there is a performance penalty with using the variable expire time?

[ben-manes]

There shouldn't be. It is amortized O(1), currently optimized for durations up to 6.5 days (not restricted by that, just not as optimal). If feedback that durations longer than a week is common then we can tune that, but it seemed like a safe bet for what I've seen.

The amortized penalty (cascading in a hierarchical timer wheel) is deferred to the executor, which by default is ForkJoinPool.commonPool(). That means even though it is cheap, it is hidden from user-facing requests by borrowing spare cpu cycles in a non-blocking fashion.

JMH benchmarks showed that the operations were very fast, e.g. at about a dozen nanoseconds to reschedule. Of course the Expiry is user code, but I'd expect that to usually be a cheap operation too.

That said, please do let me know if you observe any negative behaviors.