/ / Bloom Filter oder Kuckuckshashing? - Algorithmus, Hash, Filter

Bloomfilter oder Kuckuckshashing? - Algorithmus, Hash, Filter

Welche bevorzugen Sie und warum?

Sie können beide verwendet werden, um ähnliche Aufgaben zu erfüllen, aber ich bin neugierig, zu sehen, was Leute in tatsächlichen Anwendungen verwendet haben und ihre Gründe dafür.

Antworten:

9 für die Antwort № 1

Bloom-Filter und Cuckoo-Filter werden in ähnlichen Situationen verwendet, aber es gibt eine Menge Unterschiede darunter, die normalerweise bestimmen, welche die bessere Wahl ist.

Bloom-Filter werden intern in der Datenbank verwendetMotoren, vor allem Apache Cassandra. Die Gründe sind, wie andere Plakate sagten, um die Kosten von langsamen Set-Operationen zu reduzieren. Grundsätzlich kann jede Operation "ob dies vielleicht oder definitiv nicht existiert" mit einem hohen Aufwand einen Bloom-Filter verwenden, um die Anzahl der durchgeführten Überprüfungen zu reduzieren.

Ein weiteres gängiges Beispiel für das heutige SaaS-Modellwäre ein Remote-REST-Service mit einem Cost-per-Call. Jeder API-Aufruf mit einer binären Antwort wie "Ist diese Adresse INVALID" kann einen Bloom-Filter verwenden, um über 90% der doppelten Abfragen zu eliminieren! Beachten Sie, dass Bloom- und Cuckoo-Filter falsche positive Werte haben und daher NICHT für die umgekehrte Operation geeignet sind. "Ist diese Adresse gültig?"

Wichtig zu erinnern ist, dass Bloom und CuckooFilter haben KEINE falschen Negative. Dies macht diese Filter nützlich für Prüfungen wie "ist das definitiv nicht oder vielleicht Spam", aber nicht nützlich für Operationen, bei denen falsch positive Ergebnisse nicht akzeptabel sind, wie das Überprüfen von Benutzerberechtigungen. In diesem Aspekt können sie konzeptionell als das Gegenteil eines Caches angesehen werden. Sowohl Bloom / Cuckoo Filter als auch Caches werden hauptsächlich verwendet, um die Kosten von teuren Operationen mit einer booleschen Antwort zu reduzieren, außer dass Caches keine False Positives haben und Bloom / Cuckoo keine False Negatives haben.

Bemerkenswerte Unterschiede zwischen Cuckoo / Bloom schließen ein:

  • Kombination. Bloom-Filter können effizient zusammengeführt werden, solange sie mit den gleichen Parametern erstellt werden. Sowohl schnell als auch mit geringer Bandbreite. Aus diesem Grund werden sie oft in massiv verteilten Systemen verwendet, der Austausch von Bloom-Filtern ist schnell. Kuckuckfilter sind nicht leicht zusammensetzbar, was sie unter diesen Umständen weniger nützlich macht.

  • Falsch positive Rate. Kuckuckfilter sind platzsparender. Viele Anwendungsfälle für beide Strukturen konzentrieren sich auf Low-Level-Networking. Bei schwacher Hardware kann die ~ 40% höhere Effizienz von Cuckoo-Filtern bei gleicher falscher Positivrate wichtig sein. Die Referenzimplementierung in C ++ sortiert Elemente in jedem Bucket für zusätzliche Platzeinsparungen und nutzt die Position eines Objekts in einem Bucket, um kleinere Fingerabdrücke zu speichern. Die zusätzlichen Bibliotheken, die ich später erwähne (einschließlich meiner), scheinen dies nicht zu tun Tun Sie das. Wenn jemand jemals meine Bibliothek benutzt, könnte ich es hinzufügen :).

  • Konstante falsche positive Rate. Bloom-Filter haben asymptotisch schlechtere falsch-positive Raten, wenn sie ihre vorgesehene Größe überschreiten. Sie können Elemente für immer einfügen, aber letztendlich wird Ihre falsche positive Rate fast 100% betragen. Cuckoo-Filter, die auf Cuckoo-Hashing basieren, haben eine festgelegte Kapazität, bei der Einfügungen tatsächlich fehlschlagen. Wiederholtes Einfügen von nicht zufälligen Item-Hashes kann dazu führen, dass Cuckoo-Filter nicht eingefügt werden, möglicherweise weit vor dem geplanten Füllgrad.

  • Geschwindigkeit. Das ist subjektiv und hängt stark von der Hardware ab, aber Cuckoo-Filter sind im Durchschnitt schneller (meiner Erfahrung nach). Die meisten Bloom-Filterdesigns führen zweimal eine Hash-Funktion aus. Insbesondere bei Verwendung von sicheren Hash-Funktionen kann dies ein großes Handicap im Vergleich zu Cuckoo-Filtern sein, die nur einmal eingefügte Elemente hashen. Der Code, den ich sonst „habe verschiedene Hashing-Funktionen für Bloom und Cuckoo Filter. Google gesehen verwendet“ s Guava Bloom verwendet Murmur3, viele andere Implementierungen verwenden SHA1 oder so etwas. Wenn Hash-Kollisionen für Ihren Anwendungsfall ausgenutzt werden können, stellen Sie sicher, dass die Bibliothek einen sicheren Hash verwendet. Wichtig zu wissen ist, dass Bloom-Filter ungefähr die gleiche Zeit brauchen, um einzufügen, während Cuckoo-Filter einen konstanten Zeit-Mittelwert haben. Da ein Cuckoo-Filter nur wenige Prozent der Kapazität erreicht, verlangsamen sich die Geschwindigkeiten der Eingabemodule erheblich. Selbst dann wird nur die Geschwindigkeit der Einfügung verlangsamt, alle anderen Operationen sind konstante Durchschnittszeit.

  • Flexibilität. Bloom-Filter unterstützen nur Einfügen und enthält. Kuckuck-Filter unterstützen zusätzlich das Löschen und das begrenzte Zählen. Im Referenzdesign können Cuckoo-Filter bestimmen, wie oft ein Objekt bis zu sieben Mal eingefügt wurde. Bloom-Filter können nur Ja-Nein bestimmen. Cuckoo-Filter unterstützen auch das Löschen von eingefügten Elementen, was in vielen Anwendungsfällen im Vergleich zu Bloom ein großer Vorteil ist. Bei Verwendung von Bloom-Filtern ist es ziemlich normal, den Filter von Grund auf neu zu erstellen, wenn er "voll" ist (die geschätzte False-Positive-Rate überschreitet den Schwellenwert), da alte Objekte nicht gelöscht werden können. Beachten Sie, dass der Filter immer noch mit Cuckoo-Filtern erstellt wird Da dies in Abhängigkeit vom Anwendungsfall zu Problemen führen kann, ist dies in einigen Fällen sinnvoller, da Sie Elemente löschen können, die innerhalb der Filtergrenzen bleiben, anstatt neu zu erstellen.

  • Unterstützung. Kuckuckfilter sind neu und stabile Bibliotheken für viele Sprachen existieren einfach nicht.

Der größte Vorteil von Bloom-Filtern ist derSie haben in den meisten Sprachen eine ausgereiftere Bibliotheksunterstützung. Die Mathematik hinter Bloom-Filtern wird auch von Wissenschaftlern besser verstanden. Die meisten Eigenschaften von Cuckoo-Filtern wurden empirisch bestimmt, während Bloom-Filter eine solide numerische Basis haben. Dies schließt Cuckoo-Filter für Echtzeit- und kritische Systeme aus, die eine Überprüfung ihrer Leistung benötigen, obwohl experimentelle Beweise zeigen, dass Cuckoo-Filter in den meisten Fällen besser funktionieren.

Shameless Plug: Ich bin der Entwickler einer Cuckoo-Filterbibliothek für Java. KuckuckFilter4J . Es fehlt der Eimer Semi-Art in der verwendetPapier, so ist die Raumeffizienz etwas geringer als bei der Referenzimplementierung. In der Readme-Datei des Projekts habe ich Links zu anderen Implementierungen, die mir bekannt sind. Welche Struktur besser ist, hängt von Ihrem Anwendungsfall ab, aber vor allem davon, ob eine solide Cuckoo-Filterimplementierung für Ihre Sprache existiert.

Sie sollten sich unbedingt die Quelle ansehenbevor Sie einen Cuckoo / Bloom-Filter in der Produktion verwenden. Ich las verschiedene libs durch, bevor ich meine eigene schrieb ... viele von ihnen hatten Größenbeschränkungen aufgrund von 32-Bit-zugrundeliegenden Arrays oder offensichtlichen Leistungsproblemen. Die meisten hatten keine Tests. Google Guava Bloom Implementierung hatte bei weitem die beste Code-Qualität und Tests (und unterstützt 64-Bit-Array-Grenzen). Die einzigen Mängel mit Guava Bloom ist, dass es keine Option zur Verwendung einer sicheren Hash-Funktion und isn t Multithread.

In einem Produktionssystem möchten Sie vielleichtMulti-Threading für Geschwindigkeit. Die Antwort für Guavas Bloom ist, für jeden Thread einen anderen Filter zu erstellen und diese gelegentlich zu kombinieren. Da Cuckoo-Filter nicht kombiniert werden können, habe ich meiner Cuckoo-Filterbibliothek gleichzeitig Threading hinzugefügt. Die anderen, die ich kenne, sind nicht threadsicher oder nicht gleichzeitig.


8 für die Antwort № 2

Welche bevorzugen Sie, Wein oder Käse?

EIN Blütenfilter ist für wenn du hast begrenzter Platz, hohe Abfragekosten, und meist negative Abfragen.
In diesem Fall a Blütenfilter mit 8 Bits pro Schlüssel und 4 Hash-Funktionen gibt Ihnen 2,5% falsch positive Rate; Sie bearbeiten Anfragen fast 40 mal schneller als vorher, auf Kosten von 1 Byte pro Schlüssel.

Auf der anderen Seite, wenn einer der vorherige Bedingungen halten nicht, ein Hash-Tabelle, die als Cache fungiert macht Sinn, obwohl es offensichtlich dauert viel mehr als ein Byte pro Eintrag :-)

Sie können sogar die harten Fälle überspringen Kuckuck Hashing wenn es ein Cache ist. Das macht auch die Größenzunahme Probleme von Kuckuck Hashtabellen (oder etwas anderes als lineares Hash).


5 für die Antwort № 3

Kuckuck-Filter.

"Kuckuck Filter: Praktisch besser als Bloom." Bin Fan, David Andersen, Michael Kaminsky, Michael Mitzenmacher CoNext 2014. http://dx.doi.org/10.1145/2674005.2674994

Von einem der Autoren " Blog:

Lassen Sie mich einen Kuckuckfilter beschreiben und einige davonWenn Sie eine technische Diskussion vermeiden möchten, müssen Sie nur wissen, dass Kuckuck-Filter bei relativ großen Sets für die gleiche falsche Positivrate wie ein entsprechender Bloom-Filter weniger Platz benötigen als Bloom Filter, sind schneller auf Lookups (aber langsamer auf Insertionen / zu konstruieren), und erstaunlicherweise erlauben auch das Löschen von Schlüsseln (die Bloom-Filter nicht tun können). Wenn Sie Code anschauen wollen, gibt es sogar eine Github-Repository für Sie mit Code für Kuckucksfilter.


2 für die Antwort № 4

Ich bevorzuge Kuckuck Hashing. Ich bin vorsichtig mit den falschen positiven Ergebnissen, die bei höheren Füllfaktoren mit Bloomfiltern auftauchen können.
Habe Kuckuckshashing in einer Anwendung verwendet, in der wir sehr große Hashtabellen hatten und Probleme mit dem Speicherdruck hatten. Bitte beachten Sie meine eCollections-Bibliothek unter http://codeplex.com/ecollections für die Implementierung einer Variante des Kuckuckshashings.

Mit freundlichen Grüßen,


0 für die Antwort № 5

Wenn ich die falschen Positive tolerieren kann und Platz ist kritisch, verwende ich einen Bloom-Filter, weil es weniger Platz benötigt. Ansonsten benutze ich einen Hash.