Lequel tu préfères, et pourquoi?
Ils peuvent tous deux être utilisés pour accomplir des tâches similaires, mais je suis curieux de voir ce que les gens ont utilisé dans les applications réelles et leur raisonnement.
Réponses:
9 pour la réponse № 1Les filtres à fleurs et les filtres à coucou sont utilisés dans des situations similaires, mais il y a beaucoup de différences en dessous qui déterminent généralement le meilleur choix.
Les filtres Bloom sont utilisés en interne dans la base de donnéesmoteurs, notamment Apache Cassandra. Les raisons sont, comme d’autres affiches l’ont dit, de réduire le coût des opérations au ralenti. Fondamentalement, toute opération "cela peut-être ou pas du tout" avec un coût élevé peut utiliser un filtre Bloom pour réduire le nombre de vérifications effectuées.
Un autre exemple courant avec le modèle SaaS actuelserait un service REST distant avec un coût par appel. Tout appel API avec une réponse binaire telle que "est-ce que cette adresse est INVALID" peut utiliser un filtre Bloom pour éliminer plus de 90% des requêtes en double! Notez que puisque les filtres Bloom et Cuckoo ont des faux positifs, ils ne sont PAS utiles pour l'opération inverse "cette adresse est-elle VALIDE"?
Il est important de se rappeler que Bloom et Coucoules filtres n'ont pas de faux négatifs. Cela rend ces filtres utiles pour les vérifications comme "est-ce que ce n'est certainement pas ou peut-être un spam" mais pas utile pour les opérations où les faux positifs sont inacceptables, comme la vérification des autorisations des utilisateurs. Dans cet aspect, ils peuvent être considérés conceptuellement comme l'opposé d'un cache. Les filtres et les caches de Bloom / Cuckoo sont utilisés principalement pour réduire le coût des opérations coûteuses avec une réponse booléenne, sauf que les caches n'ont pas de faux positifs et que Bloom / Cuckoo n'a pas de faux négatifs.
Les différences notables entre Cuckoo / Bloom incluent:
Combinaison. Les filtres Bloom peuvent être efficacement fusionnés tant qu'ils sont créés avec les mêmes paramètres. À la fois rapidement et avec peu de bande passante. C'est pourquoi vous les voyez fréquemment utilisés dans les systèmes à distribution massive, l'échange de filtres Bloom est rapide. Les filtres à coucou ne sont pas facilement composables, ce qui les rend moins utiles dans ces circonstances.
Faux taux positif. Les filtres à coucou sont plus efficaces en termes d'espace. De nombreux cas d'utilisation des deux structures sont axés sur la mise en réseau de bas niveau. Sur un matériel peu performant, l'efficacité des filtres Cuckoo avec un taux de faux positifs identique peut être importante. L'implémentation de référence, en c ++, trie les éléments de chaque compartiment afin de gagner de la place, en tirant parti de la position d'un élément dans un compartiment pour stocker des empreintes plus petites. Les bibliothèques supplémentaires que j'évoquerai Si quelqu'un utilise ma bibliothèque, je pourrais l'ajouter :).
Taux de faux positifs constant. Les filtres Bloom ont des taux de faux positifs asymptotiquement pires, car ils dépassent leur taille nominale. Vous pouvez continuer à insérer des objets pour toujours, mais votre taux de faux positifs finira par atteindre presque 100%. Les filtres à coucou, basés sur le hachage du coucou, ont une capacité définie dans laquelle les insertions échouent. L'insertion répétée de hachages d'éléments non aléatoires peut entraîner l'échec de l'insertion des filtres Coucou, peut-être même avant leur niveau de remplissage.
La vitesse. Ceci est subjectif et dépend beaucoup du matériel, mais les filtres de coucou sont généralement plus rapides dans le cas moyen (selon mon expérience). La plupart des modèles de filtres Bloom exécutent une fonction de hachage deux fois. Lorsque vous utilisez des fonctions de hachage sécurisées en particulier, cela peut représenter un gros handicap par rapport aux filtres de coucou qui ne font que hacher des éléments une seule fois. Le code que j'ai vu utilise différentes fonctions de hachage pour les filtres Bloom et Cuckoo. La méthode Guava Bloom de Google utilise Murmur3, beaucoup d'autres implémentations utilisent SHA1 ou quelque chose d'autre. Si les collisions de hachage peuvent être exploitées pour votre cas d'utilisation, assurez-vous que la bibliothèque utilise un hachage sécurisé. Il est important de savoir que les filtres de Bloom prennent un temps à peu près constant pour s’insérer tandis que les filtres de coucou ont un cas MOYEN de temps constant. Comme les filtres Cuckoo atteignent quelques pourcent de la capacité, la vitesse d'insertion ralentit considérablement. Même dans ce cas, seule la vitesse d'insertion ralentit, toutes les autres opérations ont un temps moyen constant.
La flexibilité. Les filtres Bloom ne supportent qu'insérer et contiennent. Les filtres à coucou supportent en outre la suppression et le comptage limité. Dans la conception de référence, les filtres Coucou peuvent déterminer combien de fois un élément a été inséré, jusqu'à 7 fois. Les filtres Bloom ne peuvent déterminer que yes-no. Les filtres à coucou prennent également en charge la suppression des éléments insérés, ce qui constitue un grand avantage par rapport à Bloom. Lorsque vous utilisez des filtres Bloom, il est assez courant de recréer le filtre à partir de zéro lorsqu'il est "plein" (le taux de faux positifs estimé dépasse le seuil), car vous ne pouvez pas supprimer les anciens éléments. commencer à échouer, donc en fonction du cas d'utilisation, cela peut être inutile. Dans certains cas, les filtres de coucou sont plus utiles car vous pouvez supprimer des éléments pour rester dans les limites de filtre au lieu de reconstruire.
Soutien. Les filtres de coucou sont nouveaux et les bibliothèques stables pour beaucoup de langues n'existent simplement pas.
Le plus grand avantage des filtres Bloom est queils ont un support de bibliothèque plus mature dans la plupart des langues. Les maths derrière les filtres de Bloom sont également mieux compris par les scientifiques. La plupart des caractéristiques des filtres à coucou ont été déterminées de manière empirique, tandis que les filtres de Bloom ont une base numérique solide. Cela exclut les filtres de coucou pour les systèmes temps réel et critiques qui doivent vérifier leurs performances, même si des preuves expérimentales montrent que les filtres de coucou fonctionnent mieux dans la plupart des cas.
Shameless Plug: Je suis le développeur d'une bibliothèque de filtres de coucou pour Java. CoucouFiltre4J . Il manque le seau semi-tri utilisé dans lepapier pour que l'efficacité de l'espace soit quelque peu inférieure à la mise en œuvre de référence. Dans le fichier Lisezmoi du projet, j'ai des liens vers d'autres implémentations dont je suis conscient. La structure la mieux adaptée dépend de votre cas d'utilisation, mais surtout si une implémentation solide du filtre Coucou existe pour votre langue.
Vous devriez certainement regarder la sourceavant d'utiliser un filtre Coucou / Bloom en production. J'ai lu plusieurs bibliothèques avant d'écrire les miennes ... beaucoup d'entre elles avaient des limites de taille silencieuses en raison de matrices 32 bits sous-jacentes ou de problèmes de performances évidents. La plupart n'avaient aucun test. L’implémentation de Google pour la mise au point de Bloom a eu de loin la meilleure qualité de code et les meilleurs tests (et supporte les limites de tableau de 64 bits). Le seul défaut de Guava's Bloom est t multi-thread.
Dans un système de production, vous voudrez peut-êtremulti-threading pour la vitesse. La réponse pour Guava "s Bloom est de créer un filtre différent pour chaque thread et de les combiner de temps en temps. Comme les filtres Cuckoo ne peuvent pas être combinés, j'ai ajouté des threads simultanés à ma bibliothèque de filtres Cuckoo. L'autre "s" je suis conscient de l'arène "t thread safe ou aren".
8 pour la réponse № 2
Que préférez-vous, le vin ou le fromage?
UNE filtre de floraison est pour quand tu as espace limité, coût de requête élevé, et principalement des requêtes négatives.
Dans ce cas, un filtre de floraison avec 8 bits par clé et 4 fonctions de hachage vous donne 2,5% de taux de faux positifs; vous traitez des requêtes presque 40 fois plus rapide qu'auparavant, au prix de 1 octet par clé.
D'un autre côté, si l'un des les conditions précédentes ne tiennent pas, une table de hachage agissant comme cache a du sens, même si cela prendra évidemment un lot plus d'un octet par entrée :-)
Vous pouvez même sauter les cas difficiles de coucou si c est un cache. Cela fait aussi augmenter les problèmes de taille de tables de coucou (ou autre chose que le hachage linéaire) sans objet.
5 pour la réponse № 3
Filtre à coucou
"Filtre à coucou: pratiquement meilleur que Bloom." Fan de bin, David Andersen, Michael Kaminsky, Michael Mitzenmacher CoNext 2014. http://dx.doi.org/10.1145/2674005.2674994
De l'un des auteurs " Blog:
Permettez-moi de décrire un filtre de coucou et certains dece qui est dans le papier pour vous. Si vous voulez éviter une discussion technique, tout ce que vous devez savoir, c’est que pour les ensembles de taille raisonnablement grande, pour le même taux de faux positifs Les filtres sont plus rapides pour les recherches (mais plus lents pour les insertions / à construire), et permettent également étonnamment des suppressions de clés (ce que les filtres de Bloom ne peuvent pas faire). dépôt github pour vous avec le code pour les filtres de coucou.
2 pour la réponse № 4
Je préfère le hachage du coucou. Je me méfie des faux positifs qui peuvent apparaître avec les filtres de floraison à des facteurs de remplissage plus élevés.
J'ai utilisé le hachage de coucou dans une application où nous avions de très grandes tables de hachage et où nous rencontrions des problèmes de mémoire. S'il vous plaît voir ma bibliothèque eCollections à http://codeplex.com/ecollections pour la mise en œuvre d'une variante du hachage du coucou.
Sincères amitiés,
0 pour la réponse № 5
Si je peux tolérer les faux positifs et que l’espace est critique, j’utilise un filtre Bloom car il prend moins de place. Sinon, j'utilise un hachage.