The LRU Cache

In truth, all caches created using the Cache class are LRU caches. If you need to use the other caching properties without restricting the number of elements, give it a huge size or use the default constructor.

// Once 50 elements are cached the least recently accessed will be discarded.
Cache cache = new Cache( 50);

 

Just think of a linked list. When you add an item it's added to the end of the list. When you access an item it's unlinked from its current location and linked again at the end. Therfore if you add an item to a list with the maximum number of entries, then the item at the start of the list is removed, close called if closeable, and discarded.

Note that because the Cache class is used for more than just simple LRU caches, the clean operation does not happen synchronously. An item is added on request then the method returns to the caller. This makes the cache very fast. A lower priority background thread will pick up oversized caches, closing and removing least-recently-used items that aren't currently locked.

The LRU cache is commonly used to cache objects in memory that would otherwise require a more expensive retrieval procedure. The Adept browser code, for example, uses a LRU cache to hold static elements such as HTML files and images. This way they are loaded from disk once and served from memory if they are popular enough to always be at the end of the list. Items that are used infrequently are more likely to be discarded and require a disk retrieval to get back. Note that the browser caches static content in a similar way. In addition, the Adept server cache will effect files requested from multiple browsers.

Using a LRU cache, rather than storing the item in a Map, allows the developer to control memory usage.

If there's any possibility that an item being cached may change at the original source, use a trigger or time sensitive cache as well as the LRU method.

Next time we'll talk about Time Sensitive Caches.

Caching - a Commonly Used Optimisation Method

Every enterprise level application implements caching somewhere. Even loading static class-level fields when the class is first loaded is a form of caching.

The Adept Library Cache class is designed to implement pools, time sensitive and least recently used caches. Since each of these similar structures are used for completely different purposes, they are the subject of an article each. In summary:

• LRU (Last Recently Used) size limited cache are commonly used for files or data records. Once the cache size is exceeded the least recently used items are closed to make room for new ones. This way commonly used items are retrieved from memory.
• Time sensitive caching. Files or data that change infrequently can be instructed to be reloaded if they exceed a certain cache age. This is a method often combined with LRU caching. Files or data may change overnight, so having a maximum age of 12 hours guarantees that they are re-read when necessary but provide optimal retrieval at other times. Set fixedExpiry on so that the entry expires no matter how popular it is.
• Time limited caching. Sessions are a good example. Set the maximum size to large enough that it won't be reached in normal usage. It can be used to protect memory from a run-away situation. Call the ageingCache() method to tag the cache as holding items that expire. Even if the LRU limit is exceeded, non-expired items will not be deleted.
• Pools are specialised caches that are not retrieved by key. Free items are retrieved from the cache and locked for use. File handle, database connections and similar shared resources can be pooled to save creation time. Pools will frequently use the time-limiting features to make sure that unused items are closed rather than hanging around forever. Size limiting can also be used to enforce resource usage limitations. Make sure fixedExpiry is set for LRU cleaning to occur.

The Adept Cache class is based on a LRU algorithm. This method allows a cache to be limited to a specific size. Once that size has been exceeded the item that has not been used for the longest period is discarded.

Cache Entries

Entries can be any form of Java POJO, or classes that have the Closeable interface. In the latter case, the classes close() method will be called when the item has been discarded from the cache for whatever reason.

Entry Lifetimes

Because cache items can hold non-memory resources (such as connections), any item with a Closeable interface retrieved must be unlocked before it can be eligible for removal from the cache. For this reason, take great care when using caches to ensure that a cache entry is unlocked in an inescapable stream of code after the retrieval. This usually means doing it immediately or wrapping a retrieval in a try/finally block with the unlock in the finally. I cannot emphasize enough that this practice should never be missed, else you will have resource leaks. For ordinary data that does not need closing, ignore the locking and unlocking features entirely and treat a cache as you would a Map or any other generic container.

MyData data = null;
try
  {
    data = cache.get( key);
    ...
  }
finally
  {
    cache.unlock( data);
  }

 

General Caching Operations

Once a cache is created, items can be entered with add(), retrieved with get() and removed with delete(). Adding and retrieval is by key, and said key can be any object or an int primitive. For caches containing closeable items, the delete can fail if they are currently locked. The cache is synchronised so it can be accessed by multiple threads.

There will be other articles in the specific forms of cache listed above.