Please don't say EHCache or OSCache, etc. Assume for purposes of this question that I want to implement my own using just the SDK (learning by doing). Given that the cache will be used in a multithreaded environment, which datastructures would you use? I've already implemented one using LinkedHashMap and Collections#synchronizedMap, but I'm curious if any of the new concurrent collections would be better candidates.
UPDATE: I was just reading through Yegge's latest when I found this nugget:
If you need constant-time access and want to maintain the insertion order, you can't do better than a LinkedHashMap, a truly wonderful data structure. The only way it could possibly be more wonderful is if there were a concurrent version. But alas.
I was thinking almost exactly the same thing before I went with the LinkedHashMap
+ Collections#synchronizedMap
implementation I mentioned above. Nice to know I hadn't just overlooked something.
Based on the answers so far, it sounds like my best bet for a highly concurrent LRU would be to extend ConcurrentHashMap using some of the same logic that LinkedHashMap
uses.
Have a look at ConcurrentSkipListMap. It should give you log(n) time for testing and removing an element if it is already contained in the cache, and constant time for re-adding it.
You'd just need some counter etc and wrapper element to force ordering of the LRU order and ensure recent stuff is discarded when the cache is full.
I'm looking for a better LRU cache using Java code. Is it possible for you to share your Java LRU cache code using
LinkedHashMap
andCollections#synchronizedMap
? Currently I'm usingLRUMap implements Map
and the code works fine, but I'm gettingArrayIndexOutofBoundException
on load testing using 500 users on the below method. The method moves the recent object to front of the queue.get(Object key)
andput(Object key, Object value)
method calls the abovemoveToFront
method.This is round two.
The first round was what I came up with then I reread the comments with the domain a bit more ingrained in my head.
So here is the simplest version with a unit test that shows it works based on some other versions.
First the non-concurrent version:
The true flag will track the access of gets and puts. See JavaDocs. The removeEdelstEntry without the true flag to the constructor would just implement a FIFO cache (see notes below on FIFO and removeEldestEntry).
Here is the test that proves it works as an LRU cache:
Now for the concurrent version...
package org.boon.cache;
You can see why I cover the non-concurrent version first. The above attempts to create some stripes to reduce lock contention. So we it hashes the key and then looks up that hash to find the actual cache. This makes the limit size more of a suggestion/rough guess within a fair amount of error depending on how well spread your keys hash algorithm is.
Here is the test to show that the concurrent version probably works. :) (Test under fire would be the real way).
This is the last post.. The first post I deleted as it was a LFU not an LRU cache.
I thought I would give this another go. I was trying trying to come up with the simplest version of an LRU cache using the standard JDK w/o too much implementation.
Here is what I came up with. My first attempt was a bit of a disaster as I implemented a LFU instead of and LRU, and then I added FIFO, and LRU support to it... and then I realized it was becoming a monster. Then I started talking to my buddy John who was barely interested, and then I described at deep length how I implemented an LFU, LRU and FIFO and how you could switch it with a simple ENUM arg, and then I realized that all I really wanted was a simple LRU. So ignore the earlier post from me, and let me know if you want to see an LRU/LFU/FIFO cache that is switchable via an enum... no? Ok.. here he go.
The simplest possible LRU using just the JDK. I implemented both a concurrent version and a non-concurrent version.
I created a common interface (it is minimalism so likely missing a few features that you would like but it works for my use cases, but let if you would like to see feature XYZ let me know... I live to write code.).
You may wonder what getSilent is. I use this for testing. getSilent does not change LRU score of an item.
First the non-concurrent one....
The queue.removeFirstOccurrence is a potentially expensive operation if you have a large cache. One could take LinkedList as an example and add a reverse lookup hash map from element to node to make remove operations A LOT FASTER and more consistent. I started too, but then realized I don't need it. But... maybe...
When put is called, the key gets added to the queue. When get is called, the key gets removed and re-added to the top of the queue.
If your cache is small and the building an item is expensive then this should be a good cache. If your cache is really large, then the linear search could be a bottle neck especially if you don't have hot areas of cache. The more intense the hot spots, the faster the linear search as hot items are always at the top of the linear search. Anyway... what is needed for this to go faster is write another LinkedList that has a remove operation that has reverse element to node lookup for remove, then removing would be about as fast as removing a key from a hash map.
If you have a cache under 1,000 items, this should work out fine.
Here is a simple test to show its operations in action.
The last LRU cache was single threaded, and please don't wrap it in a synchronized anything....
Here is a stab at a concurrent version.
The main differences are the use of the ConcurrentHashMap instead of HashMap, and the use of the Lock (I could have gotten away with synchronized, but...).
I have not tested it under fire, but it seems like a simple LRU cache that might work out in 80% of use cases where you need a simple LRU map.
I welcome feedback, except the why don't you use library a, b, or c. The reason I don't always use a library is because I don't always want every war file to be 80MB, and I write libraries so I tend to make the libs plug-able with a good enough solution in place and someone can plug-in another cache provider if they like. :) I never know when someone might need Guava or ehcache or something else I don't want to include them, but if I make caching plug-able, I will not exclude them either.
Reduction of dependencies has its own reward. I love to get some feedback on how to make this even simpler or faster or both.
Also if anyone knows of a ready to go....
Ok.. I know what you are thinking... Why doesn't he just use removeEldest entry from LinkedHashMap, and well I should but.... but.. but.. That would be a FIFO not an LRU and we were trying to implement a LRU.
This test fails for the above code...
So here is a quick and dirty FIFO cache using removeEldestEntry.
FIFOs are fast. No searching around. You could front a FIFO in front of an LRU and that would handle most hot entries quite nicely. A better LRU is going to need that reverse element to Node feature.
Anyway... now that I wrote some code, let me go through the other answers and see what I missed... the first time I scanned them.
LinkedHashMap
is O(1), but requires synchronization. No need to reinvent the wheel there.2 options for increasing concurrency:
1. Create multiple
LinkedHashMap
, and hash into them: example:LinkedHashMap[4], index 0, 1, 2, 3
. On the key dokey%4
(orbinary OR
on[key, 3]
) to pick which map to do a put/get/remove.2. You could do an 'almost' LRU by extending
ConcurrentHashMap
, and having a linked hash map like structure in each of the regions inside of it. Locking would occur more granularly than aLinkedHashMap
that is synchronized. On aput
orputIfAbsent
only a lock on the head and tail of the list is needed (per region). On a remove or get the whole region needs to be locked. I'm curious if Atomic linked lists of some sort might help here -- probably so for the head of the list. Maybe for more.The structure would not keep the total order, but only the order per region. As long as the number of entries is much larger than the number of regions, this is good enough for most caches. Each region will have to have its own entry count, this would be used rather than the global count for the eviction trigger. The default number of regions in a
ConcurrentHashMap
is 16, which is plenty for most servers today.would be easier to write and faster under moderate concurrency.
would be more difficult to write but scale much better at very high concurrency. It would be slower for normal access (just as
ConcurrentHashMap
is slower thanHashMap
where there is no concurrency)Here's my own implementation to this problem
simplelrucache provides threadsafe, very simple, non-distributed LRU caching with TTL support. It provides two implementations:
You can find it here: http://code.google.com/p/simplelrucache/
LRU Cache can be implemented using a ConcurrentLinkedQueue and a ConcurrentHashMap which can be used in multithreading scenario as well. The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. When an element exists in the Map, we can remove it from the LinkedQueue and insert it at the tail.