A Simple LRU Cache in 5 lines
The applications usually need to cache information in memory. The most often used classes to do this in Java are HashMap and Hashtable. If you need to do any sophisticated caching, then you can use JBoss Cache, OSCache or EHCache. Even if you use an external caching system, you may still want to cache some information locally within an object just to have fast access. The problem with this approach is that, if you are not careful and do not control the size of this in-memory cache, then it may grow too big and affect the performance of your application.
A very simple solution to this problem is to set a maximum size for your in-memory cache and most preferably make it LRU (Least Recently Used). This way you will have a predictable memory utilization and only the items used recently will be kept in the cache.
Starting with JDK 1.4, a new (and very rarely used) collection class was added called LinkedHashMap. There are couple of benefits of using a LinkedHashMap:
- It is possible to preserve the order of items in the map. So, the order of iteration through the items is same as the order of insertion. A special constructor is provided for this purpose. This is very useful when you already have a sorted collection of data and you want to do some processing on it and return it as a
Map. Using aTreeMap(the only other map that allows iteration in a given order) is too expensive for this scenario. - It exposes a method
removeEldestEntry(Map.Entry)that may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map. This is what we are going to use to create a LRU cache.
Check out the following snippet for an example of simple LRU cache.
This code creates a simple LRU cache with maximum 50 entries. The magic happens during the creation of the LinkedHashMap where a boolean flag for access order is set to true and the method removeEldestEntry is overridden. Now, if you run the program, you can see that the cache size is fixed to 50 entries and the least recently used entries are removed from the map. It is possible to create a pruning thread to prune the map so you don’t always necessarily maintain the maximum number of entries.
Richard Rodger said,
November 28, 2006 @ 4:57 am
Wow. F**king cool as Tim would say. I’m going to be able to use this right away
Antonio said,
November 28, 2006 @ 7:11 am
That “public” method should be “protected”, I’m afraid!
For a shorter description see
http://blogs.sun.com/swinger/entry/collections_trick_i_lru_cache
Atif Khan said,
November 28, 2006 @ 8:36 am
Antonio,
The method need not be “protected” as you are allowed to increase the accessibility of a method in Java, hence “public” will work just as well. But, it does make sense to make it “protected”. I have made the change to the post.
Debasish Ghosh said,
November 28, 2006 @ 11:34 pm
How can we make this cache thread-safe ? LinkedHashMap is not thread-safe and one of the ways will be to use the synchronized wrappers from Collections. But to get improved concurrency it is recommended to use the new java.util.Concurrent stuff. But I do not think we can wrap LinkedHashMap with ConcurrentHashMap and have the same effect. Any thoughts ??
Kasper Nielsen said,
November 29, 2006 @ 7:16 am
There is no way to easily create an ConcurrentLRUCache. And if you really wanted to create a concurrent cache I don’t think LRU would be an optimal algorithm to use. You would much rather look for a modified versions of the CLOCK algorithm which can be maintained without (or at least very little) locking.
Atif Khan said,
November 29, 2006 @ 1:20 pm
It depends on how much of synchronization you need. If you only need the puts to be synchronized, you can create a synchronized block around with a lock. Obviously this will not result in the optimal solution as the state of item may change while the thread is waiting to insert a value since the gets are not synchronized. It all depends on what you really need and how critical is the cache for you.
Antonio said,
November 30, 2006 @ 12:42 pm
Synchronization? What about using the Collections.synchronizedMap()
function call?
That’s possibly the best way to synchronize the mCache?
Cheers,
Antonio
P.D.: Yep, changing it to “protected” is probably safer.
Atif Khan said,
November 30, 2006 @ 1:31 pm
Collections.synchronizedMap() will synchronize all the operations on the map. Also, it returns a new Map and all the subsequent operations should be performed on the returned map. That does not sound optimal in either case.
Antonio said,
December 7, 2006 @ 5:15 am
Hi Atif,
I was meaning something like this:
private Map mCache = Collections.synchronizedMap( new LinkedHashMap( etc ) );
Yes, all the operations should be performed on the synchronized map (as all are now with the existing mCache), and all operations on the map will be synchronized (which is what we want, I think, would be dangerous having only some of them synchronized).
Cheers,
Antonio
Atif Khan said,
December 7, 2006 @ 10:17 am
Antonio,
If you want all the operations to be synchronized, then definitely your solution will work. I was trying to avoid synchronizing the getters.
Arpan said,
April 13, 2007 @ 1:33 am
Nice one Can you help me I have similar kind of question.
1. I want to create a cache memory. If i have a class and its object is already existing then When i want to create a new instance it should not create it. It should return me from cache. It is to be implemented using hasmp.
Atif Khan said,
April 13, 2007 @ 5:10 pm
Arpan,
I think the example in my post should work for you. Could you explain what you need a little more? If all you want to do is to see if an object of a particular class type is not created, then create a new one and otherwise return from cache, then you can use the class name as the key and object as the value.
madhavi latha said,
January 25, 2008 @ 4:36 pm
Hi!
I would like to cache the data which is not often changed.may be once in a day i would like to refresh the cache.I need a simple caching example which I am planning to implement only for read operation.i.e select statement.I am using prepared statement and from there I have ResultSet.Can you please give me an example for putting all the data into cache.I am using JDBC.Please give me the detailed explanation of how to set the time of cache and how to get the data from cache and also how to examine whether the data is stale.Thank you very much in advance.
A Noted Path - Personal blog of Theodore Nguyen-Cao — Where inspiration meets aspiration » Blog Archive » Open Source and Caching Algorithms said,
January 27, 2008 @ 11:34 pm
[...] Least Recently Used (LRU) - the items that haven’t been accessed the longest get the boot first. This is implemented by keeping a timestamp for all items in the cache. Check out this simple LRU implementation. [...]
Open Source and Caching Algorithms - Zarang : Engineer! said,
January 28, 2008 @ 7:16 am
[...] Least Recently Used (LRU) - the items that haven’t been accessed the longest get the boot first. This is implemented by keeping a timestamp for all items in the cache. Check out this simple LRU implementation. [...]
Ben said,
March 10, 2009 @ 9:13 am
Atif,
I don’t think your solution will work. If the posts are synchronized but the gets are not, it is possible that a get will read a partially initialized value (i.e. the ordering of the constructor is not guaranteed.) You’ll need to wrap both methods, or give up the LRU behavior and use ConcurrentHashMap.