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 ;)

12 comments:

Unknown said...

superb articles, absolutely love the humor and reference frame, found that i could follow you much more intuitively; well done

Ahmed Ali said...

kevin,

Am glad you liked the post :), thank you for your comment and feedback ;hope you will like the next post ;)

Unknown said...

Love the articles! Great approach to the subject, really helped me improve my frame of reference on this topic.

Ahmed Ali said...

Devlin,

thanks for your nice comment, am glad you liked the article and hope you will like part 3 as well ;)

Edu Prado said...

try it...


package sample.cache;

import java.util.Map;
import java.util.TreeMap;

public class SampleCache {

private static Map<String, Object> cache = new TreeMap<String, Object>();

public static synchronized void addCache(String key, Object value) {
cache.put(key, value);
}

public static Object getFromCache(String key) throws NullPointerException {
return cache.get(key);
}

public static synchronized void remove(String key) {
cache.remove(key);
}

public static Map getAll() {
return cache;
}
}

Ahmed Ali said...

Edu Prado,

Thanks for you nice code snippet ;) just wait till part 3 and there will be more code and i assure you that you will like it ;)

Thanks

Anonymous said...

Excellent!!!!

Ahmed Ali said...

Hi,

Thanks for your comment , glad you liked it :)

Thanks,

MS said...

"cache! (Instead of man!)"

This was awesome!

Well written article, liked it..few places have errors with the language, but that's fine...overall, nice and informative!

Ahmed Ali said...

MS,

Thanks for your nice comment, glad you liked it :) and hope you would like the other parts ;)

Thanks,

Anonymous said...

hi,

very good article, I really enjoyed reading it.

One question, though: in few code snippets you say "// Just replace the value." but than you replace both value and key. What for, if the CacheElement already has the same key as you set ?

I am talking about this snippet:

// 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;
}

And one more comment - would be easier to understand if you mentioned what type is "table" - I guess it is a map.

--
best regards
Tomek Kaczanowski
http://kaczanowscy.pl/tomek

Ahmed Ali said...

Tomek,

Thanks for your comment as for the table , you guessed right it is a map.

As for the key setting this wont harm (it wont matter in any case except for the circular queue fashion) i just placed it there for most of the implemntations but it wont make any good for the rest of the implemntation like random cache for example , thanks for highlighting it :)

if you need anything just tell me :)

Thanks,
Ahmed Ali