雲端 Mac 上驗收 iOS LRU 記憶體快取：淘汰順序與容量契約

清單連續翻頁後，快取明明還沒達到預期容量，剛看過的資料卻被淘汰了。先別急著增加記憶體。更常見的原因是讀取時沒有更新存取順序，或是更新同一個鍵時留下了重複紀錄。在雲端 Mac 上，將快取邏輯抽成獨立的 Swift Package，就能不依賴介面、網路和模擬器，用幾組結果確定的操作序列重現問題。

先明確定義五條快取契約

本文驗證的是以項目數限制容量的 LRU：優先淘汰最久未使用的項目，不涵蓋到期時間與磁碟持久化。先訂下五條規則：

• 讀取命中時，將該鍵提升為最近使用。
• 讀取未命中時，不改變既有順序。
• 寫入既有鍵時，只更新值並提升順序，不增加項目數。
• 寫入新鍵而超出容量時，淘汰最久未使用的鍵。
• 容量為零時不儲存資料；負容量視為呼叫端錯誤。

這些規則應由團隊確認，而不是從實作細節反推。例如，某些業務需求希望「讀取不延長保留優先權」，那就不是這裡定義的存取策略，不能直接沿用同一組預期結果。

命中率是執行時的指標，淘汰順序則是功能契約。即使命中率看起來正常，仍可能藏有同鍵重複與錯誤淘汰的問題。

在獨立目錄中實作可觀察的模型

節點安裝好完整工具鏈後，在獨立的工作目錄執行以下命令。這裡不需要管理員權限，也不必啟動圖形介面。

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 會先移除舊位置，再附加到新位置，因此同一個鍵不會占用兩個順序位置。這裡使用 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。第一項失敗時，通常要檢查讀取是否正確提升順序，或未命中是否產生副作用；第二項失敗時，優先檢查同鍵更新；第三項則防止零容量仍偷偷保留一筆資料。不要只斷言最終數量：即使數量正確，留下來的鍵也可能完全不對。

檢查動作本身也可能改變順序

get 不是唯讀的觀察介面。為了檢查某個值而呼叫它，就會改變後續的淘汰對象。因此，上例先檢查順序，再讀取值；測試時不要隨手走訪所有鍵並呼叫 get，否則測試本身就在改寫現場狀態。

從三個案例擴展到序列驗收

接入實際快取時，補上容量為一、連續覆寫同鍵、連續未命中、淘汰後重新插入這四類序列。每一步都要檢查：數量未超過容量、順序中沒有重複鍵，以及順序長度等於實際項目數。

進一步測試時，可以使用固定種子的偽隨機操作，但除了種子，也要保留完整的操作清單。失敗紀錄至少應包含操作序號、鍵、寫入值，以及執行前後的順序，才能在實作升級後仍然重播。

若正式版本使用鏈結串列，就讓簡單的陣列模型作為參考模型，兩邊執行相同序列並比較結果。不要複製正式實作來當「標準答案」，否則很容易讓兩邊帶著同一個缺陷一起通過測試。

接回 iOS 專案時守住邊界

這個範例沒有同步機制。即使只有兩個非同步下載任務，也不能直接共用它。採用 actor 或統一的序列化入口後，讀取時的順序提升、寫入與淘汰都必須納入同一套保護；只替寫入加鎖，仍會破壞順序。

以項目數限制容量，也不等於限制位元組數。十張縮圖與十張原始圖片的記憶體成本不同。若改成依成本限容，就需要另外定義總成本、同鍵更新時的成本替換，以及拒絕超大單一項目的規則，不能將現有的數量測試當成符合記憶體預算的證明。

最後，應讓實際業務使用的快取適配同一套契約，而不是讓測試只涵蓋教學模型。純演算法測試通過後，再用少量整合測試確認：下載完成後的寫入與介面讀取，確實使用同一個實例。保留失敗序列，比盲目擴大快取容量更能解決問題。

常見問題