SD5.2 · LESSON 2 OF 6

Cache-aside

Design a cache key, freshness policy and miss path while calculating load and mean-latency effects.

THE IDEA

Cache-aside

In cache-aside the application reads the cache first; on a miss it fetches from the source and stores the result. A miss only says the entry is not cached, not that the record does not exist. The subtle part is concurrency: a slow reader that fetched the old value can store it after a writer has updated the source and deleted the entry, leaving stale data in the cache.

1. read a: miss → fetch from the source, populate the cache 2. read b: miss → fetch from the source, populate the cache 3. read a: hit 4. read a: hit 5. read b: hit source calls 2, hits 3 a miss only means the entry is not cached: the source may well have the record

Cache-aside: read the cache, on a miss fetch from the source and populate. Concurrent misses and write races can put old data back; a version check on populate closes the gap.

Read a sequence, then step through the write race.

Predict first. Does a cache miss mean the source has no record?

Chapter context

A cache serves a previously obtained representation instead of repeating work. Its correctness depends on which requests can share a value and how long that value may remain useful. Fast retrieval of the wrong representation is still an error.

TRY IT YOURSELF

Part 1. Do it hands-on

Replay reads and a race by hand, then write cache-aside and a version-guarded populate.

Cache-aside: read the cache, on a miss fetch from the source and populate. Concurrent misses and write races can put old data back; a version check on populate closes the gap.

source reads for a, b, a, a, b cache hits value left in the cache after the race (v1/v2) a miss means no record exists? (yes/no)

To do: Cache-aside starts empty. Reads: a, b, a, a, b. How many reads go to the source (misses)?
To do: How many are cache hits?
To do: A reader fetches value v1 from the source. Then a writer updates the source to v2 and deletes the cache entry. Then the reader (slow) writes ITS value into the cache. What value does the cache hold now? Type v1 or v2
To do: Does a cache miss mean the source has no record? Type yes or no

Part 2. Do it in code

class CacheAside(source) with self.cache (dict), self.source_calls (int) and self.hits (int).
get(key): if the key is in the cache count a hit and return it. Otherwise call source(key) (count the call). If the source returns None the record does not exist: return None and do NOT cache it. Otherwise store it and return it.
stale_after(order, source_value="v1"): simulate this interleaving. order is a list of events from: "reader_fetch" (the reader reads the source and keeps the value), "writer_update" (the source becomes "v2"), "writer_delete" (the cache entry is deleted), "reader_populate" (the reader stores the value it fetched into the cache). Return the cache content for the key afterwards (None if empty).
safe_populate_order(order): the same simulation, but the reader only populates the cache if the source version has not changed since its fetch; return the cache content.

class CacheAside:
    def __init__(self, source):
        self.source = source
        self.cache = {}
        self.source_calls = 0
        self.hits = 0

    def get(self, key):
        pass

def stale_after(order, source_value="v1"):
    pass

def safe_populate_order(order, source_value="v1"):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does a cache miss mean the source has no record?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

If h is hit probability, t-hit hit-path time and t-miss complete miss-path time:

E[T]=h\,t_{hit}+(1-h)t_{miss},\quad R_{origin}\approx(1-h)R.

The miss time here already includes lookup overhead. Means do not establish tail latency, and background refresh can add origin traffic.

Worked example

At 90% hits, 2-ms hit paths and 50-ms complete miss paths, mean latency is 0.9×2+0.1×50=6.8 ms. For 1000 requests/s, nominal origin demand is 100 requests/s. During a complete cache outage, it could become 1000 requests/s rather than remaining at the normal miss rate.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import isclose
hit=.9
assert isclose(hit*2+(1-hit)*50,6.8)
assert isclose((1-hit)*1000,100)
assert 1000/100 == 10

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A hit ratio is not a correctness guarantee. Mean latency does not reveal p95. Shared caching requires a safe identity and privacy policy; TTL does not replace authorization.