Least Frequently Used (LFU) Cache with Constant Time Complexity

In this blog post, I will explain to you how to implement an in-memory least frequently used cache(LFU) in Go. The implementation has constant time complexity O(1) for Get, Set and Removing the least frequently used item from the cache when the cache is full.

The LFU cache algorithm presented here is based on this paper written by some very very smart people (hey, they even work at FAANG).

Data Structure

Source: An O(1) algorithm for implementing the LFU cache eviction scheme

The data structure for this cache is a struct with 3 fields.

type Cache struct {
    cap           int
    frequencyList *list.List
    lookupTable   map[interface{}]*lookupTableNode
}

cap

This represents the capacity of the cache, i.e the maximum number of items the cache can contain. If the cache already has cap items and you attempt to add a new item in the cache, the least frequently used item will be evicted.

frequencyList

This is a doubly linked list which

• A doubly linked list of all the cache items which have a been accessed n number of times
• n, the frequency weight for items in that node

This list is represented by [head] -> [1] -> [2] -> [5]->[9] in the image above. All the items which have been accessed 1 time will be stored in the node with value [1] so the nodes [x] and [y] have been accessed 1 time while the node [b] has been assessed 5 times since it's under the node [5].

So as not to re-invent the wheel, I used the container/list package for the doubly linked list.

lookupTable

This is a hashmap. i.e basic key => value store. The key in this case, is the key of the item in the cache and the value is a pointer to the item's node in the frequencyList doubly linked list.

Cache Operations

Set

Set is used to an item in the LFU cache with key and value. It returns ErrInvalidCap if the cache is not initialized

func (cache *Cache) Set(key interface{}, value interface{}) (err error) {
    // check if cache has been initialized.
    if cache.Cap() <= 0 {
        return ErrInvalidCap
    }

    // if the key already exists, change the value.
    if _, ok := cache.lookupTable[key]; ok {
        cache.lookupTable[key].value = value
        return
    }

    // create a lookup table node.
    lookupTableNode := &lookupTableNode{value: value}

    // check if the lookupTable has enough space. If it doesn't, pop the least frequently used item from the Cache.
    if cache.IsFull() {
        cache.pop()
    }

    // set the lookup table node.
    cache.lookupTable[key] = lookupTableNode

    // if frequency list is empty or the first item in the list doesn't have weight 1 create a new node with weight 1.
    if cache.frequencyList.Len() == 0 || cache.frequencyList.Front().Value.(*frequencyListNode).weight != minFrequencyWeight {
        freqListNode := &frequencyListNode{weight: minFrequencyWeight, list: list.New()}
        freqListNode.element = cache.frequencyList.PushFront(freqListNode)
    }

    // get the first item in the frequency list node. We're sure the item has the weight 1.
    freqListNode := cache.frequencyList.Front().Value.(*frequencyListNode)

    // set the node parent of the newly set item in the frequency list node Cache.
    freqListNodeListNode := &frequencyListNodeListNode{parent: freqListNode, key: key}

    // set the frequencyListNodeListNode in the lookup table node.
    lookupTableNode.frequencyListNodeListNode = freqListNodeListNode

    // add the newly created frequencyListNodeListNode to the frequencyListNode of weight 1.
    freqListNodeListNode.element = freqListNode.list.PushBack(freqListNodeListNode)

    return err
}

Get

Get returns an item for the LFU cache by a key. It returns ErrCacheMiss if there's a cache miss.

func (cache *Cache) Get(key interface{}) (value interface{}, err error) {
    // check if the key exists if it doesn't return with a Cache miss error.
    node, ok := cache.lookupTable[key]
    if !ok {
        return value, ErrCacheMiss
    }

    freqListNode := node.frequencyListNodeListNode.parent

    // check if the next node's weight is equal to current weight +1
    // if not, create a new node with weight = current weight + 1 ans insert if after the current node
    if freqListNode.element.Next() == nil || (freqListNode.element.Next().Value.(*frequencyListNode).weight != freqListNode.weight+1) {
        newFreqListNode := &frequencyListNode{
            weight:  freqListNode.weight + 1,
            element: nil,
            list:    list.New(),
        }
        newFreqListNode.element = cache.frequencyList.InsertAfter(newFreqListNode, freqListNode.element)
    }

    // gets the list with weight = node weight + 1. This node MUST exist because it was created above
    nextFreqListNode := freqListNode.element.Next().Value.(*frequencyListNode)
    node.frequencyListNodeListNode.parent = nextFreqListNode

    // remove node from current frequency list node
    freqListNode.list.Remove(node.frequencyListNodeListNode.element)

    // remove freq list node from the cache's freq list if the list node has NO item in it.
    if freqListNode.list.Len() == 0 {
        cache.frequencyList.Remove(freqListNode.element)
    }

    // setting the element of the node in it's new list
    node.frequencyListNodeListNode.element = nextFreqListNode.list.PushBack(node.frequencyListNodeListNode)

    return node.value, err
}

pop

The pop method removes the least frequently used item from the LFU Cache.

func (cache *Cache) pop() {
    // The frequency list node MUST exist i.e the cache cap.
    freqListNodeListNode := cache.frequencyList.Front().Value.(*frequencyListNode).list.Front().Value.(*frequencyListNodeListNode)

    // Remove key from lookup table.
    delete(cache.lookupTable, freqListNodeListNode.key)

    // remove node from frequency list node.
    cache.frequencyList.Front().Value.(*frequencyListNode).list.Remove(freqListNodeListNode.element)

    // if frequency list node list is now empty, remove the frequency list node from Cache's frequency list.
    if cache.frequencyList.Front().Value.(*frequencyListNode).list.Len() == 0 {
        cache.frequencyList.Remove(cache.frequencyList.Front())
    }
}

Conclusion

The code for this LFU cache is on github, One improvement I'm thinking of is to make this cache generic so it can work in cases where the key is a string, int or some other comparible struct/pointer. The generics implementation can be found in 2.0-dev branch on github.