Implementierung des Blütenfilters

Question

Mit Bloom Filter erhalten wir Platzoptimierung. Das Cassandra -Framework hat auch eine Implementierung des Bloom -Filters. Aber wie wird diese Raumoptimierung im Detail erreicht?

Answer 1

Ein Blütefilter ist kein "Framework". Es ist wirklich eher einfach wie ein Algorithmus. Die Implementierung ist nicht sehr lang.

Hier ist einer in Java, den ich ausprobiert habe (.Krug, Quellcode und Javadoc sind alle verfügbar):

"Stand allein Java -Implementierungen von Cuckoo Hashing und Bloom -Filtern" (Möglicherweise möchten Sie dies googeln, falls der folgende Link nicht mehr funktioniert.)

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

Answer 2

Sie können verstehen, wie es anhand dieses Beispiels 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 von ihm eingegebene URL eine böswillige URL ist. Ich habe also einen Datensatz von etwa 1 Million böswillige URLs, die Größe dieser Datei liegt bei etwa 25 MB. Da die Größe ziemlich groß ist (groß (im Vergleich zur Größe des Browsers selbst), speichere ich diese Daten auf einem Remote -Server.

Fall 1: Ich verwende eine Hash -Funktion mit einer Hash -Tabelle. Ich entscheide mich für eine effiziente Hashing -Funktion und führe alle 1 Million URLs durch die Hashing -Funktion durch, um Hash -Tasten zu erhalten. Ich mache dann eine Hash -Tabelle (ein Array), in der mir der Hash -Schlüssel den Index gibt, um diese URL zu platzieren. Jetzt, sobald ich den Hashing -Tisch gehasht und gefüllt habe, überprüfe ich seine Größe. Ich habe alle 1 Million URLs im Hash -Tisch zusammen mit ihren Schlüssel 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 vorbeikommt und eine URL in die Adressleiste eingibt, muss ich prüfen, ob sie böswillig ist. So führe ich die URL durch die Hash -Funktion (der Browser selbst kann dies tun) und bekomme einen Hash -Schlüssel für diese URL. Ich muss nun eine Anfrage an meinen Remote -Server mit diesem Hash -Schlüssel stellen, um die jeweilige URL in meiner Hash -Tabelle mit diesem bestimmten Schlüssel zu überprüfen, wie es der Benutzer eingegeben hat. Wenn ja, dann ist es bösartig und wenn nein, dann ist es nicht bösartig. Jedes Mal, wenn der Benutzer eine URL eingibt, muss eine Anforderung an den Remote -Server gestellt werden, um zu überprüfen, ob es sich um eine böswillige URL handelt. Dies würde viel Zeit in Anspruch nehmen und so meinen Browser langsamer machen.

Fall 2: Ich benutze einen Bloom -Filter. Die gesamte Liste von 1 Million URLs wird unter Verwendung mehrerer Hash -Funktionen durch den Bloom -Filter ausgeführt, und die jeweiligen Positionen sind in einer riesigen 0S -Reihe als 1 markiert. Nehmen wir an, wir wollen eine falsch positive Rate von 1%unter Verwendung eines Blütenfilterrechners (http://hur.st/bloomfilter?n=10000&p=0.01), wir erhalten die Größe des Blütefilters als nur 1,13 MB. Diese kleine Größe wird erwartet, obwohl die Größe des Arrays riesig ist, wir speichern nur 1s oder 0s und nicht die URLs wie im Fall des Hash -Tisches. Dieses Array kann als Bit -Array behandelt werden. Da wir nur zwei Werte 1 und 0 haben, können wir einzelne Bits anstelle von Bytes festlegen. Dies würde den Raum um das 8 -fache verringern. Dieser 1,13 -MB -Bloom -Filter kann aufgrund seiner geringen Größe im Webbrowser selbst gespeichert werden !! Wenn ein Benutzer vorbeikommt und in eine URL eintritt, 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 in einer der Positionen sagt uns, dass diese URL definitiv nicht in der Liste der böswilligen URLs liegt und der Benutzer frei vorgehen kann. Daher haben wir keinen Anruf beim Server gemacht und daher Zeit gespeichert. Ein Wert von 1 sagt uns, dass die URL möglicherweise in der Liste der böswilligen URLs liegt. In diesen Fällen rufen wir den Remote -Server auf und können dort eine andere Hash -Funktion mit einer Hash -Tabelle verwenden, wie im ersten Fall zum Abrufen und Überprüfen, ob die URL tatsächlich vorhanden ist. Da eine URL in den meisten Fällen nicht böswillig ist, ist der kleine Blütefilter in den Browser -Zahlen und spart daher Zeit, indem er Anrufe auf den Remote -Server vermeidet. Nur in einigen Fällen, wenn der Bloom -Filter uns sagt, dass die URL böswillig ist, rufen wir nur in diesen Fällen einen Anruf auf den Server. Das "Macht" ist zu 99% richtig.

Durch die Verwendung eines kleinen Blütenfilters im Browser haben wir viel Zeit gespeichert, da wir keine Serveranrufe für jede eingegebene URL erstellen müssen.

Answer 3

Also habe ich diese Frage schon einmal gesehen und habe oben Ratschläge verwendet, und es stellte sich heraus, dass ich für mich langsam langsam war. Also habe ich meine eigene geschrieben. Es ist nicht ganz allgemein, aber ich bin mir sicher, ob jemand verzweifelt nach Leistung ist, wie ich es bin, sie werden es alleine allgemeiner machen :)

Ich habe 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 4

Sie können den Bloom -Filter basierend auf verwenden 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 habe a geschrieben kurzer Beitrag Über die Implementierung eines Blütenfilters mit Java 8 -Funktionen, von denen ich hoffe, dass sie für das Problem der Raumeinsparung relevant sind. Ich ging a ein bisschen weiter Um zu diskutieren, wie man eine Sammlung von Blütenfiltern in Scheiben schneiden kann, wenn einige Informationen zum Abrufen von Informationen dies tun würden, ist dies für die Effizienz relevant, wenn Sie viele Blütenfilter haben.