Implementing LRU-K for Better Eviction

In this lesson, you will learn how to evolve beyond standard Least Recently Used (LRU) caching by implementing the LRU-K algorithm to identify and protect truly frequent items.

The Problem with Simple LRU

A standard LRU cache evicts items based solely on their last access time. This makes the cache vulnerable to "scan pollution," where a single, one-off bulk operation (like a large report generation) pushes out high-value items that are used frequently but not just now.

The LRU-K Strategy

The LRU-K algorithm tracks the history of the last K accesses for each item. An item is only promoted to the "hot" cache tier after it has been accessed K times. By setting K=2, you effectively filter out the "one-hit wonders."

In Node.js, we track this using two structures: a history map for tracking timestamps of the first K-1 accesses, and a cache for items that have reached the K threshold.

Implementation Snippet

Here is a conceptual approach to tracking access frequency for an LRU-2 cache:

const history = new Map(); // Stores timestamps of first access
const cache = new Map();   // The actual cache storage

function access(key) {
  if (cache.has(key)) {
    // Standard LRU update for hot items
    refresh(cache, key);
    return cache.get(key);
  }

  // Tracking for K-th access
  const accessHistory = history.get(key) || [];
  accessHistory.push(Date.now());

  if (accessHistory.length >= 2) {
    history.delete(key);
    cache.set(key, fetchData(key)); // Promote to cache
  } else {
    history.set(key, accessHistory);
  }
}

Why This Matters

By requiring K accesses before caching, you create a natural buffer. This is significantly more resilient for your Node.js services, especially when handling mixed workloads where you want to ensure that intermittent background tasks do not flush your most critical user session data or configuration objects. Instead of blindly trusting the most recent access, you are now validating the intent of the access by checking for repetition.

Key Takeaway: LRU-K prevents cache pollution from one-off data scans by requiring items to demonstrate a minimum frequency of K before occupying high-priority memory space.