Comment implémenter une version Golang plus complète du filtre coucou

                                                     

Ce qui suit est introduit par la colonne du didacticiel go langage J'ai implémenté une version Golang plus complète du filtre coucou. J'espère qu'elle sera utile aux amis. dans le besoin !

« Déterminer si une valeur fait partie d'un ensemble énorme » (ci-après collectivement appelé test d'appartenance à un ensemble) est un problème courant de traitement des données. Dans le passé, si un certain taux de faux positifs était autorisé, les filtres Bloom étaient le premier choix, mais nous avons désormais un meilleur choix : les filtres coucou.
Les affaires récentes nécessitent l'utilisation de filtres. Après recherche, j'ai trouvé que le filtre coucou est plus rentable et meilleur que le filtre Bloom dans notre scénario.
Afin de déterminer la sélection finale de la technologie, j'ai lu l'article original. Plus tard, lorsque j'ai décidé d'utiliser le filtre coucou, j'ai découvert qu'il n'y avait presque pas d'implémentations complètes de golang. Actuellement, plusieurs implémentations de premier plan sur GitHub. présente quelques défauts et n'a pas maximisé l'utilisation de l'espace, j'ai donc transplanté et optimisé une version de la bibliothèque Golang en référence à l'article original et à l'implémentation C++ originale de l'article.
L'adresse du code est ici, bienvenue pour jouer, utiliser, contribuer et déboguer : github.com/linvon/cuckoo-filter

Cuckoo Filter

Cuckoo There Il existe déjà de nombreux articles d'introduction aux filtres sur Internet. Je n'en présenterai pas trop ici, je mentionnerai seulement les points clés pour mener au contenu suivant

Si vous souhaitez en savoir plus, vous pouvez vous référer. au papier original, ou consultez ma version traduite en chinois

Qu'est-ce qu'un filtre à coucou ?

est un filtre implémenté sur la base de l'algorithme de hachage de coucou. Il s'agit essentiellement d'une table de hachage de coucou qui stocke la valeur de hachage de l'élément de stockage.

Si vous connaissez les filtres Bloom, sachez que le principe des filtres Bloom est d'utiliser plusieurs méthodes de hachage pour mapper différents hachages d'éléments de stockage sur des tableaux de bits, et de vérifier ces bits lors de l'interrogation pour déterminer s'ils existent. .

Le filtre coucou hache l'élément de stockage, prend un certain nombre de chiffres de sa valeur de hachage et le stocke dans le tableau. Lors de l'interrogation, il détermine si le hachage avec des chiffres égaux existe dans le tableau.

Pourquoi choisir le filtre coucou ?

Ils stockent également les valeurs de hachage, stockant essentiellement des hachages multi-bits. Pourquoi le filtre coucou est-il meilleur ?

• Premièrement, parce que la table de hachage coucou est plus compacte, elle peut économiser plus d'espace.

• La deuxième raison est que lors de l'interrogation, le filtre Bloom utilise une variété de fonctions de hachage pour plusieurs hachages, tandis que le filtre coucou n'a besoin que d'un seul hachage, donc l'efficacité de la requête est très élevée

• Troisièmement, le filtre coucou prend en charge la suppression, tandis que le filtre Bloom ne prend pas en charge la suppression

Les avantages sont là, mais qu'en est-il des inconvénients ? Par rapport au filtre Bloom

• , le filtre coucou utilise une solution de compartiment candidat de sauvegarde. Le compartiment candidat et le compartiment préféré peuvent être obtenus en effectuant un XOR l'un avec l'autre via la position et la valeur de stockage. il faut que la taille du bucket soit un multiple exponentiel de 2
• Lorsque le filtre Bloom est inséré, le hachage est calculé et les bits sont écrits directement. Cependant, le filtre coucou peut montrer que la position actuelle. a été stocké après le calcul de l'empreinte digitale, à ce moment-là, il est nécessaire de placer les éléments stockés dans le compartiment candidat. À mesure que le compartiment se remplit, la possibilité de conflit devient de plus en plus grande et le temps d'insertion devient donc de plus en plus long. , ses performances d'insertion sont comparées au filtrage Bloom. Le filtre est très mauvais
• Insertion d'éléments en double : le filtre Bloom n'a aucun effet lors de l'insertion d'éléments en double, il réinitialise simplement les bits existants. Le filtre coucou supprimera les valeurs existantes, il y a donc une limite supérieure pour l'insertion d'éléments répétés
• La suppression du filtre coucou n'est pas parfaite : il existe les restrictions ci-dessus sur l'insertion répétée, et la suppression sera Un problème connexe se pose également : la suppression n'est parfaite que lorsque la même valeur de hachage est insérée une fois. Si l'élément est supprimé sans être inséré, une suppression accidentelle peut se produire, ce qui est la même raison pour le taux de faux positifs si l'élément est inséré plusieurs fois. fois, Ensuite, chaque suppression ne supprimera qu'une seule valeur. Vous devez savoir combien de fois l'élément a été inséré avant de pouvoir être supprimé, ou exécuter la suppression en boucle jusqu'à ce que la suppression échoue

Le les avantages et les inconvénients sont tous répertoriés, résumons-les à nouveau. Pour ce type de problème de test d'appartenance à un ensemble, la plupart des scénarios impliquent plus de lecture et moins d'écriture, et les insertions répétées n'ont aucun sens. Bien que la suppression du filtre coucou ne soit pas parfaite, c'est mieux que rien. , il faut dire que dans la plupart des cas, c'est un choix plus rentable.

Guide pratique

Mise en œuvre détaillée

Parlons d'abord du concept de filtre coucou Le filtre est composé de nombreux seaux, chacun. bucket stocke la valeur hachée de l'élément inséré, qui ne stocke qu'un nombre fixe de chiffres.

Il y a n buckets dans le filtre, le nombre de buckets est calculé en fonction du nombre d'éléments à stocker. Grâce à l'algorithme de hachage, nous pouvons calculer dans quel compartiment un élément doit être stocké. De plus, chaque algorithme de hachage supplémentaire peut générer un compartiment candidat pour un élément. Lorsque des insertions répétées sont effectuées, l'élément actuellement stocké sera transféré dans le compartiment candidat. . Entrez. Théoriquement, plus il y a d'algorithmes de hachage, plus l'utilisation de l'espace est élevée, mais dans les tests réels, k=2 fonctions de hachage peuvent atteindre un taux d'utilisation de 98 %.

Chaque compartiment stockera plusieurs empreintes digitales. Cela dépend de la taille du compartiment. Différentes empreintes digitales peuvent être mappées sur le même compartiment. Plus le compartiment est grand, plus l'utilisation de l'espace est élevée, mais en même temps, plus d'empreintes digitales sont analysées dans le même compartiment pour chaque requête, donc la probabilité de générer des faux positifs est plus élevée. À ce stade, il est nécessaire d'augmenter le. nombre d’empreintes digitales stockées pour réduire le taux de conflits.

mentionné dans l'article plusieurs paramètres requis pour mettre en œuvre le filtre coucou, principalement

• Nombre de fonctions de hachage (k) : nombre de hachages, prendre 2 C'est suffisant
• Taille du compartiment (b) : combien d'empreintes digitales sont stockées dans chaque compartiment
• Taille de l'empreinte digitale (f) : combien de bits de la valeur de hachage de la clé sont stockés dans chaque empreinte digitale

Lisez l'article en détail. Au chapitre 5, l'auteur s'appuie sur des données expérimentales pour nous indiquer comment choisir les paramètres de construction les plus appropriés. Nous pouvons obtenir la conclusion suivante

• Le filtre ne peut pas être rempli à 100. %, Il existe un facteur de charge maximum α, alors l'espace de stockage alloué à chaque élément est f/α
• En gardant la taille totale du filtre inchangée, plus le seau est grand, plus le facteur de charge est élevé, c'est-à-dire Autrement dit, plus l'utilisation de l'espace est élevée, mais plus il y a d'empreintes digitales stockées dans chaque compartiment, plus la probabilité de conflit lors de la requête est élevée. Afin de maintenir le même taux de faux positifs, plus le compartiment est grand, plus l'empreinte digitale est grande
<.>

Sur la base de la base théorique ci-dessus, les données expérimentales pertinentes obtenues sont :

Lorsque k=2 fonctions de hachage sont utilisées, lorsque la taille du bucket b=1 (c'est-à-dire une cartographie directe de la table de hachage), la charge Le facteur α est de 50%, mais lors de l'utilisation d'une taille de bucket b=2, 4 ou 8, il augmente respectivement à 84%, 95% et 98%
• Afin de garantir le taux de faux positifs r, il faut s'assurer $2b/2 ^fleq r$, alors la taille de l'empreinte f est d'environ $f ≥ log_2(2b/r)=log_2(1/r) + log_2(2b)$ , alors le coût amorti de chaque article est $C ≤ [log_2(1 /r) + log_2(2b)]/α$
• Les données expérimentales montrent que lorsque r>0,002. Deux entrées par seau produisent des résultats légèrement meilleurs que l'utilisation de quatre entrées par seau ; lorsque r est réduit à 0,00001
si utilisé, un seau semi-trié peut réduire 1. peu d'espace de stockage pour chaque élément de stockage, mais il n'agit que sur les filtres avec b=4

De cette façon, nous pouvons déterminer comment choisir les paramètres en construisant notre filtre coucou . :

Nous utilisons d'abord deux fonctions de hachage, ce qui est suffisant, ce qui permet d'obtenir une utilisation suffisante de l'espace. En fonction du taux de faux positifs dont nous avons besoin, nous pouvons déterminer quelle taille de bucket utiliser, bien sûr le choix de b n'est pas absolu, même si r>0,002, vous pouvez utiliser b=4 pour activer les buckets semi-triés. Nous pouvons ensuite calculer la taille de f dont nous avons besoin pour atteindre le taux de faux positifs cible basé sur b, afin que tous les paramètres du filtre soient déterminés.

En comparant la conclusion ci-dessus avec $1.44log_2(1/r)$ pour chaque élément du filtre Bloom, nous pouvons constater que lorsque le semi-tri est activé, lorsque r<0,03, l'espace du filtre coucou est plus petit, si le demi-tri n'est pas activé, il se dégradera à environ r<0,003.

Quelques explications avancées

Optimisation de l'algorithme de hachage

Bien que nous ayons précisé que deux algorithmes de hachage sont nécessaires, mais en réalité Lors de la mise en œuvre, il nous suffit d'utiliser un algorithme de hachage, car une méthode alternative de calcul de compartiment est mentionnée dans l'article. La deuxième valeur de hachage peut être XORée par la première valeur de hachage et l'empreinte digitale stockée à cet emplacement. Si vous craignez que nous devions toujours calculer séparément le hachage de l'empreinte digitale et le hachage de l'emplacement, nous pouvons simplement utiliser un seul algorithme pour créer un hachage de 64 bits, les 32 bits élevés étant utilisés pour calculer l'emplacement et les bits faibles. 32 bits utilisés pour calculer l'empreinte digitale.

Pourquoi les seaux semi-triés ne peuvent-ils être utilisés que lorsque b=4 ?

L'essence du demi-tri est de prendre quatre chiffres de chaque empreinte digitale. Les quatre chiffres peuvent être exprimés sous forme de nombre hexadécimal. Le stockage à quatre chiffres des empreintes digitales b peut être exprimé sous la forme b 16. Après avoir organisé. tous les numéros de base possibles dans l'ordre, la disposition correspondante peut être trouvée en indexant leurs positions pour obtenir la valeur réelle stockée.

Nous pouvons calculer le nombre de tous les types de situations grâce à la fonction suivante

func getNum(base, k, b, f int, cnt *int) {
    for i := base; i < 1<> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    n |= n >> 32
    n++
    return uint(n)}func getNumOfKindAndBit(b, f int) {
    cnt := 0
    getNum(0, 0, b, f, &cnt)
    fmt.Printf("Num of kinds: %v, Num of needed bits: %v\n", cnt, math.Log2(float64(getNextPow2(uint64(cnt)))))}Quand b=4, il y a un total de 3786 permutations, soit moins de 4096, soit 12 bits peut être utilisé pour stocker tous les index de permutation, et si toutes les empreintes digitales sont stockées directement, 4X4 = 16 bits sont nécessaires, ce qui économise 4 bits, c'est-à-dire qu'un bit est enregistré pour chaque empreinte digitale. 

On peut constater que lorsque b vaut 2, l'activation ou non du demi-tri nécessite le même nombre de bits stockés, ce qui n'a aucun sens. Si b est trop grand, l'index qui doit être stocké se développera également rapidement, ce qui entraînera une perte importante de performances des requêtes. Par conséquent, b=4 est l'option la plus rentable. 
De plus, le choix du codage pour stocker les empreintes digitales à quatre chiffres est dû au fait qu'il peut être représenté par un système hexadécimal, ce qui est pratique pour le stockage
Sélection des paramètres lors de l'utilisation de semi- sorting
Lorsque vous utilisez le demi-tri, vous devez vous assurer que $ceil(b(f-1)/8)f/8)$, sinon le l'espace occupé est le même que l'on utilise le demi-tri Grand

Sélection de la taille du filtre
La taille totale du seau du filtre doit être un multiple exponentiel de 2, donc lors du réglage du taille du filtre, essayez de satisfaire $size /α ~=(<) 2^n$, la taille est la quantité de données que vous souhaitez qu'un filtre stocke. Si nécessaire, vous devez choisir un filtre plus petit et utiliser plusieurs filtres pour atteindre l'objectif. effet cible
 Implémentation Golang
Cette partie est principalement liée à la bibliothèque Golang
Après avoir parcouru l'implémentation Golang de cuckoofilter sur Github, j'ai trouvé que les implémentations existantes présentent certaines lacunes :

La plupart des bibliothèques ont corrigé b et f, c'est-à-dire que le taux de faux positifs est également corrigé et l'adaptabilité n'est pas bonne
Toutes les bibliothèques f sont en octets, ne peuvent être ajustés que par multiples de 8, et il n'est pas pratique d'ajuster le taux de faux positifs
Toutes les bibliothèques n'implémentent pas de buckets semi-triés, ce qui réduit considérablement les avantages par rapport aux filtres Bloom. 

Parce que mon propre scénario nécessite un meilleur espace et un taux de faux positifs personnalisé, j'ai transplanté l'implémentation C++ de l'article original et effectué quelques optimisations, notamment 

 prend en charge les paramètres d'ajustement 
 prend en charge les seaux semi-triés 
 compresse l'espace dans un tableau de bits compact, stocke les empreintes digitales au niveau du bit 
 
Prend en charge la sérialisation binaire


Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!