Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database system keeps data cached to avoid rereading the hard drive, and a web browser caches web pages (images and assets) to avoid redownloading the contents. Put simply, in caching, the goal is to maximize hits (an item is in the cache when requested) and minimize misses (an item is not in the cache when requested).
In this chapter, two caching techniques will be discussed: least frequently used (LFU) and least recently used (LRU) caching.
Note
The concept of caching comes from the world of operating systems. You can read more about it in a lecture presentation1 by Jeff Zarnett from the University of Waterloo.
Understanding Caching
Cache design generally considers these two factors:
Temporal locality: A memory location that has been recently accessed is likely to be accessed again.
Spatial locality: A memory location near one that has recently been accessed is likely to be accessed again.
The optimal caching algorithm would be able to replace the part of the cache that will be used most distantly in the future with the new element to be inserted. This will require, for each item, calculating how many time in the future that item will be accessed. It should be obvious to you that this is impossible to implement because it requires looking into the future.
Least Frequently Used Caching
Least frequentlyused (LFU) caching is a caching algorithm used by the operating system to manage memory. The system tracks the number of times a block is referenced in memory. By design, when the cache exceeds its limit, the system deletes the item with the lowest reference frequency. The easiest implementation of the LFU cache is assigning a counter to every block loaded into the cache and incrementing a counter every time a reference is made to that block. When the cache exceeds its limit, the system searches for the block with the lowest counter and removes it from the cache.
Although LFU caching seems like an intuitive approach, it is not ideal when an item in memory is referenced repeatedly for a short amount of time and not accessed again. The frequency for that block is high because of its repeated reference, but this forces the system to delete other blocks that may be used more frequently outside the short block of time. In addition, new items in the system are susceptible to being deleted quickly because of their lower frequency of being accessed. Because of these issues, LFU is uncommon, but some hybrid systems utilize the core LFU concept. Examples of a such system are mobile keyboard apps. Suggested words appear on the keyboard apps, and it makes sense to implement this using LFU caching since the user likely uses the same words often. The frequency of a word would a great metric to see whether the word should exist in the cache.
The LFU cache uses a doubly linked list to remove elements in O(1) time. The doubly linked node in LFUs also has the freqCount property, which represents how frequently it has been accessed/set after being inserted for the first time.
1 function LFUNode(key, value) {
2 this.prev = null;
3 this.next = null;
4 this.key = key;
5 this.data = value;
6 this.freqCount = 1;
7 }
The LFU cache has two hash tables: keys and freq.freq has keys of frequency (1 to n, where n is the top frequency for element access), and each item is an instance of a doubly linked list class. keys stores each doubly linked list node for O(1) retrieval. The classes for a doubly linked list and the LFU cache are defined here:
1 function LFUDoublyLinkedList(){
2 this.head = new LFUNode('buffer head',null);
3 this.tail = new LFUNode('buffer tail',null);
4 this.head.next = this.tail;
5 this.tail.prev = this.head;
6 this.size = 0;
7 }
8
9 function LFUCache(capacity){
10 this.keys = {}; // stores LFUNode
11 this.freq = {}; // stores LFUDoublyLinkedList
12 this.capacity = capacity;
13 this.minFreq = 0;
14 this.size =0;
15 }
The LFUDoublyLinkedList class also requires the doubly linked list implementation for insertion and removal. However, only the insertion at the head and the removal at the tail is needed. This implementation is the same as the implementation from the doubly linked list class shown in Chapter 13 (Linked Lists).
Implementing set for the LFU has a few steps. There are two cases: insert the new item and replace an old item. When inserting a new item, a new node is created. If the cache is not full, it can be inserted into the freq’s doubly linked list of frequency 1. If the capacity is full, the tail item in the doubly linked list of frequency is deleted, and then the new node is inserted.
If the element already exists and needs to be replaced, the node is brought to the head of its corresponding frequency doubly linked list. Finally, the minimum frequency variable, minFreq, is incremented accordingly to compute which item should be evicted in the future.
1 LFUCache.prototype.set = function(key, value) {
2 var node = this.keys[key];
3
4 if (node == undefined) {
5 node = new LFUNode(key, value);
6
7 this.keys[key] = node;
8
9 if (this.size != this.capacity) {
10 // insert without deleting
11 if (this.freq[1] === undefined){
12 this.freq[1] = new LFUDoublyLinkedList();
13 }
14 this.freq[1].insertAtHead(node);
15 this.size++;
16 } else {
17 // delete and insert
18 var oldTail = this.freq[this.minFreq].removeAtTail();
19 delete this.keys[oldTail.key];
20
21 if (this.freq[1] === undefined){
22 this.freq[1] = new LFUDoublyLinkedList();
23 }
24
25 this.freq[1].insertAtHead(node);
26 }
27 this.minFreq = 1;
28 } else {
29 var oldFreqCount = node.freqCount;
30 node.data = value;
31 node.freqCount++;
32
33 this.freq[oldFreqCount].removeNode(node);
34
35 if (this.freq[node.freqCount] === undefined){
36 this.freq[node.freqCount] = new LFUDoublyLinkedList();
37 }
38
39 this.freq[node.freqCount].insertAtHead(node);
40
41 if (oldFreqCount == this.minFreq && Object.keys(this.freq[oldFreqCount]).size == 0) {
42 this.minFreq++;
43 }
44
45 }
46 }
To implement get, the cache needs to return existing nodes in O(1) time and increment the counter for accessing. If the element does not exist in the cache, it is forced to return a null element. Otherwise, the frequency for the element is increased, the item is brought to the head of the doubly linked list, and the minimum frequency variable, minFreq, is adjusted accordingly.
1 LFUCache.prototype.get = function(key) {
2 var node = this.keys[key];
3
4 if (node == undefined) {
5 return null;
6 } else {
7
8 var oldFreqCount = node.freqCount;
9 node.freqCount++;
10
11 this.freq[oldFreqCount].removeNode(node);
12
13 if (this.freq[node.freqCount] === undefined){
14 this.freq[node.freqCount] = new LFUDoublyLinkedList();
15 }
16
17 this.freq[node.freqCount].insertAtHead(node);
18
19 if (oldFreqCount == this.minFreq && Object.keys(this.freq[oldFreqCount]).length == 0) {
20 this.minFreq++;
21 }
22 return node.data;
23 }
24 }
With all the functions defined, the following code shows an example of this LFU usage:
1 var myLFU = new LFUCache(5);
2 myLFU.set(1, 1); // state of myLFU.freq: {1: 1}
3 myLFU.set(2, 2); // state of myLFU.freq: {1: 2<->1}
4 myLFU.set(3, 3); // state of myLFU.freq: {1: 3<->2<->1}
5 myLFU.set(4, 4); // state of myLFU.freq: {1: 4<->3<->2<->1}
6 myLFU.set(5, 5); // state of myLFU.freq: {1: 5<->4<->3<->2<->1}
7 myLFU.get(1); // returns 1, state of myLFU.freq: {1: 5<->4<->3<->2, 2: 1}
8 myLFU.get(1); // returns 1, state of myLFU.freq: {1: 5<->4<->3<->2, 3: 1}
9 myLFU.get(1); // returns 1, state of myLFU.freq:{1: 5<->4<->3<->2, 4: 1}
10 myLFU.set(6, 6); // state of myLFU.freq: {1: 6<->5<->4<->3, 4: 1}
11 myLFU.get(6); // state of myLFU.freq: {1: 5<->4<->3, 4: 1, 2: 6}
Least Recently Used Caching
Least recentlyused (LRU) caching is a caching algorithm that removes the oldest (least recently used) items first, so the item replaced is the oldest accessed item. When an item in the cache is accessed, that item moves to the back (newest in the order) of the list. When a page not found in the cache is accessed, the front item (or oldest in the order) is removed, and the new item is put at the back (newest in the order) of the list.
The implementation of this algorithm requires keeping track of which node was used when. To accomplish this, the LRU cache is implemented using a doubly linked list and hash table.
A doubly linked list is needed to keep track of the head (the oldest data). A doubly linked list is required because of the most recently used requirement. Each time new data is inserted, the head moves up until the size is exceeded. Then the oldest data is evicted.
Figure 14-1 shows a diagram of an LRU cache with a size of 5.
Figure 14-1
LRU cache
To implement the LRU cache, the node is defined similarly to the doubly linked list node in Chapter 13. This node also has a key property, and its implementation is shown in the following code block:
1 function DLLNode(key, data) {
2 this.key = key;
3 this.data = data;
4 this.next = null;
5 this.prev = null;
6 }
The LRU cache can be initialized by passing the capacity parameter. capacity defines how many nodes are allowed to be in the cache.
1 function LRUCache(capacity) {
2 this.keys = {};
3 this.capacity = capacity;
4 this.head = new DLLNode(", null);
5 this.tail = new DLLNode(", null);
6 this.head.next = this.tail;
7 this.tail.prev = this.head;
8 }
Since the LRU cache uses a doubly linked list, two functions for removing a node and adding a node to the tail will be defined here:
Two more functions need to be defined: get and set. Whenever get is called, the LRU caching scheme brings that node to the head of the doubly linked list since it was the most recently used node. This is the same as deleting and adding the node. For setting nodes via set, the keys property on the LRU cache is used to store the node to keep retrieval in O(1) time in get. However, if the cache is at full capacity, it evicts the farthest node from the tail.
24 if (Object.keys(this.keys).length > this.capacity) {
25 var realHead = this.head.next;
26 this.removeNode(realHead);
27 delete this.keys[realHead.key];
28 }
29 }
Finally, the following is an example of an LRU cache of size 5:
1 var myLRU = new LRUCache(5);
2
3 myLRU.set(1, 1); // 1
4 myLRU.set(2, 2); // 1 <-> 2
5 myLRU.set(3, 3); // 1 <-> 2 <-> 3
6 myLRU.set(4, 4); // 1 <-> 2 <-> 3 <-> 4
7 myLRU.set(5, 5); // 1 <-> 2 <-> 3 <-> 4 <-> 5
8
9
10 myLRU.get(1); // 2 <-> 3 <-> 4 <-> 5 <-> 1
11 myLRU.get(2); // 3 <-> 4 <-> 5 <-> 1 <-> 2
12
13 myLRU.set(6, 6);// 4 <-> 5 <-> 1 <-> 2 <-> 6
14 myLRU.set(7, 7);// 5 <-> 1 <-> 2 <-> 6 <-> 7
15 myLRU.set(8, 8);// 1 <-> 2 <-> 6 <-> 7 <-> 8
Summary
This chapter covered two main caching ideas: least frequently used and least recently used. The chapter talked about the concept of an optimal caching algorithm, which is impossible to implement but provides an idea of what you would want to approximate. LFU caching sounds great because it uses frequency to determine what node should be evicted, but LFU is inferior to the LRU in most cases because it does not account for temporal locality. There are other caching algorithms, but most of those algorithms are worse in general cases, such as the not recently used and first in, first out algorithms. Finally, it should be noted that given the many known data of real-life system behavior workloads, LRU is the most effective algorithm in most cases. Table 14-1 summarizes the caching algorithms.
