Caching

A small fast store that keeps hot data close so repeat requests skip the slow source — with an eviction policy for when it fills up.

10 min read Watch it move Build it

A cache is a small, fast store that holds copies of expensive-to-fetch data so repeat requests skip the slow source. The bet is simple: data you just used, you'll probably use again soon. The two facts that define any cache are its hit rate (how often the data is already there) and its eviction policy (what to drop when it fills up).

Hit, miss, and the cost of a miss

A hit means the item was already cached — answered in microseconds. A miss means it wasn't, so you pay the full cost of the slow source (a database query, a disk read, a remote API) and then add the result to the cache for next time. A cache only pays off when hits are common; if almost everything misses, you've added work, not removed it.

Eviction: LRU

A cache has fixed capacity, so when it's full a new entry forces an old one out. LRU (least-recently-used) evicts whatever hasn't been touched for the longest, on the bet that recently-used items are the ones you'll want again. It's implemented with a hash map (for O(1) lookup) plus a doubly-linked list ordered by recency (for O(1) move-to-front and evict-from-back).

1Capacity 3. Access A, B, C → cache is [C, B, A] (most-recent first). All were misses that loaded the item.
2Access A again → hit. Move A to front: [A, C, B].
3Access D → miss, and the cache is full. Evict the least-recently-used, B (at the back): [D, A, C].
4Access B → miss again — it was just evicted, so it must be reloaded from the source.

Why LRU needs both structures

The hash map answers 'is key X here?' in O(1). The linked list tracks *order of use* so the victim is always at the tail. Neither alone gives O(1) get and O(1) evict — you need the pair.

Write-through vs write-back

When data *changes*, the cache and the source can disagree. Two policies resolve this. Write-through: every write updates the cache and the underlying store synchronously — always consistent, but every write pays the slow-store cost. Write-back (write-behind): writes land in the cache immediately and are flushed to the store later in batches — fast writes, but a crash before the flush loses data, and the store is briefly stale.

The cache-aside pattern

The most common application-level pattern is cache-aside (lazy loading): the application, not the cache, owns the logic. Read the cache first; on a miss, fetch from the database, store it in the cache, and return it. On a write, update the database and invalidate (delete) the cached key so the next read reloads fresh data.

async function getUser(id) {
  let user = await cache.get(id);        // 1. try cache
  if (user) return user;                 //    hit -> done
  user = await db.query(id);             // 2. miss -> slow source
  await cache.set(id, user, { ttl: 60 });// 3. populate for next time
  return user;
}

async function updateUser(id, data) {
  await db.update(id, data);             // write source of truth
  await cache.del(id);                   // invalidate so next read reloads
}

Cache stampede

When a popular key expires, hundreds of requests can miss at the same instant and all hammer the database with the identical query — a stampede (thundering herd). Defenses: a short lock so only one request refills while others wait, staggered/jittered TTLs, or serving slightly-stale data while one background refresh runs.

A TTL (time to live) puts an expiry on each entry so the cache can't serve outdated data forever — after it elapses the entry is treated as stale and refetched. TTLs trade freshness against hit rate: shorter means fewer stale reads but more misses.

OperationTimeSpace

LRU get · hash map lookupO(1)O(capacity)

LRU put + evict · move node + drop tailO(1)O(capacity)

Check yourself

In an LRU cache of capacity 3, you access A, B, C, then A again, then D. Which key is evicted when D is inserted?