Image and Data Caching

Downloading the same image again every time a screen opens wastes both data and battery. This is why the cache exists: it keeps a response that was already fetched close at hand. Two kinds of cache are told apart. The memory cache is fast but disappears when the app closes. The disk cache is slower but stays after the app closes. Both are limited; when the limit is reached, an entry is evicted.

The question is this: when is writing to the cache safe? In an empty cache, almost every write is safe. In a full cache, which entry is discarded depends on the order of the operations. The core is the same.

// Replay.swift — classifies an operation's sensitivity to repetition and order
struct Trial<State: Equatable & CustomStringConvertible> {
    let label: String
    let once: State
    let twice: State
    let forward: State
    let backward: State

    var sensitivity: String {
        switch (once != twice, forward != backward) {
        case (false, false): return "robust"
        case (true, false): return "repeat-sensitive"
        case (false, true): return "order-sensitive"
        case (true, true): return "doubly-sensitive"
        }
    }

    func report() -> String {
        print("\(label) | once=\(once) twice=\(twice) ab=\(forward) ba=\(backward) -> \(sensitivity)")
        return sensitivity
    }
}

func replay<State>(_ label: String, from start: State, _ a: (State) -> State, then b: (State) -> State) -> Trial<State> {
    Trial(label: label, once: a(start), twice: a(a(start)), forward: b(a(start)), backward: a(b(start)))
}

func countSensitivities(_ results: [String]) {
    for name in ["robust", "repeat-sensitive", "order-sensitive", "doubly-sensitive"] {
        print("\(name): \(results.filter { $0 == name }.count)")
    }
}

A Cache with a Capacity

The model is a cache with a limited capacity that discards the entry unused for the longest time. Entries are “key=value” strings; the entry at the head of the list is the one unused for the longest time. The state comparison and the output show the entries in sorted order.

// Cache.swift — a cache with a capacity that discards the least recently used entry
struct Cache: Equatable, CustomStringConvertible {
    var capacity: Int
    var entries: [String] = []

    static func == (lhs: Cache, rhs: Cache) -> Bool {
        lhs.capacity == rhs.capacity && lhs.entries.sorted() == rhs.entries.sorted()
    }

    var description: String { "[" + entries.sorted().joined(separator: ",") + "]" }
}

func entryKey(_ entry: String) -> String {
    String(entry.split(separator: "=", maxSplits: 1).first ?? "")
}

func put(_ key: String, _ value: String) -> (Cache) -> Cache {
    { cache in
        var next = cache
        next.entries.removeAll { entryKey($0) == key }
        next.entries.append("\(key)=\(value)")
        while next.entries.count > next.capacity { next.entries.removeFirst() }
        return next
    }
}

func get(_ key: String) -> (Cache) -> Cache {
    { cache in
        var next = cache
        if let index = next.entries.firstIndex(where: { entryKey($0) == key }) {
            let entry = next.entries.remove(at: index)
            next.entries.append(entry)
        }
        return next
    }
}

put removes the old entry with the same key, adds the new one at the end, and if the capacity is exceeded, discards the one at the head. get moves the entry it finds to the end; reading is also a use. The model builds what the operation does to the state; it is not the system’s cache or the disk itself. == compares only the contents of the entries; how old an entry is does not show.

Three Operations in an Empty Cache

// main.swift — three operations in an empty cache
let empty = Cache(capacity: 2)

let sameKey = replay("same-key", from: empty, put("profile", "v1"), then: put("profile", "v1")).report()
let twoKeys = replay("two-keys", from: empty, put("profile", "v1"), then: put("feed", "v1")).report()
let writeRead = replay("write-read", from: empty, put("image", "v1"), then: get("profile")).report()

countSensitivities([sameKey, twoKeys, writeRead])

same-key | once=[profile=v1] twice=[profile=v1] ab=[profile=v1] ba=[profile=v1] -> robust
two-keys | once=[profile=v1] twice=[profile=v1] ab=[feed=v1,profile=v1] ba=[feed=v1,profile=v1] -> robust
write-read | once=[image=v1] twice=[image=v1] ab=[image=v1] ba=[image=v1] -> robust
robust: 3
repeat-sensitive: 0
order-sensitive: 0
doubly-sensitive: 0

All three operations are robust. Writing the same data to the same key twice does not change the content. Two different keys leave the same content in both orders, as long as they do not exceed the capacity. Reading a key that does not exist does nothing. In this section the cache is an example of robustness, and most of the time it is; this is why writing to a cache is thought of as an easy job.

NW13. The measurement takes the capacity as 2. With other capacities, which pairs of operations fill it changes.

NW14. The state comparison does not see the age order of the entries. Two caches with a different order but the same content are counted as equal.

The System’s Caches

NSCache is used for the memory cache, and URLCache for the disk and memory cache of network responses.

import Foundation

let memory = NSCache<NSString, NSData>()
memory.countLimit = 100
memory.setObject(Data([1, 2, 3]) as NSData, forKey: "profile" as NSString)
let entry = memory.object(forKey: "profile" as NSString)

import Foundation

let urlCache = URLCache(memoryCapacity: 20_000_000, diskCapacity: 100_000_000, directory: nil)
let configuration = URLSessionConfiguration.default
configuration.urlCache = urlCache
configuration.requestCachePolicy = .returnCacheDataElseLoad

Both snippets stay SOURCE. NSCache can discard entries by itself under memory pressure and does not document in what order it will discard them; for this reason the model above does not imitate its eviction policy, it builds the lesson’s own capacity rule. URLCache keeps responses in memory and on disk; the server’s headers also affect which response is cached. returnCacheDataElseLoad returns what is in the cache without going to the network, if there is something there.

Why the Cache Looks Robust

All three of the three operations came out robust in an empty cache. This does not mean a cache is always robust; it only means there is no eviction, because while it is empty the capacity never comes into play. An empty cache holds a single entry when the same key is written twice, and gives the same set whichever order you write two different keys. When the capacity fills, a new entry discards an old one, and the entry discarded changes with the order of the operations. The lesson’s bounding measurement shows exactly this: the same pair of operations comes out order-sensitive in a full cache.

Knowing the difference between these two situations also determines a test strategy. A test that checks the cache from an empty start does not see that the problem begins when the capacity is exceeded. A real bug usually appears after a long use, when the cache is full: the user has browsed about a hundred images, the first image they opened has been evicted, and it is downloaded again when they go back. The nature of the bug is performance, not correctness; but order sensitivity determines which entry is lost.

Where It Shows Up in a Real App

A feed screen downloads a small image for each row. As the user scrolls down, images are evicted; when they scroll back up, the same images are needed again. Without a cache every scroll is a re-download: data is spent, the screen flickers. With a cache, going back up is instant. The capacity is the balance of two forces. A very large cache bloats memory and the system terminates the app; a very small cache downloads half the screen again.

Staleness is a second problem. A user who changes their profile picture and sees the old picture still sitting in the cache thinks the change was not saved. There are two common solutions for this: adding a version to the address of the picture, so that when the address changes the old entry is never used; or explicitly deleting the relevant entry at the moment of change. Both rely on the put operation in the measurement being robust against repetition: writing the same key again replaces the old entry, it does not duplicate it.

The Wrong Setup and Its Fix

A common wrong setup is to use the image address as the cache key and not take the query parameters into account.

import Foundation

// Wrong: the key is only the path; different sizes going to the same path collide
func cacheKey(for url: URL) -> String {
    url.path
}

// Fix: the query also goes into the key; the key changes when the size or version changes
func cacheKey(for url: URL, size: Int) -> String {
    "\(url.path)?\(url.query ?? "")#\(size)"
}

This snippet stays SOURCE. The first function maps the addresses avatar.png?size=64 and avatar.png?size=512 to the same entry, and the small image looks blurry on a large screen. The second function adds the query and the size to the key. The two-keys line in the measurement is the model of this: different keys do not affect each other, and whichever order they are written in, the cache holds the same set.

The second mistake is to put every response that comes from the network into the cache as it is. An error page is also a response; if a 404 response enters the cache, the client keeps showing the error even after the image is fixed on the server. Only successful responses and images that can be decoded should be stored.

The Limit of the System Caches

The system has two caches, and each does a different job. The memory cache, that is NSCache, discards entries on its own under memory pressure; which entry is discarded and when is the system’s decision. The HTTP cache, that is URLCache, stores responses according to the headers the server sends and reuses them until they expire. The rule the model builds, discarding the entry unused for the longest time, is not an exact counterpart of either. Because the system’s eviction decision was not measured, this behavior goes into an assumption block.

What the Eviction Rule Hides

The rule in the model is to discard the entry unused for the longest time, and this rule has two sides. Writing puts a new entry at the end of the list; reading moves an existing entry to the end. For this reason reading, even though it looks like an operation that changes nothing, changes the state of the cache. The write-read line did not show this in an empty cache, because the key that was read did not exist. In a full cache, reading determines which entry escapes the next eviction. The ba column in the bounding measurement shows exactly this: because a is read first it becomes the newest, and the one discarded is b.

The counterpart of this behavior in a real app is this: showing an image also keeps it alive in the cache. A profile picture the user looks at often lives longer than feed images shown only once. The rule is simple and gives good results in most workloads. But a job that reads every entry only once, like a scan, can also push out the frequently used entries. A user who browses hundreds of images in a row evicts the profile picture and the icons that were in the cache at the start; when they return, all of them are downloaded again.

Choosing the Capacity

The capacity is a compromise between two resources. If it is chosen large, memory consumption rises; the system may terminate the app under memory pressure, and the gain the cache provides turns into a crash. If it is chosen small, the hit rate falls and the cache does almost no work. A good start is to limit the total size, not the number of entries: a hundred small icons and a hundred large photos do not use the same memory. The system’s memory cache takes both a count limit and a cost limit; the capacity in the model, which depends only on the count, is a simple counterpart of this.

A separate limit is set for the disk cache too. The disk looks large and cheap, but the space on the user’s phone is a shared resource, and the system can delete cache files to free the disk. For this reason the cache on disk should hold data whose loss does not break the app; images that can be downloaded again suit this, content created by the user does not.

Stale Entries and Validity

The least reliable side of a cache is that the data it holds can fall behind the truth on the server. There are three common ways to manage this. The first is a lifetime limit: each entry is given an expiry time, and an expired entry is not read. The second is validation: before using the entry, the client asks the server whether it has changed, and if it has not, the response returns as a short confirmation. The third is adding a version to the key; when the content changes the address changes too, the old entry is left without an owner, and is eventually deleted by eviction.

Which one to choose depends on how often the data changes. For an image that never changes, a versioned address is enough. For a list that changes often, a short lifetime limit and validation are used together. None is enough alone: a lifetime limit makes the client download data unnecessarily, validation sends a request every time, and a versioned address requires the server to generate the addresses.

Testing the Cache

Testing code with a cache requires not being content with an empty cache. This is the warning of a measurement that came out robust: in the empty state every operation is safe. A good test fills the cache up to its capacity, then adds an operation that triggers eviction, and checks which entry remains. It is necessary to verify separately that reading keeps an entry alive and that writing discards the oldest. A team that leaves these two behaviors untested learns of a bug in eviction only in production, when a user complains.

For rules that depend on time, a fake clock is used instead of the real clock; to test an entry whose lifetime limit has expired, the test does not have to wait for seconds. That the lesson’s model builds time with a counter or with ordering is, in this respect too, a convenience for testing.

Common Mistakes

• Leaving the cache unbounded. The memory cache bloats and the system can terminate the app.
• Treating the value in the cache as the single source of truth. A cache can always be stale.
• Keeping the files in the disk cache as important data the user cannot delete. The system deletes them to free the disk.
• Relying on the eviction order of the system cache. The order is undocumented.
• Putting only the address in the key and not including the version or the size. Two sizes of the same address get mixed up.

Interpreting the Measured Result

All three operations came out robust. This is not a result, it is a starting point: none of the operations touched the limit of the cache. The distinguishing feature of a cache is its limit, and when the limit is reached, a write is no longer only an addition, it is also a removal.

The Bounding Measurement

Below, the same two operations, writing the key c and reading the key a, are applied to two caches. One is empty, the other is full to its capacity, and a is the entry unused for the longest time.

// main.swift — the same pair of operations, empty and full cache
let full = put("b", "2")(put("a", "1")(Cache(capacity: 2)))

let onEmpty = replay("empty-cache", from: Cache(capacity: 2), put("c", "3"), then: get("a")).report()
let onFull = replay("full-cache", from: full, put("c", "3"), then: get("a")).report()

countSensitivities([onEmpty, onFull])

empty-cache | once=[c=3] twice=[c=3] ab=[c=3] ba=[c=3] -> robust
full-cache | once=[b=2,c=3] twice=[b=2,c=3] ab=[b=2,c=3] ba=[a=1,c=3] -> order-sensitive
robust: 1
repeat-sensitive: 0
order-sensitive: 1
doubly-sensitive: 0

In the empty cache a does not exist; the read does nothing and the two orders give the same result. In the full cache the order is decisive. If the write comes first, c discards a, the oldest entry, and the read is wasted. If the read comes first, a becomes the newest and the write discards b. The two orders leave different contents. The rule does not know the cache is full, it sees only that the two results are different.

NW15. This order behavior is not assumed for the system’s memory cache. A real NSCache discards entries with its own policy, and the measured order is valid only for the lesson’s model.

Summary

• The memory cache is fast and temporary; the disk cache is slower but persistent; both are limited and evict when full.
• Writing the same data with the same key and writing two different keys came out robust in an empty cache.
• In a full cache, the order of the write and the read determined which entry was discarded.
• The same pair of operations is robust in an empty cache and order-sensitive in a full one.
• The eviction order of the system cache is undocumented; the model is the lesson’s own capacity rule.
• This lesson’s sensitivity: robust.

Next Step

The cache is a mechanism that works while the app is open. In the next lesson, Background Transfers will measure why putting downloads that the system keeps running while the app is in the background back in the queue can download the same file twice.