MRU Cache: Most Recently Used Eviction for Sequential Access Patterns

When MRU beats LRU

LRU assumes temporal locality: recently accessed items will be accessed again soon. MRU assumes the opposite: the item you just accessed is the least likely to be needed again.

MRU is correct for:

• Sequential scans: each record is read once in order, never revisited
• Media streaming: video segments consumed linearly — rewinding is rare
• Transaction log processing: each log record processed once and discarded
• Database index traversal: B-tree pages visited once during a scan

Access sequence: A B C D E F G (sequential scan, cache size 3)

LRU eviction:
  Access D: cache=[D,C,B], evict A   → A will never be needed again, good
  Access G: cache=[G,F,E], evict C   → but LRU keeps recent scan data

MRU eviction:
  Access D: cache=[A,B,D], evict D   → evict most recent, keep older items
  Rationale: older items in cache more likely to be re-requested than the
             item just scanned

For truly sequential workloads with no re-access, MRU keeps the oldest-seen items which may actually be useful (e.g., the start of a document being revisited).

MRU fails immediately when access patterns include any re-access — evicting the most recently used item is self-defeating

GotchaCaching

MRU's assumption that recently-accessed items have no future value breaks down with any workload that revisits data. If a user reads page A, then navigates elsewhere and comes back to page A, MRU has already evicted it. For most production workloads, LRU is correct. MRU is a specialized algorithm for narrow sequential patterns.

Prerequisites

• LRU cache
• Cache eviction policies
• Access pattern analysis

Key Points

• MRU is correct for sequential workloads with no re-access (scans, streams).
• MRU fails for any workload with temporal locality (web requests, API responses, hot keys).
• Never use MRU as a general-purpose cache — only for data that is definitively accessed once.
• ARC and LRU-2 handle mixed workloads (some sequential, some recurring) by adapting between LRU and MRU behavior.

Implementation

import threading
from collections import OrderedDict

class MRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity
        self.lock = threading.Lock()

    def get(self, key: int) -> int:
        with self.lock:
            if key not in self.cache:
                return -1
            # Move to end = mark as most recently used
            self.cache.move_to_end(key)
            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        with self.lock:
            if key in self.cache:
                self.cache.pop(key)
            elif len(self.cache) >= self.capacity:
                self.cache.popitem(last=True)   # evict most recently used (last item)
            self.cache[key] = value
            self.cache.move_to_end(key)         # mark as most recently used

    def get_cache_state(self):
        with self.lock:
            return list(self.cache.items())

popitem(last=True) removes the last item (most recently used). Compare to LRU which uses popitem(last=False) to remove the first item (least recently used). The only difference in the implementations is which end of the OrderedDict is evicted.

MRU vs LRU by workload

| Workload | Correct policy | Why | |---|---|---| | Web page cache | LRU | Pages are revisited; recently viewed → likely revisited | | Database B-tree scan | MRU | Leaf pages scanned once, never revisited | | Media streaming | MRU | Video segments consumed once in order | | API response cache | LRU | Same endpoints called repeatedly | | ETL batch processing | MRU | Source records processed once | | Session data | LRU | Active sessions are recently and frequently accessed |

Most production caches use LRU. MRU appears in database buffer pools (as a scan mode) and streaming systems.

A database buffer pool uses LRU for all page accesses. A full table scan on a 50GB table runs on a server with a 4GB buffer pool. After the scan completes, the buffer pool hit rate for normal OLTP queries drops from 98% to 60% and takes 20 minutes to recover. What caused this?

medium

The table scan accessed 50GB sequentially. The buffer pool is 4GB. OLTP queries access frequently-used index pages and hot rows.

• AThe scan filled the buffer pool with cold table pages, evicting the hot OLTP pages that LRU was correctly caching

  Correct!The 50GB sequential scan accessed ~12.5× more data than the buffer pool could hold. As the scan progressed, it continuously evicted the oldest page in the LRU list — which were the OLTP hot pages. By the time the scan finished, the entire buffer pool contained scan pages that will never be accessed again. OLTP queries now miss on every hot page until natural access warms the cache back up. This is LRU scan poisoning. Fix: use MRU mode for sequential scans (enter scan pages at the MRU end so they're evicted first next time), or use a separate buffer pool partition for large scans.
• BThe scan caused disk fragmentation that slowed subsequent I/O

  Incorrect.Disk fragmentation doesn't explain a drop in buffer pool hit rate. The symptom is cache misses, not I/O slowdown.
• CLRU correctly cached the scan pages — the 60% hit rate reflects the hot scan data that was recently accessed

  Incorrect.The scan pages aren't accessed after the scan. The 60% hit rate reflects OLTP queries missing on their hot pages (which were evicted) and hitting on a minority of scan pages that happen to be relevant.
• D4GB buffer pool is too small for this workload and needs to be increased to 50GB

  Incorrect.Increasing the buffer pool to match every possible scan would be wasteful and impractical. The correct fix is algorithmic — using MRU or a scan-resistant buffer pool policy.

Hint:A 50GB scan through a 4GB LRU buffer pool evicts pages in what order?