LRU vs. LFU: Cache Replacement Policies Under a Microscope

What is Cache?

Cache is a pivotal hardware or software component designed to store data temporarily in a computing environment, thereby enabling faster access to data on subsequent requests. In essence, caches act as a high-speed data storage layer which stores a subset of data, typically transient in nature, so that future requests for that data can be served more quickly than accessing the data’s primary storage location. This mechanism is widely implemented across various domains within modern computing systems, including but not limited to CPUs (Central Processing Units), web browsers, and databases, significantly enhancing performance and efficiency.

Caches are ingeniously architected to retain frequently accessed data, thus substantially reducing access times and improving the overall responsiveness of the system. The underlying principle of a cache system hinges on the notion that data items accessed once are likely to be accessed again in the near future. However, given the limited capacity of caches compared to the main storage, an essential aspect of cache management is the strategy used to decide which items to store and which to discard when the cache is full. This is where cache replacement policies come into play, among which the Least Recently Used (LRU) and Least Frequently Used (LFU) policies are prominent. These policies are sophisticated algorithms designed to optimize the performance of the cache by determining which data should be retained and which should be replaced, thus striking a balance between performance and resource utilization.

In the forthcoming sections, we will delve deeper into the mechanics of caches and explore the nuances that differentiate LRU and LFU cache replacement policies.

LRU vs. LFU

LRU (Least Recently Used)

The Least Recently Used (LRU) cache replacement policy puts emphasis on the recency of data access. When the cache reaches its maximum capacity, the LRU policy identifies the least recently accessed data item and evicts it from the cache to make room for the new item. The rationale behind this policy is that data items accessed recently are more likely to be accessed again in the near future, making them more valuable to retain in the cache.

The snippet below illustrates the LRU cache replacement policy in action:

LRUCache lru(3);

lru.set(1, "a");
lru.set(2, "b");
lru.set(3, "c");

lru.get(1);
lru.get(1);
lru.get(2);
lru.get(3);
lru.get(3);

// Add a new item (overwriting the least recently used item)
lru.set(4, "d");

lru.get(1); // => "NULL"
lru.get(2); // => "b"
lru.get(3); // => "c"
lru.get(4); // => "d"

In the example above, the LRU cache has a capacity of 3 items. Initially, items 1, 2, and 3 are added to the cache. Subsequently, items 1, 2, and 3 are accessed multiple times, while item 4 is added to the cache, overwriting the least recently used item 1. When item 1 is accessed again, it is no longer present in the cache, as it was evicted due to its least recent usage.

Let’s take a look at the set method implementation of an LRU cache:

string LRUCache::set(int key, string val) {
  if (this->refs.find(key) == this->refs.end()) {
    if (this->store.size() == this->mx_size) {
      int key_to_remove = this->store.back().first;
      this->store.pop_back();
      this->refs.erase(key_to_remove);
    }
  } else {
    this->store.erase(this->refs[key]);
  }

  this->store.push_front(make_pair(key, val));
  this->refs[key] = this->store.begin();

  return "OK";
}

This is achieved by maintaining a doubly linked list (store) to store the key-value pairs and a hash map (refs) to store the references to the corresponding nodes in the linked list.

When the cache reaches its maximum capacity, the least recently used item is evicted by removing the last element from the linked list and deleting the corresponding reference from the hash map.

After evicting the least recently used item, the new item is added to the front of the linked list, and its reference is stored in the hash map.

LFU (Least Frequently Used)

The Least Frequently Used (LFU) cache replacement policy, on the other hand, prioritizes the frequency of data access. In an LFU cache, when the cache is full, the LFU policy identifies the least frequently accessed data item and evicts it from the cache to accommodate the new item. The LFU policy is based on the premise that data items accessed more frequently are more likely to be accessed again, thus warranting their retention in the cache.

The following snippet demonstrates the LFU cache replacement policy:

LFUCache lfu(3);

lfu.set(1, "a");
lfu.set(2, "b");
lfu.set(3, "c");

lfu.get(1);
lfu.get(1);
lfu.get(2);
lfu.get(3);
lfu.get(3);

// Add a new item (overwriting the least frequently used item)
lfu.set(4, "d");

lfu.get(1) // => "a"
lfu.get(2) // => "NULL"
lfu.get(3) // => "c"
lfu.get(4) // => "d"

In the example above, the LFU cache has a capacity of 3 items. Initially, items 1, 2, and 3 are added to the cache. Subsequently, items 1, 2, and 3 are accessed multiple times, while item 4 is added to the cache, overwriting the least frequently used item 2. When item 2 is accessed again, it is no longer present in the cache, as it was evicted due to its least frequent usage.

Let’s examine the set method implementation of an LFU cache:

void LFUCache::insert(int key, string val) {
  if (this->curr_size == this->mx_size) {
    this->store.erase(this->freq[0].first);
    this->curr_size--;
    this->freq[0] = this->freq[this->curr_size];
    this->store[this->freq[0].first].second = 0;
    heapify(0);
  }

  int idx = this->curr_size;
  this->freq[idx] = make_pair(key, 1);
  this->store[key] = make_pair(val, idx);
  this->curr_size++;

  int parent_idx = get_parent_idx(idx);
  while (idx > 0 && this->freq[parent_idx].second > this->freq[idx].second) {
    this->store[this->freq[parent_idx].first].second = idx;
    this->store[this->freq[idx].first].second = get_parent_idx(idx);
    swap(this->freq[idx], this->freq[parent_idx]);

    idx = parent_idx;
    parent_idx = get_parent_idx(idx);
  }
}

...

string LFUCache::set(int key, string val) {
  if (this->store.find(key) == this->store.end() || this->store[key].first != val)
    insert(key, val);
  else increment(this->store[key].second);

  return "OK";
}

The LFU cache implementation involves maintaining a frequency array (freq) to store the frequency of access for each key-value pair and a hash map (store) to store the key-value pairs along with their corresponding frequency indices. The implementation is based on a min-heap data structure to facilitate efficient retrieval of the least frequently used item.

When the cache reaches its maximum capacity, the least frequently used item is evicted by removing the element with the lowest frequency from the frequency array and the corresponding key from the hash map.

After evicting the least frequently used item, the new item is inserted into the cache with an initial frequency of 1 and added to the frequency array.

Then the heapify operation is performed to maintain the min-heap property, ensuring that the item with the lowest frequency is at the root of the heap.

Source

The source code for the LRU and LFU cache implementations can be found in the following GitHub repository:

[embed]GitHub - Sean0628/cache_sample: 🧠 This repository contains C++ implementations for LRU/LFU cache. 🧠 This repository contains C++ implementations for LRU/LFU cache. - Sean0628/cache_samplegithub.com

References

• What is cache? (Last access: 2024/03/25)
• Complete Tutorial on LRU Cache with Implementations (Last access: 2024/03/25)
• Least Frequently Used (LFU) Cache Implementation (Last access: 2024/03/25)
• Introduction to Heap — Data Structure and Algorithm Tutorials (Last access: 2024/03/25)