云端 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 表示。不要断言每个未插入键都返回不存在，那会把合法误报当成实现错误。

将误报测量与快照兼容性分开

误报率取决于位数、哈希次数和插入数量。验收时固定一组插入键，再用明确不相交的查询集统计阳性数量，保存样本规模和算法版本。小样本一次零误报，不代表真实误报率为零。

生产快照不能只保存上述原始位图。外层格式至少记录版本、位数、哈希次数、键编码规则和数据集代际，并校验载荷完整性。长度正确只能排除截断，不能发现某个位从一变零。

增加跨进程夹具

同进程导出再恢复只能验证部分逻辑。还应把固定键生成的快照作为仓库夹具，由另一个进程读取，再查询全部已插入键。这样才能发现算法升级或编码变更造成的兼容性破坏。格式不兼容时，从权威数据重建，不要猜测旧参数。

接入流水线时保留正确退路

并发插入不能直接共享这份值类型实现：读改写可能丢位。选择串行所有者或加锁，并保证生成快照时没有并发写入；位图更新与权威数据更新的先后关系也要写进恢复协议。

如果过滤器落后于数据库，阴性结果就不再可靠。重建期间应绕过过滤层，直接查询权威存储；完成一致性切换后再启用，而不是拿不完整的新位图接流量。

最终检查项应包括：已插入键全部命中、重复插入不改变快照、损坏格式被拒绝、旧夹具仍可读取，以及业务遇到阳性时确实执行精确回查。过滤器失效可以让查询变慢，但不能让新记录消失。

常见问题