LRU Cache

LRU Algorithm Deep Dive

LRU (Least Recently Used) is an eviction algorithm that removes the item that hasn't been accessed for the longest time.

Core Concept

Principle: Recently accessed items are more likely to be accessed again.

Access Pattern: A B C D A B E

State Tracking:
[A] → [B,A] → [C,B,A] → [D,C,B,A] → [A,D,C,B] → [B,A,D,C] → [E,B,A,D]
      MRU          MRU          MRU          MRU          MRU          MRU
      LRU          LRU          LRU          LRU          LRU          LRU

When capacity exceeded, evict LRU item (leftmost)

Operations

Operation	Description	Time Complexity
GET(key)	Access item, move to MRU	O(1)
PUT(key, val)	Insert/update, evict LRU if needed	O(1)
DELETE(key)	Remove specific item	O(1)

Why O(1) is Possible

• HashMap: O(1) key lookup
• Doubly Linked List: O(1) reordering
• Combined: O(1) for all operations

Implementation with HashMap + LinkedList

Complete O(1) LRU Cache

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> Node
        
        # Dummy head and tail for easier manipulation
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def _remove(self, node):
        """Remove node from linked list"""
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _add_to_front(self, node):
        """Add node right after head (most recently used)"""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
    
    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            # Move to front (most recently used)
            self._remove(node)
            self._add_to_front(node)
            return node.value
        return -1
    
    def put(self, key, value):
        if key in self.cache:
            # Update existing
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_front(node)
        else:
            # Add new
            if len(self.cache) >= self.capacity:
                # Evict LRU (node before tail)
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
            
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_front(new_node)

# Usage
lru = LRUCache(2)
lru.put(1, 1)    # Cache: {1:1}
lru.put(2, 2)    # Cache: {2:2, 1:1}
lru.get(1)       # Returns 1, Cache: {1:1, 2:2}
lru.put(3, 3)    # Evicts 2, Cache: {3:3, 1:1}
lru.get(2)       # Returns -1 (evicted)

Python OrderedDict Shortcut

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key):
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        return -1
    
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

Memory Layout

Doubly Linked List with Dummy Nodes:

[Head] ⇄ [A] ⇄ [B] ⇄ [C] ⇄ [Tail]
          ↑                ↑
         MRU              LRU

When accessing B:
[Head] ⇄ [B] ⇄ [A] ⇄ [C] ⇄ [Tail]
          ↑              ↑
         MRU            LRU

LRU Cache Use Cases

1. Database Query Cache

class QueryCache:
    def __init__(self, capacity=10000):
        self.cache = LRUCache(capacity)
    
    def execute_query(self, query, params):
        cache_key = hash(query + str(params))
        
        result = self.cache.get(cache_key)
        if result is not None:
            return result  # Cache hit
        
        # Cache miss - execute query
        result = db.execute(query, params)
        self.cache.put(cache_key, result)
        return result

2. DNS Cache

class DNSCache:
    def __init__(self, capacity=1000):
        self.cache = LRUCache(capacity)
    
    def resolve(self, hostname):
        cached = self.cache.get(hostname)
        if cached:
            return cached
        
        # Resolve and cache
        ip = dns.resolve(hostname)
        self.cache.put(hostname, {
            'ip': ip,
            'timestamp': time.time()
        })
        return ip

3. Web Browser Cache

Browser LRU Cache:

Page Load: A → B → C → D → A → B → E

Cache State (capacity 4):
[A,B,C,D] → [A,B,C,D] → [A,B,C,D] → [B,C,D,A] → [C,D,A,B] → [D,A,B,E]
                                              ↑ Evict C     ↑ Evict D

4. CDN Edge Cache

class CDNEdgeCache:
    def __init__(self, max_size_gb=100):
        self.cache = LRUCache(capacity=1000000)
        self.size_tracker = SizeTracker(max_size_gb)
    
    def get_content(self, url):
        content = self.cache.get(url)
        if content:
            return content
        
        # Fetch from origin
        content = fetch_from_origin(url)
        
        if self.size_tracker.can_fit(content.size):
            self.cache.put(url, content)
        
        return content

5. Application-Level Cache

# Product catalog cache
product_cache = LRUCache(capacity=50000)

def get_product(product_id):
    product = product_cache.get(product_id)
    if product:
        return product
    
    product = db.products.find(product_id)
    product_cache.put(product_id, product)
    return product