How does Guava expire entries in its CacheBuilder?
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?
Answer
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.