Building a Bounded LRU Cache in JavaScript

A module-level Map cache is the reason your service’s heap grows with every new customer ID, and you need to replace it with something that has a hard ceiling without losing the speed-up. This guide from Memory-Safe Caching Patterns in JavaScript, part of JavaScript Memory Fundamentals & Runtime Mechanics, builds a production-quality least-recently-used (LRU) cache step by step — count and byte bounds, statistics, disposal hooks — and shows how to prove it never exceeds its budget.

Symptom Root Cause Immediate Action Measurable Impact
Cache Map size grows with distinct keys forever No bound and no eviction Replace with an LRU bounded by count Size capped at max
Memory still grows with a count-bounded cache Values vary widely in size Add a byte bound with a sizeOf function Memory capped at maxBytes
Evicted values keep native resources open Eviction drops the reference but never releases resources Add an onEvict hook that disposes External resources released on eviction
No idea whether the cache helps No hit/miss counters Track hits, misses and evictions Hit rate visible; bound tuned to the knee
Race: two callers compute the same value Cache only stores finished values Cache in-flight promises and delete on failure One computation per key

Root Cause: Eviction Needs Order, and Map Already Has It

An LRU cache needs two operations to be cheap: look up a key, and find the least recently used entry to evict. Classic implementations pair a hash map with a doubly linked list. In JavaScript, Map already provides both, because it iterates keys in insertion order. If every access deletes the key and re-inserts it, the most recently used entry is always last and the least recently used is always first — map.keys().next().value gives you the eviction candidate in constant time. That makes a correct LRU a thin layer over Map rather than a data-structures exercise, with performance adequate for the vast majority of application caches.

The harder decisions are about the bound. A count bound (max entries) is simple and works when values are similar in size. When values vary — a cache of API responses where one is 2 KB and another 4 MB — count bounds do not bound memory, so you add a byte bound using a sizeOf(value) function that estimates each entry’s footprint and evicts until the total fits. Estimating well is its own topic, covered in estimating the memory footprint of a cache.

Two more features turn a toy into something you can ship. Disposal hooks: when evicted values own resources — ImageBitmaps, file handles, WebGL textures — eviction must release them, because dropping a reference does not close anything promptly (see FinalizationRegistry callbacks that never run). Statistics: hits, misses and evictions let you tune the bound to the point where hit rate stops improving. For many teams, the well-tested lru-cache package on npm, which offers max, maxSize with sizeCalculation, ttl and dispose options, is the right choice; writing your own is worthwhile when you need zero dependencies or custom behaviour, and understanding the mechanics helps you configure either.

Operations of a byte-bounded LRU A get on a hit deletes and re-inserts the key at the back of the Map and increments hits. A miss increments misses. A set inserts at the back and adds the entry's estimated bytes to the total, then an eviction loop removes entries from the front while the count exceeds max or the bytes exceed maxBytes, calling onEvict for each so resources are released. get(key) hit → move to back set(key, value) insert at back, add bytes Map (insertion order) front = LRU · back = MRU evict from front while over budget onEvict(key, value) releases resources budget: size ≤ max AND bytes ≤ maxBytes

Step-by-Step Fix

  1. Define the bounds. Decide max entries and, if values vary in size, maxBytes with a sizeOf estimator. Verification: the bounds are written down next to the cache with the memory budget they implement.
  2. Implement or adopt the cache. Use the class below, or lru-cache with equivalent options (max, maxSize, sizeCalculation, dispose). Verification: unit tests pass for hit, miss, update and eviction order.
  3. Add disposal for resource-owning values. Supply onEvict that closes bitmaps, handles or subscriptions. Verification: evicting an entry calls the hook exactly once; clear() calls it for every entry.
  4. De-duplicate in-flight work. Cache the promise for a key while it is pending and delete it if it rejects. Verification: concurrent calls for the same key trigger one computation; a failure is not cached.
  5. Replace the unbounded cache. Swap the old Map for the bounded cache at every call site. Verification: code search finds no remaining direct Map writes for that cache.
  6. Prove the budget under load. Run a soak test with many distinct keys and check size, bytes and retained size in a heap snapshot. Verification: all three stay within the bounds while hit rate remains acceptable.
Soak test: 100,000 distinct keys The unbounded Map grows linearly to about 820 megabytes as distinct keys accumulate. The byte-bounded LRU with a 64 megabyte budget rises to 64 megabytes and stays there, while its hit rate stabilises around 87 percent. 820 MB 0 unbounded Map LRU, maxBytes 64 MB (hit rate ~87%) distinct keys seen (0 → 100,000)

Command and Code Reference

Use case: a byte- and count-bounded LRU with stats and disposal.

// bounded-lru.js
export class BoundedLru {
  #map = new Map();            // key → { value, bytes }
  #bytes = 0;
  stats = { hits: 0, misses: 0, evictions: 0 };

  constructor({ max = 1000, maxBytes = Infinity, sizeOf = () => 1, onEvict } = {}) {
    this.max = max;
    this.maxBytes = maxBytes;
    this.sizeOf = sizeOf;
    this.onEvict = onEvict;
  }

  get(key) {
    const entry = this.#map.get(key);
    if (!entry) { this.stats.misses++; return undefined; }
    this.#map.delete(key);                 // refresh recency
    this.#map.set(key, entry);
    this.stats.hits++;
    return entry.value;
  }

  set(key, value) {
    const bytes = this.sizeOf(value);
    if (bytes > this.maxBytes) return false; // too big to cache at all
    this.delete(key);                        // replace existing entry cleanly
    this.#map.set(key, { value, bytes });
    this.#bytes += bytes;
    this.#evict();
    return true;
  }

  delete(key) {
    const entry = this.#map.get(key);
    if (!entry) return false;
    this.#map.delete(key);
    this.#bytes -= entry.bytes;
    this.onEvict?.(key, entry.value);        // release resources on removal
    return true;
  }

  #evict() {
    while (this.#map.size > this.max || this.#bytes > this.maxBytes) {
      const oldest = this.#map.keys().next().value;
      this.delete(oldest);
      this.stats.evictions++;
    }
  }

  clear() { for (const key of [...this.#map.keys()]) this.delete(key); this.#map = new Map(); }
  get size() { return this.#map.size; }
  get bytes() { return this.#bytes; }
}

Use case: de-duplicate concurrent loads without caching failures.

const users = new BoundedLru({ max: 5000 });

export function getUser(id) {
  const cached = users.get(id);
  if (cached) return cached;                       // value or pending promise
  const p = fetchUser(id).catch((err) => {
    users.delete(id);                              // never cache a failure
    throw err;
  });
  users.set(id, p);
  return p;
}

Use case: a test that proves the bound.

import { test, expect } from 'vitest';
import { BoundedLru } from './bounded-lru.js';

test('never exceeds its byte budget', () => {
  const cache = new BoundedLru({ max: Infinity, maxBytes: 1_000, sizeOf: (v) => v.length });
  for (let i = 0; i < 10_000; i++) {
    cache.set(`k${i}`, 'x'.repeat(1 + (i % 50)));  // varied sizes
    expect(cache.bytes).toBeLessThanOrEqual(1_000);
  }
});

Verification and Regression Prevention

Verify three things under a realistic soak: the cache’s size and bytes never exceed their bounds; its retained size in a heap snapshot is close to bytes (if it is much larger, your sizeOf underestimates or values reference extra data); and the hit rate is at or near the level you need. Tune max/maxBytes down until the hit rate starts to drop, then step back up — that knee is the most memory-efficient setting.

Export stats and bytes as metrics and alert when hit rate collapses (a sign of key explosion or a wrong key) or when bytes sits at the budget with frequent evictions (a sign the budget is too small for the working set). Keep one shared implementation for the whole codebase so every cache benefits from the same tests. Where freshness matters as much as memory, combine this with expiry as described in TTL vs LRU eviction.

Comparing enforced bytes to retained size Under a realistic soak, compare the cache’s own bytes counter with its retained size in a heap snapshot. If they are close, sizeOf is accurate. If retained is much larger, sizeOf underestimates or values reference extra data. If the hit rate is below target, raise the bound; if it stays high at a lower bound, shrink it. Retained size vs cache.bytes sizeOf is accurate; bounds are real close sizeOf underestimates, or values hold extra data retained much larger Shrink max/maxBytes until the hit rate drops hit rate unchanged at lower max

Edge Cases and Gotchas

sizeOf must be cheap

The size estimator runs on every set. Computing JSON.stringify(value).length for large values on every insert is expensive; compute sizes from known fields or cache them on the value.

Refreshing on get costs a delete and insert

Moving keys on every hit is cheap but not free. For extremely hot caches you can refresh only occasionally (for example on every Nth hit), trading a little precision in eviction order for less work.

Map backing stores after clear

Replacing the internal Map in clear() ensures the old hash table is released, rather than relying on it shrinking.

Values shared outside the cache

If a cached value is also held by components or other caches, evicting it does not free memory. Retained size in snapshots reveals this: evicted values should disappear, and if they do not, something else owns them.

Frequently Asked Questions

How do you implement an LRU cache in JavaScript?

Use a Map: on every read, delete and re-insert the key so it moves to the end; on insert, if the cache is over its limit, delete map.keys().next().value, which is the least recently used key. Add byte accounting and a disposal hook for production use.

Should I use the lru-cache npm package or write my own?

The package is mature, fast and well tested, with count, size and TTL options and disposal callbacks. Use it unless you need zero dependencies or special behaviour. Writing your own is straightforward with Map, but it needs the same tests.

What should the maximum size be?

Measure hit rate at several sizes with real traffic and pick the smallest size near the point where hit rate stops improving. Then check that its measured retained memory fits your memory budget.

Why cache promises instead of values?

Caching the pending promise lets concurrent callers share one in-flight computation instead of starting duplicates. Remove the entry if the promise rejects so that failures are retried rather than cached.