Cache replacement policy

As explained in Latency

A cache replacement policy is a rule for selecting which cached element to evict when storage capacity is exhausted.

A cache replacement policy decides which entry to evict when a full cache must make room for another. Fast storage is limited and expensive, so a cache usually holds only part of its backing dataset. The choice matters: evict an entry that is needed again soon, and the next access must pay the cost of fetching it from the backing store. section 6.6 section 6.5

Judge a policy by the workload it serves, not by its name alone. Cache hit ratio is the share of accesses served by the cache. A policy that preserves frequently needed entries can improve that ratio and reduce latency, but capacity also matters: a 1 MB cache cannot hold a 10 MB working set. Changing access patterns—for example, processing repeated passes in cache-sized batches—may help alongside changing the policy. section 6.5 section 6.6

Common approaches make different choices about which entry deserves to stay:

• FIFO evicts the entry added earliest, without promoting it on access. section 6.6.3
• LRU eagerly promotes an accessed entry to the head of the cache; LFU is another named replacement policy. section 6.6.3 section 6.11
• SIEVE builds on FIFO: it marks accessed entries as visited and checks that mark when considering an entry for eviction, avoiding the immediate eviction of some recently accessed entries. section 6.6.3

An eviction under SIEVE

Suppose a full cache has its eviction hand pointing at C. A lookup of C marks it visited. When a miss for D requires space, the hand checks C, clears its visited mark, and moves on. If B is next and unvisited, B is evicted and D is inserted. This defers C’s eviction without moving C on every hit. section 6.6.3

Figure 6.9 The SIEVE algorithm in action. The first-in, first-out (FIFO) replacement policy evicts elements based on when they were added to the cache. SIEVE is a variant of FIFO, which keeps track of cached elements that were accessed to avoid evicting hot elements.

Follow the hand and visited marks through the SIEVE eviction sequence. section 6.6.3

Replacement is not the only cache decision. Entries may also need to expire because source values change. A time-to-live balances freshness against hit ratio: too short can cause unnecessary misses, while too long can leave stale data in use. section 6.2 section 6.11

How Latency covers it

How deep it goes

Defines the eviction decision and walks through FIFO and SIEVE behavior, without specifying a complete cache implementation.

Examples

Uses a 10 MB working set against a 1 MB cache and a SIEVE eviction that skips visited C to evict B.

What it assumes

Defines eviction from a full cache while assuming familiarity with cache hits, misses, and backing storage.

What you can do after

Evaluate/understand how capacity, workload, and eviction choice affect cache hit ratio and latency.

How it connects

Links replacement to cache hit ratio, working-set size, backing-store latency, and time-to-live.

liveBookmanning.com

Read Latency on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  100 Go Mistakes and How to Avoid ThemA cache replacement policy selects an existing cache line to evict when a new block must be stored in a full set.

Compare how 2 books explain cache replacement policy →

Related concepts

• cachingconfigures · Caching is the practice of storing reusable data or computation results so later access can avoid repeating retrieval or computation.
• queueincludes · A queue is an ordered collection that holds items for retrieval or processing, typically removing them in the order they were added.
• LRUincludes · LRU is a cache replacement policy that evicts the item whose most recent access occurred furthest in the past.
• memoizationconfigures · Memoization is an optimization technique that stores computation results with their inputs so equivalent later evaluations can reuse them without recomputation.

This explainer was generated by Manning's knowledge graph from the text of Latency. The section links point to the parts of the book it draws on.