The Interview:
“Cachingis a temp location where I store data in (data that I need itfrequently) as the original data is expensive to be fetched, so I canretrieve it faster. “
That what programmer 1 answered in theinterview (one month ago he submitted his resume to a company whowanted a java programmer with a strong experience in caching andcaching frameworks and extensive data manipulation)
Programmer 1did make his own cache implementation using hashtable and that what heonly knows about caching and his hashtable contains about 150 entrywhich he consider an extensive data(caching = hashtable, load thelookups in hashtable and everything will be fine nothing else) so letssee how will the interview goes.
Interviewer: Nice and based on what criteria do you choose your caching solution?
Programmer 1 :huh, (thinking for 5 minutes) , mmm based on, on , on the data (coughing…)
Interviewer: excuse me! Could you repeat what you just said again?
Programmer 1: data?!
Interviewer: oh I see, ok list some caching algorithms and tell me which is used for what
Programmer 1
staring at the interviewer and making strange expressions with hisface, expressions that no one knew that a human face can do
)
Interviewer: ok, let me ask it in another way, how will a caching behave if it reached its capacity?
Programmer 1:capacity? Mmm (thinking… hashtable is not limited to capacity I can addwhat I want and it will extend its capacity) (that was in programmer 1mind he didn’t say it)
The Interviewer thanked programmer 1 (theinterview only lasted for 10minutes) after that a woman came and said:oh thanks for you time we will call you back have a nice day
Thiswas the worst interview programmer 1 had (he didn’t read that there wasa part in the job description which stated that the candidate shouldhave strong caching background ,in fact he only saw the line talkingabout excellent package
)
Talk the talk and then walk the walk
Afterprogrammer 1 left he wanted to know what were the interviewer talkingabout and what are the answers to his questions so he started to surfthe net, Programmer 1 didn’t know anything else about caching except:when I need cache I will use hashtable
After using his favorite search engine he was able to find a nice caching article and started to read.
Why do we need cache?
Longtime ago before caching age user used to request an object and thisobject was fetched from a storage place and as the object grow biggerand bigger, the user had spend more time to fulfill his request, itreally made the storage place suffer a lot coz it had to be working forthe whole time this caused both the user and the db to be angry andthere were one of 2 possibilities
1- The user will get upset and complain and even wont use this application again(that was the case always)
2-The storage place will pack up its bags and leave your application ,and that made a big problems(no place to store data) (happened in raresituations )
Caching is a god sent:
After few years researchers at IBM (in 60s) introduced a new concept and named it “Cache”
What is Cache?
Cachingis a temp location where I store data in (data that I need itfrequently) as the original data is expensive to be fetched, so I canretrieve it faster.
Caching is made of pool of entries and theseentries are a copy of real data which are in storage (database forexample) and it is tagged with a tag (key identifier) value for retrieval.
Great so programmer 1 already knows this but what he doesn’t know is caching terminologies which are as follow:
Cache Hit:
Whenthe client invokes a request (let’s say he want to view productinformation) and our application gets the request it will need toaccess the product data in our storage (database), it first checks thecache.
If an entry can be found with a tag matching that of the desired data (say product Id), the entry is used instead. This is known as a cache hit (cache hit is the primary measurement for the caching effectiveness we will discuss that later on).
And the percentage of accesses that result in cache hits is known as the hit rate or hit ratio of the cache.
Cache Miss:
On the contrary when the tag isn’t found in the cache (no match were found) this is known as cache miss, a hit to the back storage is made and the data is fetched back and itis placed in the cache so in future hits it will be found and will makea cache hit.
If we encountered a cache miss there can be either a scenarios from two scenarios:
First scenario:there is free space in the cache (the cache didn’t reach its limit andthere is free space) so in this case the object that cause the cache miss will be retrieved from our storage and get inserted in to the cache.
Second Scenario: there is no free space in the cache (cache reached its capacity) so the object that cause cache misswill be fetched from the storage and then we will have to decide whichobject in the cache we need to move in order to place our newly createdobject (the one we just retrieved) this is done by replacement policy (caching algorithms) that decide which entry will be remove to make more room which will be discussed below.
Storage Cost:
Whena cache miss occurs, data will be fetch it from the back storage, loadit and place it in the cache but how much space the data we justfetched takes in the cache memory? This is known as Storage cost
Retrieval Cost:
And when we need to load the data we need to know how much does it take to load the data. This is known as Retrieval cost
Invalidation:
Whenthe object that resides in the cache need is updated in the backstorage for example it needs to be updated, so keeping the cache up todate is known as Invalidation.
Entry will be invalidate from cache and fetched again from the back storage to get an updated version.
Replacement Policy:
Whencache miss happens, the cache ejects some other entry in order to makeroom for the previously uncached data (in case we don’t have enoughroom). The heuristic used to select the entry to eject is known as the replacement policy.
Optimal Replacement Policy:
The theoretically optimal page replacement algorithm (also known as OPT or Belady’s optimal page replacement policy)is an algorithm that tries to achieve the following: when a cachedobject need to be placed in the cache, the cache algorithm shouldreplace the entry which will not be used for the longest period of time.
Forexample, a cache entry that is not going to be used for the next 10seconds will be replaced by an entry that is going to be used withinthe next 2 seconds.
Thinking of the optimal replacement policy wecan say it is impossible to achieve but some algorithms do near optimalreplacement policy based on heuristics.
So everything is based on heuristics so what makes algorithm better than another one? And what do they use for their heuristics?
Nightmare at Java Street:
While reading the article programmer 1 fall a sleep and had nightmare (the scariest nightmare one can ever have)
Programmer 1: nihahha I will invalidate you. (Talking in a mad way)
Cached Object: no no please let me live, they still need me, I have children.
Programmer 1: all cached entries say that before they are invalidated and since when do you have children? Never mind now vanish for ever.
Buhaaahaha, laughed programmer 1 in a scary way, ,silence took over the place forfew minutes and then a police serine broke this silence, police caughtprogrammer 1 and he was accused of invalidating an entry that was stillneeded by a cache client, and he was sent to jail.
Programmer 1work up and he was really scared, he started to look around andrealized that it was just a dream then he continued reading aboutcaching and tried to get rid of his fears.
Caching Algorithms:
No one can talk about caching algorithms better than the caching algorithms themselves
Least Frequently Used (LFU):
I am Least Frequently used; I count how often an entry is needed by incrementing a counter associated with each entry.
Iremove the entry with least frequently used counter first am not thatfast and I am not that good in adaptive actions (which means that itkeeps the entries which is really needed and discard the ones thataren’t needed for the longest period based on the access pattern or inother words the request pattern)
Least Recently Used (LRU):
Iam Least Recently Used cache algorithm; I remove the least recentlyused items first. The one that wasn’t used for a longest time.
Irequire keeping track of what was used when, which is expensive if onewants to make sure that I always discards the least recently used item.
Webbrowsers use me for caching. New items are placed into the top of thecache. When the cache exceeds its size limit, I will discard items fromthe bottom. The trick is that whenever an item is accessed, I place atthe top.
So items which are frequently accessed tend to stay inthe cache. There are two ways to implement me either an array or alinked list (which will have the least recently used entry at the backand the recently used at the front).
I am fast and I amadaptive in other words I can adopt to data access pattern, I have alarge family which completes me and they are even better than me (I dofeel jealous some times but it is ok) some of my family member are(LRU2 and 2Q) (they were implemented in order to improve LRU caching
Least Recently Used 2(LRU2):
Iam Least recently used 2, some people calls me least recently usedtwice which I like it more, I add entries to the cache the second timethey are accessed (it requires two times in order to place an entry inthe cache); when the cache is full, I remove the entry that has asecond most recent access. Because of the need to track the two mostrecent accesses, access overhead increases with cache size, If I amapplied to a big cache size, that would be a problem, which can be adisadvantage. In addition, I have to keep track of some items not yetin the cache (they aren’t requested two times yet).I am better that LRUand I am also adoptive to access patterns.
-Two Queues:
Iam Two Queues; I add entries to an LRU cache as they are accessed. Ifan entry is accessed again, I move them to second, larger, LRU cache.
Iremove entries a so as to keep the first cache at about 1/3 the size ofthe second. I provide the advantages of LRU2 while keeping cache accessoverhead constant, rather than having it increase with cache size.Which makes me better than LRU2 and I am also like my family, amadaptive to access patterns.
Adaptive Replacement Cache (ACR):
Iam Adaptive Replacement Cache; some people say that I balance betweenLRU and LFU, to improve combined result, well that’s not 100% trueactually I am made from 2 LRU lists, One list, say L1, contains entriesthat have been seen only once “recently”, while the other list, say L2,contains entries that have been seen at least twice “recently”.
Theitems that have been seen twice within a short time have a lowinter-arrival rate, and, hence, are thought of as “high-frequency”.Hence, we think of L1as capturing “recency” while L2 as capturing“frequency” so most of people think I am a balance between LRU and LFUbut that is ok I am not angry form that.
I am considered one ofthe best performance replacement algorithms, Self tuning algorithm andlow overhead replacement cache I also keep history of entries equal tothe size of the cache location; this is to remember the entries thatwere removed and it allows me to see if a removed entry should havestayed and we should have chosen another one to remove.(I really havebad memory)And yes I am fast and adaptive.
Most Recently Used (MRU):
Iam most recently used, in contrast to LRU; I remove the most recentlyused items first. You will ask me why for sure, well let me tell yousomething when access is unpredictable, and determining the least mostrecently used entry in the cache system is a high time complexityoperation, I am the best choice that’s why.
I am so common inthe database memory caches, whenever a cached record is used; I replaceit to the top of stack. And when there is no room the entry on the topof the stack, guess what? I will replace the top most entry with thenew entry.
First in First out (FIFO):
Iam first in first out; I am a low-overhead algorithm I require littleeffort for managing the cache entries. The idea is that I keep track ofall the cache entries in a queue, with the most recent entry at theback, and the earliest entry in the front. When there e is no place andan entry needs to be replaced, I will remove the entry at the front ofthe queue (the oldest entry) and replaced with the current fetchedentry. I am fast but I am not adaptive
-Second Chance:
HelloI am second change I am a modified form of the FIFO replacementalgorithm, known as the Second chance replacement algorithm, I ambetter than FIFO at little cost for the improvement. I work by lookingat the front of the queue as FIFO does, but instead of immediatelyreplacing the cache entry (the oldest one), i check to see if itsreferenced bit is set(I use a bit that is used to tell me if this entryis being used or requested before or no). If it is not set, I willreplace this entry. Otherwise, I will clear the referenced bit, andthen insert this entry at the back of the queue (as if it were a newentry) I keep repeating this process. You can think of this as acircular queue. Second time I encounter the same entry I cleared itsbit before, I will replace it as it now has its referenced bit cleared.am better than FIFO in speed
-Clock:
I amClock and I am a more efficient version of FIFO than Second chancebecause I don’t push the cached entries to the back of the list likeSecond change do, but I perform the same general function asSecond-Chance.
I keep a circular list of the cached entries inmemory, with the “hand” (something like iterator) pointing to theoldest entry in the list. When cache miss occurs and no empty placeexists, then I consult the R (referenced) bit at the hand’s location toknow what I should do. If R is 0, then I will place the new entry atthe “hand” position, otherwise I will clear the R bit. Then, I willincrement the hand (iterator) and repeat the process until an entry isreplaced.I am faster even than second chance.
Simple time-based:
Iam simple time-based caching; I invalidate entries in the cache basedon absolute time periods. I add Items to the cache, and they remain inthe cache for a specific amount of time. I am fast but not adaptive foraccess patterns
Extended time-based expiration:
Iam extended time based expiration cache, I invalidate the items in thecache is based on relative tim …