Bloom-Filter-Implementierung

Question

Mit Hilfe des Bloom-Filters können wir den Speicherplatz optimieren. Das Cassandra-Framework verfügt ebenfalls über eine Implementierung des Bloom-Filters. Aber wie wird diese Platzoptimierung im Detail erreicht?

Answer 1

Anhand dieses Beispiels können Sie nachvollziehen, wie es Platz spart: Nehmen wir an, ich arbeite für Google im Chrome-Team und möchte dem Browser eine Funktion hinzufügen, die den Benutzer benachrichtigt, wenn die eingegebene URL eine bösartige URL ist. Ich habe also einen Datensatz von etwa 1 Million bösartiger URLs, die Größe dieser Datei beträgt etwa 25 MB. Da die Datei ziemlich groß ist (groß im Vergleich zur Größe des Browsers selbst), speichere ich diese Daten auf einem entfernten Server.

Fall 1: Ich verwende eine Hash-Funktion mit einer Hash-Tabelle. Ich entscheide mich für eine effiziente Hash-Funktion und lasse alle 1 Million URLs durch die Hash-Funktion laufen, um Hash-Schlüssel zu erhalten. Dann erstelle ich eine Hash-Tabelle (ein Array), in der der Hash-Schlüssel den Index für diese URL angibt. Sobald ich die Hash-Tabelle gefüllt habe, überprüfe ich ihre Größe. Ich habe alle 1 Million URLs zusammen mit ihren Schlüsseln in der Hashtabelle gespeichert. Die Größe beträgt also mindestens 25 MB. Diese Hash-Tabelle wird aufgrund ihrer Größe auf einem Remote-Server gespeichert. Wenn ein Benutzer eine URL in die Adressleiste eingibt, muss ich prüfen, ob sie bösartig ist. Also lasse ich die URL durch die Hash-Funktion laufen (der Browser selbst kann dies tun) und erhalte einen Hash-Schlüssel für diese URL. Mit diesem Hash-Schlüssel muss ich nun eine Anfrage an meinen entfernten Server stellen, um zu prüfen, ob die bestimmte URL in meiner Hash-Tabelle mit diesem bestimmten Schlüssel mit der vom Benutzer eingegebenen URL übereinstimmt. Wenn ja, dann ist sie bösartig, wenn nein, dann ist sie nicht bösartig. Jedes Mal, wenn der Benutzer eine URL eingibt, muss also eine Anfrage an den entfernten Server gestellt werden, um zu prüfen, ob es sich um eine bösartige URL handelt. Dies würde sehr viel Zeit in Anspruch nehmen und meinen Browser langsam machen.

Fall 2: Ich verwende einen Bloomfilter. Die gesamte Liste von 1 Million URLs wird mit Hilfe mehrerer Hash-Funktionen durch den Bloom-Filter geleitet, und die entsprechenden Positionen werden in einem riesigen Feld von 0s als 1 markiert. Nehmen wir an, wir wollen eine Falsch-Positiv-Rate von 1 % und verwenden einen Bloom-Filter-Rechner ( http://hur.st/bloomfilter?n=1000000&p=0.01 ), ergibt sich eine Größe des erforderlichen Bloom-Filters von nur 1,13 MB. Diese geringe Größe ist zu erwarten, da wir trotz der enormen Größe des Arrays nur 1en oder 0en speichern und nicht die URLs wie bei der Hash-Tabelle, die wie ein Bit-Array behandelt werden kann. Das heißt, da wir nur zwei Werte 1 und 0 haben, können wir einzelne Bits anstelle von Bytes setzen. Dies würde den Platzbedarf um das 8-fache reduzieren. Dieser 1,13 MB große Bloom-Filter kann aufgrund seiner geringen Größe im Webbrowser selbst gespeichert werden! Wenn also ein Benutzer eine URL eingibt, wenden wir einfach die erforderlichen Hash-Funktionen (im Browser selbst) an und überprüfen alle Positionen im Bloom-Filter (der im Browser gespeichert ist). Ein Wert von 0 an einer der Positionen sagt uns, dass diese URL definitiv nicht in der Liste der bösartigen URLs enthalten ist und der Benutzer ungehindert fortfahren kann. Wir haben also keine Anfrage an den Server gestellt und somit Zeit gespart. Ein Wert von 1 bedeutet, dass die URL möglicherweise in der Liste der bösartigen URLs enthalten ist. In diesen Fällen rufen wir den Remote-Server an und können dort eine andere Hash-Funktion mit einer Hash-Tabelle wie im ersten Fall verwenden, um zu prüfen, ob die URL tatsächlich vorhanden ist. Da eine URL in den meisten Fällen wahrscheinlich nicht bösartig ist, findet der kleine Bloom-Filter im Browser dies heraus und spart somit Zeit, indem er Anrufe beim Remote-Server vermeidet. Nur in einigen Fällen, wenn der Bloom-Filter uns sagt, dass die URL möglicherweise bösartig ist, rufen wir den Server an. Dieses "MÖGLICH" ist zu 99 % richtig.

Durch die Verwendung eines kleinen Bloom-Filters im Browser haben wir also eine Menge Zeit gespart, da wir nicht für jede eingegebene URL einen Serveraufruf tätigen müssen.

Answer 2

Ich habe diese Frage schon einmal gesehen, und ich habe den obigen Ratschlag befolgt, und es stellte sich heraus, dass er für mich viel zu langsam war. Also habe ich meine eigene geschrieben. Sie ist nicht ganz allgemein, aber ich bin sicher, wenn jemand so verzweifelt nach Leistung sucht wie ich, wird er sie selbst allgemeiner gestalten :)

Ich habe die Murmur-Hash-Implementierung verwendet, die Sie hier herunterladen können: http://d3s.mff.cuni.cz/~holub/sw/javamurmurhash/

Der Code: Paket uk.ac.cam.cl.ss958.SpringBoardSimulation;

    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));

        }
    }

Answer 3

Ein Bloomfilter ist kein "Rahmenwerk". Er ist eigentlich eher ein einfacher Algorithmus. Die Implementierung ist nicht sehr lang.

Hier ist eine in Java, die ich ausprobiert habe ( .jar , Quellcode und JavaDoc sind alle verfügbar):

"Eigenständige Java-Implementierungen von Cuckoo Hashing und Bloom-Filtern" (Sie können danach googeln, falls der folgende Link nicht mehr funktioniert):

http://lmonson.com/blog/?page_id=99

Answer 4

Sie können Bloom-Filter verwenden, die auf Redis Server mit Redisson lib. Basierend auf 128-Bit HighwayHash . Hier ist ein Beispiel:

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));

Answer 5

Ich schrieb eine kurzer Beitrag über die Implementierung eines Bloom-Filters unter Verwendung von Java 8-Funktionen, der hoffentlich für die Frage der Platzersparnis relevant ist. Ich habe eine etwas weiter zu erörtern, wie man eine Sammlung von Bloom-Filtern aufteilt, wenn einige Informationssuchsysteme dies tun würden, was für die Effizienz bei vielen Bloom-Filtern relevant ist.