Node LRU cache: the Map trick is 25x slower than lru-cache

The popular "Map delete-and-set" LRU cache is about 25x slower than the lru-cache package once the cache holds 10,000 keys. In our Node.js benchmark it managed 0.59 million operations per second, against 14.9 million for lru-cache 11.5.3 on the same workload. The cause is not the LRU logic. It is the way the trick finds the oldest key, and it gets worse as the cache grows.

This post gives the numbers for six implementations, the cause of the slowdown, a 25-line replacement you can paste, and a catch in quick-lru's hit rate that most comparisons miss.

What is an LRU cache, and why does Node.js need one?

An LRU cache is a bounded key-value store that, when full, throws away the least recently used entry. Node servers use one to keep hot database rows, rendered templates or API responses in memory without growing without limit.

The goal is a high hit rate. A hit rate is the share of lookups that find the key already cached. Every miss costs a database call or a slow computation. For example, at 1,000 requests per second, 3 points of hit rate removes 30 database calls per second, which can matter more than raw speed.

An LRU needs two operations to be fast: look up a key, and move that key to the "newest" end. The common implementations differ in how they do the second step.

lru-cache is an npm package by Isaac Schlueter that provides a bounded LRU map with TTL and size options, and it is the most used package for this job (see the isaacs/node-lru-cache repository). quick-lru is a smaller npm package by Sindre Sorhus that offers a fast approximate LRU, described in the sindresorhus/quick-lru repository. Its README says it implements a variant of the hashlru algorithm using JavaScript's Map. The older bench-lru project compared many such packages, but its numbers date from earlier Node versions. We reran the comparison on Node 22 and added the hand-rolled approaches that people copy from blog posts.

How we measured it

The test setup and methodology are listed below.

The test setup was an Apple M2 laptop with 8 GB of RAM, Node.js 22, lru-cache 11.5.3 and quick-lru 7.3.0. Every cache had a capacity of 10,000 entries over a key space of 200,000.

We replayed 2 million operations per run. Each operation did a get, and on a miss it did a set, which is how a read-through cache behaves. We warmed up the engine first and report the median of three runs.

We used three workloads:

• Zipf with s = 1.0. A Zipf distribution is one where a few keys get most of the traffic. This is typical of real web traffic.
• Zipf with s = 0.8. A flatter version, where popularity is spread wider.
• Uniform. Every key is equally likely. This is the worst case for any cache.

The six implementations were:

1. Map FIFO. A Map that evicts the oldest inserted key and never reorders on a hit.
2. Map delete+set. A Map that deletes and reinserts a key on every hit, and evicts map.keys().next().value.
3. Map + linked list. A Map from key to node, plus a doubly linked list. This is the textbook LRU.
4. lru-cache. The package, with default options.
5. lru-cache + TTL. The package with a 60-second TTL.
6. quick-lru. The package, with maxSize: 10000.

Results: throughput and hit rate

On the Zipf workload, four implementations ran between 12 and 16 million operations per second, and two ran below 1 million.

Implementation	Zipf 1.0 ops/s	Zipf 1.0 hit rate	Uniform ops/s
Map FIFO	0.35 M	64.7%	0.13 M
Map delete+set	0.59 M	68.3%	0.13 M
Map + linked list	15.6 M	68.3%	9.7 M
lru-cache 11.5.3	14.9 M	68.3%	8.9 M
lru-cache + 60 s TTL	12.5 M	68.3%	7.9 M
quick-lru 7.3.0	16.4 M	71.2%	12.8 M

Three facts stand out. First, the three real LRUs agree on the hit rate, 68.3%, as they must, because they make identical eviction choices. Second, the FIFO cache lost 3.6 points of hit rate, 64.7% against 68.3% (our lab, 2026), so recency tracking earns its cost on skewed traffic. Third, the two Map-only versions are the slowest by a wide margin, in every workload.

On the uniform workload, the gap grew to 69x: 0.13 million operations per second for the Map trick, against 8.9 million for lru-cache. No cache can do much with uniform traffic. The hit rate stayed near 5% (our lab, 2026), which is the capacity divided by the key space (10,000 / 200,000).

Why is the Map delete-and-set trick so slow?

The trick is slow because deleting from the front of a JavaScript Map leaves empty slots that keys().next() must walk past on every eviction. The cost grows with how many deleted slots sit at the front.

Here is the code that most tutorials show:

class MapLRU {
  constructor(max) { this.max = max; this.map = new Map(); }
  get(key) {
    const v = this.map.get(key);
    if (v !== undefined) { this.map.delete(key); this.map.set(key, v); }
    return v;
  }
  set(key, v) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.max) this.map.delete(this.map.keys().next().value);
    this.map.set(key, v);
  }
}

A tombstone is a deleted slot that a hash table keeps in place until the next rebuild. A Map remembers insertion order, so the first key is the oldest. Deleting and re-adding a key moves it to the end. It is a neat idea, and it is correct. The MDN documentation for Map confirms the ordering guarantee.

The cost shows up in the engine. A hot loop that deletes the oldest entries and appends new ones leaves tombstones at the front of the table. We measured how the average eviction time moved with the cache size, using the same workload:

Cache size	Operations per second	Time per eviction
100	7.12 M	0.14 µs
1,000	2.25 M	0.45 µs
10,000	0.13 M	7.94 µs
50,000	0.06 M	24.53 µs

At 100 keys, the trick is fine, such as in a unit test with a handful of entries. That is why it looks good in a demo and in unit tests. At 50,000 keys, one eviction costs about 175 times what it cost at 100 keys (our lab, 2026). A cache that gets slower as it fills is the opposite of what you want, and the slowdown only appears under production-size data.

If you cannot add a dependency, do not use this pattern above a few hundred entries. If you use it, test at your real capacity, not with ten keys.

A 25-line replacement

A Map of key to node plus a doubly linked list gives constant-time lookup, move and evict. It ran at 15.6 million operations per second in our test, which is slightly faster than lru-cache.

class LRU {
  constructor(max) { this.max = max; this.map = new Map(); this.head = null; this.tail = null; }
  #unlink(n) {
    if (n.prev) n.prev.next = n.next; else this.head = n.next;
    if (n.next) n.next.prev = n.prev; else this.tail = n.prev;
    n.prev = n.next = null;
  }
  #front(n) {
    n.next = this.head; if (this.head) this.head.prev = n;
    this.head = n; if (!this.tail) this.tail = n;
  }
  get(key) {
    const n = this.map.get(key);
    if (!n) return undefined;
    if (n !== this.head) { this.#unlink(n); this.#front(n); }
    return n.value;
  }
  set(key, value) {
    let n = this.map.get(key);
    if (n) { n.value = value; this.#unlink(n); this.#front(n); return; }
    if (this.map.size >= this.max) { const old = this.tail; this.#unlink(old); this.map.delete(old.key); }
    n = { key, value, prev: null, next: null };
    this.map.set(key, n); this.#front(n);
  }
}

It lacks everything lru-cache adds: TTL, size-based limits, async fetch with stale-while-revalidate, and disposal hooks. For a plain bounded cache, though, it is correct and fast.

This implementation allocates one object per entry. In our run it was within 5% of lru-cache, so the allocation cost did not show up at 10,000 entries.

The catch in quick-lru's hit rate

quick-lru scored the best hit rate in our test, 71.2% (our lab, 2026), but it did so by keeping about half again as many entries as maxSize says. It is not an exact LRU. It is an approximation that holds two generations of entries.

The quick-lru README describes the design as a variant of the hashlru algorithm. Entries go into a current Map. When that map fills to maxSize, it becomes the "old" map, and a fresh one starts. A hit in the old map moves the entry back to the current one. The oldest generation is dropped in bulk.

That makes every operation cheap, which is why quick-lru was the fastest at 16.4 million operations per second. But the cache can hold between maxSize and about twice maxSize entries. We counted the entries physically held after the run: 15,288 for a maxSize of 10,000. The size property reports at most 10,000 because it caps the number.

So the hit-rate comparison is not fair. We gave lru-cache more room to check:

Cache	Capacity setting	Zipf 1.0 hit rate
lru-cache	10,000	68.3%
quick-lru	10,000 (held 15,288)	71.2%
lru-cache	15,000	72.2%
lru-cache	20,000	75.0%
quick-lru	5,000	64.8%

At the same effective capacity of about 15,000 entries, lru-cache scored 72.2%, one point above quick-lru (our lab, 2026). So quick-lru is a good, fast cache, but its hit-rate lead is memory you did not budget for.

For example, if you sized the cache to fit 10,000 entries of 50 KB each, which is 500 MB, quick-lru can reach about 750 MB. Set maxSize so that twice its value still fits in memory, or about two thirds of the budget you would give an exact LRU.

What does a TTL cost?

A TTL, short for time to live, is a limit on how long an entry may be served before it expires. Adding one cost lru-cache about 16% of its throughput in our run (our lab, 2026). Throughput fell from 14.9 to 12.5 million operations per second on the Zipf workload, and from 8.9 to 7.9 million on the uniform one.

That is a fair price. Without a TTL, a cached value lives until it is evicted, so a changed database row can be served stale for hours on a quiet key. The lru-cache README says stale items are not removed on their own at expiry, only on access or when space is needed, so you also need to size the cache for them.

Use a TTL when correctness depends on freshness. Use explicit invalidation when you know the moment a value changes. A TTL of 30 to 60 seconds on a hot read path bounds the staleness.

Which Node.js LRU cache should you use?

Use lru-cache when you need TTL or size limits, quick-lru for a small fast cache where overshooting memory is acceptable, and your own linked list when you want zero dependencies. Never use the Map delete-and-set pattern above a few hundred keys.

1. Need TTL, size-based limits or async fetch? Use lru-cache.
2. A simple bounded cache and memory has some slack? quick-lru is the fastest, with a looser size bound.
3. No dependencies allowed? Paste the 25-line linked list above.
4. Fewer than 500 keys? The Map trick is fine, but switching later costs more than starting right.

One more check before shipping any of them: measure your own hit rate. A cache with a 5% hit rate, like our uniform case, adds code and memory and removes almost nothing. In that case, spend the effort on the query behind it. We covered a related way to avoid repeat lookups in Bloom filter for username checks: 2.4 MB, but is it worth it?, and a way to protect a cached endpoint from a flood in Rate limiter algorithms compared: the 2x burst most miss.

If you want to test your own workload, log every get result for a day and replay it against the candidates, as we did. If your own numbers differ from ours, contact the NiharDaily editor with your Node version and key distribution, and we will compare them with the lab.

The bottom line: the cache you copy matters

The Map delete-and-set trick is correct and tempting, and it ran 25x slower than lru-cache at 10,000 keys. A 25-line linked list matched the package, and quick-lru's hit-rate lead came from holding 15,288 entries instead of 10,000 (our lab, 2026).

Pick the implementation by capacity and by features. Test at the size you will run in production, and count the memory the library really uses.