Fast Flexible Efficient In Memory Java LRU cache

In this post I will share the ideas and code for my Java LRU cache implementation.
My requirements were:

• Bounded cache -- the number of maximum entries is bounded.
• LRU cache -- eviction is done to the Least Recently Used item first.
• Low Memory footprint -- since each entry can consume unbounded amounts of memory the cache should holds its values using WeakReference, this makes it possible for the cache to evict elements even when the cache is not full when memory is short.
• Minimized locking -- the cache should not be locked when an entry is searched, only the searched entry can be locked.
• Minimized computation -- in case of multiple threads searching for the same key, the computation of the value should be done only once.

We will not insert the values to the cache explicitly, instead we will define the Compute Interface that will be called to compute missing values and fill the cache when needed.





The Compute interface is very similar to Java Callable interface. The only difference is that each call to compute receives the key and returns its value.
The Cache constructor receives 3 parameters:

• A Compute instance -- computes the values for objects that are not in the cache.
• An ExecutorService -- executes the computation of missing values (the call to compute)
• The size of the LRU cache -- the maximum number of entries that can be kept in this cache.

The cache itself built using 3 building blocks provided by Java:

• LinkedHashMap -- Hash table and linked list implementation of the Map interface, with predictable iteration order.
• Future -- an interface that represents the result of an asynchronous computation.
• And SoftReference --  which are cleared at the discretion of the garbage collector in response to memory demand.

We use SoftValue that is a subclass of Java SoftReference to hold the values. The reason is that we wish to have the value removed on memory shortage and we need the keys of the values that were removed because we need to clear the keys from the map.
Here is the code of SoftValue:





One more Interface the cache is using is the ExceptionStrategy, it is used to decide what to do when the call to compute(key) throws an Exception, the 2 options is to keep the mapping in the map to discard this entry (when the exception may be temporary,  for example  network  exception ).
Here is the source of ExceptionStrategy:

When a call to compute results in Exception the cache invoke it's instance of ExceptionStrategy removeEntry method with the key and the Exception, if removeEnty returns false the pair is kept in the cache, otherwise it does not and the next call to cache.get(key) will try to compute the value for key again.

For example the function alwaysRetain, a factory method that returns an ExceptionStrategy that always keep the mapping of an Exception in the cache can be define as:

We are now ready to take a closer look at the Cache constructor

The important part is the definition of the internal map on line 5, the map is defined as mapping from the key to a SoftValue that holds the key and a Future of the value, possibly an un-computed value.

We used the LinkedHashMap constructor that specify the accessOrder of the map as true so that get(key) will mark key as recently used as well as put(key).

The removeEldestEntry is called on each put. its result determines if the eldest entry should be removed from the map or not.

Neutrally the most used method of the cache is the get method, we'll now go over it's code:

We can see in line 5 the usage of exceptionStrategy to decide how to deal with exceptions.

The method getTask(key) in line 3 returns a Future to the computation of this entry and the computation itself is done only at the call to get() (last call in line 3).

Here is the code for getTask:

Since getTask only returns Future of the value (it does not compute the value) it can be synchronized because it's execution time is not related to the compute execution time.
On line 2 we see a call to processQueue this method removes from the map all the entries that their value was collected by the GC. we will have a look at it in short time.

Next the Future for the key is searched in the map and in case it is there it is returned (line 8),  in case there is no Future for this key a new one is created by submitting a computation to the ExecutorService (line 11), the new Future is then wrapped with SoftValue to enable the gc to reclaim this value in case of memory shortage, inserted into the map and returned as the result.

It is important to notice that in this case the compute was not called yet, it will be called only when the Future's get method will be first invoked.

The usage of  ExecutorService in this case give us the flexibility to control the number of threads that will  be used to compute values at any given time.

For example by passing  Executors.newFixThreadPoolExecutor(2) to the Cache we limit the number of concurrent calls to compute to 2, note that if we wish to call the compute on the user thread we need to write our own DirectExcutorService.

Next we will look at the processQueue method:

This method is looping over the entries that were reclaim by the GC and remove them from the map.

Here is the binary version of the Cache and here is the zip file that includes all the sources with the tests and the ant build file, or you can get all the sources from github.