iOS-Bloom-Filter prüfen: Fehlalarme und Snapshot-Grenzen

Beim Synchronisieren einer Offline-Liste muss der Client erkennen, ob er einen Datensatz bereits gesehen hat. Für jeden Eintrag auf den Datenträger zuzugreifen, kann zusätzlichen Aufwand verursachen. Ein Bloom-Filter kann Schlüssel vorab aussortieren, die sicher nicht vorhanden sind. Wird „möglicherweise vorhanden“ jedoch als „bereits verarbeitet“ interpretiert, gehen neue Datensätze unbemerkt verloren. Solche Fehler lassen sich leichter eingrenzen, wenn diese Logik in einem regelmäßig ausgeführten Testjob auf einem Cloud-Mac geprüft wird, statt erst nach der Bereitstellung fehlenden Daten nachzugehen.

Zuerst klären, ob ein probabilistischer Index nötig ist

Exakte Mengen, Datenbankindizes und Bloom-Filter haben jeweils ihren Platz: Bei kleinen Datenmengen und wenn unmittelbar eine eindeutige Antwort benötigt wird, eignet sich eine exakte Menge. Liegen die Daten bereits auf dem Datenträger und sind die Abfragekosten vertretbar, hat ein Datenbankindex Vorrang. Eine zusätzliche Filterschicht lohnt sich erst dann, wenn viele nicht vorhandene Schlüssel teure Abfragen auslösen.

Ein Bloom-Filter markiert einen Schlüssel an mehreren durch Hashwerte bestimmten Bitpositionen. Ist bei einer Abfrage auch nur eines dieser Bits null, steht fest, dass der Schlüssel nicht vorhanden ist. Sind alle Bits eins, lautet die Antwort lediglich „möglicherweise vorhanden“. Der Filter kann die ursprünglichen Schlüssel nicht auflisten und ersetzt nicht den maßgeblichen Datenspeicher.

„Keine falsch negativen Ergebnisse“ gilt nur unter bestimmten Voraussetzungen: Der Schlüssel wurde eingefügt, das Bitfeld ist unbeschädigt, die Abfrage verwendet denselben Algorithmus und es sind keine Aktualisierungen verloren gegangen. Das ist keine bedingungslose Zusage für das gesamte Anwendungssystem.

Dieses Beispiel prüft ausschließlich einen Filter, der nur Einfügungen unterstützt. Beim Löschen eines Datensatzes dürfen die zugehörigen Bits nicht einfach zurückgesetzt werden, da andere Schlüssel dieselben Bits nutzen können. Werden Löschungen benötigt, muss der Filter neu aufgebaut oder eine andere Datenstruktur mit Löschunterstützung gewählt werden.

Schlüsselcodierung und Berechnung der Bitpositionen festlegen

Ein persistierter Filter darf sich nicht direkt auf Swifts Hasher stützen: Dieser garantiert keine identischen Ergebnisse über Prozessgrenzen hinweg. Zunächst muss die UTF-8-Codierung der Schlüssel eindeutig feststehen. Anschließend sind der Digest-Algorithmus und die Berechnung der Bitpositionen festzulegen. Anwendungsregeln wie die Umwandlung von Groß- und Kleinschreibung oder das Entfernen führender und nachgestellter Leerzeichen gehören einheitlich an den Eingang der Verarbeitung. Aufrufer dürfen sie nicht nach Bedarf selbst festlegen.

Die folgende feste Konfiguration dient der Veranschaulichung: 1024 Bits und vier Bitpositionen. Speichern Sie den Code als bloom-check.swift. Vier Abschnitte des Digests werden jeweils auf eine Position im Bitfeld abgebildet. Diese Parameter sind nicht für beliebige Datenmengen im Produktivbetrieb optimiert.

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

Die leere Zeichenfolge ist hier ein gültiger Schlüssel. Erlaubt die Anwendung keine leeren Schlüssel, muss sie diese am Eingang zurückweisen, statt sie vom Filter stillschweigend ignorieren zu lassen. Auch die Strategie zur Zeichenfolgennormalisierung muss versioniert werden. Andernfalls können visuell identische Texte unterschiedliche Bytefolgen ergeben.

Den grundlegenden Vertrag mit deterministischen Zusicherungen prüfen

Ergänzen Sie dieselbe Datei um den folgenden Code und führen Sie anschließend den Befehl aus. Die Tests müssen dieselbe Implementierung verwenden, die auch im ausgelieferten Code zum Einsatz kommt. Eine separate Kopie nur für Tests sollte nicht dauerhaft gepflegt werden.

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

Schlägt eine Zusicherung fehl, schlägt auch der Job fehl. Führen Sie dieses Prüfskript nicht mit einer Optimierungskonfiguration aus, die solche Prüfungen deaktiviert. Das vollständig mit Einsen belegte Bitfeld zeigt gezielt, dass der Filter auch für einen nie eingefügten Schlüssel ein positives Ergebnis liefern kann.

Die Tests sollten außerdem lange Schlüssel, Schlüssel mit chinesischen Zeichen und unterschiedliche Unicode-Darstellungen abdecken. Fordern Sie nicht, dass jeder nicht eingefügte Schlüssel ein negatives Ergebnis liefert. Damit würden zulässige Fehlalarme als Implementierungsfehler gewertet.

Fehlalarmrate und Snapshot-Kompatibilität getrennt prüfen

Die Fehlalarmrate hängt von der Anzahl der Bits, der Anzahl der Hashberechnungen und der Anzahl eingefügter Schlüssel ab. Verwenden Sie für die Prüfung eine feste Menge eingefügter Schlüssel. Zählen Sie anschließend die positiven Ergebnisse für eine Abfragemenge, die nachweislich keine Überschneidung mit dieser Menge hat. Halten Sie den Stichprobenumfang und die Algorithmusversion fest. Eine einzelne kleine Stichprobe ohne Fehlalarm bedeutet nicht, dass die tatsächliche Fehlalarmrate null beträgt.

Ein Snapshot für den Produktivbetrieb darf nicht nur das oben gezeigte rohe Bitfeld enthalten. Das umschließende Format muss mindestens Version, Bitanzahl, Anzahl der Hashberechnungen, Regeln zur Schlüsselcodierung und die Generation des Datenbestands erfassen. Außerdem muss die Integrität der Nutzdaten geprüft werden. Eine korrekte Länge kann lediglich eine Kürzung ausschließen, aber nicht erkennen, ob ein einzelnes Bit von eins auf null gekippt ist.

Eine prozessübergreifende Test-Fixture ergänzen

Export und Wiederherstellung innerhalb desselben Prozesses prüfen nur einen Teil der Logik. Zusätzlich sollte ein aus festen Schlüsseln erzeugter Snapshot als Test-Fixture im Repository liegen. Ein anderer Prozess liest ihn ein und fragt alle eingefügten Schlüssel ab. Erst damit lassen sich Kompatibilitätsbrüche durch Algorithmus-Upgrades oder Änderungen der Codierung erkennen. Ist das Format inkompatibel, muss der Filter aus den maßgeblichen Daten neu aufgebaut werden, statt alte Parameter zu erraten.

Bei der Pipeline-Integration einen sicheren Ausweichpfad erhalten

Für gleichzeitige Einfügungen darf diese Werttyp-Implementierung nicht einfach gemeinsam verwendet werden: Beim Lesen, Ändern und Zurückschreiben können gesetzte Bits verloren gehen. Verwenden Sie entweder eine einzige zuständige Instanz mit serieller Verarbeitung oder eine Sperre. Stellen Sie außerdem sicher, dass während der Snapshot-Erstellung keine parallelen Schreibzugriffe stattfinden. Auch die Reihenfolge zwischen der Aktualisierung des Bitfelds und der maßgeblichen Daten muss im Wiederherstellungsprotokoll festgehalten werden.

Hinkt der Filter der Datenbank hinterher, sind negative Ergebnisse nicht mehr verlässlich. Während des Neuaufbaus muss die Filterschicht umgangen und direkt der maßgebliche Datenspeicher abgefragt werden. Aktivieren Sie den Filter erst wieder nach einem konsistenten Wechsel, statt Anfragen mit einem unvollständigen neuen Bitfeld zu bedienen.

Die abschließende Prüfung sollte Folgendes abdecken: Alle eingefügten Schlüssel liefern ein positives Ergebnis, wiederholtes Einfügen verändert den Snapshot nicht, beschädigte Formate werden zurückgewiesen, alte Fixtures bleiben lesbar und die Anwendung führt bei einem positiven Ergebnis tatsächlich eine exakte Gegenprüfung durch. Ein Ausfall des Filters darf Abfragen verlangsamen, aber keine neuen Datensätze verschwinden lassen.

Häufig gestellte Fragen