directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel L├ęcharny <>
Subject Random thoughts about LRU Cache
Date Sat, 28 Apr 2012 11:58:00 GMT
Hi guys,

as I was conducting some perf tests yesterday and this morning, I found 
that the LRUCache.get(...) took around 14% of all the CPU, which is 
quite big.

There is nothing wrong with the current implementation though. It's 
pretty normal that when the data are cached, that at some point, it 
becomes ne of the major bottleneck. The alternative would be to fetch 
the serialized value from disk, and that would cost way more time.

I also digged the code to see where we can improve it, but it's pretty 

Basically (correct me if I'm wrong), we are looking for an element in a 
hash table, then we try to find the correct version, as the cache stores 
versionned elements, and then we 'touch' the element so that it won't be 
evicted fast.

Here are a few ideas I have had, some food for thoughts.

1) Do we need to touch the elements ?
the touch() method move the element from the middle of a circular linked 
list to the beginning of the list. This is not exactly a free operation. 
What if we simply update a flag with the latest version in this elemnt ? 
The eviction strategy would then be to select the elements that have the 
lower counter. Of course, that would imply we have to go through all the 
elemnts from time to time, and remove a set of them when kicking the 
eviction (This would be very similar to a garbage collection).

It's likely to be more efficient than a touch() done for every access.

2) Do we need to keep all the versions ?
When we fetch an element from the cache, in a LDAP context, we won't 
fetch it a second time. Never. That means we will use a different 
version than the previous one. So the question to keep versions in the 
cache is raised : what if we simply replace the element when some 
modification occurs ?

(just in case these versionned elements are needed in the context of an 
optimistic locking system, I wonder if those versionned cache are 
critical too, as the number of changes will in any case limited to a 
very few numbers of elements. But I may be wrong here...)

I any case, I do think that we should keep the current LRUCache as is 
and start thinkig about a better version - if any -for after 2.0. This 
is typically something a student might want to play with...

Thoughts ?

Emmanuel L├ęcharny

View raw message