Purpose to to be curious

Updated : 2022-12-02

In this piece, we are going to demonstrate how to implement an LRU cache in Golang. I encountered this problem recently in an interview and decided to solidify my understanding by building one from scratch. Let’s examine how the LRU cache works.

From a high level, think of the LRU cache as a list of a specific cache number of items. That is the cache can only have a specific number of items at a time. This is the cache’s capacity. If it happens the cache is full, the algorithm will evict the least recently used item. Hence the name Least Recently Used. We are going to use a map and a linked list to have a cache whose operations are O(1). Let’s now write some code.

import (
    "container/list"
)

type struct LRUCache{
    containerList *list.List
	storage       map[string]*Node
	capacity      int
	maxCapacity int
}

We define the cache structure as a struct LRUCache. The containerList field is a pointer to a doubly-linked list that will move items either left or right depending on how least frequently they are used. capacity tells us the current number of items in the cache while maxCapacity indicated how many items the cache can hold. storage field points to a map that will store items. Items will be defined as nodes.

type Node struct {
	key   string
	value string
}

Let’s now introduce a NewCache that will instantiate the cache.

func NewCache(max int) *cache {
	cache := &cache{
		containerList: list.New(),
		storage:       make(map[string]*Node),
		capacity:      0,
		maxCapacity:   max,
	}
	return cache
}

Notice that we pass the maxCapacity as an argument instead of hard-coding a value. This will give our cache flexibility depending on our use case.

Next, we define two main functions to operate on the cache. One is to add items to the cache while the other is to retrieve an item from the cache. We will name the functions Set and `Get. Let’s begin with the set function.

func (cache *cache) set(key, value string) string {
    // TODO: add implementation
}

As we can see, adding an item to the cache returns the value as a string. Ideally, we would use a generic so that the cache can store values of any type. However for now we’ll keep things simple. Next, we need to check whether the key is in the cache. If present, we update its node by moving it to the back of our linked list. In our use case, the most used items are at the back of our linked list. Meaning when we finally implement an eviction algorithm, we will remove the front-most item.

node0, ok := cache.storage[key]
if ok {
	n := cache.update_node(node0, value)
	return n.value
}

Notice we call the update_node method which is not yet defined. Let’s add it.

func (cache *cache) update_node(node *Node, value string) *Node {
	node.value = value
	cache.containerList.MoveToBack(&list.Element{Value: node})
	return node
}

Back to the set function. Now that we have a way to check if a node is present in the cache, we need to handle the situation when the node is not present. We do that by first checking whether the cache has enough capacity for a new item. Otherwise, we evict the least used item from the cache.

if cache.capacity == cache.maxCapacity {
	front := cache.containerList.Front()
	n := front.Value.(*Node)
	delete(cache.storage, n.key)
	cache.containerList.Remove(front)
	cache.capacity -= 1
}

Finally, we create a node object and add it in both the map and the linked list.

node := &Node{key: key, value: value}
cache.storage[key] = node
elm := cache.containerList.PushBack(node)
n := elm.Value.(*Node)
cache.capacity += 1
return n.value

With that, the set operation is complete. Next, we move to the get operation which is the simplest. All it has to do is use the provided key and retrieve it from the map. If not found, an error is returned. Otherwise, the node is moved back of the linked list and its value returned to the caller.

func (cache *cache) get(key string) (string, error) {
	node, ok := cache.storage[key]
	if ok {
		cache.containerList.MoveToBack(&list.Element{Value: node})
		return node.value, nil
	}

	return "", errors.New("key not found")
}

We are done. Here is the full implementation.

import (
	"container/list"
	"errors"
)

type struct LRUCache{
    containerList *list.List
	storage       map[string]*Node
	capacity      int
	maxCapacity int
}

type Node struct {
	key   string
	value string
}

func NewCache(max int) *cache {
	cache := &cache{
		containerList: list.New(),
		storage:       make(map[string]*Node),
		capacity:      0,
		maxCapacity:   max,
	}
	return cache
}

func (cache *cache) set(key, value string) string {
    node0, ok := cache.storage[key]
    if ok {
        n := cache.update_node(node0, value)
        return n.value
    }

    if cache.capacity == cache.maxCapacity {
        front := cache.containerList.Front()
        n := front.Value.(*Node)
        delete(cache.storage, n.key)
        cache.containerList.Remove(front)
        cache.capacity -= 1
    }

    node := &Node{key: key, value: value}
    cache.storage[key] = node
    elm := cache.containerList.PushBack(node)
    n := elm.Value.(*Node)
    cache.capacity += 1
    return n.value
}

func (cache *cache) get(key string) (string, error) {
	node, ok := cache.storage[key]
	if ok {
		cache.containerList.MoveToBack(&list.Element{Value: node})
		return node.value, nil
	}

	return "", errors.New("key not found")
}

func (cache *cache) update_node(node *Node, value string) *Node {
	node.value = value
	cache.containerList.MoveToBack(&list.Element{Value: node})
	return node
}

Improvements

We can use generics instead of concrete types to make it work of any type.
We can introduce sync.RWMutex or sync.Map to make the cache safe for multiple goroutines.

May 10, 2021

LRU cache implementation in Golang

Improvements

Share