29

I want to use a CacheBuilder, as recommended here:

Java time-based map/cache with expiring keys

However I don't understand when Guava knows to expire entries.

How does Guava do it and what performance cost does it incurr?

Community
  • 1
  • 1
Cedric Martin
  • 5,945
  • 4
  • 34
  • 66

1 Answers1

61

Guava team member here.

The Guava Cache implementation expires entries in the course of normal maintenance operations, which occur on a per-segment basis during cache write operations and occasionally during cache read operations. Entries usually aren't expired at exactly their expiration time, just because Cache makes the deliberate decision not to create its own maintenance thread, but rather to let the user decide whether continuous maintenance is required.

I'm going to focus on expireAfterAccess, but the procedure for expireAfterWrite is almost identical. In terms of the mechanics, when you specify expireAfterAccess in the CacheBuilder, then each segment of the cache maintains a linked list access queue for entries in order from least-recent-access to most-recent-access. The cache entries are actually themselves nodes in the linked list, so when an entry is accessed, it removes itself from its old position in the access queue, and moves itself to the end of the queue.

When cache maintenance is performed, all the cache has to do is to expire every entry at the front of the queue until it finds an unexpired entry. This is straightforward and requires relatively little overhead, and it occurs in the course of normal cache maintenance. (Additionally, the cache deliberately limits the amount of work done in a single cleanup, minimizing the expense to any single cache operation.) Typically, the cost of cache maintenance is dominated by the expense of computing the actual entries in the cache.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413
  • +1... Thanks a lot for the explanation and thanks a lot for Guava. The linked list "trick" is very neat! I'm installing Guava right away: thanks to your detailed answer I'm now sold on Guava : ) – Cedric Martin Apr 13 '12 at 17:41
  • 3
    Charles Fry gave a great presentation on MapMaker / CacheBuilder at Strange Loop. The talk is available [on InfoQ](http://www.infoq.com/presentations/Concurrent-Caching-at-Google) – Etienne Neveu Apr 13 '12 at 22:55
  • would using a Datastructure other than LinkedList would somehow help improve the eviction process? – asgs Jul 03 '16 at 19:39
  • That's complicated because you need to actually specify the alternative. Just swapping in an `ArrayList`, for example, would hurt performance: the operations you need in the data structure as described are random removes from inside the recency list, which would be O(n) for ArrayList but O(1) for a linked list because you already have a pointer to the entry. – Louis Wasserman Jul 03 '16 at 19:41
  • `When cache maintenance is performed` - Interested to know when does it actually get triggered, is it on access of an expired entry or access of some random number of entries or periodic (maybe by maintaining a last cleanup time)? – mickeymoon Mar 21 '23 at 15:48
  • @mickeymoon: "during cache write operations and occasionally during cache read operations" – Louis Wasserman Mar 21 '23 at 19:11