Verdrängung und Kapazität eines iOS-LRU-Caches testen

Nach mehrmaligem Weiterblättern in einer Liste werden gerade erst angezeigte Daten aus dem Cache verdrängt, obwohl dessen vorgesehene Kapazität noch gar nicht erreicht ist. Mehr Arbeitsspeicher ist hier nicht der erste Lösungsansatz. Häufiger liegt es daran, dass Lesezugriffe die Zugriffsreihenfolge nicht aktualisieren oder Updates desselben Schlüssels doppelte Einträge hinterlassen. Auf einem Cloud-Mac lässt sich die Cache-Logik in ein eigenständiges Swift-Paket auslagern. So kann man den Fehler mit wenigen deterministischen Operationsfolgen reproduzieren – unabhängig von Benutzeroberfläche, Netzwerk und Simulator.

Zuerst fünf Regeln für den Cache festlegen

Wir prüfen hier einen LRU-Cache, dessen Kapazität durch die Anzahl der Einträge begrenzt ist: Verdrängt wird jeweils der am längsten nicht verwendete Eintrag. Ablaufzeiten und persistente Speicherung auf Datenträgern gehören nicht dazu. Zunächst legen wir fünf Regeln fest:

• Ein erfolgreicher Lesezugriff macht den Schlüssel zum zuletzt verwendeten Schlüssel.
• Ein Lesezugriff ohne Treffer verändert die bestehende Reihenfolge nicht.
• Beim Schreiben auf einen vorhandenen Schlüssel werden nur der Wert aktualisiert und der Schlüssel als zuletzt verwendet markiert. Die Anzahl der Einträge bleibt gleich.
• Überschreitet das Schreiben eines neuen Schlüssels die Kapazität, wird der am längsten nicht verwendete Schlüssel verdrängt.
• Bei einer Kapazität von null werden keine Daten gespeichert; eine negative Kapazität ist ein Aufruffehler.

Diese Regeln muss das Team vereinbaren, statt sie aus Implementierungsdetails abzuleiten. Soll ein Lesezugriff in einer Anwendung beispielsweise die Verweildauer nicht verlängern, entspricht das nicht der hier definierten Zugriffsstrategie. Dieselben Testerwartungen lassen sich dann nicht unverändert übernehmen.

Die Trefferquote ist eine Betriebskennzahl, die Verdrängungsreihenfolge dagegen ein funktionaler Vertrag. Auch hinter einer unauffälligen Trefferquote können sich doppelte Schlüssel und falsche Verdrängungen verbergen.

Ein beobachtbares Modell in einem separaten Verzeichnis implementieren

Sobald auf dem Knoten die vollständige Toolchain installiert ist, führen Sie die folgenden Befehle in einem separaten Arbeitsverzeichnis aus. Dafür sind weder Administratorrechte noch eine grafische Oberfläche erforderlich.

mkdir LRUContract
cd LRUContract
swift package init --type library

Ersetzen Sie Sources/LRUContract/LRUContract.swift durch die folgende Implementierung. Das Array enthält die Schlüssel vom ältesten bis zum zuletzt verwendeten Eintrag und erleichtert damit Assertions. Die Implementierung ist nicht auf die Performance großer Caches ausgelegt.

public final class LRU<Key: Hashable, Value> {
    private let capacity: Int
    private var values: [Key: Value] = [:]
    public private(set) var oldestFirst: [Key] = []

    public init(capacity: Int) {
        precondition(capacity >= 0)
        self.capacity = capacity
    }

    public var count: Int { values.count }

    public func get(_ key: Key) -> Value? {
        guard let value = values[key] else { return nil }
        touch(key)
        return value
    }

    public func put(_ key: Key, _ value: Value) {
        guard capacity > 0 else { return }
        values.updateValue(value, forKey: key)
        touch(key)
        if values.count > capacity {
            let victim = oldestFirst.removeFirst()
            values.removeValue(forKey: victim)
        }
    }

    private func touch(_ key: Key) {
        oldestFirst.removeAll { $0 == key }
        oldestFirst.append(key)
    }
}

touch entfernt zuerst die bisherige Position und hängt den Schlüssel anschließend am Ende an. Derselbe Schlüssel kann dadurch nicht zwei Plätze in der Reihenfolge belegen. Zum Schreiben wird updateValue verwendet, damit die Löschsemantik einer Zuweisung über den Dictionary-Subscript nicht in die Update-Logik hineinspielt. Wird die Produktionsimplementierung auf ein Dictionary mit doppelt verketteter Liste umgestellt, können die Tests aus diesem Artikel bestehen bleiben. Dem hier gezeigten Array-Modell darf jedoch keine konstante Zeitkomplexität zugeschrieben werden.

Lese- und Updatefehler mit kurzen Sequenzen unterscheiden

Löschen Sie den automatisch erzeugten Beispieltest im Testverzeichnis und speichern Sie den folgenden Inhalt unter Tests/LRUContractTests/LRUContractTests.swift. Wir verwenden ausdrücklich XCTest und sind damit unabhängig davon, welches Testframework die Initialisierungsvorlage gewählt hat.

import XCTest
@testable import LRUContract

final class LRUContractTests: XCTestCase {
    func testReadPromotesAndMissDoesNot() {
        let cache = LRU<String, Int>(capacity: 2)
        cache.put("a", 1)
        cache.put("b", 2)
        XCTAssertNil(cache.get("missing"))
        XCTAssertEqual(cache.oldestFirst, ["a", "b"])
        XCTAssertEqual(cache.get("a"), 1)
        XCTAssertEqual(cache.oldestFirst, ["b", "a"])
        cache.put("c", 3)
        XCTAssertNil(cache.get("b"))
        XCTAssertEqual(cache.oldestFirst, ["a", "c"])
        XCTAssertEqual(cache.count, 2)
    }

    func testUpdateDoesNotConsumeAnotherSlot() {
        let cache = LRU<String, Int>(capacity: 2)
        cache.put("a", 1)
        cache.put("b", 2)
        cache.put("a", 9)
        XCTAssertEqual(cache.count, 2)
        XCTAssertEqual(cache.oldestFirst, ["b", "a"])
        cache.put("c", 3)
        XCTAssertNil(cache.get("b"))
        XCTAssertEqual(cache.get("a"), 9)
    }

    func testZeroCapacityStoresNothing() {
        let cache = LRU<String, Int>(capacity: 0)
        cache.put("a", 1)
        XCTAssertEqual(cache.count, 0)
        XCTAssertTrue(cache.oldestFirst.isEmpty)
        XCTAssertNil(cache.get("a"))
    }
}

Führen Sie swift test aus. Schlägt der erste Test fehl, liegt das meist an der Aktualisierung der Reihenfolge bei einem Treffer oder an Seiteneffekten eines erfolglosen Lesezugriffs. Beim zweiten Test sollten Sie zuerst Updates desselben Schlüssels prüfen. Der dritte stellt sicher, dass bei einer Kapazität von null nicht doch ein Eintrag gespeichert bleibt. Prüfen Sie nicht nur die abschließende Anzahl: Sie kann stimmen, obwohl die völlig falschen Schlüssel im Cache verbleiben.

Schon die Prüfung kann die Reihenfolge verändern

get ist keine rein lesende Beobachtungsschnittstelle. Ein Aufruf zur Kontrolle eines Werts verändert, welcher Eintrag als Nächstes verdrängt wird. Deshalb prüft das Beispiel zuerst die Reihenfolge und liest erst danach den Wert. Iterieren Sie im Test nicht beiläufig über alle Schlüssel, um jeweils get aufzurufen – damit würde der Test selbst den zu prüfenden Zustand verändern.

Von drei Testfällen zur Prüfung ganzer Sequenzen

Ergänzen Sie beim Anschluss des tatsächlichen Caches vier Arten von Sequenzen: Kapazität eins, wiederholtes Überschreiben desselben Schlüssels, mehrere erfolglose Lesezugriffe hintereinander und erneutes Einfügen nach einer Verdrängung. Prüfen Sie nach jedem Schritt, dass die Anzahl der Einträge die Kapazität nicht überschreitet, die Reihenfolge keine doppelten Schlüssel enthält und ihre Länge der tatsächlichen Anzahl der Einträge entspricht.

Für weitergehende Tests eignen sich pseudozufällige Operationen mit festem Seed. Speichern Sie zusätzlich zum Seed aber auch die vollständige Operationsliste. Ein Fehlerprotokoll sollte mindestens die Operationsnummer, den Schlüssel, den geschriebenen Wert sowie die Reihenfolge vor und nach der Operation enthalten. So lässt sich die Sequenz auch nach Änderungen an der Implementierung wiedergeben.

Verwendet die Produktionsversion eine verkettete Liste, dient das einfache Array-Modell als Referenz. Führen Sie auf beiden dieselbe Sequenz aus und vergleichen Sie die Ergebnisse. Kopieren Sie nicht die Produktionsimplementierung als „Soll-Lösung“: Sonst kann derselbe Fehler auf beiden Seiten unbemerkt bleiben.

Bei der Integration ins iOS-Projekt die Grenzen beachten

Das Beispiel enthält keine Synchronisierung. Selbst zwei asynchrone Download-Tasks dürfen diese Instanz daher nicht ohne Weiteres gemeinsam nutzen. Auch bei Verwendung eines Actors oder eines einheitlichen seriellen Zugriffswegs müssen die Aktualisierung der Reihenfolge beim Lesen, das Schreiben und die Verdrängung gemeinsam geschützt werden. Nur Schreibzugriffe zu sperren reicht nicht aus, um die Reihenfolge konsistent zu halten.

Eine Begrenzung nach Eintragszahl ist außerdem keine Begrenzung nach Bytes. Zehn Vorschaubilder beanspruchen unterschiedlich viel Speicher als zehn Originalbilder. Wird stattdessen nach Speicherkosten begrenzt, müssen eigene Regeln für die Gesamtkosten, den Ersatz der Kosten bei Updates desselben Schlüssels und die Ablehnung übergroßer Einzeleinträge festgelegt werden. Die vorhandenen Tests zur Eintragszahl sind kein Nachweis dafür, dass ein Speicherbudget eingehalten wird.

Passen Sie schließlich den tatsächlichen Anwendungscache an denselben Vertrag an, statt mit den Tests nur das Lehrmodell abzudecken. Sobald die reinen Algorithmustests bestehen, prüfen Sie mit wenigen Integrationstests, ob Schreibzugriffe nach abgeschlossenen Downloads und Lesezugriffe der Benutzeroberfläche tatsächlich dieselbe Instanz verwenden. Fehlerauslösende Sequenzen aufzubewahren hilft eher bei der Problemlösung, als die Cache-Kapazität blind zu vergrößern.

Häufig gestellte Fragen