Skip to content

L22 Caches and storage

24 minSuggested first: L21 Streams and subscriptions

Outcome

Distinguish cache identity, freshness, invalidation, and eviction; infer the cost of a stated mechanism.

Learn

A cache key identifies a result. A TTL (time to live) says how long an entry counts as fresh in this example. Invalidation marks an entry unusable, or removes it, after a relevant change. Eviction frees space under a capacity policy. LRU evicts the least recently used entry.

How much an operation costs depends on the implementation, not on the policy's name.

Worked example

Capacity is 2 and every entry is fresh. Insert A, insert B, read A, then insert C. Which entry is evicted?

An LRU cache with capacity 2Text
After insert A: A
After insert B: A B      oldest first
After read A:   B A
After insert C: A C      B evicted
Predict first, then show the worked explanation

Reading A makes it the most recent, so inserting C evicts B. In a simple list, finding or removing a key may need a scan. A hash map plus a linked list supports expected constant-time lookup and recency updates, under the usual hashing assumptions, at the cost of extra memory.

Practice and check

Guided practice

Practice, not scored

Skip the read of A. Which entry is evicted when C arrives?

Choose one answer

Exit check

Counts toward completion

There's room in the cache, and entry A expires before a read. Which rule causes the miss?

Choose one answer

Common mistake

Assuming an LRU cache guarantees fresh data, or that private results can share a cache key without regard to who owns them.

Practice on a real repository

Try the first puzzle below, then one of the others. This lesson's example gives no detail of their implementations.

Related topics: Caching and storage

Practice is optional. Solving a puzzle doesn't complete a lesson, and lessons never change a puzzle's points.

References