Présentation

Un filtre de Bloom est une structure probabiliste qui répond à la question « l’élément X appartient‑il à l’ensemble ? » par « définitivement non » ou « probablement oui ». En choisissant un taux de faux positifs acceptable, on obtient un tableau de bits très compact et des opérations de test très rapides. Bluesky utilise ces filtres pour éviter des millions de requêtes par seconde contre Scylla, notamment pour les relations de blocage, de mute ou de label. Les mesures affichées montrent un taux de positif d’environ 1 %, ce qui signifie que 99 % des accès disque sont évités.

Architecture traditionnelle et double hachage

Un filtre classique possède k fonctions de hachage indépendantes appliquées à chaque clé. Chaque fonction indique une position dans le tableau de bits ; l’ajout consiste à mettre à 1 les k bits, le test vérifie que tous sont à 1. Le coût principal réside dans le calcul de k hachages. En 2008, Kirsch et Mitzenmacher ont montré que deux hachages suffisent : la i‑ème position s’obtient par (hash1 + i·hash2) % n. Le taux de faux positifs reste identique, ce qui réduit le coût de calcul.

Dans le code Go bits‑and‑blooms, on exécute Murmur3 128 bits deux fois pour obtenir quatre valeurs 64 bits, puis on les combine pour générer les k positions. Cette implémentation n’est pas thread‑safe ; l’accès était protégé par un mutex. Le profilage (pprof) a révélé que la contention du mutex était le goulot d’étranglement, allongeant le déploiement de 90 minutes à 15 minutes après le passage à atomic‑bloom, qui utilise des instructions atomiques CPU.

Filtre de Bloom à un seul hachage (OHBF)

Le projet gloom implémente le One Hash Bloom Filter (OHBF) décrit par Lu et al. Au lieu d’un tableau unique, il crée k partitions de tailles mutuellement premières. Un seul hachage 128 bits est calculé : la partie haute (hash.Hi) sélectionne le bloc, la partie basse (hash.Lo) fournit le hachage de base. Pour chaque partition p, la position est hash.Lo % size_p. Ainsi, un unique calcul de hachage génère k positions distinctes.

L’implémentation Go montre deux optimisations matérielles : les blocs de 64 octets correspondent à la taille d’une ligne de cache CPU, garantissant qu’une recherche ne provoque qu’un seul cache miss. De plus, l’allocation dépasse légèrement la taille requise et utilise unsafe pour aligner les blocs sur les frontières de cache. Enfin, la sélection du bloc s’effectue avec une multiplication (MUL) au lieu d’un modulo, évitant l’instruction de division coûteuse.

hash := xxh3.Hash128(key)        // 128‑bit hash
block := hash.Hi % numBlocks    // sélection du bloc
h := hash.Lo                     // hachage de base

Le filtre est créé de façon atomique :

f := gloom.NewAtomic(1_000_000, 0.01) // 1 M d’éléments, 1 % FP

Impact et limites

Sur le backend de Bluesky, OHBF a fonctionné pendant neuf mois sans incident majeur, offrant le même taux de faux positifs (≈1 %) que les filtres à double hachage tout en réduisant le nombre d’opérations de hachage et les accès mémoire. La division du tableau en blocs coprimes élimine le besoin de calculer plusieurs fonctions de hachage, ce qui se traduit par une latence plus faible et une consommation CPU moindre. Cependant, la réduction du nombre de hachages ne profite que si la contention était le facteur limitant ; dans des scénarios où le taux de faux positifs domine les performances, le gain est marginal. De plus, la dépendance à des tailles de partitions coprimes impose une contrainte de configuration qui peut compliquer le dimensionnement pour des jeux de données très variables.