So implementieren Sie eine umfassendere Golang-Version des Kuckucksfilters

                                                        O Das Folgende wird in der Tutorial-Kolumne „Go-Sprache“ vorgestellt, um mir eine umfassendere Golang-Version des Tuchtal-Vogelfilters vorzustellen. Ich hoffe, dass es den Freunden, die es brauchen, hilfreich sein wird!

„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

Beim Einfügen des Bloom-Filters wird der Hash berechnet und direkt in das Bit geschrieben. Nach der Berechnung des Kuckucksfilters kann es jedoch so aussehen, als ob der Fingerabdruck an der aktuellen Position gespeichert wurde. Der gespeicherte Fingerabdruck muss in den Kandidaten-Bucket geworfen werden. Je voller der Bucket ist, desto größer wird die Möglichkeit eines Konflikts und die Einfügezeit wird immer höher. Daher ist seine Einfügeleistung im Vergleich zum Bloom sehr schlecht Filter

• 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.
  Wenn wir die obige Schlussfolgerung mit $1,44log_2(1/r)$ für jedes Element des Bloom-Filters vergleichen, können wir feststellen, dass der Kuckucksfilterraum kleiner ist, wenn die halbe Sortierung aktiviert ist und r<0,03 nicht aktiviert, Sortierung, es verschlechtert sich auf etwa r<0,003.

  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!