Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am going to write a bachelor's science work on caching strategies and really, can't find any links to specifications or full descriptions of some of them. Only something like summaries from wikipedia. Please, help with some links on LRU, MRU caching and new-one - Clock Pro.


Thanks a lot. All links are very useful for me. The purpose of work - is to compare different cache strategies to get more effiency. It based on WebApplication with ejb 2.0, so algorithm's will be implemented there, espesially in ejbLoad() and ejbFindByPrimarKey(). Also, one of aspects of this application - it will use not common scheme of tables in database - it based on metamodel. So, if you had any experience on this topic, i would be grateful to take some of your knowledge)

share|improve this question
2  
Note that SE is not a forum. You should edit your original questions to thank people. Also, don't forget to up-vote the answers that you find useful and vote the one that you like most. –  faif Dec 14 '11 at 19:45
add comment

5 Answers

Those three strategies (LRU, MRU, and Clock) are well-known and heavily used. You should be able to find many papers on sites like citeseer and pseuco-code in textbooks similar to what @alexander-galkin recommends. If you want to do some real research about newer (and probably more efficient) strategies like ARC, you should consult your university library. They will tell you how to get free access to the latest research papers which are normally not publicly available.

share|improve this answer
    
sorry, in Russia we dont have those ones)) –  golgofa Dec 14 '11 at 22:58
add comment

There is no good or bad algorithm. You need to take a look at your statistics:

  1. How many times you need the same value?
  2. How many times you require another value?
  3. How many different values you have?
  4. How much bigger is your data?
  5. etc

Without this stats you can't choose wisely.

share|improve this answer
add comment

Even though Wikipedia is a good place to start your research, it shouldn't be the primary source of information, especially if you are going to write thesis on this topic.

I would recommend to take some fundamental books on distributed computing, like the one from Tannenbaum. You will find in-depth explanations for many caching strategies there.

share|improve this answer
add comment

Maybe you could take a look at the source code of EhCache, or JCS ? EhCache provides LRU, LFU and FIFO eviction policies.

Sure, these are not specifications, or full-text descriptions of caching strategies, but at least you may see how they are implemented.

Edit: googling up a little bit on the subject, I found the following free papers:

Finally, maybe you could search with Google Scholar and try to find more suitable academic papers?

share|improve this answer
    
thanks, it was useful for me –  golgofa Dec 14 '11 at 23:02
add comment

CLOCK-Pro combines best worlds of CLOCK and LIRS. Using three different page types hot and resident cold and non-resident cold pages. This allows flush resistant caching, which is always a problem with LRU. Clock-Pro adapts between hot and cold pages automatically based on request profiles. Compared to LRU Clock-Pro improves hit ratio most when hit rate is relatively low, when hit rate approaches 100% difference is diminished but in that case Clock-Pro is faster than LRU cache.

Compared to LRU Clock-Pro achieves about 30% hit ratio improvement compared to LRU on data sets which achieve about 30% hit ratio and are based on real world distribution aka Pareto distribution. You'll find my charts from the link.

As you might have found out the paper describing it wasn't exactly easy or straight forward to understand, even if you have been working with cache eviction algorithms earlier.

Here's simple and easy to understand Python implementation of CLOCK-Pro (PyClockPro), which also can be used as decorator function cache, efficiently replacing lru_cache from functools.

Btw. ARC is patented and CLOCK-Pro offers same benefits and is faster than ARC. There is also CAR cache, which is clock based version of ARC.

References: LIRS caching algorithm @ Wikipedia and it's also good idea to see original CLOCK-Pro design paper. (No direct linking because, more link's aren't allowed.)

share|improve this answer
1  
Please consider providing a summary of the information provided within the link as links go stale and the value of your answer would be lost. –  GlenH7 Mar 3 '13 at 15:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.