Caching in Distributed Systems

Caching has always been a favorite question of interviewers when talking about distributed systems.

Let’s break it down from the start to make it easier to understand:

1. What is Cache?

A cache is a hardware or software component that stores data so that future requests for that data can be served faster.

If your requested data is found in the cache then it’s a cache hit. And if it’s not found it’s naturally a miss.

When we talk about distributed systems, different activities occur in concurrent environments which leads to shared resources like an underlying network. Sharing these resources and allocating them could be challenging when there is a high load of client requests on the web application and database. In such cases, the unsung heroes such as load-balancer, clusters, and cache come into the picture. Well, we would focus only on cache today!

Any frequent action could be cached like database connection, external configuration file, user preference or frequently accessed webpages to improve the performance and availability.

2. What makes cache performance better?

There could be several factors that affect the cache performance:

1. Underlying data structure (which is mostly hash tables)

2. Cache eviction policy ( Based on the Replacement Algorithm)

3. Cache Utilizing policy

Let’s make a solid caching strategy!… For that, we need to answer two questions:

1. What resources are we storing in the cache?
2. How long data should be stored in the cache?

The Locality Principle guides the first part of the question.

The Locality Principle is the tendency of a processor to access the same set of memory locations repetitively over a short period. There are two basic types of reference locality — temporal and spatial locality.

Temporal Locality means the set of instructions that are very frequently accessed. These instructions can be stored in the cache to access quickly when needed, and this type of cache is also called temporal cache.

Spatial Locality means that all those instructions that are stored nearby to the recently executed instruction have a high chance of execution. For Example, If you search for something on Google, the first 10 links would have a higher probability of being visited than the next 10 and further on. So, it would be a good idea to cache the first 10 links while loading the page.

The second question could be answered by deciding on the Cache Replacement Algorithm.

As time passes Spatial cache could become stale, and to prevent the stale cache we need an eviction policy that kicks out the old information from the cache and updates it with fresh information, There are several policies:

1. Least Recently Used
2. Most Recently Used
3. First In First Out

The goal of the Replacement algorithm is to minimize the paging and maximize the cache hit.

(Paging: To store a new resource in the cache, an existing resource will be moved out of the cache to a secondary storage such as a hard disk.)

Hope this helps! Stay tuned for more…