Caching Strategies & Eviction (LRU/LFU)

Metadata

1. Overview

What problem does it solve?

Reading from a traditional database (which often relies on reading from a hard drive) takes milliseconds. Reading from RAM takes nanoseconds. If you have data that is accessed frequently but changes rarely (like a user's profile, a product's description, or the front page of a news site), hitting the database for every single request is incredibly wasteful.

A Cache is a high-speed data storage layer (usually entirely in RAM) that stores a subset of data so that future requests for that data are served much faster than accessing the primary storage location.

Because RAM is expensive and limited, caches inevitably fill up. Eviction Policies (like LRU and LFU) determine which data to delete when the cache is full.

What breaks without it?

• Database Meltdown: Relational databases (like PostgreSQL) are bottlenecked by CPU and Disk I/O. Without caching, a sudden spike in read traffic will crash the database.
• High Latency: Users far away from the database experience slow page loads.
• Cost: Scaling databases horizontally to handle pure read traffic is significantly more expensive than running a Redis cache cluster.

2. Motivation

Why Redis/Memcached?

In the early web, caching was done within the application server's memory (Local Caching). If you had 10 servers, you had 10 separate, unsynchronized caches. If a user updated their profile, Server 1 knew about it, but Server 2 would serve the stale, cached profile.

Distributed Caching (Redis, Memcached) solved this by moving the cache out of the app servers into a central, incredibly fast memory cluster that all application servers share.

The Problem of Invalidation

Phil Karlton famously said: "There are only two hard things in Computer Science: cache invalidation and naming things." If the database updates, but the cache doesn't, the user sees stale data. Choosing the right caching strategy determines how you handle this problem.

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The Big 3 Caching Strategies

graph TD
    subgraph "1. Cache-Aside (Lazy Loading)"
        App1[App] --> |1. Read| Cache1[(Cache)]
        Cache1 -.-> |2. Miss| App1
        App1 --> |3. Read| DB1[(Database)]
        App1 --> |4. Write| Cache1
    end
    
    subgraph "2. Write-Through"
        App2[App] --> |1. Write| Cache2[(Cache)]
        Cache2 --> |2. Sync Write| DB2[(Database)]
        App2 --> |3. Read| Cache2
    end
    
    subgraph "3. Write-Behind (Write-Back)"
        App3[App] --> |1. Write| Cache3[(Cache)]
        App3 -.-> |Returns instantly| Client
        Cache3 -.-> |2. Async Bulk Write| DB3[(Database)]
    end

LRU vs LFU Eviction

If your cache holds exactly 3 items and is currently full: [A, B, C]. You need to insert D. Who gets deleted?

• LRU (Least Recently Used): Looks at Time. If B was accessed 10 minutes ago, but A and C were accessed 1 minute ago, delete B.
• LFU (Least Frequently Used): Looks at Count. If A was accessed 100 times, B 50 times, and C 5 times, delete C (even if C was accessed 10 seconds ago).

6. Internal Working

6.1 Cache-Aside (Most Common)

The application code takes full responsibility for managing the cache. Flow: Check cache -> If miss, check DB -> Write to cache -> Return to user. Pros: Only requested data is cached. Cache failures don't bring down the system (app just falls back to DB). Cons: High latency on a cache miss (3 network hops). Prone to data staleness.

6.2 Write-Through

The application writes data directly to the Cache, and the Cache synchronously writes to the DB before returning success. Pros: Data is never stale. Cache is always perfectly synced with DB. Cons: Writes are slow because you have to wait for two network hops (Cache + DB) to succeed.

6.3 Write-Behind (Write-Back)

The application writes data to the Cache, and the Cache immediately says "Success!". Every few minutes, a background worker sweeps the Cache and writes all changes to the DB in bulk. Pros: Insanely fast writes. Massive reduction in DB load. Cons: DATA LOSS RISK. If the Cache server crashes before the background worker runs, the data is gone forever. (Used for non-critical data like YouTube views, not banking transactions).

6.4 How LRU Works Internally

You need O(1) lookup and O(1) eviction.

• You use a Hash Map for O(1) lookup.
• You use a Doubly Linked List for O(1) ordering.
• When an item is accessed, you detach it from the linked list and move it to the "head". When the cache is full, you delete the node at the "tail".

7. Implementation

Why Go? We will implement a thread-safe LRU Cache from scratch. Go's pointers, structs, and built-in sync.Mutex make it perfect for demonstrating how the Hash Map + Doubly Linked List combination works under the hood.

/*
010 & 011 - LRU Cache Implementation
A thread-safe, concurrent LRU cache built from scratch using 
a Hash Map and a Doubly Linked List.
Run: `go run lru.go`
*/
package main

import (
	"fmt"
	"sync"
)

// ── Doubly Linked List Node ──

type Node struct {
	key   string
	value string
	prev  *Node
	next  *Node
}

// ── LRU Cache Structure ──

type LRUCache struct {
	capacity int
	cache    map[string]*Node
	head     *Node // Most Recently Used
	tail     *Node // Least Recently Used
	mu       sync.Mutex
}

func NewLRUCache(capacity int) *LRUCache {
	// Initialize with dummy head and tail to avoid nil checks
	lru := &LRUCache{
		capacity: capacity,
		cache:    make(map[string]*Node),
		head:     &Node{},
		tail:     &Node{},
	}
	lru.head.next = lru.tail
	lru.tail.prev = lru.head
	return lru
}

// ── Internal List Helpers (O(1)) ──

func (l *LRUCache) removeNode(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (l *LRUCache) moveToHead(node *Node) {
	// Insert right after the dummy head
	node.prev = l.head
	node.next = l.head.next
	
	l.head.next.prev = node
	l.head.next = node
}

// ── Public Cache Methods ──

// Get retrieves an item and marks it as Most Recently Used
func (l *LRUCache) Get(key string) (string, bool) {
	l.mu.Lock()
	defer l.mu.Unlock()

	if node, exists := l.cache[key]; exists {
		// Data accessed! Unlink it and move it to the front
		l.removeNode(node)
		l.moveToHead(node)
		return node.value, true
	}
	return "", false
}

// Put inserts a new item or updates an existing one
func (l *LRUCache) Put(key string, value string) {
	l.mu.Lock()
	defer l.mu.Unlock()

	if node, exists := l.cache[key]; exists {
		// Update existing node and mark as most recently used
		node.value = value
		l.removeNode(node)
		l.moveToHead(node)
	} else {
		// Create new node
		newNode := &Node{key: key, value: value}
		l.cache[key] = newNode
		l.moveToHead(newNode)

		// Check if we exceeded capacity (Eviction)
		if len(l.cache) > l.capacity {
			// Evict the Least Recently Used item (right before dummy tail)
			lruNode := l.tail.prev
			l.removeNode(lruNode)
			delete(l.cache, lruNode.key)
			fmt.Printf("[EVICTED] %s\n", lruNode.key)
		}
	}
}

// Print visually displays the cache state (from Head to Tail)
func (l *LRUCache) Print() {
	l.mu.Lock()
	defer l.mu.Unlock()

	fmt.Print("Cache State (MRU -> LRU): [Head] ")
	curr := l.head.next
	for curr != l.tail {
		fmt.Printf("<- (%s: %s) -> ", curr.key, curr.value)
		curr = curr.next
	}
	fmt.Println("[Tail]")
}

// ── Simulation ──

func main() {
	fmt.Println("--- Starting LRU Cache (Capacity: 3) ---")
	cache := NewLRUCache(3)

	cache.Put("A", "Apple")
	cache.Put("B", "Banana")
	cache.Put("C", "Cherry")
	cache.Print() // [A, B, C]

	fmt.Println("\n--- Accessing 'A' (Moves to MRU) ---")
	val, _ := cache.Get("A")
	fmt.Printf("Got: %s\n", val)
	cache.Print() // [A, C, B] (B is now LRU!)

	fmt.Println("\n--- Adding 'D' (Triggers Eviction of 'B') ---")
	cache.Put("D", "Date") // B is evicted
	cache.Print() // [D, A, C]

	fmt.Println("\n--- Trying to get evicted 'B' ---")
	if _, ok := cache.Get("B"); !ok {
		fmt.Println("Miss! 'B' is no longer in cache.")
	}
}

Sample Output

--- Starting LRU Cache (Capacity: 3) ---
Cache State (MRU -> LRU): [Head] <- (C: Cherry) -> <- (B: Banana) -> <- (A: Apple) -> [Tail]

--- Accessing 'A' (Moves to MRU) ---
Got: Apple
Cache State (MRU -> LRU): [Head] <- (A: Apple) -> <- (C: Cherry) -> <- (B: Banana) -> [Tail]

--- Adding 'D' (Triggers Eviction of 'B') ---
[EVICTED] B
Cache State (MRU -> LRU): [Head] <- (D: Date) -> <- (A: Apple) -> <- (C: Cherry) -> [Tail]

--- Trying to get evicted 'B' ---
Miss! 'B' is no longer in cache.

8. Complexity

Note on LFU (Least Frequently Used)

Implementing LFU in O(1) time is significantly harder than LRU. It requires two Hash Maps and a Doubly Linked List of Doubly Linked Lists (one for frequencies, one for items within that frequency). Due to this complexity, most systems (like standard Redis) default to LRU, or use approximated algorithms (like Redis's LFU implementation which uses probabilistic counters).

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. How do you implement an LRU cache with O(1) Get and Put operations? Hint: You need two data structures. A Hash Map for O(1) lookups, and a Doubly Linked List to maintain the time-ordered queue for O(1) evictions.

2. Your application uses a Cache-Aside pattern. If the cache goes down, what happens? Hint: The application falls back to querying the database directly. However, if traffic is high, the sudden spike in DB load will likely crash the database. This is why large caches must be highly available.

3. What is a "Cache Stampede" and how do you prevent it? Hint: When a popular key expires and thousands of requests hit the DB concurrently. Prevented by locking the cache key (using Redis SETNX) so only one thread rebuilds the cache.

4. Why is Write-Behind caching dangerous? Hint: Because the cache acknowledges the write before it's saved to the persistent database. If the cache server loses power, all un-synced data is lost forever.

13. Used By (Downstream Blocks)

• 012 CDN — A CDN is just a massive distributed cache at the edge of the network.
• 039 Distributed Cache (Redis/Memcached) — Deep dive into cluster architectures.
• 013 Database Indexing — DBs use LRU internally for their Buffer Pools.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Implement TTL (Time-To-Live)

Modify the Go LRU Cache. When calling Put, accept a ttlSeconds parameter. Store expiresAt in the Node. In the Get method, if the current time is past expiresAt, remove the node, return false, and print [EXPIRED].

Exercise 2: The "Scan" Flaw

Write a loop that adds 100 new keys to the capacity-3 cache. Observe how the original valuable keys (A, B, C) are instantly destroyed. This demonstrates why LRU is vulnerable to database scans, and why LFU is sometimes preferred.

Website Metadata