LRU-K and Advanced LRU Variants
What You'll Learn
You'll discover how tracking multiple access timestamps instead of just one makes caching smarter and more resistant to temporary spikes in data access.
The Problem with Basic LRU
Standard LRU (Least Recently Used) evicts items based on a single timestamp—the last time something was accessed. This works well for normal workloads, but struggles with two common scenarios:
- Sequential scans: When someone runs a large report that reads thousands of records once, those records flood the cache and evict frequently-used data
- One-time reads: Data accessed once but never again still gets treated as "recently used"
How LRU-K Works
LRU-K tracks the last K accesses for each cache entry, not just one. The eviction decision uses the timestamp of the K-th most recent access (often K=2 or K=3).
Think of it like judging restaurant popularity: instead of just noting when someone last visited, you track their last several visits. A restaurant visited twice recently is probably more valuable than one visited once yesterday but never before.
Key Behavior
- New items start with lower priority until they prove their worth with K accesses
- One-time reads don't pollute the cache as aggressively
- Frequently accessed items build "history" that protects them from scan workloads
For example, with LRU-2:
- Item A accessed at times [100, 150]: second-most-recent = 100
- Item B accessed at times [140]: second-most-recent = undefined (stays longer)
- Item C accessed at times [120, 145]: second-most-recent = 120
Item A would be evicted first despite being accessed recently, because its history shows it's been around longer.
Key Takeaway: LRU-K improves cache efficiency by requiring multiple accesses before treating data as "valuable," making it resistant to scans and one-time reads that would poison a basic LRU cache.