Cache Eviction policies

Why do we need such policies?

Cache is small. Small means limited storage capacity. So we cannot store all of our data in cache. We need an eviction mechanism to remove the data. Now the question arises what data to remove?

We cannot just remove any data. We have to have some mechanism or some way to recognize a particular key to remove. What if we remove the data that is frequently read? That’d be a big no and big drop in performance as the request in case of cache miss, will translate to database read which is expensive.

Well known eviction policies —

1. Least recently used.
2. Most recently used.
3. Least frequently used.
4. Most frequently used.

Also an important point — Some data residing in cache may become stale or outdated over time. Such cache entries become invalid and must be marked for deletion or updates. This is where the Cache invalidation comes into the picture. Read below.

Cache Invalidation —

How do we identify the such cache entries that becomes stale over time? The idea is to store metadata corresponding to each cache entry. Specifically, maintaining a time-to-live value to deal with outdated cache items.

There are 2 different approaches to deal with outdated items using TTL:

1. Active expiration — This method actively checks the TTL of cache entries through a process or thread. Once the TTL reaches, the data is evicted.
2. Passive expiration — This method checks the TTL at the read request or at the time of access.