What is an LRU cache — and why a cache with no limit becomes a memory leak

You built a fast cache. A plain object: the key is the request, the value is the response.

const cache = {};

async function getUser(id) {
  if (cache[id]) return cache[id];
  const user = await fetch(`/api/users/${id}`).then(r => r.json());
  cache[id] = user;
  return user;
}

For a week everything flies. Then the server dies with "out of memory". Here's the catch: this cache only grows. Every new id stays in memory forever. A cache with no limit isn't a speed-up — it's a very slow memory leak.

You need a limit. And a limit raises a question: when you run out of room, what do you throw away? That's exactly what LRU answers.

What LRU means, simply

LRU — Least Recently Used. One rule: when the cache is full, evict the entry nobody has touched for the longest time.

Picture a shelf that holds exactly five books. You take a book to read — you put it back on the left end. A new book also goes on the left. No room — the dustiest one falls off the right end. The shelf always holds the five books you touched last.

That's the whole algorithm. The subtle part is one word: used. Reading an entry makes it fresh, not just writing it.

How it works

The cache needs two operations, both fast:

1. Get by key — and mark the entry as fresh.
2. Put a new entry — and if there's no room, evict the oldest one.

The classic implementation is a hash table plus a doubly linked list. The table finds an entry instantly; the list keeps the "freshest to oldest" order. Both operations take constant time, however many entries there are.

JavaScript has a simpler trick. A Map remembers insertion order. So the first key in a Map is the oldest. To refresh an entry, you delete it and insert it again — it moves to the end.

class LRU {
  constructor(limit) {
    this.limit = limit;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key);
    this.map.delete(key);      // take it out
    this.map.set(key, value);  // put it at the end — now it's fresh
    return value;
  }
  set(key, value) {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.limit) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);  // the stalest is first in the Map
    }
  }
}

Trace it by hand, limit 2: set(a), set(b), get(a), set(c). Who gets evicted? Not a — it was just read. It evicts b. That's the key point: a plain first-in-first-out queue would have evicted a.

Why it matters to you

• Memory under control. The cache no longer grows forever. You decide: 500 entries, period.
• Hot stuff stays. Popular entries get read all the time, so they never age. Rare ones leave on their own.
• Zero tuning. No guessing how long to keep each entry. The access order decides for you.

Where LRU is weak. One big pass over rare data — a report, an export, a crawler bot — pushes out everything hot. The shelf gets buried in books nobody will open again. That's why LFU (evict the least frequently used) and hybrids exist.

LRU also says nothing about freshness. An entry can be "hot" but stale. So LRU is usually paired with an expiry time. More on expiry and invalidation in the article on caching. And what happens when a hot entry expires for everyone at once — in the breakdown of a cache stampede.

Where you'll meet it

• Redis. With maxmemory-policy allkeys-lru it evicts keys that haven't been touched in a while. But its LRU is approximate: Redis samples 5 random keys (maxmemory-samples, default 5) and evicts the oldest of them. Exact LRU over millions of keys would cost too much memory.
• The lru-cache package on npm. A lot of Node.js tooling uses it. It supports both a count limit and an expiry time.
• CPU caches and memory pages in your operating system — LRU and its approximations have run there for decades.
• AI response caching. If you cache model responses, an LRU with a limit saves you from a memory bill.

How is LRU different from a priority queue?

A priority queue hands out the element with the lowest priority you assigned. LRU doesn't ask for a priority — the time of last access sets it. More in the article on the priority queue.

What limit should I set?

Start with the size you're happy to keep in memory, and watch the hit rate. If you're at 90% hits and raising the limit barely moves it — you've found your limit.

Can I just delete old entries on a timer?

You can — that's TTL. But it doesn't cap size: a million new keys can arrive in an hour. It's safer to keep both rules at once — a count limit and an expiry time.