How to implement a most-recently-used cache

Question

What would be the best way to implement a most-recently-used cache of objects?

Here are the requirements and restrictions...

• Objects are stored as key/value Object/Object pairs, so the interface would be a bit like Hashtable get/put
• A call to 'get' would mark that object as the most recently used.
• At any time, the least recently used object can be purged from the cache.
• Lookups and purges must be fast (As in Hashtable fast)
• The number of Objects may be large, so list lookups are not good enough.
• The implementation must be made using JavaME, so there is little scope for using third-party code or neat library classes from the standard Java libraries. For this reason I'm looking more for algorithmic answers rather than recommendations of off-the-peg solutions.

Noami

Answer 1

Java Collections provide LinkedHashMap out of the box, which is well-suited to building caches. You probably don't have this in Java ME, but you can grab the source code here:

http://kickjava.com/src/java/util/LinkedHashMap.java.htm

If you can't just copy-paste it, looking at it should get you started implementing one for inclusion in your mobile app. The basic idea is just to include a linked list through the map elements. If you keep this updated whenever someone does put or get, you can efficiently track access order and use order.

The docs contain instructions for building an MRU Cache by overriding the removeEldestEntry(Map.Entry) method. All you really have to do is make a class that extends LinkedHashMap and override the method like so:

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
   return size() > MAX_ENTRIES;
}

There's also a constructor that lets you specify whether you want the class to store things in order by insertion or by use, so you've got a little flexibility for your eviction policy, too:

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)

Pass true for use-order and false for insertion order.

Envoi

Score! (I was just coming to post the same thing.) – Parturifacient

This looks perfect for something I had been wanting to implement as well - thanks! – Levin

false for mru and true for lru – Adriene

SUN PROPRIETARY/CONFIDENTIAL – Hagen

the described solution will be a LRU cache not MRU. – Meadowsweet

Answer 2

A ConcurrentLinkedHashMap is difficult to construct, due to the locking requirements. A LinkedHashMap with a lock is straightforward, but not always performant. A concurrent version would attempt to reduce the amount of locking, either by lock splitting or ideally making CAS operations to make locking very cheap. If the CAS operations ever do become expensive, then similarly bucket splitting can be helpful. As an LRU requires writes for every access operation, and uses a doubly-linked list, this is very tricky to implement with pure CAS operations. I've attempted it, but I need to continue to mature my algorithm. If you search for ConcurrentLinkedHashMap, you'll see my project page...

If Java ME doesn't support CAS operations, which I'd expect to be true, then basic synchronization is all you can do. This is probably good enough with a LHM, given that I've only seen performance problems at high thread count on the server-side. So +1 to the answers above.

Fruit

Ben: How come there is no ConcurrentLinkedHashMap in the Java Collections API or in Google Collections? Can com.google.common.collect.CustomConcurrentHashMap.Builder help? Also your project is nice. Edit your answer to link to it. – Harangue

Julien: CCHM is very new, not flexible enough, and seems to be a rewrite of their ReferenceMap in reaction to JBoss' CRHM which is in Java-7. It seems to be mostly a customized CHM. We had a use-case where locking was killing us, so I only toyed with the idea of lock splitting and tried CAS instead. – Fruit

Answer 3

Why implement something already implemented? Use Ehcache.

However, if third-party libraries are totally out of the question, I guess you are looking to implement a data structure which looks something like this:

• Basically is a HashMap (extends HashMap<Object, Object> if you will)
• Each value in the Map points to an object in a sorted list, based on which is most used.
• Objects recently used are added to the head of the list - O(1)
• Purging least-recently used means truncating the end of the list - O(1)
• Still gives you Map lookups, but still keeps recently-used items first...

Gao

Because of my last point... this must be made to run using JavaME on a mobile phone. – Noami

The problem in that algorithm is that although you can look up the value in the hashmap quickly, you still need to look it up again in the list and move it to the head. – Noami

... although whilst writing that, I suddenly realised that the value object in the hashmap can be a list node object that can be moved to the list head, rather than the actual value object itself. Yay :) – Noami

Answer 4

Another approach may be to take a look at section 5.6 in Java Concurrency in Practice by Brian Goetz: "Building an efficient, scalable result cache". Take a look at the Memoizer, although you may have to customize it for your purposes.

As an aside, what I cannot figure out is why Java does not have a ConcurrentLinkedHashMap out of the box. This data structure would be very helpful for building a cache.

Harangue