Cache-Aside with LRU Eviction

Foundations

A cache keeps copies of hot data in memory, close to the service, so a repeat read skips the slower store behind it. In cache-aside, the service checks the cache first: a hit returns at once, and a miss reads the store and writes the value into the cache on the way back. The store stays the source of truth; the cache only holds copies.

Memory is limited, so a full cache must evict something. Least recently used, LRU, evicts the key that has gone longest without a read, betting that recent keys will be read again soon. A hash map finds a key in O(1), and a linked list ordered by recency moves a hit to the front and drops the tail.

Take a two-entry LRU cache and reads of keys a, b, a, c. a misses and is filled, b misses and is filled, and a hits and becomes the most recent, so when c misses, the cache evicts b. Three of four reads went to the store here, but on skewed traffic, where a few keys dominate, most reads hit.

• Interfaces

  That lesson writes each endpoint and its row before any box is drawn. These blocks serve those reads and writes.

  Open lesson

Case Scenario

To see how caching transforms read latency, consider a URL shortener service like bit.ly, where a 7-character short code redirects to a long destination URL: codes are looked up hundreds of times a second, a handful far more than the rest, and a mapping rarely changes. Cache-aside keeps hot codes in memory, and LRU evicts the cold ones.

Short codes are opened hundreds of times a second, but traffic is uneven: a few codes receive most requests and their mappings rarely change. Sending every repeat across the network to the mappings table wastes its limited read capacity and makes visitor latency depend on that table. The database must see well under 10% of redirects even when a handful of codes become hot.