Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature request: unconditional expiration of entries based on absolute age (time since load) #141

Closed
oakad opened this issue Feb 1, 2017 · 8 comments

Comments

@oakad
Copy link

oakad commented Feb 1, 2017

Presently, the cache supports "TTL after access" and "TTL after write" expiration policies. In some cases, however, it is handy to expire objects based on their absolute age - essentially "TTL after load" (one usage example of this policy are authenticated network sessions which must expire unconditionally even if client keeps sending data). Considering that this policy is probably easier to implement that the 2 already existing expiration policies, may the Caffeine benefit by providing it as well?

@ben-manes
Copy link
Owner

I'd prefer to leave this to a pending feature, variable expiration. That is more complicated to do correctly, but carries a much higher power-to-weight ratio. Otherwise we'd be stuck trying to provide one-off solutions for the easy problems, which adds usage and implementation complexity, with little overall gain.

I have a general idea for how to implement variable expiration in O(1) time by using a timer wheel variant. That's nicer than the common solutions of requiring either a O(lg n) priority queue or relying on a maximum size to discard dead entries. But I haven't prototyped it, so unfortunately its on the backlog at the moment.

@oakad
Copy link
Author

oakad commented Feb 2, 2017

Suddenly I realized than issue #70 talks about the same thing, so sorry for double posting.

Could you kindly point me to the description of "variable expiration" feature (if it exists in some written form, that is)? I have looked around but could not quite establish what exactly you mean by that.

@ben-manes
Copy link
Owner

In memcached it might be set(key, value, duration, TimeUnit), where key1 and key2 can have expire at different intervals. That makes sense for a shared cluster, e.g. a session token has a 1 hour expiration that's being refreshed constantly, whereas a password reset token might be 48 hours.

Memcached does the above by setting an expiration timestamp. When an entry expires it fakes a miss and the entry eventually gets removed due to a LRU eviction. The alternative is an O(lg n) priority queue, but that's expensive to maintain. The timer wheel approach is an alternative used by kernels that I'd like to explore.

@ben-manes
Copy link
Owner

See these slides for a talk I'll be giving soon. There is a section showing a hierarchical timer wheel.

@oakad
Copy link
Author

oakad commented Feb 3, 2017

Thank you, most interesting.

ben-manes added a commit that referenced this issue May 1, 2017
The expiration time can now be customized on a per entry basis to allow
them to expire at different rates. This is acheived in O(1) time using
a timer wheel and evaluating using the new Expiry interface. This
setting can be combined with refreshAfterWrite, but is incompatible
with the fixed expiration types (expireAfterAccess, expireAfterWrite).

While the test suite was updated to incorporate this new configuration
option, there is still remaining work before this should be released.
 - New tests specific to this feature (such as exceptional conditions)
   have not yet been written
 - Incorporate a data integrity check for the timer wheel into the
   validation listener
 - Inspection through cache.policy()
 - JCache integration
 - Documentation
@ben-manes
Copy link
Owner

This feature is implemented, but additional tests are needed before release. You would be able to perform this expiration by using,

Caffeine.newBuilder().expiry(new Expiry<K, V> {
  public long expireAfterCreate(K key, V value, long currentTime) {
    // return expiration duration, e.g. 5 minutes
  }
  public long expireAfterUpdate(K key, V value, long currentTime, long currentDuration) {
    return currentDuration
  }
  public long expireAfterRead(K key, V value, long currentTime, long currentDuration) {
    return currentDuration;
  }
}).build()

@oakad
Copy link
Author

oakad commented May 1, 2017

This is most impressive (TimerWheel in particular).
Thank you for your effort.

ben-manes added a commit that referenced this issue May 1, 2017
The expiration time can now be customized on a per entry basis to allow
them to expire at different rates. This is acheived in O(1) time using
a timer wheel and evaluating using the new Expiry interface. This
setting can be combined with refreshAfterWrite, but is incompatible
with the fixed expiration types (expireAfterAccess, expireAfterWrite).

While the test suite was updated to incorporate this new configuration
option, there is still remaining work before this should be released.
 - New tests specific to this feature (such as exceptional conditions)
   have not yet been written
 - Incorporate a data integrity check for the timer wheel into the
   validation listener
 - Inspection through cache.policy()
 - JCache integration
 - Documentation
ben-manes added a commit that referenced this issue May 1, 2017
The expiration time can now be customized on a per entry basis to allow
them to expire at different rates. This is acheived in O(1) time using
a timer wheel and evaluating using the new Expiry interface. This
setting can be combined with refreshAfterWrite, but is incompatible
with the fixed expiration types (expireAfterAccess, expireAfterWrite).

While the test suite was updated to incorporate this new configuration
option, there is still remaining work before this should be released.
 - New tests specific to this feature (such as exceptional conditions)
   have not yet been written
 - Incorporate a data integrity check for the timer wheel into the
   validation listener
 - Inspection through cache.policy()
 - JCache integration
 - Documentation
ben-manes added a commit that referenced this issue May 1, 2017
The expiration time can now be customized on a per entry basis to allow
them to expire at different rates. This is acheived in O(1) time using
a timer wheel and evaluating using the new Expiry interface. This
setting can be combined with refreshAfterWrite, but is incompatible
with the fixed expiration types (expireAfterAccess, expireAfterWrite).

While the test suite was updated to incorporate this new configuration
option, there is still remaining work before this should be released.
 - New tests specific to this feature (such as exceptional conditions)
   have not yet been written
 - Incorporate a data integrity check for the timer wheel into the
   validation listener
 - Inspection through cache.policy()
 - JCache integration
 - Documentation
@ben-manes
Copy link
Owner

Released 2.5.0

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants