So implementieren Sie eine umfassendere Golang-Version des Kuckucksfilters-Golang-php.cn

„Bestimmen, ob ein Wert in einer großen Menge enthalten ist“ (im Folgenden gemeinsam als Mengenzugehörigkeitstest bezeichnet) ist ein häufiges Datenverarbeitungsproblem. Wenn in der Vergangenheit eine bestimmte Falsch-Positiv-Rate zulässig ist, sind Bloom-Filter die erste Wahl, aber jetzt haben wir eine bessere Wahl: Kuckucksfilter. Neuere Unternehmen müssen Filter verwenden. Nach der Suche habe ich festgestellt, dass der Kuckucksfilter in unserem Szenario kostengünstiger und besser ist als der Bloom-Filter. Um die endgültige Technologieauswahl zu bestimmen, habe ich später, als ich mich für die Verwendung des Kuckucksfilters entschieden habe, festgestellt, dass es derzeit fast keine umfassenden Implementierungen von Golang gibt Fehler und Die Speicherplatznutzung wurde nicht maximiert, daher habe ich eine Version der Golang-Bibliothek unter Bezugnahme auf das Originalpapier und die ursprüngliche C++-Implementierung des Papiers transplantiert und optimiert. Die Details finden Sie unten. Die Codeadresse finden Sie hier. Willkommen zum Starren, Verwenden, Mitwirken und Debuggen: github.com/linvon/cuckoo-filter

Kuckucksfilter

Es gibt viele Einführungsartikel zum Kuckucksfilter im Internet, hier nicht mehr Einführung: Erwähnen Sie einfach die Hauptpunkte, um den folgenden Inhalt vorzustellen.

ist ein Filter, der auf dem Cuckoo-Hash-Algorithmus basiert. Es handelt sich im Wesentlichen um eine Cuckoo-Hash-Tabelle, die den Hash-Wert des Speicherelements speichert. Wenn Sie Bloom-Filter verstehen, sollten Sie wissen, dass das Prinzip von Bloom-Filtern darin besteht, mehrere Hashing-Methoden zu verwenden, um verschiedene Hashes von Speicherelementen Bit-Arrays zuzuordnen, und diese Bits bei der Abfrage zu überprüfen, um festzustellen, ob sie vorhanden sind.

Der Kuckucksfilter hasht das Speicherelement, entnimmt eine bestimmte Anzahl von Ziffern aus seinem Hash-Wert und speichert sie in einem Array. Bei der Abfrage stellt er fest, ob ein Hash gleicher Ziffern im Array vorhanden ist.

Warum Cuckoo Filter wählen? Sie speichern auch Hash-Werte, im Wesentlichen Multi-Bit-Hashes. Warum ist der Kuckucksfilter besser?

Erstens kann der Cuckoo-Hash-Tisch mehr Platz sparen, da er kompakter ist.

Der zweite Grund liegt darin, dass der Bloom-Filter beim Abfragen verschiedene Hash-Funktionen für mehrere Hashes verwendet, während der Cuckoo-Filter nur einen Hash benötigt, sodass die Abfrageeffizienz sehr hoch ist.

Der dritte Grund ist, dass der Cuckoo-Filter unterstützt wird Löschen, aber der Bloom-Filter unterstützt das Löschen nicht

Die Vorteile sind da, aber was sind die Nachteile? Im Vergleich zum Bloom-Filter verwendet der Cuckoo-Filter eine Backup-Kandidaten-Bucket-Lösung. Der Kandidaten-Bucket und der bevorzugte Bucket können durch XOR-Verknüpfung über die Position und den Speicherwert ermittelt werden. Diese Entsprechung erfordert, dass die Größe des Buckets exponentiell sein muss von 2
Einfügen doppelter Elemente: Stoff Der Long-Filter hat beim Einfügen doppelter Elemente keine Auswirkung, er setzt lediglich die vorhandenen Bits zurück. Der Kuckucksfilter verwirft vorhandene Werte, daher gibt es eine Obergrenze für das Einfügen wiederholter Elemente. Das Löschen des Kuckucksfilters ist nicht perfekt: Beim wiederholten Einfügen gelten die oben genannten Einschränkungen, und beim Löschen treten auch damit verbundene Probleme auf. : Das Löschen ist nur dann perfekt, wenn derselbe Hash-Wert einmal eingefügt wird. Wenn das Element gelöscht wird, ohne dass es eingefügt wurde, kann es zu einem versehentlichen Löschen kommen. Dies ist der gleiche Grund wie die Falsch-Positiv-Rate, wenn das Element mehrmals eingefügt wird Es wird nur ein Wert gelöscht. Sie müssen wissen, wie oft das Element eingefügt wurde, bevor es gelöscht werden kann, oder den Löschvorgang in einer Schleife ausführen, bis der Löschvorgang fehlschlägt. Lassen Sie uns sie noch einmal zusammenfassen. Bei dieser Art von Satzzugehörigkeitstestproblemen sind in den meisten Fällen mehr Lesevorgänge und weniger Schreibvorgänge erforderlich, und das Löschen des Kuckucksfilters ist zwar nicht perfekt, aber es gibt auch bessere Abfragen und eine bessere Speichereffizienz Es sollte gesagt werden, dass es in den meisten Fällen eine kostengünstigere Wahl ist.

Praktische Anleitung

Detaillierte Implementierung

Lassen Sie uns zunächst über das Konzept des Kuckucksfilters sprechen. Jeder Bucket speichert den Wert des eingefügten Elements nach der Hash-Berechnung Anzahl der Ziffern wird gespeichert.

Der Filter enthält n Eimer und die Anzahl der Eimer wird basierend auf der Anzahl der zu lagernden Artikel berechnet. Mithilfe des Hash-Algorithmus können wir berechnen, in welchem Bucket ein Element gespeichert werden soll. Darüber hinaus kann jeder zusätzliche Hash-Algorithmus einen Kandidaten-Bucket für ein Element generieren. Bei wiederholten Einfügungen wird das aktuell gespeicherte Element in den Kandidaten-Bucket verschoben . Geh rein. Theoretisch ist die Speicherplatzauslastung umso höher, je mehr Hash-Algorithmen vorhanden sind. In tatsächlichen Tests wurden jedoch k=2 Hash-Funktionen verwendet, um eine Auslastungsrate von 98 % zu erreichen.

Jeder Bucket speichert mehrere Fingerabdrücke. Dies hängt von der Größe des Buckets ab. Verschiedene Fingerabdrücke können demselben Bucket zugeordnet werden. Je größer der Bucket, desto höher ist die Speicherplatzauslastung, aber gleichzeitig werden bei jeder Abfrage mehr Fingerabdrücke im selben Bucket gescannt, sodass die Wahrscheinlichkeit, dass falsch positive Ergebnisse generiert werden, zu diesem Zeitpunkt höher ist Anzahl der gespeicherten Fingerabdrücke, um die Konfliktrate zu reduzieren.

In dem Papier werden mehrere Parameter erwähnt, die zur Implementierung des Kuckucksfilters erforderlich sind, hauptsächlich
- Anzahl der Hash-Funktionen (k): Anzahl der Hashes, 2 reicht aus
- Bucket-Größe (b): Wie viele Fingerabdrücke werden darin gespeichert Jeder Eimer
- Fingerabdruckgröße (f): Wie viele Bits des Hash-Werts jedes Fingerabdruckspeicherschlüssels
Lesen Sie den Artikel im Detail. In Kapitel 5 stützt sich der Autor auf experimentelle Daten, um uns zu sagen, wie wir den am besten geeigneten auswählen können Zu den Konstruktionsparametern können wir folgende Schlussfolgerung ziehen
- Der Filter kann nicht zu 100 % gefüllt werden, es gibt einen maximalen Belastungsfaktor α, dann beträgt der jedem Artikel zugewiesene Speicherplatz f/α
- Bei Beibehaltung der Gesamtgröße von Der Filter ändert sich nicht: Je größer der Bucket, desto höher der Auslastungsfaktor, d Bei gleicher Falsch-Positiv-Rate gilt: Je größer der Bucket, desto höher der Auslastungsfaktor.
Gemäß der obigen theoretischen Grundlage sind die relevanten experimentellen Daten:
- Wenn k=2 Hash-Funktionen verwendet werden Wenn die Bucket-Größe b = 1 ist (d. h. direkte Zuordnung der Hash-Tabelle), beträgt der Auslastungsfaktor α 50 %, bei Verwendung der Bucket-Größe b = 2, 4 oder 8 erhöht er sich jedoch auf 84 %, 95 % bzw. 98 %
- Um die Falsch-Positiv-Rate r sicherzustellen, muss $2b/2 ^fleq r$ sichergestellt werden, dann beträgt die Größe des Fingerabdrucks f ungefähr $f ≥ log_2(2b/r)=log_2( 1/r) + log_2(2b)$, dann betragen die amortisierten Anschaffungskosten jedes Artikels $C ≤ [log_2(1 /r) + log_2(2b)]/α$
- Die experimentellen Daten zeigen, dass bei r>0,002. Zwei Einträge pro Bucket führen zu etwas besseren Ergebnissen als die Verwendung von vier Einträgen pro Bucket. Wenn r auf 0,00001 0,002 ist, können Sie b = 4 verwenden, um halbsortierte Buckets zu aktivieren. Anschließend können wir die Größe von f berechnen, die wir benötigen, um die angestrebte Falsch-Positiv-Rate basierend auf b zu erreichen, sodass alle Filterparameter bestimmt sind.
Einige erweiterte Erklärungen
Optimierung des Hash-Algorithmus
Obwohl wir angegeben haben, dass zwei Hash-Algorithmen erforderlich sind, reicht es für uns in der tatsächlichen Implementierung aus, einen Hash-Algorithmus zu verwenden, da dieser im Artikel als erwähnt wird Bei einer alternativen Bucket-Berechnungsmethode kann der zweite Hash-Wert durch XOR-Verknüpfung des ersten Hash-Werts mit dem an diesem Ort gespeicherten Fingerabdruck berechnet werden. Wenn Sie befürchten, dass wir den Hash des Fingerabdrucks und den Hash des Standorts immer noch separat berechnen müssen, können wir einfach einen Algorithmus verwenden, um einen 64-Bit-Hash zu erstellen, wobei die hohen 32 Bit zur Berechnung des Standorts und die niedrigen verwendet werden Zur Berechnung des Fingerabdrucks werden 32 Bit verwendet.
Warum kann ein halbsortierter Eimer nur bei b=4 verwendet werden?
Die Essenz der Halbsortierung besteht darin, vier Ziffern jedes Fingerabdrucks zu erfassen. Die vierstellige Speicherung von b-Fingerabdrücken kann als b-Hexadezimalzahl ausgedrückt werden In dieser Reihenfolge kann die entsprechende Anordnung gefunden werden, indem ihre Position indiziert wird, um den tatsächlich gespeicherten Wert zu erhalten. Wir können die Anzahl aller Situationstypen mit der folgenden Funktion berechnen
```
func getNum(base, k, b, f int, cnt *int) {
    for i := base; i < 1<> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    n |= n >> 32
    n++
    return uint(n)}func getNumOfKindAndBit(b, f int) {
    cnt := 0
    getNum(0, 0, b, f, &cnt)
    fmt.Printf("Num of kinds: %v, Num of needed bits: %v\n", cnt, math.Log2(float64(getNextPow2(uint64(cnt)))))}Wenn b = 4, gibt es insgesamt 3786 Permutationen, was weniger als 4096 ist. Das heißt, 12 Bits können zum Speichern aller Permutationsindizes verwendet werden Wenn alle Fingerabdrücke direkt gespeichert werden, werden 4 x 4 = 16 Bit benötigt, wodurch 4 Bit eingespart werden, d. h. für jeden Fingerabdruck wird ein Bit gespeichert. 
Es kann festgestellt werden, dass, wenn b 2 ist, die gleiche Anzahl gespeicherter Bits erforderlich ist, um die Halbsortierung zu aktivieren, was bedeutungslos ist. Wenn b zu groß ist, wird auch der zu speichernde Index schnell erweitert, was zu einem großen Verlust an Abfrageleistung führt. Daher ist b = 4 die kostengünstigste Option. 
Darüber hinaus liegt die Wahl der Codierung zum Speichern vierstelliger Fingerabdrücke darin begründet, dass sie durch ein Hexadezimalsystem dargestellt werden kann, was für die Speicherung praktisch ist. 
Parameterauswahl bei Verwendung der Halbsortierung
Bei Verwendung der Halbsortierung sollten Sie dies tun Stellen Sie sicher, dass $ceil(b (f-1)/8)f/8)$, andernfalls ist der von der Halbsortierung belegte Platz derselbe 

Auswahl der Filtergröße
Der Gesamteimer Die Größe des Filters muss Exponentiell mal 2 sein. Versuchen Sie daher beim Festlegen der Filtergröße, $size/α ~=(<) 2^n$ zu erfüllen. Größe ist die Datenmenge, die ein Filter speichern soll, und Sie sollten bei Bedarf einen kleineren Wert wählen. Verwenden Sie mehrere Filter, um den Zieleffekt zu erzielen. 

Golang-Implementierung stellte fest, dass die vorhandenen Implementierungen einige Mängel aufweisen: 
Die meisten Bibliotheken haben feste b und f, das heißt, die Falsch-Positiv-Rate ist ebenfalls behoben und die Anpassungsfähigkeit ist nicht gut
Alle Bibliotheken f sind in Bytes und können nur Wenn die Anpassung in Vielfachen von 8 ausgedrückt wird, ist es unpraktisch, die Falsch-Positiv-Rate anzupassen. 
Alle Bibliotheken implementieren keine halbsortierten Buckets, was die Vorteile im Vergleich zu Bloom-Filtern erheblich verringert. Da Ihre eigenen Szenarien mehr Platz erfordern und angepasst werden müssen Falsch-Positiv-Rate, daher wurde die C++-Implementierung des Originalpapiers übertragen und einige Optimierungen vorgenommen, hauptsächlich einschließlich 

 Unterstützung für die Anpassung von Parametern 

 Unterstützung für halbsortierte Buckets 

 komprimierter Raum in ein kompaktes Bit Array und gespeicherte Fingerabdrücke Stück für Stück 
 
Unterstützt binäre Serialisierung
```

Das obige ist der detaillierte Inhalt vonSo implementieren Sie eine umfassendere Golang-Version des Kuckucksfilters. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!