LRU: Implementing a Cache Invalidation Policy

Originally published at https://blog.shams-nahid.com.

On the internet, there’s a very popular quote from Phil Karlton,

There are only two hard things in Computer Science: cache invalidation and naming things.

Using in-memory storage for accessing data is blazing fast, reducing repeated calculation. But we have to consider the trade-offs, memory is limited and costly. So it’s a crucial job for us to find out when and how should we remove/invalidate data from the cache memory.

Cache Invalidation Policies

It’s time to look at how can we invalidate/remove cache from the distributed caching system. According to the application requirements, we can go for various approaches to invalid cache,

• Least Recently Used Replace the data, that was used the longest time ago.
• Least Frequently Used Replace the data, that has a very low use rate.
• Most Recently Used Replace the most recent data that is used. In this case, the data was cached on the prediction that, it might be accessed. Only when it goes to the clients, the data is no longer required in the cache.
• FIFO Replace the oldest data from the cache by caching the latest data.

Among them, one of the most popular policies is LRU. With this approach, when our memory reached its maximum value, we will remove the oldest accessed data.

Limitation for Plain Key-Value Hashmap

Usually, for faster accessing, we store key-value in memory as follows,

Here, as key, we store the band name and as value, save their genre. The problem is, any time we access data, we need to make sure, the data is being accessed recently. Similar way, we have to track, which data is not being accessed for the longest time period.

So, when it comes to tracking the most recent and oldest accessed data, we can not simply use a key/value pair.

Now if we make use of a linked list to track the recent and oldest data, we can go the following architecture,

Here in the Hashmap in the key, we are saving the as usual key. For the value of the hashmap, we are storing a linked list node.

So we can access the data using the key from hashmap with O(1).

But the magic is with the linked list. This is a doubly-linked list, and any time if we have a node, we can do remove/insert/move with O(1).

The head of the linked list always points to the most recent data and the tail of the node will always point to the oldest accessed data.

Now if with hashmap, any data is being accessed, we will put the recently accessed data to the head.

For example, now, the head node is Air Supply key. In the hashmap, if we access the Aerosmith, the Aerosmith will become the head.

With this in mind, we can easily detect which one is the recently accessed data and which one is the oldest accessed data.

Code Implementation

Our Linked List implementation be like,

class LinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
    }
    insert(node) {
        if (!this.head) {
            this.head = node;
            this.tail = node;
            return;
        }
        this.head.prev = node;
        node.next = this.head;
        this.head = node;
    }
    makeHead(node) {
        // when linked list is empty
        if (!this.head) {
            this.head = node;
            this.tail = node;
            return;
        }
        // node is already head
        if (node === this.head) {
            return;
        }
        // node is a tail node
        if (node.next === null) {
            const previousNode = node.prev;
            previousNode.next = null;
            node.prev = null;
            node.next = this.head.next;
            this.head = node;
            this.tail = previousNode;
            return;
        }
        // node is in the middle, so remove it
        node.prev.next = node.next;
        node.next.prev = node.prev;
        // make the node as head
        node.next = this.head.next;
        node.prev = null;
        this.head = node;
    }
    remove(node) {
        // when the list is empty
        if (!this.head) {
            return;
        }
        // when the list has only head, removing head node
        if (node === this.head && !this.head.next) {
            this.head = null;
            this.tail = null;
            return;
        }
        // removing the tail node
        if (node === this.tail) {
            this.tail = this.tail.prev;
            this.tail.next = null;
            return;
        }
        // removing the middle node
        const previousNode = node.prev;
        const nextNode = node.next;
        previousNode.next = nextNode;
        nextNode.prev = previousNode;
    }
    removeLast() {
        this.remove(this.tail);
    }
    get(node) {
        let currentNode = this.head;
        while (currentNode) {
            if (currentNode === node) {
                return node;
            }
            currentNode = currentNode.next;
        }
        return null;
    }
}
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}
module.exports = {
    Node,
    LinkedList
}

And our Hashmap implementation be like,

const { LinkedList, Node } = require('./doubly-link-list');
const MAX_HASHMAP_SIZE = 3;
class HashMap {
  constructor() {
    this.linkedList = new LinkedList();
    this.size = 0;
    this.dataMap = {};
  }
  insert({ key, value }) {
    // When we are max size and inserting a new data
    // remove the last data from hash map
    // remove the last one from linked list
    if (!this.dataMap[key] && this.size === MAX_HASHMAP_SIZE) {
      // get oldest used data
      const lastNode = this.linkedList.tail;

      // remove oldest from hashmap
      if (lastNode) {
        delete this.dataMap[lastNode.data.key];
      }
      // remove oldest node from linked list
      this.linkedList.removeLast();
      this.size--;
    }
    this.linkedList.insert(new Node({ key, value }));
    this.dataMap[key] = this.linkedList.head;
    this.size++;
  }
  remove() { }
  get(key) {
    if (!this.dataMap[key]) {
      return null;
    }
    // make head first
    console.log(this.dataMap[key])
    this.linkedList.makeHead(this.dataMap[key])
    return this.dataMap[key].data.value;
  }
}
module.exports = {
  HashMap
}

Please find the complete code in the github.

Learn more about Distributed Cache System.

Also let me know for any query or additional explanation.