Intro To Caching, Caching Algorithms And Caching Frameworks, Part 2

Tuesday, January 13, 2009

Intro to Caching,Caching algorithms and caching frameworks part 2 Introduction: In this part we are going to show how to implement some of the famous replacement algorithms as we mentioned in part 1, the code in this article is just for demonstration purpose which means you will have to do some extra effort if you want to make use of it in your application (if you are going to build your own implementation and wont use any caching frameworks)

The Leftover policy: After programmer 1 read the article he proceeded to review the comments on this article, one of these comments were talking about leftover policy, which is named Random Cache

Random Cache: I am random cache, I replace any cache entry I want, I just do that and no one can complain about that, you can say the unlucky entry, by doing this I remove any overhead of tracking references or so, am better than FIFO policy, in some cases I perform even better than LRU but in general LRU is better than me.

It is comment time: While programmer 1 was reading the rest of the comments, he found very interesting comment about implementation of some of the famous replacement policies, actually it was a link to the commenter site which has the actual implementation so programmer 1 clicked the link and here what he got:

Meet the Cache Element: public class CacheElement { private Object objectValue; private Object objectKey; private int index; private int hitCount; .

. // getters and setters . }

This is the cache entry which will use to hold the key and the value; this will be used in all the cache algorithms implementation

Common Code for All Caches: public final synchronized void addElement(Object key,Object value) { int index; Object obj; // get the entry from the table obj = table.get(key); // If we have the entry already in our table then get it and replace only its value. if (obj != null) { CacheElement element; element = (CacheElement) obj; element.setObjectValue(value); element.setObjectKey(key); return; } }

The above code will be common for all our implementation; it is about checking if the cacheElemnet already exists in our cache, if so then we just need to place its value and we don t need to make anything else but what if we didn t find it ? Then we will have to dig deeper and see what will happen below.

The Talk Show: Today s episode is a special episode , we have special guests , they are in fact compotators we are going to hear what everyone has to say but first lets introduce our guests: Random Cache, FIFO Cache Let s start with the Random Cache.

Meet Random Cache implementation:

public final synchronized void addElement(Object key,Object value) { int index; Object obj; obj = table.get(key); if (obj != null) { CacheElement element; // Just replace the value. element = (CacheElement) obj; element.setObjectValue(value); element.setObjectKey(key); return; } // If we haven't filled the cache yet, put it at the end. if (!isFull()) { index = numEntries; ++numEntries; } else { // Otherwise, replace a random entry. index = (int) (cache.length * random.nextFloat()); table.remove(cache[index].getObjectKey()); } cache[index].setObjectValue(value); cache[index].setObjectKey(key); table.put(key, cache[index]); }

Analyzing Random Cache Code (Talk show): In today s show the Random Cache is going to explain the code line by line and here we go. I will go straight to the main point; if I am not full then I will place the new entry that the client requested at the end of the cache (in case there is a cache miss). I do this by getting the number of entries that resides in the cache and assign it to index (which will be the index of the current entry the client is adding) after that I increment the number of entries.

if (!isFull()) { index = numEntries; ++numEntries; }

If I don t have enough room for the current entry, I will have to kick out a random entry (totally random, bribing isn t allowed). In order to get the random entry, I will use the random util. shipped with java to generate a random index and ask the cache to remove the entry that its index equal to the generated index. else { // Otherwise, replace a random entry. index = (int) (cache.length * random.nextFloat()); table.remove(cache[index].getObjectKey()); }

At the end I just place the entry -either the cache was full or no- in the cache. cache[index].setObjectValue(value); cache[index].setObjectKey(key); table.put(key, cache[index]);

Magnifying the Code: It is said that when you look at stuff from a near view it is better to understand it, so that s why we have a magnifying glass and we are going to magnify the code to get more near to it (and maybe understand it more). Cache entries in the same voice: hi ho, hi ho, into cache we go. New cache entry: excuse me; I have a question! (Asking a singing old cache entry near to him) Old cache entry: go ahead. New cache entry: I am new here and I don t understand my role exactly, how will the algorithm handle us? Old cache entry: cache! (Instead of man!), you remind me of myself when I was new (1st time I was added to the cache), I used to ask questions like that, let me show you what will happen.

Meet FIFO Cache Implementation: public final synchronized void addElement(Object key,Object value) { int index; Object obj; obj = table.get(key); if (obj != null) { CacheElement element; // Just replace the value. element = (CacheElement) obj; element.setObjectValue(value); element.setObjectKey(key); return; } // If we haven't filled the cache yet, put it at the end. if (!isFull()) { index = numEntries; ++numEntries; } else { // Otherwise, replace the current pointer, entry with the new one index = current; // in order to make Circular FIFO if (++current >= cache.length) current = 0;

table.remove(cache[index].getObjectKey()); } cache[index].setObjectValue(value); cache[index].setObjectKey(key); table.put(key, cache[index]); }

Analyzing FIFO Cache Code (Talk show): After Random Cache, audience went crazy for random cache, which made FIFO a little bit jealous so FIFO started talking and said: When there is no more rooms for the new cache entry , I will have to kick out the entry at the front (the one came first) as I work in a circular queue like manner, by default the current position is at the beginning of the queue(points to the beginning of the queue). I assign current value to index (index of the current entry) and then check to see if the incremented current greater than or equals to the cache length(coz I want to reset current pointer- position to the beginning of the queue) ,if so then I will set current to zero again ,after that I just kick the entry at the index position (Which is the first entry in the queue now) and place the new entry. else { // Otherwise, replace the current pointer, which takes care of // FIFO in a circular fashion. index = current; if (++current >= cache.length) current = 0; table.remove(cache[index].getObjectKey()); } cache[index].setObjectValue(value); cache[index].setObjectKey(key); table.put(key, cache[index]);

Magnifying the Code: Back to our magnifying glass we can observe the following actions happening to our entries

Conclusion: As we have seen in this article how to implement the FIFO replacement policy and also Random replacement policy, in the upcoming articles we will try to take our magnifying glass and magnify LFU, LRU replacement policy, till then stay tuned ;)