[concurrency-interest] Concurrent approximate LRU?

Sanne Grinovero sanne.grinovero at gmail.com
Sat Nov 7 06:28:18 EST 2009

Hi Bryan,
I don't know the details of the implementation but Infinispan is doing
something similar; it's LGPL, so you might want to have a look in the
sources or ask to in the forums: www.jboss.org/infinispan
It implements "ConcurrentHashMap" so it should be straight-forward to drop in.
Especially related to your use case: have a look at the Hibernate
second level cache implementation based on Infinispan.


2009/10/21 Bryan Thompson <bryan at systap.com>:
> Hello,
> We have a database with many different backing stores all of which compete to buffer ram in a shared LRU cache policy.  We have implemented this using an outer concurrent hash map providing indirection to a collection of inner hash maps (we use LinkedHashMap here for better performance on its iterator, but we do not use its ability to impose an LRU ordering because the order must be shared across all inner cache instances).  The keys are Long's.  The values are elements in a double-linked list.  If there is an LRU eviction then the record is evicted from the inner hash map corresponding to the store.  This spreads out the memory constraint across the backing stores based on access.
> The problem with this approach is that the double-linked list is not thread-safe so we have to obtain a lock when testing the cache put adding to the cache and hold it across that operation.  This is about a 10% performance penalty involved.
> Unfortunately, the ConcurrentHashMap does not allow us to impose an access policy, or we could use a single ConcurrentHashMap instance and use the store's identifier and the Long address of the record as a composite key and all would be good.
> I am wondering if there is a way to maintain an approximate LRU ordering across the elements in these different caches?
> Thanks in advance,
> -bryan
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

More information about the Concurrency-interest mailing list