Overview
LFU stands for Least Frequently Used. In the LFU cache, the least frequently used object is removed whenever there is a new entry that needs to be inserted and the cache is full. Let’s first see the requirements then we will see an example to understand LFU better.
Requirements
Below are the requirements
- The cache should support Set and Get Operation
- O(logn) Time Complexity for both Set and Get
- Assume the maximum capacity of the cache is n. 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 the eviction algorithm – LFU (Least Frequently Used). If two cache entries have the same frequency or count then remove the one which is Least Recently Used
- Assume both key and value in the cache are of type string
LFU Example
As an example consider a cache of size two where both the key and value of the cache entry is a string. Let’s assume below are the operations
- Set (“a”, “1”) – It adds one element to the cache
- Set (“b”, “2”) – Adds the second element in the cache
- Get (“a”) – Get cache entry with key “a”. Cache entry with key “a” is now used twice while cache entry with key “b” is used only once
- Set (“c”, “3”) – A third cache entry needs to be created. The cache is already full so we need to evict one of the cache entries by the LFU algorithm. Cache entry with key “a” is used twice while cache entry with key “b” is used only once. Hence we will delete the cache with key “b” as it is the Least Frequently Used. Once “b” is deleted we will insert the entry with key “c”
Data Structures to use
As per the requirements, both Set and Get operations should be O(logn). MinHeap seems to be the right size for maintaining the Least Frequently Used Entry. Other than that we are also going to use a Map in order to ensure O(logn) Time complexity. Overall below data structure will be used
Map
A map can only have a key and a value where
- The Key of the map will be the key of the cache entry
- The value of the map will be a pointer to the Min Heap Node.
MinHeap
Each minheap node will have four entries
- Key of the cache entry
- Value of the cache entry
- Index into the Min Heap
- Count of how many times it has been used
As an example for the below set of operations
- Set (“a”, “1”)
- Set (“b”, “2”)
- Get (“a”)
Below will be entries in these data structures
Map
{
"a": "bff5a400", #Pointer to "a" minHeap Node
"b": "bff5a3f6" #Pointer to "a" minHeap Node
}Min Heap
[
{
Key: "b",
Value: "2",
Index: 0,
Count: 1
},
{
Key: "a",
Value: "1",
Index: 1,
Count: 2
}
]Two things
- The count for “a” is 2 because it has been used twice i.e once using the SET operation and the other during the GET operation. The count for “b” is one as it is only used once during the SET operation
- The index for “b” is 0 because it has the lowest count among “a” and “b”
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
- The cache class will be using a combination of a Map and a Min Heap for storing everything. Both map and Min Heap are used so that GET and SET operations are of O(logn) even with evictions. How this is achieved, we will see 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 Min Heap as discussed above
- Min Heap Node will have four entries as discussed above
- There will be an evictionAlgorithm interface. There will be LFU which implements this evictionAlgorithm Interface
- The cache class will also embed an instance of evictionAlgorithm interface.
Let’s see how Get and Set are going to work in O(logn) time
Set Operation (key string, value string)
For any set operation, it is first going to check if the entry with the given key exists in the cache or not. It can be checked by looking at the Map. If the entry exists there we are simply going to update the count and the value in the Min Heap Node. Since the count is increasing we are going to Down Heapify that MinHeap node as the count has changed.
If the cache entry with the given key doesn’t exist, it will first create a Min Heap node with the below details
- The Key will be the key of the cache entry
- The Value will be the value of the cache entry
- Index as the (size of MinHeap+1)
- Count as 1
Once the MinHeap node is created there are two cases
- The cache is not full – In this case, it will pass the control to the current evictionAlgorithm interface. The LFU Algo (implementor of eviction Algorithm Interface) is going to insert that node in the Min Heap at the end and then call Up Heapfiy so that the node reaches its right place in the MinHeap. Overall operation will be O(logn) here
- The cache is full – In this case, it will pass the control to the LFU algorithm. It is going to evict the node which has the least count. Once that node is evicted it will insert the new node. Overall operation is O(logn) here
Get(key string)
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 Min Heap Node pointed to by the key in the map. It will then fetch the value from that MinHeap Node. Then it will pass the control to the current LFU algorithm. The LFU algorithm is going to increase the count of that MinHeap Node by 1 and then call the Down Heapify so that the node reaches its right place in the MinHeap
Let’s see the UML diagram now
UML Diagram
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 {
minHeap *minheap
storage map[string]*minHeapNode
evictionAlgo evictionAlgo
capacity int
maxCapacity int
}
func initCache(evictionAlgo evictionAlgo, maxCapacity int) Cache {}
func (this *Cache) setEvictionAlgo(e evictionAlgo) {}
func (this *Cache) set(key, value string) {}
func (this *Cache) get(key string) string {}
func (this *Cache) evict() string {}
func (this *Cache) print() {}Min Heap Class
type minheap struct {
heapArray []*minHeapNode
size int
}
type minHeapNode struct {
key string
value string
index int
count int
}
func newMinHeap() *minheap {}
func (this *minheap) insert(node *minHeapNode) error {}
func (this *minheap) upHeapify(index int) {}
func (this *minheap) downHeapify(current int) {}
func (this *minheap) remove() *minHeapNode {}
func (this *minheap) print() {}Eviction Algorithm Interface
type evictionAlgo interface {
evict(c *Cache) *minHeapNode
get(node *minHeapNode, c *Cache)
set(node *minHeapNode, c *Cache)
set_overwrite(node *minHeapNode, value string, c *Cache)
}LFU Algorithm – It implements the Eviction Algorithm Interface
type lfu struct {
}
func (l *lfu) evict(c *Cache) *minHeapNode {}
func (l *lfu) get(node *minHeapNode, c *Cache) {}
func (l *lfu) set(node *minHeapNode, c *Cache) {}
func (l *lfu) set_overwrite(node *minHeapNode, value string, c *Cache) {}Full Working Code
Here is the full working code if anyone is interested in the GO programming language
minHeap.go
package main
import "fmt"
type minheap struct {
heapArray []*minHeapNode
size int
}
type minHeapNode struct {
key string
value string
index int
count int
}
func newMinHeap() *minheap {
minheap := &minheap{
heapArray: []*minHeapNode{},
size: 0,
}
return minheap
}
func (this *minheap) leaf(index int) bool {
if index >= (this.size/2) && index <= this.size {
return true
}
return false
}
func (this *minheap) parent(index int) *minHeapNode {
parentIndex := (index - 1) / 2
return this.heapArray[parentIndex]
}
func (this *minheap) leftchild(index int) *minHeapNode {
leftChildIndex := 2*index + 1
if leftChildIndex > this.size-1 {
return nil
}
return this.heapArray[leftChildIndex]
}
func (this *minheap) rightchild(index int) *minHeapNode {
rightChildIndex := 2*index + 2
if rightChildIndex > this.size-1 {
return nil
}
return this.heapArray[rightChildIndex]
}
func (this *minheap) insert(node *minHeapNode) error {
this.heapArray = append(this.heapArray, node)
this.size++
node.index = this.size - 1
this.upHeapify(this.size - 1)
return nil
}
func (this *minheap) swap(first, second *minHeapNode) {
this.heapArray[first.index] = second
this.heapArray[second.index] = first
temp := first.index
first.index = second.index
second.index = temp
}
func (this *minheap) upHeapify(index int) {
parentNode := this.parent(index)
for this.heapArray[index].count < parentNode.count {
this.swap(this.heapArray[index], this.parent(index))
}
}
func (this *minheap) downHeapify(current int) {
if this.leaf(current) {
return
}
currNode := this.heapArray[current]
smallest := currNode
smallestIndex := currNode.index
leftChildNode := this.leftchild(current)
rightChildNode := this.rightchild(current)
//If current is smallest then return
if leftChildNode != nil && leftChildNode.count < smallest.count {
smallest = leftChildNode
smallestIndex = leftChildNode.index
}
if rightChildNode != nil && rightChildNode.count < smallest.count {
smallest = rightChildNode
smallestIndex = rightChildNode.index
}
if smallest != currNode {
this.swap(currNode, smallest)
this.downHeapify(smallestIndex)
}
return
}
func (this *minheap) buildMinHeap() {
for index := ((this.size / 2) - 1); index >= 0; index-- {
this.downHeapify(index)
}
}
func (this *minheap) getMinimum() *minHeapNode {
top := this.heapArray[0]
this.heapArray[0] = this.heapArray[this.size-1]
this.heapArray[0].index = 0
this.heapArray = this.heapArray[:(this.size)-1]
this.size--
this.downHeapify(0)
return top
}
func (this *minheap) print() {
fmt.Println("Printing MinHeap:")
for _, v := range this.heapArray {
fmt.Printf("%+v\n", *v)
}
}evictionAlgorithm.go
package main
type evictionAlgo interface {
evict(c *Cache) *minHeapNode
get(node *minHeapNode, c *Cache)
set(node *minHeapNode, c *Cache)
set_overwrite(node *minHeapNode, value string, c *Cache)
}
func createEvictioAlgo(algoType string) evictionAlgo {
if algoType == "lfu" {
return &lfu{}
}
return nil
}lfu.go
package main
import "fmt"
type lfu struct {
}
func (l *lfu) evict(c *Cache) *minHeapNode {
node := c.minHeap.getMinimum()
fmt.Printf("Evicting by lfu strtegy. Evicted Node Key: %s", node.key)
return node
}
func (l *lfu) get(node *minHeapNode, c *Cache) {
fmt.Printf("Shuffling node with key:%s in the minHeap due to get operation\n", node.key)
node.count++
c.minHeap.downHeapify(node.index)
}
func (l *lfu) set(node *minHeapNode, c *Cache) {
fmt.Printf("Adding a new node with key:%s to minHeap due to set operation\n", node.key)
node.count++
c.minHeap.insert(node)
}
func (l *lfu) set_overwrite(node *minHeapNode, value string, c *Cache) {
fmt.Printf("Shuffling node with key:%s in the minHeap due to set_overwrite operation\n", node.key)
node.value = value
node.count++
c.minHeap.downHeapify(node.index)
}cache.go
package main
import "fmt"
type Cache struct {
minHeap *minheap
storage map[string]*minHeapNode
evictionAlgo evictionAlgo
capacity int
maxCapacity int
}
func initCache(evictionAlgo evictionAlgo, maxCapacity int) Cache {
storage := make(map[string]*minHeapNode)
return Cache{
minHeap: newMinHeap(),
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 := &minHeapNode{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 {
minHeapNode := this.evictionAlgo.evict(this)
this.capacity--
return minHeapNode.key
}
func (this *Cache) print() {
fmt.Println("Printing Entire Cache:")
fmt.Println("Printing Map:")
for k, v := range this.storage {
fmt.Printf("key :%s value: %s\n", k, (*v).value)
}
this.minHeap.print()
fmt.Println()
}main.go
package main
import "fmt"
func main() {
lfu := createEvictioAlgo("lfu")
cache := initCache(lfu, 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()
value = cache.get("b")
fmt.Printf("key: a, value: %s\n", value)
cache.print()
value = cache.get("c")
fmt.Printf("key: a, value: %s\n", value)
cache.print()
cache.set("d", "4")
cache.print()
cache.set("e", "5")
cache.print()
}Output
Adding a new node with key:a to minHeap due to set operation
Printing Entire Cache:
Printing Map:
key :a value: 1
Printing MinHeap:
{key:a value:1 index:0 count:1}
Adding a new node with key:b to minHeap due to set operation
Printing Entire Cache:
Printing Map:
key :a value: 1
key :b value: 2
Printing MinHeap:
{key:a value:1 index:0 count:1}
{key:b value:2 index:1 count:1}
Adding a new node with key:c to minHeap due to set operation
Printing Entire Cache:
Printing Map:
key :a value: 1
key :b value: 2
key :c value: 3
Printing MinHeap:
{key:a value:1 index:0 count:1}
{key:b value:2 index:1 count:1}
{key:c value:3 index:2 count:1}
Shuffling node with key:a in the minHeap due to get operation
key: a, value: 1
Printing Entire Cache:
Printing Map:
key :a value: 1
key :b value: 2
key :c value: 3
Printing MinHeap:
{key:b value:2 index:0 count:1}
{key:a value:1 index:1 count:2}
{key:c value:3 index:2 count:1}
Shuffling node with key:b in the minHeap due to get operation
key: a, value: 2
Printing Entire Cache:
Printing Map:
key :b value: 2
key :c value: 3
key :a value: 1
Printing MinHeap:
{key:c value:3 index:0 count:1}
{key:a value:1 index:1 count:2}
{key:b value:2 index:2 count:2}
Shuffling node with key:c in the minHeap due to get operation
key: a, value: 3
Printing Entire Cache:
Printing Map:
key :a value: 1
key :b value: 2
key :c value: 3
Printing MinHeap:
{key:c value:3 index:0 count:2}
{key:a value:1 index:1 count:2}
{key:b value:2 index:2 count:2}
Evicting by lfu strtegy. Evicted Node Key: cAdding a new node with key:d to minHeap due to set operation
Printing Entire Cache:
Printing Map:
key :a value: 1
key :b value: 2
key :d value: 4
Printing MinHeap:
{key:d value:4 index:0 count:1}
{key:a value:1 index:1 count:2}
{key:b value:2 index:2 count:2}
Evicting by lfu strtegy. Evicted Node Key: dAdding a new node with key:e to minHeap due to set operation
Printing Entire Cache:
Printing Map:
key :a value: 1
key :b value: 2
key :e value: 5
Printing MinHeap:
{key:e value:5 index:0 count:1}
{key:a value:1 index:1 count:2}
{key:b value:2 index:2 count:2}Full Working Code in one file
Here is the full working code in one file
package main
import "fmt"
type minheap struct {
heapArray []*minHeapNode
size int
}
type minHeapNode struct {
key string
value string
index int
count int
}
func newMinHeap() *minheap {
minheap := &minheap{
heapArray: []*minHeapNode{},
size: 0,
}
return minheap
}
func (this *minheap) leaf(index int) bool {
if index >= (this.size/2) && index <= this.size {
return true
}
return false
}
func (this *minheap) parent(index int) *minHeapNode {
parentIndex := (index - 1) / 2
return this.heapArray[parentIndex]
}
func (this *minheap) leftchild(index int) *minHeapNode {
leftChildIndex := 2*index + 1
if leftChildIndex > this.size-1 {
return nil
}
return this.heapArray[leftChildIndex]
}
func (this *minheap) rightchild(index int) *minHeapNode {
rightChildIndex := 2*index + 2
if rightChildIndex > this.size-1 {
return nil
}
return this.heapArray[rightChildIndex]
}
func (this *minheap) insert(node *minHeapNode) error {
this.heapArray = append(this.heapArray, node)
this.size++
node.index = this.size - 1
this.upHeapify(this.size - 1)
return nil
}
func (this *minheap) swap(first, second *minHeapNode) {
this.heapArray[first.index] = second
this.heapArray[second.index] = first
temp := first.index
first.index = second.index
second.index = temp
}
func (this *minheap) upHeapify(index int) {
parentNode := this.parent(index)
for this.heapArray[index].count < parentNode.count {
this.swap(this.heapArray[index], this.parent(index))
}
}
func (this *minheap) downHeapify(current int) {
if this.leaf(current) {
return
}
currNode := this.heapArray[current]
smallest := currNode
smallestIndex := currNode.index
leftChildNode := this.leftchild(current)
rightChildNode := this.rightchild(current)
//If current is smallest then return
if leftChildNode != nil && leftChildNode.count < smallest.count {
smallest = leftChildNode
smallestIndex = leftChildNode.index
}
if rightChildNode != nil && rightChildNode.count < smallest.count {
smallest = rightChildNode
smallestIndex = rightChildNode.index
}
if smallest != currNode {
this.swap(currNode, smallest)
this.downHeapify(smallestIndex)
}
return
}
func (this *minheap) buildMinHeap() {
for index := ((this.size / 2) - 1); index >= 0; index-- {
this.downHeapify(index)
}
}
func (this *minheap) getMinimum() *minHeapNode {
top := this.heapArray[0]
this.heapArray[0] = this.heapArray[this.size-1]
this.heapArray[0].index = 0
this.heapArray = this.heapArray[:(this.size)-1]
this.size--
this.downHeapify(0)
return top
}
func (this *minheap) print() {
fmt.Println("Printing MinHeap:")
for _, v := range this.heapArray {
fmt.Printf("%+v\n", *v)
}
}
type evictionAlgo interface {
evict(c *Cache) *minHeapNode
get(node *minHeapNode, c *Cache)
set(node *minHeapNode, c *Cache)
set_overwrite(node *minHeapNode, value string, c *Cache)
}
func createEvictioAlgo(algoType string) evictionAlgo {
if algoType == "lfu" {
return &lfu{}
}
return nil
}
type lfu struct {
}
func (l *lfu) evict(c *Cache) *minHeapNode {
node := c.minHeap.getMinimum()
fmt.Printf("Evicting by lfu strtegy. Evicted Node Key: %s", node.key)
return node
}
func (l *lfu) get(node *minHeapNode, c *Cache) {
fmt.Printf("Shuffling node with key:%s in the minHeap due to get operation\n", node.key)
node.count++
c.minHeap.downHeapify(node.index)
}
func (l *lfu) set(node *minHeapNode, c *Cache) {
fmt.Printf("Adding a new node with key:%s to minHeap due to set operation\n", node.key)
node.count++
c.minHeap.insert(node)
}
func (l *lfu) set_overwrite(node *minHeapNode, value string, c *Cache) {
fmt.Printf("Shuffling node with key:%s in the minHeap due to set_overwrite operation\n", node.key)
node.value = value
node.count++
c.minHeap.downHeapify(node.index)
}
type Cache struct {
minHeap *minheap
storage map[string]*minHeapNode
evictionAlgo evictionAlgo
capacity int
maxCapacity int
}
func initCache(evictionAlgo evictionAlgo, maxCapacity int) Cache {
storage := make(map[string]*minHeapNode)
return Cache{
minHeap: newMinHeap(),
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 := &minHeapNode{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 {
minHeapNode := this.evictionAlgo.evict(this)
this.capacity--
return minHeapNode.key
}
func (this *Cache) print() {
fmt.Println("Printing Entire Cache:")
fmt.Println("Printing Map:")
for k, v := range this.storage {
fmt.Printf("key :%s value: %s\n", k, (*v).value)
}
this.minHeap.print()
fmt.Println()
}
func main() {
lfu := createEvictioAlgo("lfu")
cache := initCache(lfu, 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()
value = cache.get("b")
fmt.Printf("key: a, value: %s\n", value)
cache.print()
value = cache.get("c")
fmt.Printf("key: a, value: %s\n", value)
cache.print()
cache.set("d", "4")
cache.print()
cache.set("e", "5")
cache.print()
}Output
Adding a new node with key:a to minHeap due to set operation
Printing Entire Cache:
Printing Map:
key :a value: 1
Printing MinHeap:
{key:a value:1 index:0 count:1}
Adding a new node with key:b to minHeap due to set operation
Printing Entire Cache:
Printing Map:
key :b value: 2
key :a value: 1
Printing MinHeap:
{key:a value:1 index:0 count:1}
{key:b value:2 index:1 count:1}
Adding a new node with key:c to minHeap due to set operation
Printing Entire Cache:
Printing Map:
key :a value: 1
key :b value: 2
key :c value: 3
Printing MinHeap:
{key:a value:1 index:0 count:1}
{key:b value:2 index:1 count:1}
{key:c value:3 index:2 count:1}
Shuffling node with key:a in the minHeap due to get operation
key: a, value: 1
Printing Entire Cache:
Printing Map:
key :c value: 3
key :a value: 1
key :b value: 2
Printing MinHeap:
{key:b value:2 index:0 count:1}
{key:a value:1 index:1 count:2}
{key:c value:3 index:2 count:1}
Shuffling node with key:b in the minHeap due to get operation
key: a, value: 2
Printing Entire Cache:
Printing Map:
key :a value: 1
key :b value: 2
key :c value: 3
Printing MinHeap:
{key:c value:3 index:0 count:1}
{key:a value:1 index:1 count:2}
{key:b value:2 index:2 count:2}
Shuffling node with key:c in the minHeap due to get operation
key: a, value: 3
Printing Entire Cache:
Printing Map:
key :b value: 2
key :c value: 3
key :a value: 1
Printing MinHeap:
{key:c value:3 index:0 count:2}
{key:a value:1 index:1 count:2}
{key:b value:2 index:2 count:2}
Evicting by lfu strtegy. Evicted Node Key: cAdding a new node with key:d to minHeap due to set operation
Printing Entire Cache:
Printing Map:
key :d value: 4
key :a value: 1
key :b value: 2
Printing MinHeap:
{key:d value:4 index:0 count:1}
{key:a value:1 index:1 count:2}
{key:b value:2 index:2 count:2}
Evicting by lfu strtegy. Evicted Node Key: dAdding a new node with key:e to minHeap due to set operation
Printing Entire Cache:
Printing Map:
key :a value: 1
key :b value: 2
key :e value: 5
Printing MinHeap:
{key:e value:5 index:0 count:1}
{key:a value:1 index:1 count:2}
{key:b value:2 index:2 count:2}Conclusion
This is all about designing an LFU-based Memory Cache. Hope you have liked this article. Please share feedback in the comments
Note: Check out our system design tutorial series System Design Questions