How do you design a cache: memory and disk layers, TTL, eviction, and what to key it by?

13.5.2 · L5 · Interview

Predict first

A tiny LRU cache with a TTL and an injected clock holds two entries. What does it return as entries are read, added and aged?

struct Cache {
    var now: () -> Int
    let capacity: Int, ttl: Int
    var order: [String] = []
    var store: [String: (value: Int, at: Int)] = [:]
    init(capacity: Int, ttl: Int, now: @escaping () -> Int) { self.capacity = capacity; self.ttl = ttl; self.now = now }
    mutating func get(_ k: String) -> Int? {
        guard let e = store[k], now() - e.at < ttl else { store[k] = nil; order.removeAll { $0 == k }; return nil }
        order.removeAll { $0 == k }; order.append(k); return e.value
    }
    mutating func set(_ k: String, _ v: Int) {
        order.removeAll { $0 == k }; order.append(k); store[k] = (v, now())
        while order.count > capacity { store[order.removeFirst()] = nil }
    }
}
nonisolated(unsafe) var t = 0
var c = Cache(capacity: 2, ttl: 10, now: { t })
c.set("a", 1); c.set("b", 2)
_ = c.get("a")
c.set("c", 3)
print(c.get("a") as Any, c.get("b") as Any)
t = 20
print(c.get("c") as Any)

Optional(1) nil, then nil
nil Optional(2), then Optional(3)
Optional(1) Optional(2), then nil

Mental model. A cache is a small desk next to a big warehouse. LRU is clearing the item you have not touched for longest when the desk is full; TTL is a “use by” date on each item; and the key is the label that says exactly which version of the item it is.

A cache trades memory or disk for time, and its policy is the design. Decide five things. Key: everything that changes the value, for example the URL and the requested size; a key that is too coarse returns the wrong value. Capacity: limit by count or by cost (bytes of decoded data), because a hundred thumbnails and a hundred photos are very different. Eviction: when full, who goes? LRU (least recently used) is the usual choice: keep an ordering updated on each read and evict the oldest-used entry; LFU, FIFO and random exist but LRU matches typical access patterns. Expiry: a TTL (time to live) makes entries stale after a duration; check it on read and treat an expired entry as a miss (optionally returning it while a refresh runs, “stale-while-revalidate”). Inject a clock so tests can advance time. Invalidation: the hard part; clear on sign-out and on schema or version change, and write-through or invalidate when the underlying data changes, or you serve stale data forever.

Layers: a memory cache (NSCache evicts automatically under memory pressure and is thread-safe but not LRU-strict and not predictable; a hand-written LRU gives precise control but needs a lock or an actor) in front of a disk cache in the Caches directory (files named by a hash of the key, with size and age limits enforced by a periodic sweep, and tolerance for the OS purging it). Read through the layers (memory, then disk, then source), promote on a hit, and write to all on a miss. Protect it for concurrency (an actor or a lock), de-duplicate in-flight loads so ten requests for one key start one load, and make it observable (hit rate, size) so you can tune it. Disk writes should be atomic and a corrupt or old-format entry should be treated as a miss, not a crash; version the on-disk format. Cache only what is cheap to recompute or expensive to fetch and safe to share; do not cache personal data in a place that outlives the user’s session, and size caches to the device (not unlimited), since the system will purge or kill an app that holds too much memory.

Reading "a" made it most recent, so adding "c" evicted "b", the least recently used. After the clock moves past the TTL, "c" has expired and reads as a miss.

Common traps

Using the URL alone as the key. A thumbnail can be returned where the full image was requested; include the size.
No invalidation story. The cache serves stale or another user’s data after sign-out or a data change.

They might follow up with

How does an LRU cache evict? Reading or writing marks an entry most recent; when over capacity the least recently used is removed.
How do you test expiry? Inject a clock into the cache and advance it, instead of sleeping.

How do you design a cache: memory and disk layers, TTL, eviction, and what to key it by?

Predict first

Common traps

They might follow up with

Related questions