Cache is king
Imagine you want to read about a topic from several books, but each time you need to reference a different book, you have to get up and go to another room to retrieve it. This can be time-consuming and disrupt your workflow. After realizing this, you decide to bring all books you will use with you to your desk so you can quickly access them whenever you need them. This is an example of caching, which is a process used in other systems to improve performance.
So a cache is a high-speed data storage layer that stores a subset of data, temporarily, so that future requests for that data are served up faster. Caching allows you to efficiently reuse previously retrieved or computed data. So for example, when you visit a website for the first time the website takes some time to load the contents, and instead of loading the contents each time you visit the website, the contents are saved in the cache for future visits.
Ok, so since the cache provides quicker access, why do not we store all our data on cache memory so we can access it quicker?
Good question. However, we can’t use cache memory liberally because it’s currently expensive. Furthermore, any data stored in the cache is temporary and will be lost if the power goes out. Therefore, it’s necessary to store data on a permanent storage device to prevent loss in case of power failures.
Now we understand caching and its limitations, it’s time to discuss some of the algorithms used for read/write operations related to caching. (Some times they are called cache invalidation methods, as they are used to update the cache when data is no longer valid)
Write through:-
In this technique, the data is written to the cache, then written to the permanent storage system, and when the cache receives an acknowledgment from the main memory it sends an acknowledgment to the user.
Pros:-
The data is safe (won’t be lost in case of power failures)
The data is consistent (the data in the cache is the same as the one in the persistent storage)
Cons:-
Takes some time to make sure the data is safely written to the persistent (main) storage system.
Write back:-
The data is written to the cache and an acknowledgment is sent to the user, then the data is forwarded to the persistent storage to be written, so this doesn’t freeze users until the data is written to the persistent storage, so it is faster than the “write through” algorithm.
Pros:-
Faster writes, as the user is not waiting for the persistent storage to send an acknowledgment.
Cons:-
Risky, as what would happen if the user received an acknowledgment that his or her data is written but at that moment exactly the cache failed to write the data to the persistent storage, the data would be inconsistent as the data on the cache will be different from the data on the persistent storage.
Write Aside (Lazy loading):-
In this technique, when the application receives a request to fetch some data (the visited website content) it checks if the data is in the cache or not, if found the data is sent to the user, if not the app fetches the data from the persistent storage send it to the user then updates the cache.
Pros:-
Only requested data is cached which avoids filling up the cache with data that is not requested.
Get Zeyad Omar’s stories in your inbox
Join Medium for free to get updates from this writer.
Cons:-
Longer response time (more delay) in case of a cache miss (requested data not found in the cache).
We have learned how to write to the cache, but constantly doing so will eventually fill it up. This means that there will be no room left to store frequently used data, resulting in longer loading times for new websites. To avoid this, we need to find a way to clear out unused data from the cache, freeing up space for frequently used information.
There are several algorithms for clearing cache memory, but we’ll focus on the most common ones.
LRU:-
The first algorithm is LRU (Least Recently Used). With this technique, you clear the least recently used data from the cache. For instance, if you haven’t visited a website in a while, its content will be removed from the cache. You may have noticed that when you stop visiting a favorite website for a while, it takes longer to load its contents when you return. This is because it’s been cleared from the cache memory.
MRU:-
The second algorithm is MRU (Most Recently Used). This technique is useful when you need to free up cache memory, but it’s only employed when the amount of data stored on the cache exceeds a predetermined threshold. It may seem counterintuitive, but removing the most recently used data can be helpful. For example, if you recently watched an episode of your favorite show on a streaming platform, you probably won’t watch it again soon. Therefore, it’s better to remove this data from the cache using the MRU technique.
LFU:-
The third algorithm is LFU (Least Frequently Used). This method ignores the date on which the data was inserted into the cache and only takes the frequency of use into account. For example, if you visit website A 20 times and website B 5 times, the content of website B will be removed from the cache, regardless of when you visited the website.
There are more eviction algorithms than the ones discussed above, I will add a link to extra resources so you can learn more about them.
Conclusion:-
To summarize, caching is a process used to improve system performance by temporarily storing a subset of data in high-speed storage, allowing for faster access to that data in the future. However, caching has limitations, such as its cost and the fact that cached data is temporary and can be lost in case of power failures. We also discussed different algorithms for read/write operations related to caching, such as Write Through, Write Back, and Write Aside. Additionally, we covered cache eviction algorithms, such as LRU, MRU, and LFU, to clear out unused data from the cache, freeing up space for frequently used information.
That’s it for this article, I encourage you to go through the resources as caching is widely used in almost every scalable system and found a lot in system design interviews, so it is better to get familiar with this topic and be prepared for the interview.
Goodbye…
Resources:-
- Microsoft learn: Cache aside
- Amazon Cache patterns
- Gaurav Sen youtube video
- Arslan’s Ahmad article
