What is LRU cache

A cache is a way to store data that ac­cessed fre­quently and needs to be fast. We can use cache to store a re­sult from com­pu­ta­tion or re­sult of SQL query. A cache is usu­ally stored in mem­ory with a key-value style to make sure it fast to store item and ac­cess.

One of the cache al­go­rithms is LRU or Least Recently Used. LRU will limit the mem­ory us­age by gives max­i­mum items that can be stored. When there is a new item to be store and it al­ready reached the limit, it dis­cards the least used item.

How to make LRU Cache in GO

TLDR

Check the full code in this repo

• lru­cache (non con­cur­rent)
• lru­cache (concurrent)

There are two main com­po­nents in LRU cache, those are Queue and Hash Map. The Queue is used to store the items that im­ple­mented in a linked list, while the Hash Map is used to make the com­plex­ity O(1) when ac­cessed.

Creating Queue perma­link

Disclaimer

The queue I im­ple­mented is based on my opin­ion, it may not be the “right” one :)

We need to cre­ate a struct for the cache item, a linked list node, and the queue.

type Queue struct {
	head *Node
	tail *Node
}

type Node struct {
	item Item
	next *Node
	prev *Node
}

type Item struct {
	Key   string
    // Value is used to store an item
	Value interface{}
}

We will cre­ate three meth­ods for the queue InsertFirst, RemoveLast, and RemoveNode.

The struc­ture of the Node. It has three parts, prev, value, and next. The prev and next are point­ers to an ad­ja­cent node. The value is an interface{} that can hold any data type.

These are al­go­rithm and code for InsertFirst

// insert a node into the first of the queue
func (q *Queue) InsertFirst(newHead *Node) {
	if q.isEmpty() {
		q.head = newHead
		q.tail = newHead
		return
	}

	oldHead := q.head
	newHead.next = oldHead
	oldHead.prev = newHead
	q.head = newHead
}

These are al­go­rithm and code for RemoveLast

// remove a node from the last queue
func (q *Queue) RemoveLast() *Node {
	if q.isEmpty() {
		return nil
	}

	if q.isOne() {
		last := q.tail
		q.tail = nil
		q.head = nil
		last.breakLinks()
		return last
	}

	oldLast := q.tail
	newLast := q.tail.prev
	q.tail = newLast
	oldLast.breakLinks()
	return oldLast
}

These are al­go­rithm and code for RemoveNode

// remove a node from any position in the queue
func (q *Queue) RemoveNode(node *Node) {
	if q.isEmpty() {
		return
	}

	if q.isOne() {
		q.head.breakLinks()
		q.tail.breakLinks()
		node.breakLinks()
		return
	}

	// node is first in the queue with following N-nodes
	if node == q.head {
		// new head is the next in the queue
		q.head = node.next
		node.breakLinks()
		return
	}

	// node is the last in the queue with previos N-nodes
	if node == q.tail {
		// new tail is the one before the node
		q.tail = node.prev
		node.breakLinks()
		return
	}

	// node is in the middle of the queue
	after := node.next
	before := node.prev
	// link the before & after
	before.next = after
	after.prev = before
	node.breakLinks()
}

The code for MoveToFirst

func (q *Queue) MoveToFirst(node *Node) {
	// no need to move, there is one or none in the queue
	if q.isEmpty() || q.isOne() {
		return
	}

	if q.head == node {
		return
	}

	if q.tail == node {
		beforeTail := node.prev
		q.tail = beforeTail
		beforeTail.next = nil

		node.breakLinks()
		node.next = q.head
		q.head = node
		return
	}

	nodeBefore := node.prev
	nodeAfter := node.next
	nodeBefore.next = nodeAfter
	nodeAfter.prev = nodeBefore
	node.breakLinks()
	node.next = q.head
	q.head = node
}

Helper meth­ods for the Queue

func (q *Queue) isEmpty() bool {
	return q.head == nil && q.tail == nil
}

func (q *Queue) isOne() bool {
	return q.head != nil && q.head.next == nil
}

The breakLinks method is im­ple­mented as fol­lows

// set next & prev to nil
func (n *Node) breakLinks() {
	if n == nil {
		return
	}

	n.next = nil
	n.prev = nil
}

Creating LRUCacher perma­link

// LRUCacher not concurrent safe
type LRUCacher struct {
	queue       *Queue
	hash        map[string]*Node
	MaxSize     int
	count int
}

Codes for Put

// Put set new or replace existing item
func (l *LRUCacher) Put(key string, value interface{}) {
	if l.MaxSize < 1 {
		l.MaxSize = DefaultMaxSize
	}

	if l.queue == nil {
		l.queue = NewQueue()
	}

	if l.hash == nil {
		l.hash = make(map[string]*Node)
	}

	item := Item{
		Key:   key,
		Value: value,
	}

	// if key already exist just replace the cache item
	oldNode, ok := l.hash[key]
	if ok {
		oldNode.item = item
		return
	}

	node := &Node{item: item}
	if l.queueIsFull() {
		last := l.queue.RemoveLast()
		l.removeItem(last.item)

		l.hash[key] = node
		l.queue.InsertFirst(node)
		return
	}

	l.hash[key] = node
	l.queue.InsertFirst(node)
	l.count++
}

The re­cently called item, will be move to the first of the queue

func (l *LRUCacher) Get(key string) interface{} {
	if l.hash == nil {
		return nil
	}

	val, ok := l.hash[key]
	if !ok {
		return nil
	}

	l.queue.MoveToFirst(val)

	return val.item.Value
}

Codes for Del

func (l *LRUCacher) Del(key string) interface{} {
	node, ok := l.hash[key]
	if !ok {
		return nil
	}

	l.queue.RemoveNode(node)
	l.removeItem(node.item)
    l.count--
	return node.item.Value
}

Notes on Implement Synchronization for Concurrency

The pre­vi­ous codes work for non-con­cur­rent us­age be­cause when ac­cess­ing & writ­ing to the hash map or queue, there are needs for lock and syn­chro­niza­tion. Also keep in mind, that adding syn­chro­niza­tion will im­pact the per­for­mance.

We can use a mutex for syn­chro­niza­tion. In Go, there are two types of mu­tex, Mutex and RWMutex. The Mutex is gen­eral pur­pose for lock­ing only one gor­ou­tine that has ac­cess to a re­source. The RWMutex has two lock­ing mech­a­nisms. The first is RLock that can be­hold by mul­ti­ple goru­ti­nes and is used for read­ing. The Second is a Lock that can only be­hold by one gor­ou­tine and is used for writ­ing.

I use two mu­texes for LRUCacher, hashMutex for ac­cess & mu­tat­ing hash, and countMutex when mu­tat­ing the count. Also, to help to de­tects race con­di­tion, I use -race flag when run­ning the go test

go test -race ./...

The rest of the code can be checked in this repo lru­cache

type LRUCacher struct {
	maxSize int64

	queue      *Queue
	count      int64
	countMutex sync.RWMutex

	hash      map[string]*Node
	hashMutex sync.RWMutex
}

The bench­mark

go test -benchmem -run=^$ -bench ^(BenchmarkLRUCacher)$ github.com/fahmifan/lrucache

goos: linux
goarch: amd64
pkg: github.com/fahmifan/lrucache
cpu: Intel(R) Core(TM) i5-7400 CPU @ 3.00GHz
BenchmarkLRUCacher/Put-4         	 2813918	       422.4 ns/op	      89 B/op	       4 allocs/op
BenchmarkLRUCacher/Get-4         	 9076047	       131.4 ns/op	      16 B/op	       1 allocs/op
BenchmarkLRUCacher/Del-4         	11179544	       107.6 ns/op	      12 B/op	       1 allocs/op
PASS
ok  	github.com/fahmifan/lrucache	4.228s

That’s the LRU Cache and how you can im­ple­ment it in Go :)