雲端 Mac 上的 iOS 布隆過濾器測試：假陰性、誤判與快照邊界

同步離線清單時，用戶端需要判斷某筆記錄是否已經出現過。逐筆查詢磁碟可能增加成本，布隆過濾器可以先排除確定不存在的鍵；但如果把「可能存在」當成「已經處理」，就會在不知不覺間漏掉新記錄。將這段邏輯納入雲端 Mac 的固定測試作業，比上線後才追查資料遺失更容易定位問題。

先決定是否需要機率型索引

精確集合、資料庫索引與布隆過濾器各有適用情境：資料量小，而且必須直接得到確定答案時，使用精確集合；資料已寫入磁碟，且查詢成本可以接受時，優先使用資料庫索引；只有在大量不存在的鍵會觸發高成本查詢時，才考慮增加過濾層。

布隆過濾器會透過多個雜湊位置標記一個鍵。查詢時，只要有一個位元為零，就能判定不存在；所有位元都為一，則只能判定可能存在。它無法列出原始鍵，也不能取代權威資料儲存。

「沒有假陰性」的前提是：鍵已插入、位元圖未損壞、查詢使用相同演算法，而且沒有遺失更新。這並不是對整個業務系統的無條件保證。

本例只驗收僅支援新增的過濾器。刪除記錄時不能直接清除位元，因為其他鍵可能共用該位元；需要刪除功能時，應重建過濾器，或改用支援刪除的資料結構。

固定鍵編碼與位元索引演算法

需要持久化的過濾器不能直接依賴 Swift Hasher：它不保證不同處理程序會產生相同結果。應先明確定義鍵的 UTF-8 編碼，再固定摘要演算法與位元索引的計算方式。大小寫轉換、移除頭尾空白等業務規則應在入口統一處理，不能由呼叫端臨時決定。

以下是教學用的固定設定：1024 位元、四個位元索引。請將程式碼儲存為 bloom-check.swift。摘要的四個區段分別對應至位元圖；這組參數並非針對任意資料量最佳化後的正式環境設定。

import Foundation
import CryptoKit

enum SnapshotError: Error {
    case invalidLength
}

struct Bloom {
    private var bytes: [UInt8]

    init() {
        bytes = [UInt8](repeating: 0, count: 128)
    }

    init(snapshot: Data) throws {
        guard snapshot.count == 128 else {
            throw SnapshotError.invalidLength
        }
        bytes = Array(snapshot)
    }

    var snapshot: Data {
        Data(bytes)
    }

    private func positions(_ key: String) -> [Int] {
        let digest = Array(SHA256.hash(data: Data(key.utf8)))
        return stride(from: 0, to: 32, by: 8).map { start in
            let value = digest[start..<(start + 8)].reduce(UInt64(0)) {
                ($0 << 8) | UInt64($1)
            }
            return Int(value % 1024)
        }
    }

    mutating func insert(_ key: String) {
        for bit in positions(key) {
            bytes[bit / 8] |= UInt8(1 << (bit % 8))
        }
    }

    func mightContain(_ key: String) -> Bool {
        positions(key).allSatisfy { bit in
            bytes[bit / 8] & UInt8(1 << (bit % 8)) != 0
        }
    }
}

空字串在這裡是有效的鍵。如果業務不接受空鍵，應在業務入口拒絕，而不是讓過濾器默默忽略。字串正規化策略也必須納入版本管理，否則視覺上相同的文字可能產生不同的位元組。

用確定性斷言驗收基本契約

將以下內容附加到同一個檔案，再執行指令。測試必須使用實際發布流程中的同一份實作，不能長期維護一份僅供測試的複本。

var filter = Bloom()
precondition(!filter.mightContain(""))

let keys = (0..<80).map { "record-\($0)" } + [""]
for key in keys {
    filter.insert(key)
}
for key in keys {
    precondition(filter.mightContain(key))
}

let before = filter.snapshot
for key in keys {
    filter.insert(key)
}
precondition(filter.snapshot == before)

let restored = try Bloom(snapshot: before)
for key in keys {
    precondition(restored.mightContain(key))
}

do {
    _ = try Bloom(snapshot: Data(repeating: 0, count: 127))
    preconditionFailure("Invalid snapshot accepted")
} catch SnapshotError.invalidLength {
}

let saturated = try Bloom(
    snapshot: Data(repeating: 255, count: 128)
)
precondition(saturated.mightContain("never-inserted"))

xcrun swift bloom-check.swift

斷言失敗就會使作業失敗。不要使用停用斷言檢查的最佳化設定執行這份驗收指令碼。位元全部為一的範例，是為了明確證明：即使某個鍵從未插入，過濾器仍可能回傳存在。

測試還應涵蓋長鍵、中文鍵，以及不同的 Unicode 表示方式。不要斷言每個未插入的鍵都必須回傳不存在，否則會把合法的誤判當成實作錯誤。

將誤判率測量與快照相容性分開

誤判率取決於位元數、雜湊次數與插入數量。驗收時，應固定一組插入鍵，再用確定沒有交集的查詢集統計陽性結果數量，並記錄樣本規模與演算法版本。小樣本在單次測試中沒有誤判，不代表實際誤判率為零。

正式環境的快照不能只儲存上述原始位元圖。外層格式至少要記錄版本、位元數、雜湊次數、鍵編碼規則與資料集世代，並驗證酬載完整性。長度正確只能排除資料遭截斷的情況，無法偵測某個位元從一變成零。

增加跨處理程序測試資料

在同一個處理程序內匯出再還原，只能驗證部分邏輯。還應將固定鍵產生的快照存入版本庫，作為測試資料，交由另一個處理程序讀取，再查詢所有已插入的鍵。這樣才能發現演算法升級或編碼變更造成的相容性問題。格式不相容時，應從權威資料重建，不要猜測舊參數。

接入流水線時保留正確的回退機制

並行插入時，不能直接共用這份值型別實作：讀取、修改、寫回的過程可能遺失位元更新。應由單一序列執行的擁有者管理，或使用鎖定，並確保產生快照時沒有並行寫入；位元圖更新與權威資料更新的先後關係，也必須寫進復原協定。

如果過濾器的狀態落後於資料庫，陰性結果就不再可靠。重建期間應略過過濾層，直接查詢權威資料儲存；完成一致性切換後再啟用，而不是將流量導向尚未完整建立的新位元圖。

最終檢查項目應包括：已插入的鍵全部命中、重複插入不改變快照、損壞的格式會被拒絕、舊測試資料仍可讀取，以及業務邏輯遇到陽性結果時確實執行精確回查。過濾器失效可以讓查詢變慢，但不能讓新記錄消失。

常見問題