LRU Cache Design - Welcome to Tech by Example

Table of Contents

Overview

In this tutorial, we are also going to consider the FIFO approach in our design as well other than LRU so that the design is flexible enough to switch to any algorithm at run time

The objective is to Design an in-memory cache. Below are the requirements

It should support Set and Get Operation

O(1) Time Complexity for both Set and Get

Assume the maximum capacity of the cache is 3. Once the cache is full and there is one more key to be inserted then one of the existing entries needs to be deleted from the cache

Deletion should be based on eviction algorithm – FIFO or LRU

Assume key and value in the cache are of type string

The eviction Algorithm it should support is First-In-First-Out(FIFO) and Least Recently Used (LRU)

The Eviction Algorithm should be pluggable. That means that you should be able to change your eviction algorithm at runtime.

Below are the high-level things we will have in our design

We will have a Cache class that will act as an interface for interacting with the client

Cache class will be using a combination of a Map and a Doubly-linked List for storing everything. Both map and doubly-linked list are used so that get and set are of O(1) even with evictions. How this is achieved, we will later in this tutorial.

The Map will have the key of type string and the value of the type pointer to a node in the Doubly-linked List

Each node of the Doubly Linked List will contain the key as well as value. Each node will also have a pointer to the previous node in the double linked list and a pointer to the next node in the doubly linked list

There will be an evictionAlgorithm interface. There will be LRU and FIFO class which implements this evictionAlgorithm Interface

Cache class will also embed an instance of evictionAlgorithm interface.

evictionAlgorithm interface exists to decouple our Cache class with the algorithm such that we should be able to change the algorithm at run time. Also Cache class should not change when a new algorithm is being added. This is where Strategy DesignPattern comes into the picture. The strategy pattern suggests creating a family of the algorithm with each algorithm having its own class. Each of these classes follows the same interface and this makes the algorithm interchangeable within the family. Let’s say the common interface name is evictionAlgo. Then FIFO and LRU classes will implement this interface.

Now our main Cache class will embed evictionAlgo interface. Instead of implementing all types of eviction algorithms in itself, our Cache class will delegate all of them to the evictionAlgo interface. Since evictionAlgo is an interface, we can run time change the algorithm to either be LRU, or FIFO without any change in Cache class.

Also, we will use the Factory Design Pattern to create the instance of each of the algorithms ie. FIFO, LRU

Let’s see how Get and Set are going to work in O(1) time

Set(key int, value int)

For any set operation, it will first create a doubly-linked list node with key and value supplied. Then an entry will be made into the map with key as the input key and value as the address of the node. Once the node is created, then there are two cases

The cache is not full – In this case, it will pass the control to the current evictionAlgorithm interface. The evictionAlgorithm interface is going to do insert that node in a double-linked list either at the end or at the front depending upon the current eviction algorithm. Every operation is O(1) here

The cache is full – In this case, it will pass the control to the current evictionAlgorithm interface to evict one of the nodes based upon the current eviction Algorithm. Once that node is evicted it will insert the new node. Every operation is O(1) here

Get(key int)

For any Get operation, it will first check the map if the given key exists. If it exists then it will fetch the address of the node pointed to by key in the map. It will then fetch the value from the node. Then it will pass the control to the current evictionAlgorithm interface. The evictionAlgorithm interface is going to shuffle the current node in the doubly-linked list either at the end or front depending upon the current eviction algorithm. Every operation is O(1) here.

Low-Level Design

Below is the low-level design expressed in go programming language. Later we will see a UML diagram as well as a working example

Cache Class

type cache struct {
	dll          *doublyLinkedList
	storage      map[string]string
	evictionAlgo evictionAlgo
	capacity     int
	maxCapacity  int
}

func (c *cache) setEvictionAlgo(e evictionAlgo)

func (c *cache) add(key, value string)

func (c *cache) get(key string)

func (c *cache) evict()

Doubly Linked List

type node struct {
    data string
    prev *node
    next *node
}

type doublyLinkedList struct {
    len  int
    tail *node
    head *node
}

func initDoublyList() *doublyLinkedList {
    return &doublyLinkedList{}
}

func (d *doublyLinkedList) AddFrontNodeDLL(data string) 

func (d *doublyLinkedList) AddEndNodeDLL(data string) 

func (d *doublyLinkedList) MoveToFront(node *node) error 

func (d *doublyLinkedList) MoveToBack(node *node) error

func (d *doublyLinkedList) Size() int

Eviction Algorithm Interface

type evictionAlgo interface {
	evict(c *cache)
}

func createEvictioAlgo(algoType string) evictionAlgo

FIFO Algorithm – It implements the Eviction Algorithm Interface

type fifo struct {
}

func (l *fifo) evict(c *cache)

LRU Algorithm – It implements the Eviction Algorithm Interface

type lru struct {
}

func (l *lru) evict(c *cache)

UML Diagram

Program

Here is the full working code in go programming language if anyone is interested.

doublylinklist.go

package main

import "fmt"

type node struct {
	key   string
	value string
	prev  *node
	next  *node
}

type doublyLinkedList struct {
	len  int
	tail *node
	head *node
}

func initDoublyList() *doublyLinkedList {
	return &doublyLinkedList{}
}

func (d *doublyLinkedList) AddToFront(key, value string) {
	newNode := &node{
		key:   key,
		value: value,
	}
	if d.head == nil {
		d.head = newNode
		d.tail = newNode
	} else {
		newNode.next = d.head
		d.head.prev = newNode
		d.head = newNode
	}
	d.len++
	return
}

func (d *doublyLinkedList) RemoveFromFront() {
	if d.head == nil {
		return
	} else if d.head == d.tail {
		d.head = nil
		d.tail = nil
	} else {
		d.head = d.head.next
	}
	d.len--
}

func (d *doublyLinkedList) AddToEnd(node *node) {
	newNode := node
	if d.head == nil {
		d.head = newNode
		d.tail = newNode
	} else {
		currentNode := d.head
		for currentNode.next != nil {
			currentNode = currentNode.next
		}
		newNode.prev = currentNode
		currentNode.next = newNode
		d.tail = newNode
	}
	d.len++
}
func (d *doublyLinkedList) Front() *node {
	return d.head
}

func (d *doublyLinkedList) MoveNodeToEnd(node *node) {
	prev := node.prev
	next := node.next

	if prev != nil {
		prev.next = next
	}

	if next != nil {
		next.prev = prev
	}
	if d.tail == node {
		d.tail = prev
	}
	if d.head == node {
		d.head = next
	}
	node.next = nil
	node.prev = nil
	d.len--
	d.AddToEnd(node)
}

func (d *doublyLinkedList) TraverseForward() error {
	if d.head == nil {
		return fmt.Errorf("TraverseError: List is empty")
	}
	temp := d.head
	for temp != nil {
		fmt.Printf("key = %v, value = %v, prev = %v, next = %v\n", temp.key, temp.value, temp.prev, temp.next)
		temp = temp.next
	}
	fmt.Println()
	return nil
}

func (d *doublyLinkedList) Size() int {
	return d.len
}

evictionAlgorithm.go

package main

type evictionAlgo interface {
	evict(c *Cache) string
	get(node *node, c *Cache)
	set(node *node, c *Cache)
	set_overwrite(node *node, value string, c *Cache)
}

func createEvictioAlgo(algoType string) evictionAlgo {
	if algoType == "fifo" {
		return &fifo{}
	} else if algoType == "lru" {
		return &lru{}
	}

	return nil
}

lru.go

package main

import "fmt"

type lru struct {
}

func (l *lru) evict(c *Cache) string {
	key := c.doublyLinkedList.Front().key
	fmt.Printf("Evicting by lru strtegy. Evicted Node Key: %s: ", key)
	c.doublyLinkedList.RemoveFromFront()
	return key
}

func (l *lru) get(node *node, c *Cache) {
	fmt.Println("Shuffling doubly linked list due to get operation")
	c.doublyLinkedList.MoveNodeToEnd(node)
}

func (l *lru) set(node *node, c *Cache) {
	fmt.Println("Shuffling doubly linked list due to set operation")
	c.doublyLinkedList.AddToEnd(node)
}

func (l *lru) set_overwrite(node *node, value string, c *Cache) {
	fmt.Println("Shuffling doubly linked list due to set_overwrite operation")
	node.value = value
	c.doublyLinkedList.MoveNodeToEnd(node)
}

fifo.go

package main

import "fmt"

type fifo struct {
}

func (l *fifo) evict(c *Cache) string {
	fmt.Println("Evicting by fifo strtegy")
	key := c.doublyLinkedList.Front().key
	c.doublyLinkedList.RemoveFromFront()
	return key
}

func (l *fifo) get(node *node, c *Cache) {
	fmt.Println("Shuffling doubly linked list due to get operation")
}

func (l *fifo) set(node *node, c *Cache) {
	fmt.Println("Shuffling doubly linked list due to set operation")
	c.doublyLinkedList.AddToEnd(node)
}

func (l *fifo) set_overwrite(node *node, value string, c *Cache) {
	fmt.Println("Shuffling doubly linked list due to set_overwrite operation")
}

cache.go

package main

import "fmt"

type Cache struct {
	doublyLinkedList *doublyLinkedList
	storage          map[string]*node
	evictionAlgo     evictionAlgo
	capacity         int
	maxCapacity      int
}

func initCache(evictionAlgo evictionAlgo, maxCapacity int) Cache {
	storage := make(map[string]*node)
	return Cache{
		doublyLinkedList: &doublyLinkedList{},
		storage:          storage,
		evictionAlgo:     evictionAlgo,
		capacity:         0,
		maxCapacity:      maxCapacity,
	}
}

func (this *Cache) setEvictionAlgo(e evictionAlgo) {
	this.evictionAlgo = e
}

func (this *Cache) set(key, value string) {
	node_ptr, ok := this.storage[key]
	if ok {
		this.evictionAlgo.set_overwrite(node_ptr, value, this)
		return
	}
	if this.capacity == this.maxCapacity {
		evictedKey := this.evict()
		delete(this.storage, evictedKey)
	}
	node := &node{key: key, value: value}
	this.storage[key] = node
	this.evictionAlgo.set(node, this)
	this.capacity++
}

func (this *Cache) get(key string) string {
	node_ptr, ok := this.storage[key]
	if ok {
		this.evictionAlgo.get(node_ptr, this)
		return (*node_ptr).value
	}
	return ""
}

func (this *Cache) evict() string {
	key := this.evictionAlgo.evict(this)
	this.capacity--
	return key
}

func (this *Cache) print() {
	for k, v := range this.storage {
		fmt.Printf("key :%s value: %s\n", k, (*v).value)
	}
	this.doublyLinkedList.TraverseForward()
}

main.go

package main

import "fmt"

func main() {
	lru := createEvictioAlgo("lru")
	cache := initCache(lru, 3)
	cache.set("a", "1")
	cache.print()

	cache.set("b", "2")
	cache.print()

	cache.set("c", "3")
	cache.print()

	value := cache.get("a")
	fmt.Printf("key: a, value: %s\n", value)
	cache.print()

	cache.set("d", "4")
	cache.print()

	cache.set("e", "5")
	cache.print()
}

Output

Shuffling doubly linked list due to set operation
key :a value: 1
key = a, value = 1, prev = <nil>, next = <nil>

Shuffling doubly linked list due to set operation
key :a value: 1
key :b value: 2
key = a, value = 1, prev = <nil>, next = &{b 2 0xc00007e1e0 <nil>}
key = b, value = 2, prev = &{a 1 <nil> 0xc00007e210}, next = <nil>

Shuffling doubly linked list due to set operation
key :a value: 1
key :b value: 2
key :c value: 3
key = a, value = 1, prev = <nil>, next = &{b 2 0xc00007e1e0 0xc00007e2a0}
key = b, value = 2, prev = &{a 1 <nil> 0xc00007e210}, next = &{c 3 0xc00007e210 <nil>}
key = c, value = 3, prev = &{b 2 0xc00007e1e0 0xc00007e2a0}, next = <nil>

Shuffling doubly linked list due to get operation
key: a, value: 1
key :a value: 1
key :b value: 2
key :c value: 3
key = b, value = 2, prev = <nil>, next = &{c 3 0xc00007e210 0xc00007e1e0}
key = c, value = 3, prev = &{b 2 <nil> 0xc00007e2a0}, next = &{a 1 0xc00007e2a0 <nil>}
key = a, value = 1, prev = &{c 3 0xc00007e210 0xc00007e1e0}, next = <nil>

Evicting by lru strtegy. Evicted Node Key: %s:  b
Shuffling doubly linked list due to set operation
key :d value: 4
key :c value: 3
key :a value: 1
key = c, value = 3, prev = &{b 2 <nil> 0xc00007e2a0}, next = &{a 1 0xc00007e2a0 0xc00007e450}
key = a, value = 1, prev = &{c 3 0xc00007e210 0xc00007e1e0}, next = &{d 4 0xc00007e1e0 <nil>}
key = d, value = 4, prev = &{a 1 0xc00007e2a0 0xc00007e450}, next = <nil>

Evicting by lru strtegy. Evicted Node Key: %s:  c
Shuffling doubly linked list due to set operation
key :a value: 1
key :d value: 4
key :e value: 5
key = a, value = 1, prev = &{c 3 0xc00007e210 0xc00007e1e0}, next = &{d 4 0xc00007e1e0 0xc00007e570}
key = d, value = 4, prev = &{a 1 0xc00007e2a0 0xc00007e450}, next = &{e 5 0xc00007e450 <nil>}
key = e, value = 5, prev = &{d 4 0xc00007e1e0 0xc00007e570}, next = <nil>

Conclusion

This is all about designing an In-Memory Cache. Hope you have liked this article. Please share feedback in the comments

cache

lru