MRU — Most Recently Used — Cache Eviction

Overview

What this concept solves

MRU — Most Recently Used — flips LRU on its head: when the cache is full, evict the entry that was accessed most recently. The bet is the opposite of LRU's: that the thing you just touched is the one you're least likely to need again soon.

It sounds absurd at first. Caching exists because of locality — recently-used data is usually re-used soon. MRU only makes sense when locality runs the other way: large sweeps, sequential scans, repeated full passes over a dataset bigger than the cache. In those workloads, LRU is the wrong policy, and MRU can hit nearly 100% on entries that LRU would miss entirely.

Mechanics

How it works

Same structure as LRU — opposite eviction end

Implementation-wise, MRU is just LRU with one line changed. The same HashMap + doubly-linked list works. On hit, you still move the entry to the head of the list. The only difference is which end you evict from:

Get(key) — look up in the map. Move the node to the head of the list. Return the value.
Put(key, value) — insert at the head. If over capacity, evict the head's previous neighbour (the most-recently-used entry that isn't the new arrival).

The classic MRU win: loop bigger than cache

Cache size 3, loop A, B, C, D, A, B, C, D... With LRU, every access is a miss — by the time you come back to A, it's been evicted. With MRU, you keep three of the four entries permanently and get a 75% hit rate. The intuition flips because the next access is always the one furthest in the future of the loop.

When MRU is the right bet

MRU wins exactly when the access pattern has anti-locality — re-access is unlikely for what you just used. The textbook case is a database join scanning a relation in order: once you've finished reading row N, you're moving to N+1, not back to N. LRU keeps the rows you've already passed; MRU keeps the rows you haven't reached yet.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › MRU — Most Recently Used

About this simulation

Capacity 4 — same layout as LRU, with the most recently used entry on the left. The twist: when the cache is full, that front (most recent) slot is the next one to die. Hit Run demo and watch the newest arrivals get evicted while older entries stick around.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

See the newest slot die

Click A, B, C, D to fill the cache. Now click E. Look at which slot vanished: it's D, the most recent arrival — not A. The opposite of LRU.

try 02

A hit makes you the next victim

Click Reset. Click A, B, C, D, then click A again — A jumps to the front. Now click E. A is evicted, even though three letters were older. Touching something under MRU is what kills it.

try 03

The loop that makes MRU shine

Reset. Click A, B, C, D — cache full. Now click A — it bumps to front. Click E — A dies. Click A — miss, A returns and bumps the front. Repeat. With anti-locality (you never re-read what you just touched), MRU keeps the older entries instead of churning them.

In practice

When to use it — and what you give up

When to reach for it

Sequential scans larger than the cache — database joins, sorted-merge operations, full-table reads.
Repeated full-loop workloads — your workload reads A, B, C, D, A, B, C, D... and the loop is larger than your cache.
Streaming with anti-locality — workloads where 'just used' is a strong negative signal for future use.
As a niche tier in a hybrid cache — combined with LRU for general traffic, MRU for known scan ranges.

Real-world example

MRU shows up most often inside database query engines — not as the top-level buffer pool policy, but for specific operators. PostgreSQL's Sort and Hash Join choose buffer-replacement strategies operator by operator: a sequential scan uses a ring buffer (MRU-like) to avoid polluting the shared buffer pool. Oracle has documented MRU buffer eviction for full scans.

Pros

Crushes LRU on loop/scan workloads larger than the cache — can go from 0% hit rate to near-100%.
Same O(1) implementation as LRU — just swap the eviction end. No new data structures.
Trivial to combine with LRU as two halves of a hybrid cache, segmented by workload type.

Cons

Disastrous on normal recency-correlated traffic — it evicts exactly the items you'd want to keep.
Niche by nature. If your workload isn't a scan, MRU is the wrong answer, full stop.
Almost never a sensible default for a general-purpose cache — you need to know your access pattern.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

mru.ts

// MRU: same as LRU, but evict from the most-recent end.
// In JS, Map preserves insertion order — last key in is the
// most-recently-used. Drop *that* on overflow.
class MRU<K, V> {
  private store = new Map<K, V>();
  constructor(private capacity: number) {}

  get(key: K): V | undefined {
    if (!this.store.has(key)) return undefined;
    const value = this.store.get(key)!;
    this.store.delete(key);
    this.store.set(key, value); // re-insert as most-recent
    return value;
  }

  set(key: K, value: V): void {
    if (this.store.has(key)) {
      this.store.delete(key);
    } else if (this.store.size >= this.capacity) {
      // Evict the most-recently-used: the last key currently in the map.
      // We have to walk to the end since Map has no "last" accessor.
      let lastKey: K | undefined;
      for (const k of this.store.keys()) lastKey = k;
      if (lastKey !== undefined) this.store.delete(lastKey);
    }
    this.store.set(key, value);
  }
}

References & further reading

3 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

When does MRU beat LRU on hit rate?

question 02 / 03

An MRU cache of size 3 starts empty. We access: A, B, C, D, A. After the access to D and then A, which keys remain in the cache?

question 03 / 03

Why do database query engines sometimes use MRU-like ring buffers for full table scans?

0/3 answered