🎓 A1Learner
🔍
0 of 47 lessons completed

Eviction and Invalidation

Eviction is the removal of entries when a cache grows full, and invalidation is the removal of an entry because the real data changed. Both keep a cache small and honest about what it holds.

Least recently used, in order

This cache holds 3 entries at most. Reading an entry makes it recent again, so other entries leave first.

order = []
cache = {}

def put(key):
    if key in cache:
        order.remove(key)
    cache[key] = key.upper()
    order.append(key)
    if len(cache) > 3:
        old = order.pop(0)
        del cache[old]
        print("evicted:", old)

def get(key):
    order.remove(key)
    order.append(key)

put("a")
put("b")
put("c")
get("a")
put("d")
put("e")
print("cache holds:", sorted(cache))

A TTL counted in steps

Time here is a step counter, not a clock. An entry set with a TTL of 3 steps expires when the counter passes it.

step = 0
cache = {}

def put(key, ttl):
    cache[key] = step + ttl

def get(key):
    if key not in cache:
        print("step", step, key, "miss, never stored")
    elif step >= cache[key]:
        print("step", step, key, "miss, TTL expired")
    else:
        print("step", step, key, "hit")

put("notice", 3)
get("notice")
step = 2
get("notice")
step = 3
get("notice")

Invalidation after a change

A profile name changes in the database. Removing the old copy forces the next read to fetch the new name.

db = {"user-9": "Ana"}
cache = {"user-9": "Ana"}

print("before change, cache serves:", cache["user-9"])
db["user-9"] = "Ana Maria"
del cache["user-9"]
print("entry invalidated, cache holds:", len(cache))
cache["user-9"] = db["user-9"]
print("after refill, cache serves:", cache["user-9"])

Example

order = []
cache = {}

def put(key):
    cache[key] = key.upper()
    order.append(key)
    if len(cache) > 3:
        old = order.pop(0)
        del cache[old]
        print("evicted:", old)

for key in ["a", "b", "c", "d", "e"]:
    put(key)
print("cache holds:", sorted(cache))
db = {"c": "old price"}
cache["c"] = "old price"
db["c"] = "new price"
del cache["c"]
print("after invalidation, cache holds:", sorted(cache))

Key points

  • Eviction: the removal of one entry to make room for a newer one.
  • Least recently used: an eviction rule that removes the entry untouched for the longest time.
  • TTL: a time limit on an entry, short for time to live, after which the entry expires.
  • Cache invalidation: the removal of an entry because the data behind it changed.

In this example, 5 entries pass through a cache that holds 3, so the 2 oldest leave in order. One entry then leaves early by invalidation, because its price changed in the database.

Note

a TTL bounds how old an entry can get, while invalidation reacts the moment a change is known.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

An entry is removed because the data behind it just changed in the database. What is that removal called?