Course contentsShow
← System Design
Lesson 151 of 1,9194. Caching StrategiesFree lesson

LRU-K and Advanced LRU Variants

Tracking the last K accesses instead of just one to better handle scan-resistant workloads and one-time reads.

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:

  1. Sequential scans: When someone runs a large report that reads thousands of records once, those records flood the cache and evict frequently-used data
  2. 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.