Caching Strategies

Caching trades memory for time. By keeping the result of a slow operation close to where you need it, repeated requests become almost free.

Hits, Misses, and Hit Rate

A cache hit means the value was already in the cache. A cache miss means you had to do the slow work and store the result. The hit rate (hits divided by total lookups) is the single most useful number to track. Aim high, and look at the misses you do have.

Time To Live (TTL)

A TTL sets how long a cached value is considered fresh. After it expires, the next lookup misses and the cache is refilled. Short TTLs mean fresher data and lower hit rates. Long TTLs mean stale data and higher hit rates.

Eviction Policies

Caches have a fixed size. When full, you must evict something. LRU (Least Recently Used) evicts whatever has been untouched the longest. It works well when recent access predicts future access, which is true for most real workloads.

The example implements LRU with a hash map for lookup and a doubly linked list (or ordered map) for recency. Both get and put run in O(1).

Other policies include LFU (least frequently used) and FIFO (oldest first).

Write Strategies

When data changes, the cache and the source of truth must agree.

• Write-through: every write goes to the cache and the database before returning. Simple, slower writes, no risk of losing data.
• Write-back: writes go to the cache only and are flushed later. Fast, but a crash can lose unwritten changes.
• Cache-aside: the application reads from the cache, falls back to the database on miss, and writes directly to the database. The cache is invalidated or updated separately.

Try It Yourself

• Add a TTL to the LRU cache so entries expire after N seconds.
• Track hit rate over a stream of requests with a Zipfian distribution and compare it to random access.
• Implement write-through and write-back versions and contrast their failure modes.