Bloom Mise en oeuvre du filtre
https://stackoverflow.com/questions/4546447
-
13-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
En utilisant le filtre Bloom, nous obtiendrons l'optimisation de l'espace. Le cadre cassandra a également une implémentation de filtre Bloom. Mais en détail, comment cette optimisation de l'espace atteint?
La solution
Un filtre bloom n'est pas un « cadre ». Il est vraiment plus comme simplement un algorithme. La mise en œuvre est pas très longtemps.
Voici une en Java j'ai essayé ( .jar , le code source et JavaDoc étant tous disponibles):
"stand alone Java implémentations de Coucou et filtres Bloom Hashcoding" (vous pouvez Google pour cela dans le cas où le lien suivant ne fonctionne plus):
Autres conseils
Vous pouvez comprendre comment il économise de l'espace en utilisant cet exemple: Disons que je travaille pour Google, dans l'équipe de Chrome, et je veux ajouter une fonctionnalité au navigateur qui avertit l'utilisateur si l'URL, il est entré dans une URL malveillante. J'ai donc un ensemble de données d'environ 1 million d'URL malveillantes, la taille de ce fichier étant autour de 25MB. Étant donné que la taille est assez grand, (grand par rapport à la taille du navigateur lui-même), je stocke ces données sur un serveur distant.
Cas n ° 1: J'utilise une fonction de hachage avec une table de hachage. Je décide d'une fonction de hachage efficace et exécuter tous les 1 million urls par la fonction de hachage pour obtenir les clés de hachage. Je fais ensuite une table de hachage (un tableau), où la clé de hachage me donnerait l'index lieu cette URL. Alors maintenant, une fois que je l'ai haché et rempli la table de hachage, je vérifie sa taille. J'ai stocké toutes les URL 1 million dans la table de hachage avec les clés qu'ils sont. Ainsi, la taille est d'au moins 25 Mo. Cette table de hachage, en raison de sa taille sera stockée sur un serveur distant. Lorsqu'un utilisateur arrive et entre dans une URL dans la barre d'adresse, je dois vérifier si malveillant. Ainsi je lance l'URL par la fonction de hachage (le navigateur lui-même peut le faire) et je reçois une clé de hachage pour cette URL. Je dois maintenant faire une demande à mon serveur distant avec cette clé de hachage, pour vérifier si l'URL particulière dans ma table de hachage avec cette touche particulière, est le même que ce que l'utilisateur est entré. Si oui, alors il est malveillant et si non, alors il est pas méchant. Ainsi, chaque fois que l'utilisateur entre une URL, une requête au serveur distant doit être fait pour vérifier si elle est une URL malveillante. Cela prendrait beaucoup de temps et donc en tant que navigateur lent.
Cas n ° 2: J'utilise un filtre bloom. La liste complète des URL 1 million sont dirigées à travers le filtre de fleur en utilisant de multiples fonctions de hachage et les positions respectives sont marqués comme 1, dans un grand éventail de 0s. Disons que nous voulons un taux de faux positifs de 1%, à l'aide d'une calculatrice de filtre bloom ( http: // hur .ST / filtre de bloom? n = 1000000 & p = 0,01 ), nous obtenons la taille du filtre bloom nécessaire que seulement 1,13 MB. Cette petite taille devrait que, même si la taille du tableau est énorme, nous ne stockons 1 ou de 0 et non les URL comme dans le cas du tableau de table.This de hachage peut être traitée comme un tableau de bits. C'est, puisque nous avons seulement deux valeurs 1 et 0, nous pouvons mettre en bits individuels au lieu d'octets. Cela réduirait l'espace pris par 8 fois. Ce filtre bloom 1,13 Mo, en raison de sa petite taille, peut être stocké dans le navigateur Web lui-même !! Ainsi, lorsqu'un utilisateur arrive et entre dans une URL, nous appliquons simplement les fonctions de hachage requises (dans le navigateur lui-même), et vérifier toutes les positions dans le filtre bloom (qui est stocké dans le navigateur). Une valeur de 0 dans l'une des positions nous dit que cette URL est certainement pas dans la liste des URL malveillantes et l'utilisateur peut procéder librement. Ainsi, nous n'avons pas fait un appel au serveur et donc un gain de temps. Une valeur de 1 nous dit que l'url peut-être dans la liste des URLS malveillants. Dans ces cas, nous faisons un appel au serveur distant et là-bas, nous pouvons utiliser une autre fonction de hachage avec une table de hachage comme dans le premier cas, pour récupérer et vérifier si l'URL est réellement présent. Comme la plupart du temps, une URL n'est pas susceptible d'être un méchant, le petit filtre bloom dans les chiffres du navigateur qui permet d'économiser sur et donc du temps en évitant les appels vers le serveur distant. Seulement, dans certains cas, si le filtre bloom nous dit que l'URL peut être malveillant, que dans ces cas, nous faisons un appel au serveur. Ce Might 'est juste 99%.
Ainsi, en utilisant un petit filtre de fleurs dans le navigateur, nous avons économisé beaucoup de temps que nous ne avons pas besoin de faire des appels de serveur pour chaque URL entré.
Je l'ai vu cette question avant, et j'utilisé conseils ci-dessus et il est avéré être moyen de ralentir pour moi. Alors, je l'ai écrit moi-même. Il est pas complètement général, mais je suis sûr que si quelqu'un a désespérément besoin de performances comme je suis, ils le rendre plus général eux-mêmes :)
je Murmur la mise en œuvre de hachage que vous pouvez télécharger ici: http: // D3s .mff.cuni.cz / ~ Holub / sw / javamurmurhash /
Le code: uk.ac.cam.cl.ss958.SpringBoardSimulation paquet;
import ie.ucd.murmur.MurmurHash;
import java.util.BitSet;
import java.util.Random;
public class FastBloomFilter {
private final BitSet bs;
final int [] hashSeeds;
final int capacity;
public FastBloomFilter(int slots, int hashFunctions) {
bs = new BitSet(slots);
Random r = new Random(System.currentTimeMillis());
hashSeeds = new int[hashFunctions];
for (int i=0; i<hashFunctions; ++i) {
hashSeeds[i] = r.nextInt();
}
capacity = slots;
}
public void add(int value) {
byte [] b = new byte[] {
(byte)(value >>> 24),
(byte)(value >>> 16),
(byte)(value >>> 8),
(byte)value};
for (int i=0; i<hashSeeds.length; ++i) {
int h = MurmurHash.hash32(b, 4, hashSeeds[i]);
bs.set(Math.abs(h)%capacity, true);
}
}
public void clear() {
bs.clear();
}
public boolean mightContain(int value) {
byte [] b = new byte[] {
(byte)(value >>> 24),
(byte)(value >>> 16),
(byte)(value >>> 8),
(byte)value};
for (int i=0; i<hashSeeds.length; ++i) {
int h = MurmurHash.hash32(b, 4, hashSeeds[i]);
if(!bs.get(Math.abs(h)%capacity)) {
return false;
}
return true;
}
public static void main(String [] args) {
FastBloomFilter bf = new FastBloomFilter(1000, 10);
System.out.println("Query for 2000: " + bf.mightContain(2000));
System.out.println("Adding 2000");
bf.add(2000);
System.out.println("Query for 2000: " + bf.mightContain(2000));
}
}
Vous pouvez utiliser le filtre Bloom basé sur le serveur Redis avec Redisson lib. Sur la base de 128 bits HighwayHash . Voici un exemple:
RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample");
// initialize bloom filter once with
// expectedInsertions = 55000000
// falseProbability = 0.03
bloomFilter.tryInit(55000000L, 0.03);
bloomFilter.add(new SomeObject(someStateHere1));
bloomFilter.add(new SomeObject(someStateHere2));
// does it contain object?
bloomFilter.contains(new SomeObject(someStateHere3));
J'ai écrit un court après sur la mise en œuvre d'un filtre bloom en utilisant Java 8 fonctionnalités, que je l'espère est pertinente à la question des économies d'espace. Je suis allé un peu plus loin pour discuter de la façon de bit tranche une collection des filtres de la floraison, lorsque certains systèmes de recherche d'information se faire, ce qui est pertinent pour l'efficacité lorsque vous avez beaucoup de filtres de fleurs.
