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 L
east R
ecently U
sed. 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
orsync.Map
to make the cache safe for multiple goroutines.