クラウドMacでiOSのLRUキャッシュを検証する

リストを続けてページ送りしていると、キャッシュが想定の容量に達していないのに、さっき見たデータが削除されてしまう。そんなとき、まずメモリを増やすのは早計です。よくある原因は、読み取り時にアクセス順が更新されていないことや、同じキーへの更新で重複レコードが残っていることです。クラウドMac上でキャッシュのロジックを独立したSwift Packageに切り出せば、UIやネットワーク、シミュレータに依存せず、再現性のある短い操作列で問題を再現できます。

まずキャッシュの契約を5つ定義する

この記事で検証するのは、エントリ数で容量を制限するLRUです。最後に使われてから最も時間がたったエントリを優先して削除し、有効期限やディスクへの永続化は扱いません。まず、次の5つのルールを確定します。

• 読み取りがヒットしたら、そのキーを直近に使われた位置へ移動する。
• 読み取りがミスしても、既存の順序は変えない。
• 既存キーへの書き込みでは、値と使用順序だけを更新し、エントリ数は増やさない。
• 新しいキーの書き込みで容量を超えたら、最後に使われてから最も時間がたったキーを削除する。
• 容量がゼロならデータを保存しない。負の容量は呼び出し側の誤りとする。

これらは実装の詳細から逆算するのではなく、チームで合意しておく必要があります。たとえば「読み取っても保持の優先順位を上げない」という要件なら、ここで定義するアクセス方針とは異なるため、同じ期待値をそのまま流用できません。

ヒット率は運用上の指標であり、削除順序は機能上の契約です。ヒット率が正常に見えても、同一キーの重複や誤った削除が隠れていることがあります。

独立したディレクトリに状態を観察できるモデルを実装する

ノードに完全なツールチェーンをインストールしたら、独立した作業ディレクトリで以下のコマンドを実行します。管理者権限もGUIの起動も必要ありません。

mkdir LRUContract
cd LRUContract
swift package init --type library

Sources/LRUContract/LRUContract.swift を次の実装に置き換えます。順序を保持する配列は古いものから新しいものへ並べ、アサーションしやすくしています。大容量キャッシュ向けに性能を最適化した実装ではありません。

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 は既存の位置からキーを削除してから末尾に追加するため、同じキーが順序配列の2か所を占めることはありません。また、書き込みに updateValue を使うことで、辞書の添字への代入が持つ削除の意味を更新ロジックに持ち込まずに済みます。本番実装を辞書と双方向リストの組み合わせに変更しても、この記事のテストは引き続き使えます。ただし、この配列版の時間計算量が定数時間だと説明してはいけません。

短い操作列で読み取りと更新の不具合を切り分ける

テストディレクトリに自動生成されたサンプルテストを削除し、以下を Tests/LRUContractTests/LRUContractTests.swift に保存します。初期化テンプレートでどのテストフレームワークが選ばれたかに依存しないよう、XCTestを明示的に使用します。

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"))
    }
}

swift test を実行します。最初のテストが失敗した場合は、読み取り時の順序更新か、ミス時の副作用が主な確認対象です。2つ目が失敗したら、まず同一キーの更新を調べます。3つ目は、容量ゼロでも1件だけ保存されてしまう不具合を防ぎます。最終的な件数だけを検証してはいけません。件数が正しくても、残っているキーがまったく違う可能性があります。

確認操作そのものが順序を変えることもある

get は状態を変えずに観察するためのインターフェースではありません。値を確認しようと呼び出すだけで、その後の削除対象が変わります。そのため、上の例では順序を確認してから値を読み取っています。テスト中に何気なく全キーを走査して get を呼ぶと、テスト自体が検証対象の状態を書き換えてしまいます。

3つのテストから操作列全体の検証へ広げる

実際のキャッシュを接続するときは、容量が1の場合、同じキーへの連続上書き、連続した読み取りミス、削除後の再挿入という4種類の操作列を追加します。各ステップで、件数が容量を超えていないこと、順序に重複キーがないこと、順序配列の長さが実際のエントリ数と一致することを確認します。

さらに検証を進めるなら、シードを固定した疑似乱数による操作も使えます。ただし、シードだけでなく、操作列全体も保存してください。失敗時の記録には、少なくとも操作番号、キー、書き込む値、実行前後の順序を含めます。そうすれば、実装を更新した後でも再現できます。

本番版がリンクリストを使っているなら、単純な配列モデルを参照モデルにし、両方で同じ操作列を実行して結果を比較します。本番実装をコピーして「正解」にしてはいけません。同じ不具合を抱えたまま、両方のテストが通ってしまうおそれがあります。

iOSプロジェクトへ戻すときに守るべき境界

このサンプルには同期機構がありません。非同期のダウンロードタスクが2つだけでも、そのまま共有してはいけません。actorや単一の直列実行経路を導入し、読み取り時の順序更新、書き込み、削除をすべて同じ保護範囲に置く必要があります。書き込みだけをロックしても、順序は壊れます。

また、エントリ数による容量制限は、バイト数の制限ではありません。サムネイル10枚と元画像10枚では、メモリ使用量が異なります。コストに基づく制限へ変更するなら、総コスト、同一キー更新時のコスト置き換え、単体で上限を超えるエントリの拒否について、別途ルールを定義する必要があります。既存の件数テストを、メモリ予算を守れている証拠として扱うことはできません。

最後に、テストが教材用モデルだけを対象にしないよう、実際の業務で使うキャッシュを同じ契約に適合させます。アルゴリズム単体のテストが通ったら、少数の結合テストで、ダウンロード完了後の書き込みとUIからの読み取りが本当に同じインスタンスを使っているか確認します。むやみにキャッシュ容量を増やすより、失敗した操作列を残すほうが問題解決につながります。

よくある質問