Testing iOS Bloom Filters: False Positives and Snapshot Boundaries

When syncing a list for offline use, the client needs to determine whether it has already seen a record. Checking disk for every record can add overhead. A Bloom filter can screen out keys that are definitely absent, but treating “possibly present” as “already processed” will silently drop new records. Running this logic as a regular test job on a cloud Mac makes these problems easier to isolate than investigating missing data after release.

Decide Whether You Need a Probabilistic Index

Exact sets, database indexes, and Bloom filters each have their place. Use an exact set when the dataset is small and you need a definitive answer. Prefer a database index when the data is already on disk and query costs are acceptable. Consider an additional filtering layer only when large numbers of absent keys would otherwise trigger expensive queries.

A Bloom filter marks multiple hash-derived bit positions for each key. If any of those bits is zero during a lookup, the key is absent. If all are one, the key is only possibly present. The filter cannot enumerate the original keys or replace the authoritative store.

“No false negatives” assumes that the key has been inserted, the bitmap is intact, queries use the same algorithm, and no updates have been lost. It is not an unconditional guarantee for the entire application.

This example tests only an append-only filter. Deleting a record must not directly clear bits, because other keys may share them. If deletion is required, rebuild the filter or choose a data structure that supports deletion.

Fix the Key Encoding and Bit-Index Algorithm

A persisted filter cannot rely directly on Swift’s Hasher: it does not guarantee identical results across processes. Define the key’s UTF-8 encoding, then fix the digest algorithm and the method for calculating bit indexes. Apply business rules such as case conversion and whitespace trimming consistently at the application boundary rather than leaving them to individual callers.

The following fixed configuration is for teaching purposes: 1024 bits and four bit indexes. Save the code as bloom-check.swift. Four sections of the digest are mapped to positions in the bitmap; these are not production parameters optimized for arbitrary dataset sizes.

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

The empty string is a valid key here. If the application does not allow empty keys, reject them at the application boundary instead of having the filter silently ignore them. The string normalization policy must also be versioned; otherwise, visually identical text may produce different bytes.

Verify the Basic Contract with Deterministic Assertions

Append the following to the same file, then run the command below. Tests must exercise the same implementation used in the release path, not a separate copy maintained indefinitely for testing.

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

A failed assertion will fail the job. Do not run this acceptance script with an optimization configuration that disables assertion checks. The all-ones bitmap specifically demonstrates that the filter can return a positive result even for a key that was never inserted.

Tests should also cover long keys, keys containing Chinese text, and different Unicode representations. Do not assert that every key that was never inserted returns a negative result: that would treat legitimate false positives as implementation errors.

Separate False-Positive Measurement from Snapshot Compatibility

The false-positive rate depends on the number of bits, the number of hashes, and the number of inserted keys. For acceptance testing, use a fixed set of insertion keys, then count positive results against a query set that is explicitly disjoint from it. Record the sample size and algorithm version. A single small sample with zero false positives does not mean the true false-positive rate is zero.

Production snapshots must contain more than the raw bitmap shown above. The enclosing format should record at least the version, bit count, hash count, key encoding rules, and dataset generation, and it must verify payload integrity. A correct length can rule out truncation, but it cannot detect a bit changing from one to zero.

Add a Cross-Process Fixture

Exporting and restoring within the same process verifies only part of the logic. Also commit a snapshot generated from fixed keys as a repository fixture. Have another process read it and query every inserted key. This is how you catch compatibility breaks caused by algorithm upgrades or encoding changes. If the format is incompatible, rebuild from the authoritative data rather than guessing the old parameters.

Preserve a Safe Fallback When Integrating into the Pipeline

Concurrent insertions must not directly share this value-type implementation: read-modify-write operations can lose set bits. Use a serial owner or locking, and ensure that no concurrent writes occur while generating a snapshot. The recovery protocol must also specify the ordering between bitmap updates and updates to the authoritative data.

If the filter lags behind the database, negative results are no longer reliable. During a rebuild, bypass the filtering layer and query the authoritative store directly. Re-enable the filter only after a consistent cutover, rather than sending traffic through an incomplete new bitmap.

The final checklist should confirm that every inserted key returns a positive result, repeated insertion leaves the snapshot unchanged, malformed snapshots are rejected, old fixtures remain readable, and the application actually performs an exact lookup when the filter returns a positive result. A failed filter may make queries slower, but it must not make new records disappear.

Frequently asked questions