LRU Eviction

The memory problem

Every cached entry uses memory. If you cache every book detail, every search result, and every aggregation, the cache grows without bound. Eventually, the Node.js process runs out of memory and crashes.

Eviction removes entries from the cache to free memory. The question is: which entries to remove?

Least Recently Used (LRU)

The LRU strategy evicts the entry that has not been accessed for the longest time. The logic: if an entry has not been requested recently, it is unlikely to be requested soon. Keep the frequently accessed entries, discard the rarely accessed ones.

Cache capacity: 3 entries

Request book-1 → miss → cache: [book-1]
Request book-2 → miss → cache: [book-2, book-1]
Request book-3 → miss → cache: [book-3, book-2, book-1]
Request book-4 → miss → evict book-1 (least recently used)
                         cache: [book-4, book-3, book-2]
Request book-2 → hit  → move to front
                         cache: [book-2, book-4, book-3]
Request book-5 → miss → evict book-3 (least recently used)
                         cache: [book-5, book-2, book-4]

Accessing an entry moves it to the front. When the cache is full and a new entry arrives, the entry at the back (least recently used) is evicted.

LRU cache implementation

// src/lru-cache.ts
interface LRUEntry<T> {
  value: T;
  expiresAt: number;
}

export class LRUCache<T> {
  private cache = new Map<string, LRUEntry<T>>();
  private readonly maxSize: number;

  constructor(maxSize: number) {
    this.maxSize = maxSize;
  }

  get(key: string): T | undefined {
    const entry = this.cache.get(key);
    if (!entry) return undefined;

    // Check TTL
    if (Date.now() > entry.expiresAt) {
      this.cache.delete(key);
      return undefined;
    }

    // Move to end (most recently used) by re-inserting
    this.cache.delete(key);
    this.cache.set(key, entry);

    return entry.value;
  }

  set(key: string, value: T, ttlMs: number): void {
    // Delete first to update position if key already exists
    this.cache.delete(key);

    // Evict if at capacity
    if (this.cache.size >= this.maxSize) {
      // Map iterates in insertion order — first key is oldest
      const oldestKey = this.cache.keys().next().value;
      if (oldestKey !== undefined) this.cache.delete(oldestKey);
    }

    this.cache.set(key, {
      value,
      expiresAt: Date.now() + ttlMs,
    });
  }

  delete(key: string): void {
    this.cache.delete(key);
  }

  clear(): void {
    this.cache.clear();
  }

  get size(): number {
    return this.cache.size;
  }
}

This works because JavaScript’s Map iterates in insertion order. get re-inserts the entry (moves it to the end). set deletes the first entry (the oldest) when the cache is full.

[!NOTE] This LRU implementation relies on JavaScript’s Map iterating in insertion order. The first key is always the least recently used because get re-inserts accessed entries at the end. This is a guaranteed property of Map in the ECMAScript specification.

Using the LRU cache

// Create a cache with a maximum of 1000 entries
const bookCache = new LRUCache<any>(1000);

route.get("/books/:id", {
  resolve: (c) => {
    const id = c.input.params.id as string;
    const cached = bookCache.get(`book:${id}`);
    if (cached) return Response.json(cached);

    const book = db.prepare("SELECT ...").get(id);
    if (!book) return Response.json({ error: "Not found" }, { status: 404 });

    bookCache.set(`book:${id}`, book, 10 * 60_000); // 10 minute TTL
    return Response.json(book);
  },
});

With 5,000 books but only 1,000 cache slots, the most popular books stay cached (frequently accessed → never evicted) and rarely viewed books are evicted to make room.

Choosing cache size

Too small (100 entries): Frequent evictions. Popular entries are evicted before they can be reused. The cache hit rate is low.

Too large (1,000,000 entries): Uses too much memory. Each cached book might be 1KB — a million entries uses 1GB of RAM.

Right size: Estimate the working set — the number of entries accessed within a typical TTL window. If 500 different books are accessed every 10 minutes and the TTL is 10 minutes, a cache of 500-1,000 entries captures the working set.

Monitor the hit rate to tune the size: if 90%+ of requests hit the cache, the size is good. If less than 50% hit, the cache is too small or the TTL is too short.

Exercises

Exercise 1: Create an LRU cache with capacity 3. Insert 5 entries. Verify the first 2 are evicted.

Exercise 2: Access the second entry before inserting the 4th. Verify the first entry (not the second) is evicted.

Exercise 3: Monitor the cache hit rate: count hits and misses. Log hits / (hits + misses) every minute.