iOSブルームフィルタの検証：偽陰性、偽陽性とスナップショット

オフラインのリストを同期するとき、クライアントは各レコードが既に取得済みかどうかを判断する必要があります。1件ずつディスクを検索すると、その分のコストがかかります。ブルームフィルタを使えば、確実に存在しないキーを先に除外できます。ただし、「存在する可能性がある」を「処理済み」と扱うと、新しいレコードが気づかないうちに取りこぼされます。このロジックをクラウドMacの定期テストに組み込んでおけば、リリース後にデータ欠落の原因を追うよりも問題を特定しやすくなります。

まず確率的インデックスが必要かを判断する

正確な集合、データベースのインデックス、ブルームフィルタには、それぞれ適した用途があります。データ量が少なく、その場で確定的な答えが必要なら、正確な集合を使います。データが既にディスクに保存されていて、検索コストも許容範囲なら、データベースのインデックスを優先します。フィルタ層の追加を検討するのは、存在しない大量のキーによって高コストな検索が発生する場合に限ります。

ブルームフィルタは、キーから求めた複数のハッシュ位置のビットを立てます。照会時に、そのうち1ビットでもゼロなら「存在しない」と判断できます。すべてが1でも、わかるのは「存在する可能性がある」ことだけです。元のキーを列挙することはできず、正本のデータストアを置き換えるものでもありません。

「偽陰性がない」という保証には、キーが挿入済みであること、ビットマップが破損していないこと、照会に同じアルゴリズムを使うこと、更新が失われていないこと、という前提があります。業務システム全体に対する無条件の保証ではありません。

この例で検証するのは、追加専用のフィルタだけです。レコードを削除するときに、対応するビットをそのままクリアしてはいけません。他のキーが同じビットを共有している可能性があるためです。削除が必要ならフィルタを再構築するか、削除に対応した別のデータ構造を選びます。

キーのエンコーディングとビット位置の計算方法を固定する

永続化するフィルタをSwiftの Hasher に直接依存させることはできません。プロセスが変わっても同じ結果になるとは保証されていないためです。まずキーをUTF-8でどう表現するかを定め、そのうえでハッシュアルゴリズムとビット位置の計算方法を固定します。大文字・小文字の変換や前後の空白除去などの業務ルールは、入力時に統一して適用し、呼び出し側の都合で変えないようにします。

以下は学習用の固定構成で、1024ビットと4つのビット位置を使います。コードを bloom-check.swift として保存してください。ハッシュ値を4つの部分に分け、それぞれをビットマップ上の位置に対応づけます。任意のデータ量に対して最適化された、本番向けのパラメータではありません。

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

アサーションが失敗すると、ジョブも失敗します。この検証スクリプトは、アサーションのチェックを無効にする最適化設定で実行しないでください。全ビットが1のビットマップを使った例は、一度も挿入していないキーに対しても、フィルタが存在を示す結果を返し得ることを確認するためのものです。

テストには、長いキー、中国語を含むキー、異なるUnicode表現も含めます。未挿入のキーがすべて「存在しない」と判定されることをアサーションで要求してはいけません。それでは、仕様上許容される偽陽性を実装の不具合と見なしてしまいます。

偽陽性の測定とスナップショットの互換性を切り分ける

偽陽性率は、ビット数、ハッシュ回数、挿入件数によって変わります。検証では挿入するキーの集合を固定し、それと確実に重複しない照会集合で陽性の件数を数え、サンプル数とアルゴリズムのバージョンを記録します。小さなサンプルで一度偽陽性がゼロになっても、実際の偽陽性率がゼロという意味ではありません。

本番用のスナップショットには、上記の生のビットマップだけを保存するのでは不十分です。外側のフォーマットには、少なくともバージョン、ビット数、ハッシュ回数、キーのエンコーディング規則、データセットの世代を記録し、ペイロードの整合性も検証します。長さが正しいことだけでは、データの切り詰めは検出できても、あるビットが1からゼロに変わったことは検出できません。

プロセスをまたぐテスト用フィクスチャを追加する

同じプロセス内でエクスポートして復元するだけでは、ロジックの一部しか検証できません。固定のキーから生成したスナップショットをテスト用フィクスチャとしてリポジトリに保存し、別のプロセスで読み込んで、挿入済みの全キーを照会するテストも必要です。これにより、アルゴリズムの更新やエンコーディングの変更による互換性の破壊を検出できます。フォーマットに互換性がない場合は、古いパラメータを推測せず、正本データから再構築してください。

パイプラインへの組み込みでは正しい迂回経路を確保する

この値型の実装を、そのまま複数の処理で共有して並行挿入してはいけません。読み取り・変更・書き戻しの競合で、ビットの更新が失われる可能性があります。単一の所有者で処理を直列化するか、ロックを使い、スナップショットの生成中は並行書き込みが発生しないようにします。ビットマップと正本データをどの順序で更新するかも、復旧プロトコルに明記する必要があります。

フィルタの更新がデータベースより遅れていると、陰性の結果も信頼できなくなります。再構築中はフィルタ層を迂回して正本のデータストアを直接検索し、整合性を保った切り替えが完了してからフィルタを再び有効にします。未完成の新しいビットマップにリクエストを流してはいけません。

最終的な確認項目には、挿入済みの全キーがヒットすること、重複挿入でスナップショットが変わらないこと、破損したフォーマットが拒否されること、古いフィクスチャを引き続き読み込めること、そして陽性の場合に業務処理が実際に正確な照合を行うことを含めます。フィルタの不具合で検索が遅くなることはあっても、新しいレコードが消えてはなりません。

よくある質問