This post is about the Caching. The importance of Caching, its pros and cons,web cache management, cache algorithms and some caching strategy techniques are further described below.
In computer science, the term “cache” is a component that stores certain types of data for future request so that they can be served faster. Caches are high-speed storage mechanism, either a part of the main memory or an independent high-speed storage device like SSD. A simple example of cache can be seen in a browser when we hit the back button. The browser almost instantly pulls the previous webpage without any delay. The data fetched previously are stored in a browser’s memory. This is possible using cache. Most of the modern browsers today stores data for frequently visited websites as a cache to better serve users.
Importance of Caching
The types of data that are stored vary in different contexts. In case of CPU, many data are fetched and used repeatedly. When these data are stored in a cache memory that is near to the CPU, processing occurs faster resulting in higher performance of a computer system. In web applications, there are many static data that do not change for a long period of time. These types of data can be stored as a cache. Storing previous responses for data in a web cache results to lower the amount of information that needs to be transmitted across the network. This also reduces bandwidth and repetitive processing for a web server. The main purpose of having a cache is to store program instructions that are frequently re-referenced by software during operation to achieve short data access times, reduced latency and improved I/O.
Pros and Cons of Caching
Caching improves overall performance of the system by reducing the numbers of resources that would otherwise be used. It saves the use of costly bandwidth. Likewise, it is also a fast way to serve as resources. But it is not always easy to achieve what caching can provide. For example, in case of Web Caching, faster page loading cannot always be guaranteed. A cache hit occurs when the requested data is found in the cache memory and a cache miss occurs when it cannot. Slower performance can be experienced if the resources are not found in the cache memory. Also, if the cache uses the weak cache consistency protocol, there is always the risk that a stale copy is fetched when an up-to-date copy is needed. Because going via one or more proxy server is more complicated, there is an increased risk in the shuffle of this complexity that a web resource being transferred might get lost or mangled as it is passed along. Many caching algorithms are implemented, for instance to search a cache faster and reduce waiting time for a user. This gives rise to another problem. This increases the complexity of a system by having to implement caching algorithms and makes harder to maintain whenever the business needs change.
Cache management refers to proper use of the cache system. We already learnt that caching can be implemented in various fields of computing. This section will be mainly focused on Web Caching. Before that, we have to know about different Caching Algorithms.
Cache capacity is not finite. Therefore, blocks in the cache memory need to be evicted in order to put a new data in it. Better performance is achieved by choosing better replacement decision.
Like mentioned previously, various algorithms are designed and implemented to achieve best performance using caching. These algorithms are called cache algorithms. Since cache memory is expensive and hence limited, the algorithm should determine which items to discard to make room for the new ones. Below are the existing on-line cache replacement algorithms and their brief descriptions as mentioned in The Multi-Queue Replacement Algorithm for Second Level Buffer Caches:
- Least Recently Used (LRU):
LRU has been widely employed for buffer cache management. It replaces the block in the cache which has not been used for the longest period of time.
- Most Recently Used (MRU):
It is also called “fetch and discard” replacement algorithm. Blocks that have recently been accessed in a second level buffer cache will likely stay in a first level buffer for a period of time, so they won’t be reused in the second level buffer cache in the near future.
- Least Frequently Used (LFU):
It replaces the block that is less frequently used. The motivation for this algorithm is that some blocks are accessed more frequently than others so that the reference counts can be used as an estimate of the probability of a block being referenced.
- Frequency Based Replacement (FBR):
It is the combination of LRU and LFU to achieve the benefits of both algorithms. It maintains the LRU ordering of cache blocks, but the replacement decision is based on the frequency count.
- Least kth-to-last Reference (LRU-k):
Replacement decision is based on the reference density observed during the past K references, i.e. the time of Kth-to-last reference of the block.
- Least Frequently Recently Used (LFRU):
It strives to replace blocks that are the least frequently used and not recently used. It calculates a value called Combined Recency and Frequency (CRF), and replaces the block with minimum CRF value.
- Two Queue (2Q):
This algorithm is designed to remove the cold blocks quickly.
Fig 2: Caching in a Distributed Environment
In case of web applications, there are different approaches to achieve proper management of caches. These approaches vary according to technologies. However, they can be categorized as browser level caching and server level caching according to where they are implemented. Browser level caching can be controlled by developers and users, whereas server level caching can be controlled only by the developers. Examples of browser caching include storing static contents like images and script files in the user’s browser instead of requesting the same content over and over again. Server side caching includes of storing the computation results in the server cache so that it is instantly available when the user requests it. Reddit for instance sorts out millions of posts by its users based on different categories like hot, new, rising, controversial, etc. These computations requires not only a substantial amount of time, but also multiple access to large databases. It’s impossible to calculate and fulfill these data as they are requested from the users. Hence, Reddit precomputes and stores those results in a cache for making it readily available to users when it is requested.
There is no perfect cache policy. It depends on traffic pattern, type of data served, and application specific requirement for data freshness. Below are some of the techniques for caching strategy as mentioned in the Google Developers article:
- Use consistent URL:
To avoid fetching of same content multiple times, we have to avoid frequent changes of URL.
- Ensure that the server provides a validation token(ETag):
This will eliminate having to transfer data if the content has not been changed on the server.
- Identifying which resources can be cache by the intermediaries:
These types of resources can be cached by CDN and other intermediaries.
- Determine optimal cache lifetime for each resources:
Different resources might need different cache lifetime. Determine the approximate age for each of them.
- Determine the best cache hierarchy for the website:
As mentioned earlier, different application required different cache hierarchy. Determine what best for your application.
 Pros and Cons of Web Caching,http://www.macs.hw.ac.uk/~hamish/3NI/topic172.html accessed: 3rd May 2015.
 Yuanyuan Zhou , James F. Philbin and Kai Li, “The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, ” USENIX Annual Technical Conference, Boston, Massachusetts, June, 2000.
 HTTP Caching,https://developers.google.com/web/fundamentals/performance/optimizing-content-efficiency/http-caching, accessed: 3rd May, 2015.
This content was researched and written for the college project. If you liked this article, please feel free to check my other page CrazyTechTips where you will find cool, interesting and some crazy tech stuffs! Your words and support mean the world to me. Stay along. Thank You!! :)