🗝️ 🤞🏻 🎦 Everything you need to know about caching ⛅️ ✍🏾 🎾

Good day.

I present to you the translation of the article "Everything you need to know about Caching - System Design" by Animesh Gaitonde.

Introduction

Have you noticed that when browsing a webpage with a poor Internet connection, text is loaded before high-quality images? However, when you visit the same page again, it loads much faster. When you visit a new site, it takes much longer to download it than to download frequently visited sites such as Facebook or Amazon. Do you know why this is happening? It's all about caching.

This is what my Instagram page looks like when connected slowly. As you can see, the text is displayed while the images have not yet loaded.

It is very important to provide the best experience using the application to retain and engage users. In a modern world where the spirit of competition reigns, business suffers greatly due to poor user experience. Imagine that you are watching your favorite series or streaming video on a website, but the video is constantly stopped for additional loading (buffering). How long will you endure such an “attitude” and will you return to such a site?

Caching works on the principle of "localization of links." The cache is a local data warehouse to speed up information retrieval and data recovery. The main purpose of the cache is to reduce the delay in reading data and increase the throughput of the application. Let's look at some real life examples.

Cache usage

Suppose you cook dinner every day. For cooking, you need various ingredients, vegetables, spices, etc. However, do you go to the store every day for this? This can be quite burdensome and time consuming. Of course, the first thing you look into the closet in the kitchen or refrigerator. This helps to avoid an unnecessary trip to the supermarket.

Your refrigerator is a kind of cache for vegetables. The obvious advantage of this cache is a significant saving in dinner preparation time.

How does the cache work?

Server applications typically store data in a database. When a client requests data, the application sends a request to the database, receives data from there and sends it to the client. The database server is offline and can be located on a different computer than the computer on which the application server is located.

Reading data from the database is a very slow process, because you need to send a request and perform I / O to get data from the file system. If the data is stored in the cache, the read operation will be very fast. When a client repeatedly requests the same data, it makes sense to return data from the cache instead of the database.

For example: if a tweet is viral, all clients will request data for the same tweet. Because Twitter has millions of users, using a cache avoids millions of database queries.

Thus, the cache reduces the load on the database. If the requested data is in the cache, the database request will be redirected (intercepted). You can draw some analogy with a hash table that stores key-value pairs.

The following diagram shows the process of reading data from the cache:

Key cache concepts

Time to Live (TTL)

These are limits on the amount of data that can be stored in the cache. You must delete entries in the cache that the application server no longer needs.

In the case of Netflix, the server will cache the most viewed or popular shows. There is no need to cache shows that no one is watching.

For example: caching the Paper House series is more rational than the Indiana Jones movie.

Delete policy

At some point, the cache is full. Hence the need arises to delete old (irrelevant) data and replace it with new (relevant) information.

There are several policies for clearing the cache, such as "old (least recently used)" (Least Recently Used, LRU), "rarely requested (least used)" (Least Frequently Used, LFU), "last (most recently used)" ( Most Recently Used, MRU). These policies delete data from the cache according to a specific principle.

Old

Data that has not been requested for a long time is deleted from the cache. As soon as the cache is full, old data is deleted, new data is added.

Suppose Facebook caches celebrity photos. Analysis of subscriber requests indicates the relevance of new photos. When the cache is full, the oldest photo will be deleted from it.

Rarely requested

The LFU tracks the frequency or number of data requests. When the cache size approaches the threshold value, the most rarely requested data will be deleted.

When we enter the text, the phone begins to offer various options for ending the word, one of which can be selected instead of the full set (completion). Smartphone software caches the most frequently typed words.

Rarely typed words are subsequently deleted from this cache. In the above example, if you use the words “feature”, “features”, “feather”, etc., after some time the phone will stop offering you “feat”, since it will be removed from the cache.

Last

In this policy, the latest data is subject to deletion, preference is given to older data stored in the cache. This strategy is used if the data acquisition template is such that the user is least interested in retrieving the latest data. Consider an example.

Dating applications such as Tinder usually cache all potential partners (potential matches or preferences) of the user. When a user flips through a feed by moving a specific profile of a potential partner left or right, the application should no longer recommend this profile to him. If this happens, it will lead to a bad user experience.

In this case, there is a need to delete the latest data. The application should delete the profiles viewed from the cache.

Cache types

Cache Recording

As the name implies, the data is written first to the cache, then to the database. This ensures data consistency in the cache and database. Each read of data from the cache corresponds to the most recent record.

The disadvantage of this approach is the increase in recording time. It is not suitable for heavily loaded systems with frequent data write operations. However, it is great for applications that often re-read data stored in the database. Slow writing is offset by fast reading and consistency.

Cache entry

An alternative to the first approach is to write data to the cache and add a note about data changes for their subsequent update to the database.

Using periodic asynchronous operations, you can read updated data in the cache and make changes to the corresponding data in the database. This approach does not increase the read / write operations. The only drawback here is the delay in synchronization between the cache and the database. This can lead to the fact that applications that rely on the database as a source of truth will read outdated data.

Youtube, for example, uses this approach to store information about the number of views of a particular video. Updating the database for each view of the viral video will be very expensive. The best solution is to write data to the cache and then synchronize with the database.

Cache Bypass Record

Several server applications do not often reread the latest data. In this case, a cache bypass entry is used.

In this approach, the database is updated without a cache. This avoids loading unclaimed data into the cache. However, if the application still requests the latest data that is not in the cache, this will lead to the loading of such data from the database with all the ensuing consequences.

Distributed Cache Usage Examples

List of open cache projects:

Redis
Memcached
Voltdb
Aerospike dbs
Apache ignite

Thank you for attention.

Everything you need to know about caching