I have used LinkedHashMap with accessOrder true along with allowing a maximum of 500 entries at any time as the LRU cache for data. But due to scalability issues I want to move on to some thread-safe alternative. ConcurrentHashMap seems good in that regard, but lacks the features of accessOrder and removeEldestEntry(Map.Entry e) found in LinkedHashMap. Can anyone point to some link or help me to ease the implementation.
views:
396answers:
5
A:
Wrap the map in a Collections.synchronizedMap(). If you need to call additional methods, then synchronize on the map that you got back from this call, and invoke the original method on the original map (see the javadocs for an example). The same applies when you iterate over the keys, etc.
Aaron Digulla
2009-11-29 14:26:15
Aaron this will worsen my scalability issues. Since the update of the map would become serial in nature. ConcurrentHashMap has feature so that more than one can update the map at the same time.
DKSRathore
2009-11-29 14:32:15
ConcHM has some specific properties which don't map easily to LinkedHM (namely it allows to insert concurrently as long as the hash doesn't map to the same segment key). This optimization is not possible when you need to keep the insert order. You must decide which one is more important to you.
Aaron Digulla
2009-11-29 15:04:21
+3
A:
I did something similar recently with ConcurrentHashMap<String,CacheEntry>, where CacheEntry wraps the actual item and adds cache eviction statistics: expiration time, insertion time (for FIFO/LIFO eviction), last used time (for LRU/MRU eviction), number of hits (for LFU/MFU eviction), etc. The actual eviction is synchronized and creates an ArrayList<CacheEntry> and does a Collections.sort() on it using the appropriate Comparator for the eviction strategy. Since this is expensive, each eviction then lops off the bottom 5% of the CacheEntries. I'm sure performance tuning would help though.
In your case, since you're doing FIFO, you could keep a separate ConcurrentLinkedQueue. When you add an object to the ConcurrentHashMap, do a ConcurrentLinkedQueue.add() of that object. When you want to evict an entry, do a ConcurrentLinkedQueue.poll() to remove the oldest object, then remove it from the ConcurrentHashMap as well.
Update: Other possibilities in this area include a Java Collections synchronization wrapper and the Java 1.6 ConcurrentSkipListMap.
Jim Ferrans
2009-11-29 15:21:40
Your suggestion seems much like I need. It means I have some overhead of keeping other elements which will consume same size as that of set of the map. Anyhow this is fine for me.
DKSRathore
2009-11-29 16:04:28
+1
A:
Have you tried using one of the many caching solutions like ehcache? You could try using LinkedHashMap with a ReadWriteLock. This would give you concurrent read access.
Peter Lawrey
2009-11-29 16:35:29
A:
You mention wanting to solve scalability problems with a "thread-safe" alternative. "Thread safety" here means that the structure is tolerant of attempts at concurrent access, in that it won't suffer corruption by concurrent use without external synchronization. However, such tolerance does not necessarily help to improve "scalability". In the simplest -- though usually misguided -- approach, you'll try to synchronize your structure internally and still leave non-atomic check-then-act operations unsafe.
LRU caches require at least some awareness of the total structure. They need something like a count of the members or the size of the members to decide when to evict, and then they need to be able to coordinate the eviction with concurrent attempts to read, add, or remove elements. Trying to reduce the synchronization necessary for concurrent access to the "main" structure fights against your eviction mechanism, and forces your eviction policy to be less precise in its guarantees.
The currently accepted answer mentions "when you want to evict an entry". Therein lies the rub. How do you know when you want to evict an entry? Which other operations do you need to pause in order to make this decision?
seh
2009-11-30 00:35:42