Least Recently Used (LRU)
You'll learn how LRU eviction works by removing the data accessed longest ago when cache space runs out.
What Is LRU?
When your cache fills up, you need to decide which item to remove to make room for new data. Least Recently Used (LRU) removes the item that hasn't been accessed (read or written) for the longest time. The logic is simple: if something hasn't been used recently, it probably won't be needed soon.
How It Works
LRU tracks access order, not just when items were added. Every time you access an item, it moves to the "front" of the line. When eviction happens, the item at the "back" (accessed longest ago) gets removed.
Think of it like a stack of books on your desk. Every time you read a book, you place it on top of the pile. When your desk gets too full, you remove the book at the bottom—the one you haven't touched in the longest time.
Why Use LRU?
LRU works well for temporal locality—the pattern where recently accessed data is likely to be accessed again soon. If a user views their profile repeatedly, LRU keeps that data cached. Old data that hasn't been touched gets pushed out naturally.
Implementation Insight
LRU typically uses a linked list (to maintain access order) combined with a hash map (for fast lookups). When you access an item, you move it to the list's head. Eviction simply removes from the tail. This keeps both operations fast.
Key Takeaway: LRU evicts the least recently accessed item, making it ideal for workloads where recent data matters most—tracked efficiently with linked lists to maintain access order.