What is Cache?
Caching is a temp location where We store data in (data that we need it frequently) as the original data is expensive
to be fetched, so We can retrieve it faster. Caching is made of pool of entries and these entries are a copy of real data which are in storage (database for example) and it is tagged with a tag (key identifier) value for retrieval.
When the client invokes a request (let s say he want to view product information) and our application gets the
request it will need to access the product data in our storage (database), it first checks the cache. 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 rateo r hit ratio of the cache.
On the contrary when the tagi sn 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 it is placed in the cache so in future hits it will be
found and will make a 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 and there 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 miss will be fetched from the storage and then we will have to decide which object in the cache we need to
move in order to place our newly created object (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.
When a cache miss occurs, data will be fetch it from the back storage, load it and place it in the cache but how
much space the data we just fetched takes in the cache memory? This is known as Storage 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
When the object that resides in the cache need is updated in the back storage for example it needs to be
updated, so keeping the cache up to date is known as Invalidation.
Entry will be invalidate from cache and fetched again from the back storage to get an updated version.
When cache miss happens, the cache ejects some other entry in order to make room for the previously uncached
data (in case we don t have enough room). The heuristic used to select the entry to eject is known as the
Optimal Replacement Policy:
The theoretically optimal page replacement algorithm (also known as
OPTo r Belady s optimal page replacement policy) is an algorithm that tries to achieve the following: when a cached object need to be placed in the cache, the cache algorithm should replace the entry which will not be used for the longest period of time. For example, a cache entry that is not going to be used for the next 10 seconds will be replaced by an entry that is going to be used within the next 2 seconds. Thinking of the optimal replacement policy we can say it is impossible to achieve but some algorithms do near optimal replacement 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?