Introduction

A cache is a temporary storage area that holds frequently accessed data to reduce the need for costly retrievals from slower sources, such as databases or external APIs. An LRU cache implements a specific eviction policy that removes the least recently used item when the cache reaches its capacity.

Purpose in Optimizing Data Access:

Reduced latency: By storing frequently accessed data in memory, LRU caches can significantly decrease the time it takes to retrieve that data, leading to faster application response times and a smoother user experience.
Reduced network traffic: By minimizing the need to fetch data from external sources repeatedly, LRU caches can conserve network bandwidth and reduce strain on backend systems.
Improved scalability: LRU caches can help applications handle more requests and scale more effectively.
Enhanced user experience: Faster data access and reduced latency often translate into a more responsive and enjoyable user experience, especially for applications that rely heavily on data retrieval.

Common use cases where LRU caches are beneficial

Web Servers:

Caching static assets: Images, CSS stylesheets, JavaScript files, and other static resources are cached to reduce server load and improve page load times.
Session data management: User session data, such as login information and shopping cart contents, can be cached for quick retrieval and improved user experience.

Database Systems:

Query caching: Results of frequently executed database queries can be cached to reduce database load and enhance query performance.
Row-level caching: Individual rows or data objects are cached to accelerate data retrieval and updates.

File Systems:

Caching file metadata: Information about files and directories can be cached to speed up file operations and reduce disk I/O.
Caching file content: Frequently accessed file content can be cached in memory for faster reads, especially for files or frequently accessed parts of larger files.

LRU Algorithm Core Principle

Evicting Least Recently Used Items: When the cache reaches its capacity, the LRU algorithm removes the item that is least Retrieved recently to make room for new items. This prioritization uses the assumption that recently accessed items are more likely to be needed again shortly.

Key Data Structures

Map (Hash Table):
- Stores key-value pairs for efficient retrieval.
- Provides fast lookups by key, typically in O(1) time.
- Maps keys to corresponding nodes in the doubly linked list.
Doubly Linked List:
- Maintains the order of items based on their access time.
- The head of the list represents the most recently used item, while the tail represents the least recently used.
- Nodes are moved to the head of the list when accessed, ensuring the LRU eviction policy.

LRU Cache Visualisation

Implementation Steps

Define Data Structures:
- node: Represents a key-value pair in the cache.
  - value: The value stored in the cache.
  - key: The key associated with the value.
  - prev: Pointer to the previous node in the doubly linked list.
  - nxt: Pointer to the next node in the doubly linked list.

        package main

        type node struct {
            value int
            key   int
            prev  *node
            nxt   *node
        }

cache: Represents the LRU cache itself.
- hashMap: A map to store key-value pairs for efficient lookup.
- capacity: The maximum number of items the cache can hold.
- head: Pointer to the head of the doubly linked list (most recently used).
- tail: Pointer to the tail of the doubly linked list (least recently used).

        type cache struct {
            hashMap  map[int]*node
            capacity int
            head     *node
            tail     *node
        }

Implement a function to return a cache:

Create a new cache using the newLRUCache function:
Pass the desired capacity as argument size.

Initialize the hashMap, capacity, head, and tail fields.

  func newLRUCache(size int) *cache {
      headNode := &node{
          prev: nil,
      }
      tailNode := &node{
          prev: headNode,
          nxt:  nil,
      }
      headNode.nxt = tailNode
      return &cache{
          capacity: size,
          hashMap:  make(map[int]*node),
          head:     headNode,
          tail:     tailNode,
      }
  }

Test for newLRUCache, to be written in main_test.go.

  package main

  import (
      "testing"
  )

  func TestNewLRUCache(t *testing.T) {
      // Test case 1: Create a new LRU cache with size 3
      cache := newLRUCache(3)

      // Check if the cache initialized correctly
      if cache.capacity != 3 || cache.head == nil || cache.tail == nil || cache.head.nxt != cache.tail || cache.tail.prev != cache.head {
          t.Error("NewLRUCache initialization failed.")
      }

      // Test case 2: Create a new LRU cache with size 0
      emptyCache := newLRUCache(0)

      // Check if the cache is initialized correctly for size 0
      if emptyCache.capacity != 0 || emptyCache.head == nil || emptyCache.tail == nil || emptyCache.head.nxt != emptyCache.tail || emptyCache.tail.prev != emptyCache.head {
          t.Error("NewLRUCache initialization failed for size 0.")
      }
  }

Implement Core LRU Operations:

addNode(n node): Adds a node to the head of the doubly linked list.

  // add a new node to the head
  func (c *cache) addNode(n *node) {
      nxtNode := c.head.nxt
      prevNode := c.head
      prevNode.nxt = n
      nxtNode.prev = n
      n.nxt = nxtNode
      n.prev = prevNode
  }

Test for addNode(n node):

  func TestCacheAddNode(t *testing.T) {
      // Test case 1: Add a node to an empty cache
      cache := newLRUCache(3)

      newNode1 := &node{value: 101, key: 1}
      cache.addNode(newNode1)

      // Check if the node is correctly added to the head
      if cache.head.nxt != newNode1 || newNode1.prev != cache.head || newNode1.nxt != cache.tail {
          t.Error("AddNode failed for an empty cache.")
      }

      // Test case 2: Add a node to a non-empty cache
      newNode2 := &node{value: 102, key: 2}
      cache.addNode(newNode2)

      // Check if the new node is correctly added to the head and linked to the previous head
      if cache.head.nxt != newNode2 || newNode2.prev != cache.head || newNode2.nxt != newNode1 {
          t.Error("AddNode failed for a non-empty cache.")
      }

      // Test case 3: Add a node to a cache at full capacity
      newNode3 := &node{value: 103, key: 3}
      cache.addNode(newNode3)

      // Check if the new node is correctly added to the head, linked to the previous head, and the tail is updated
      if cache.head.nxt != newNode3 || newNode3.prev != cache.head || newNode3.nxt != newNode2 || newNode2.nxt != newNode1 || cache.tail.prev != newNode1 {
          t.Error("AddNode failed for a cache at full capacity.")
      }
  }

removeNode(n node) bool: Removes a node from the doubly linked list.

  //Remove a node from the list
  func (c *cache) removeNode(n *node) bool {
      prev := n.prev
      next := n.nxt
      if prev == nil && next == nil {
          return false
      }
      prev.nxt = next
      next.prev = prev
      n.prev = nil
      n.nxt = nil
      return true
  }

Test for removeNode(n node) bool:

  func TestCacheRemoveNode(t *testing.T) {
      // Test case 1: Remove a node from a non-empty cache
      cache := newLRUCache(3)

      // Add nodes to the cache
      node1 := &node{value: 101, key: 1}
      node2 := &node{value: 102, key: 2}
      node3 := &node{value: 103, key: 3}
      cache.addNode(node1)
      cache.addNode(node2)
      cache.addNode(node3)

      // Remove node2 from the cache
      cache.removeNode(node2)

      // Check if node2 is correctly removed
      if node2.prev != nil || node2.nxt != nil || node1.prev != node3 || node3.nxt != node1 || cache.head.nxt != node3 {
          t.Error("RemoveNode failed for a non-empty cache.")
      }

      // Test case 2: Remove the node3 from the cache
      cache.removeNode(node3)

      // Check if node3 no longer exists in the cache, and the tail is updated
      if node3.prev != nil || node3.nxt != nil || cache.tail.prev != node1 || node1.nxt != cache.tail || cache.head.nxt != node1 {
          t.Error("RemoveNode failed for the last node in the cache.")
      }

      // Test case 3: Remove a node from a cache with only one node
      cache.removeNode(node1)

      // Check if node1 no longer exists in the cache, and the cache becomes empty
      if node1.prev != nil || node1.nxt != nil || cache.head.nxt != cache.tail || cache.tail.prev != cache.head {
          t.Error("RemoveNode failed for the last node in the cache.")
      }

      // Test case 4: Remove a node that is not in the cache
      notInCache := &node{value: 104, key: 4}
      cache.removeNode(notInCache)

      // Check if the cache remains unchanged after removing a node not in the cache
      if cache.head.nxt != cache.tail || cache.tail.prev != cache.head {
          t.Error("RemoveNode failed for a node not in the cache.")
      }
  }

moveToHead(n node): Moves a node to the head of the list, marking it as recently used.

  //Move the node in the middle of the list to the head
  func (c *cache) moveToHead(n *node) {
      ok := c.removeNode(n)
      if ok {
          c.addNode(n)
      }
  }

Test for moveToHead(n node):

      func TestCacheMoveToHead(t *testing.T) {
      // Test case 1: Move a node to the head in a non-empty cache
      cache := newLRUCache(3)

      // Add nodes to the cache
      node1 := &node{value: 101, key: 1}
      node2 := &node{value: 102, key: 2}
      node3 := &node{value: 103, key: 3}
      cache.addNode(node1)
      cache.addNode(node2)
      cache.addNode(node3)

      // Move node2 to the head
      cache.moveToHead(node2)

      // Check if node2 is correctly moved to the head
      if cache.head.nxt != node2 || node2.prev != cache.head || node2.nxt != node3 || node3.prev != node2 {
          t.Error("MoveToHead failed for a non-empty cache.")
      }

      // Test case 2: Move the last node to the head
      cache.moveToHead(node1)

      // Check if node1 has been relocated to the head and the tail is updated
      if cache.head.nxt != node1 || node1.prev != cache.head || node1.nxt != node2 || cache.tail.prev != node3 {
          t.Error("MoveToHead failed for the last node in the cache.")
      }

      // Test case 3: Move a node in a cache with only one node
      cache.moveToHead(node3)

      // Check if node3 is correctly moved to the head, and the cache remains unchanged
      if cache.head.nxt != node3 || node3.prev != cache.head || node3.nxt != node1 || cache.tail.prev != node2 {
          t.Error("MoveToHead failed for a cache with only one node.")
      }

      // Test case 4: Move a node that is not in the cache
      notInCache := &node{value: 104, key: 4}
      cache.moveToHead(notInCache)

      // Check if the cache remains unchanged when trying to move a node not in the cache
      if cache.head.nxt != node3 || node3.prev != cache.head || node3.nxt != node1 || cache.tail.prev != node2 {
          t.Error("MoveToHead failed for a node not in the cache.")
      }
  }

popTail() node: Removes and returns the least recently used node from the tail of the list.

  // pop tail
  func (c *cache) popTail() *node {
      res := c.tail.prev
      if res.prev == nil {
          return nil
      }
      c.removeNode(res)
      return res
  }

Test for popTail() node:

  func TestCachePopTail(t *testing.T) {
      // Test case 1: Pop the tail node in a non-empty cache
      cache := newLRUCache(3)

      // Add nodes to the cache
      node1 := &node{value: 101, key: 1}
      node2 := &node{value: 102, key: 2}
      node3 := &node{value: 103, key: 3}
      cache.addNode(node1)
      cache.addNode(node2)
      cache.addNode(node3)

      // Pop the tail node
      poppedNode := cache.popTail()

      // Check if the tail node is correctly popped and returned
      if poppedNode != node1 || cache.tail.prev != node2 || node2.nxt != cache.tail {
          t.Error("PopTail failed for a non-empty cache.")
      }

      // Test case 2: Pop the tail node in a cache with only one node
      cache = newLRUCache(1)
      soleNode := &node{value: 201, key: 1}
      cache.addNode(soleNode)

      // Pop the tail node
      poppedNode = cache.popTail()

      // Check if the sole node is correctly popped and returned, and the cache becomes empty
      if poppedNode != soleNode || cache.head.nxt != cache.tail || cache.tail.prev != cache.head {
          t.Error("PopTail failed for a cache with only one node.")
      }

      // Test case 3: Pop the tail node from an empty cache
      emptyCache := newLRUCache(0)

      // Pop the tail node
      poppedNode = emptyCache.popTail()

      // Check if nil is returned when popping from an empty cache
      if poppedNode != nil {
          t.Error("PopTail failed for an empty cache.")
      }
  }

Retrieve Values:

get(key int) node: Retrieves a value from the cache and checks if the key exists in the hashMap.If found, move the corresponding node to the head using moveToHead(n node) and return it. If not found, returns nil.
```
  func (c *cache) get(key int) *node {
      n, ok := c.hashMap[key]
      if ok {
          c.moveToHead(n)
          return n
      }
      return nil
  }
```

Test for get(key int) node:

  func TestCacheGet(t *testing.T) {
      // Test case 1: Get a node with an existing key in the cache
      cache := newLRUCache(3)

      // Add nodes to the cache
      node1 := &node{value: 101, key: 1}
      node2 := &node{value: 102, key: 2}
      node3 := &node{value: 103, key: 3}
      cache.addNode(node1)
      cache.hashMap[node1.key] = node1
      cache.addNode(node2)
      cache.hashMap[node2.key] = node2
      cache.addNode(node3)
      cache.hashMap[node3.key] = node3

      // Get node with key 2
      resultNode := cache.get(2)

      // Check if the correct node is returned and moved to the head
      if resultNode != node2 || cache.head.nxt != node2 || node2.prev != cache.head || node2.nxt != node3 {
          t.Error("Get failed for an existing key in the cache.")
      }

      // Test case 2: Get a node with a non-existing key in the cache
      nonExistingKey := 4
      resultNode = cache.get(nonExistingKey)

      // Check if nil is returned for a non-existing key, and the cache remains unchanged
      if resultNode != nil || cache.head.nxt != node2 || node2.prev != cache.head || node2.nxt != node3 {
          t.Error("Get failed for a non-existing key in the cache.")
      }
  }

Add or Update Values:

put(key, value int): Adds or updates a key-value pair in the cache and checks if the key exists in the hashMap. If found, update the value and move the node to the head. If not found, create a new node and add it to the head. If the cache is full, evict the least recently used node (using popTail) to make space.

  func (c *cache) put(key, value int) {
      n, ok := c.hashMap[key]
      if ok {
          c.removeNode(n)
      }
      newNode := &node{
          value: value,
          key:   key,
      }
      c.addNode(newNode)
      c.hashMap[key] = newNode
      if len(c.hashMap) > c.capacity {
          nodeToRemove := c.popTail()
          delete(c.hashMap, nodeToRemove.key)
      }
  }

Test for put(key, value int):

  func TestCachePut(t *testing.T) {
      // Test case 1: Put a new node into the cache
      cache := newLRUCache(3)

      // Put a new node with key 1 and value 101
      cache.put(1, 101)

      // Check if the node is correctly added to the cache and hashMap
      if len(cache.hashMap) != 1 || cache.head.nxt.key != 1 || cache.head.nxt.value != 101 || cache.tail.prev.key != 1 || cache.tail.prev.value != 101 {
          t.Error("Put failed for adding a new node.")
      }

      // Test case 2: Put a node with an existing key into the cache
      cache.put(1, 102)

      // Check if the existing node is correctly updated and moved to the head
      if len(cache.hashMap) != 1 || cache.head.nxt.key != 1 || cache.head.nxt.value != 102 || cache.tail.prev.key != 1 || cache.tail.prev.value != 102 {
          t.Error("Put failed for updating an existing node.")
      }

      // Test case 3: Put nodes into the cache until reaching capacity, causing eviction
      cache.put(2, 202)
      cache.put(3, 303)
      cache.put(4, 404)

      // Check if the eviction occurred and the cache is at its capacity
      if len(cache.hashMap) != 3 || cache.head.nxt.key != 4 || cache.head.nxt.value != 404 || cache.tail.prev.key != 2 || cache.tail.prev.value != 202 {
          t.Error("Put failed for reaching cache capacity and eviction.")
      }
  }

Usage Example:

 package main

 func main() {
     cache := newLRUCache(2) // Create a cache with capacity 2
     cache.put(1, 10)
     cache.put(2, 20)
     val := cache.get(1) // Returns 10, moves node 1 to the head
     cache.put(3, 30) // Evicts node 2 (least recently used)
 }

Conclusion

This article explored the key concepts and implementation details of LRU (Least Recently Used) caches in Golang. Here are the key takeaways:

Caching Principle: LRU caches store frequently accessed data in memory to reduce expensive retrieval costs from slower sources. They prioritize recently used items, evicting the least recently used when reaching capacity.
Data Structures: LRU caches typically use a combination of a map for fast key-value lookup and a doubly linked list to maintain the access order.
Implementation Steps: The article outlined the core functions of an LRU cache in Golang, including adding, retrieving, updating, and removing key-value pairs while managing eviction and maintaining the linked list order.

By understanding the principles and benefits of LRU caching and exploring advanced options and practical applications, Golang developers can leverage this powerful technique to enhance performance, optimize resource utilization, and build more efficient and responsive applications.

References

Implementing Least Recently Used (LRU) Cache

Implement a Least Recently Used Cache in Go.

Table of contents