Tester un filtre de Bloom iOS : faux positifs et instantanés

Lors de la synchronisation d’une liste hors ligne, le client doit déterminer s’il a déjà rencontré un enregistrement. Interroger le disque pour chaque élément peut alourdir le traitement. Un filtre de Bloom permet d’écarter d’emblée les clés dont l’absence est certaine, mais assimiler « peut-être présent » à « déjà traité » risque de faire disparaître silencieusement de nouveaux enregistrements. Intégrer cette logique à une tâche de test régulière sur un Mac distant permet de repérer le problème plus facilement qu’en enquêtant sur une perte de données après la mise en production.

Déterminer d’abord si un index probabiliste est nécessaire

Ensemble exact, index de base de données et filtre de Bloom ont chacun leur place. Si le volume de données est faible et qu’une réponse certaine est indispensable, utilisez un ensemble exact. Si les données sont déjà sur disque et que le coût des requêtes reste acceptable, privilégiez un index de base de données. N’ajoutez une couche de filtrage que si de nombreuses clés absentes déclenchent des requêtes coûteuses.

Un filtre de Bloom représente une clé en positionnant plusieurs bits déterminés par hachage. Lors d’une requête, un seul bit à zéro suffit pour conclure à l’absence de la clé ; si tous les bits valent un, on peut uniquement conclure à sa présence possible. Le filtre ne permet pas d’énumérer les clés d’origine et ne remplace pas le stockage faisant autorité.

L’« absence de faux négatifs » suppose que la clé a été insérée, que le tableau de bits est intact, que les requêtes utilisent le même algorithme et qu’aucune mise à jour n’a été perdue. Ce n’est pas une garantie inconditionnelle pour l’ensemble du système métier.

Cet exemple valide uniquement un filtre à ajouts seuls. Lors de la suppression d’un enregistrement, il ne faut pas remettre directement ses bits à zéro : d’autres clés peuvent les partager. Si les suppressions sont nécessaires, reconstruisez le filtre ou choisissez une structure de données qui les prend en charge.

Fixer l’encodage des clés et le calcul des positions de bits

Un filtre persistant ne peut pas s’appuyer directement sur Hasher de Swift : celui-ci ne garantit pas des résultats identiques d’un processus à l’autre. Définissez d’abord l’encodage UTF-8 des clés, puis fixez l’algorithme de condensat et le calcul des positions de bits. Les règles métier, comme la conversion de casse ou la suppression des espaces en début et en fin de chaîne, doivent être appliquées uniformément au point d’entrée, et non laissées au choix de chaque appelant.

Voici une configuration fixe à visée pédagogique : 1024 bits et quatre positions de bits. Enregistrez ce code dans bloom-check.swift. Les quatre segments du condensat sont chacun associés à une position dans le tableau de bits ; ces paramètres ne sont pas optimisés pour tous les volumes de données en production.

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

La chaîne vide est ici une clé valide. Si les règles métier interdisent les clés vides, rejetez-les au point d’entrée plutôt que de laisser le filtre les ignorer silencieusement. La stratégie de normalisation des chaînes doit elle aussi être versionnée : des textes visuellement identiques peuvent produire des octets différents.

Valider le contrat de base avec des assertions déterministes

Ajoutez le contenu suivant au même fichier, puis exécutez la commande. Les tests doivent utiliser la même implémentation que celle livrée en production, et non une copie distincte maintenue durablement à leur seul usage.

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

L’échec d’une assertion fait échouer la tâche. N’exécutez pas ce script de validation avec une configuration d’optimisation qui désactive la vérification des assertions. L’exemple dont tous les bits valent un démontre précisément qu’un filtre peut signaler une présence même pour une clé qui n’a jamais été insérée.

Les tests doivent également couvrir les clés longues, les clés en chinois et les différentes représentations Unicode. N’exigez pas par assertion que toute clé non insérée soit déclarée absente : vous traiteriez alors un faux positif normal comme une erreur d’implémentation.

Séparer la mesure des faux positifs de la compatibilité des instantanés

Le taux de faux positifs dépend du nombre de bits, du nombre de hachages et du nombre de clés insérées. Pour la validation, fixez un ensemble de clés à insérer, puis comptez les réponses positives sur un ensemble de requêtes dont vous savez qu’il est disjoint du premier. Conservez la taille des échantillons et la version de l’algorithme. L’absence de faux positifs lors d’un essai sur un petit échantillon ne signifie pas que le taux réel est nul.

En production, un instantané ne peut pas se limiter au tableau de bits brut présenté ci-dessus. Le format qui l’encapsule doit au minimum consigner la version, le nombre de bits, le nombre de hachages, les règles d’encodage des clés et la génération du jeu de données, et vérifier l’intégrité de la charge utile. Une longueur correcte permet seulement d’écarter une troncature ; elle ne détecte pas le passage d’un bit de un à zéro.

Ajouter un jeu de référence interprocessus

Exporter puis restaurer dans le même processus ne valide qu’une partie de la logique. Il faut aussi conserver dans le dépôt un instantané généré à partir de clés fixes comme jeu de référence, le faire lire par un autre processus, puis y rechercher toutes les clés insérées. C’est ainsi que l’on peut détecter les ruptures de compatibilité dues à une évolution de l’algorithme ou de l’encodage. Si le format est incompatible, reconstruisez le filtre à partir des données faisant autorité plutôt que de deviner les anciens paramètres.

Préserver un repli correct lors de l’intégration au pipeline

Cette implémentation de type valeur ne peut pas être partagée directement pour des insertions concurrentes : les opérations de lecture-modification-écriture risquent de perdre des mises à jour de bits. Confiez les accès à un propriétaire unique qui les sérialise, ou utilisez un verrou, et assurez-vous qu’aucune écriture concurrente n’a lieu pendant la création d’un instantané. L’ordre des mises à jour du tableau de bits et des données faisant autorité doit également figurer dans le protocole de reprise.

Si le filtre est en retard sur la base de données, les réponses négatives ne sont plus fiables. Pendant la reconstruction, contournez la couche de filtrage et interrogez directement le stockage faisant autorité. Ne réactivez le filtre qu’une fois la bascule cohérente effectuée, au lieu d’envoyer du trafic vers un nouveau tableau de bits encore incomplet.

La vérification finale doit confirmer que toutes les clés insérées sont reconnues, qu’une nouvelle insertion des mêmes clés ne modifie pas l’instantané, qu’un format endommagé est rejeté, que les anciens jeux de référence restent lisibles et que la logique métier effectue bien une vérification exacte en cas de réponse positive. Une défaillance du filtre peut ralentir les requêtes, mais ne doit jamais faire disparaître de nouveaux enregistrements.

Questions fréquentes