Friday, January 27, 2012

Quick and Simple LRU Cache in Java

Many times I have come across the need to cache values where using a fully fledged caching library like EHCache is an overkill. All I want is a bounded Map of key / value pairs with an LRU eviction policy. There are few options mentioned on the web and few common ones are

  • LinkedHashMap from JDK
Example from here. This is not really LRU but removing the oldest entry added to the map when it reaches the capacity. Also LinkedHashMap is not thread safe and as you can see in the example you need to wrap it with Collections.synchronizedMap which makes every get / put method to lock the map. This will not perform that well in a multi-threaded environment.

This uses LRU algorithm to evict objects but again is not thread safe and you need to wrap it in a synchronized map interface as in the LinkedHashMap's case which will incur a performance penalty on muti-threaded access.


This open source implementation is the one I finally settled on. It's easy to use as you can construct the cache in a single line, thread safe and doesn't seem to have a big performance hit due to locking in muti-threaded apps. According to the diagram on the main page, get and put performance seems to be comparable to ConcurrentHashMap from the JDK.


As you can see it's pretty simple to create a cache and you can use the put an get methods from the Map interface to add and retrieve entries from the cache

Don' forget to click the +1 button below if this post was helpful.

4 comments:

Kronzucker said...

I suggest you take a look at the google guava-libraries project. It provides a very good caching api and many components for different caching use cases ( http://code.google.com/p/guava-libraries/)

Kind regards,
Georg

MEWG said...

Thanks for the tip. I did take a quick look at guava and definitely seems to provide lot more features. Also according to the ConcurrentLinkedHashMap page, it has been integrated into Guava.

For my current project I wanted something simple so decided to stick with plain ConcurrentLinkedHashMap.

Ben Manes said...

Guava's caching (CacheBuilder, formerly MapMaker) are derived from my work in CLHM. There are some interesting technical differences where CLHM has better concurrency behavior by not relying on segment locks. Hopefully a final marriage will occur when Doug Lea starts a JDK8 implementation.

Guava is the long-term home, while CLHM was perhaps that researchy project to scratch an itch. Both are used heavily in large production environments, so either choice is good (e.g. CLHM is used by Cassandra).

Cheers,
Ben
(author of CLHM)

P.S. Thanks for the plug, glad that you're happy with it!

MEWG said...

Thanks Ben for taking time to comment and giving a little bit more details about the future of CLHM.

I am actively using CLHM in a couple of projects since I wrote this blog entry and yes I have been pretty happy with the library. Keep up the good work.