Caching in System Design: Strategies and Eviction

A cache stores a copy of data somewhere fast, so that later requests avoid slow work. Memory is thousands of times faster than disk, and a small amount of data often gets most of the traffic.

Where caches live#

Browser --> CDN --> Load balancer --> App cache --> Redis --> Database
 cache                                 (memory)              (own cache)

The closer to the user, the faster. Most design discussions focus on a shared cache such as Redis or Memcached, in front of the database.

Cache-aside#

This is the most common pattern. The app checks the cache, and on a miss, it reads the database and fills the cache:

cache = {}
database = {"user:1": "Asha", "user:2": "Ravi"}
db_reads = 0


def get(key):
    global db_reads
    if key in cache:
        return cache[key]
    db_reads += 1
    value = database[key]
    cache[key] = value
    return value


for key in ["user:1", "user:1", "user:2", "user:1"]:
    print(key, "->", get(key))
print("Database reads:", db_reads)

user:1 -> Asha
user:1 -> Asha
user:2 -> Ravi
user:1 -> Asha
Database reads: 2

Four requests caused only two database reads.

Write strategies#

Eviction#

Memory is limited, so a cache removes something when full. The most common rule is LRU, which removes the least recently used item:

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity):
        self.items = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.items:
            return None
        self.items.move_to_end(key)
        return self.items[key]

    def put(self, key, value):
        self.items[key] = value
        self.items.move_to_end(key)
        if len(self.items) > self.capacity:
            removed, _ = self.items.popitem(last=False)
            print("Evicted", removed)


lru = LRUCache(2)
lru.put("a", 1)
lru.put("b", 2)
lru.get("a")
lru.put("c", 3)
print(list(lru.items))

Evicted b
['a', 'c']

b was removed, since a had just been used. Others are LFU (least frequently used), and FIFO (first in, first out).

Why hit ratio matters#

The hit ratio is the share of requests found in the cache. A small change in it can mean a big change in load:

requests = 100_000
for hit in (0.80, 0.90, 0.99):
    to_db = requests * (1 - hit)
    avg_ms = hit * 1 + (1 - hit) * 20
    print(f"Hit ratio {hit:.0%}: {to_db:>6,.0f} database reads, average {avg_ms:.1f} ms")

Hit ratio 80%: 20,000 database reads, average 4.8 ms
Hit ratio 90%: 10,000 database reads, average 2.9 ms
Hit ratio 99%:  1,000 database reads, average 1.2 ms

Going from 90% to 99% cuts database load by ten times.

Keeping data fresh#

There is an old saying that cache invalidation is one of the hard problems in computing. The main tools are:

• TTL (time to live): entries expire after a set time. Simple, but data can be stale until then.
• Delete on write: remove the entry when data changes.
• Versioned keys: use a new key, such as user:1:v7, after a change.

Most systems use delete on write, with a TTL as a safety net.

Common cache problems#

This shows how a little randomness spreads expiry times:

import random

random.seed(3)
ttl = 600
expiry = sorted(ttl + random.randint(0, 60) for _ in range(5))
print(expiry)

[608, 615, 623, 634, 637]

When not to cache#

Do not cache data that must be exact, such as a bank balance at the moment of payment, or data that is rarely read twice. Each cache adds complexity, and a chance of stale data.

Common mistakes#

Practice#

seen = set()
hits = 0
keys = "a b a c a b d a".split()
for key in keys:
    if key in seen:
        hits += 1
    seen.add(key)
print(f"{hits}/{len(keys)} = {hits / len(keys):.0%}")

4/8 = 50%

Key takeaway#

Next: CDNs and Object Storage.