Understand Caching and LRU Cache

Understand the need for cache

Let's start with an example. You've likely heard about Domain Name System (DNS) servers. A DNS server is a directory consisting of domain names and their corresponding IP addresses so the user can reach a server. For example, when go to the URL https://www.educative.io in a browser, the following operations are performed:

1. The request hits a DNS server, which can be maintained by your Internet Service Provider (ISP).

2. In the DNS server, the URL is mapped to its IP address, because all the servers and websites are hosted on a physical computer.

3. This IP address is used to hit the server hosting the website. The server sends a response and the web page is displayed in our browsers.

The graphic below illustrates this process:

This is a very high-level view of DNS, but there are a lot of things going on during this process. Now, let us assume that the DNS server is not located near our location. So, at great distances, it may take around 100ms to get the IP address for a URL. If we are hitting the URL multiple times in a span of a few hours, then there is an unnecessary wait time of 100ms for every request.

We need some sort of mechanism, so that the first request to the URL may take 100ms, but subsequent requests to the same URL don't take as long to get the IP address.

So how can we do this?

Obviously, we can store the mapping of URLs and their corresponding IP addresses in our browser's storage and the browser can refer to it for subsequent hits to the same URLs. The process of storing pre-calculated or fetched data to avoid unnecessary computations is called caching, and the data structure that is used to store the data is called a cache. A cache is generally implemented using hashmaps and linked lists. Let's go through the slides to see how caches work:

Explanation

• Slide 1: The first time our machine makes a request for a particular URL, the request goes to the cache. Since we're making this request for the first time, we will not find the mapping of the IP address stored in the cache (this is known as a cache miss), so we will call DNS to get the IP address. Once we obtain the IP address, we will store the URL and its IP address in a key-value pair in the cache.

• Slide 2: When we make a request for the same URL again, the cache returns the IP address it had stored (this is known as cache hit). This takes significantly less time than the first time we made the request, and makes the operation much faster! ...