1. Einführung
Kunde: Existiert dieser Schlüssel?
Server: existiert nicht/weiß nicht
Der Bloom-Filter ist eine relativ clevere probabilistische Datenstruktur, und sein Wesen ist eine Datenstruktur. Es bietet effizientes Einfügen und Abfragen. Wenn wir jedoch mithilfe eines Bloom-Filters überprüfen möchten, ob ein Schlüssel in einer bestimmten Struktur vorhanden ist, können wir schnell lernen, dass „dieser Schlüssel nicht existieren darf oder existieren kann“. Im Vergleich zu herkömmlichen Datenstrukturen wie List, Set und Map ist es effizienter und nimmt weniger Platz ein, aber die zurückgegebenen Ergebnisse sind probabilistisch und ungenau.
Bloom-Filter werden nur zum Testen der Mitgliedschaft in einer Sammlung verwendet. Das klassische Beispiel eines Bloom-Filters besteht darin, die Effizienz zu verbessern, indem teure Suchvorgänge auf der Festplatte (oder im Netzwerk) nach nicht vorhandenen Schlüsseln reduziert werden. Wie wir sehen können, kann ein Bloom-Filter in der konstanten Zeit von O(k) nach einem Schlüssel suchen, wobei k die Anzahl der Hash-Funktionen ist, und die Prüfung auf das Nichtvorhandensein eines Schlüssels erfolgt sehr schnell.
2. Anwendungsszenario
2.1 Cache-Penetration
Um die Zugriffseffizienz zu verbessern, werden wir einige Daten in den Redis-Cache legen. Bei der Datenabfrage können Sie zunächst die Daten aus dem Cache abrufen, ohne die Datenbank zu lesen. Dadurch kann die Leistung effektiv verbessert werden.
Beim Abfragen von Daten müssen Sie zunächst feststellen, ob sich Daten im Cache befinden. Wenn Daten vorhanden sind, rufen Sie die Daten direkt aus dem Cache ab.
Aber wenn keine Daten vorhanden sind, müssen Sie die Daten aus der Datenbank abrufen und sie dann in den Cache legen. Wenn eine große Anzahl von Zugriffen nicht auf den Cache zugreifen kann, wird die Datenbank einem größeren Druck ausgesetzt, was zum Absturz der Datenbank führt. Mithilfe von Bloom-Filtern können Sie beim Zugriff auf einen nicht vorhandenen Cache schnell zurückkehren, um einen Cache- oder DB-Absturz zu vermeiden.
2.2 Bestimmen Sie, ob bestimmte Daten in massiven Daten vorhanden sind.
HBase speichert eine sehr große Datenmenge, um festzustellen, ob bestimmte ROWKEYS oder eine bestimmte Spalte vorhanden sind Der Filter kann schnell ermitteln, ob bestimmte Daten vorhanden sind. Aber es gibt eine gewisse Fehleinschätzungsquote. Wenn ein Schlüssel jedoch nicht existiert, muss er korrekt sein.
3. Probleme mit HashMap
Um festzustellen, ob ein Element vorhanden ist, ist die Effizienz der Verwendung von HashMap sehr hoch. HashMap kann eine konstante Zeitkomplexität von O(1) erreichen, indem Werte HashMap-Schlüsseln zugeordnet werden.
Wenn jedoch die gespeicherte Datenmenge sehr groß ist (z. B. Hunderte Millionen Daten), verbraucht HashMap sehr viel Speicher. Und es ist einfach unmöglich, riesige Datenmengen auf einmal in den Speicher einzulesen.
4. Verstehen Sie das Funktionsprinzip des Bloom-Filters
:
Bloom-Filter Gerät ist ein Bit-Array oder ein Bit-Binärvektor
Die Elemente in diesem Array sind entweder 0 oder 1
k Hash-Funktionen sind unabhängig voneinander und jede Hash-Funktion Das berechnete Ergebnis modulo der Länge m der Array und setzt ein Bit auf 1 (blaue Zelle)
Wir setzen die Zellen für jeden Schlüssel auf diese Weise, nämlich „Bloom-Filtergerät“
5. Elemente basierend auf Bloom abfragen Filter
Angenommen, ein Schlüssel ist eingegeben, verwenden wir die vorherigen k-Hash-Funktionen, um den Hash zu finden und k-Werte zu erhalten#🎜 🎜# Bestimmen Sie, ob die k-Werte alle blau sind. Wenn einer nicht vorhanden ist blau, dann darf der Schlüssel nicht existieren
Wenn alle blau sind, dann kann der Schlüssel existieren (Bloom-Filter führt zu Fehleinschätzungen)
Denn wenn es viele Eingabeobjekte gibt und die Sammlung relativ klein ist, sind die meisten Positionen in Wenn ein bestimmter Schlüssel blau markiert wird, wird zu diesem Zeitpunkt fälschlicherweise angenommen, dass sich der Schlüssel in der Sammlung befindet gelöscht werden?
Herkömmliche Bloom-Filter unterstützen keine Löschvorgänge. Allerdings kann eine Variante namens Counting Bloom-Filter verwendet werden, um zu testen, ob die Anzahl der Elementzählungen absolut unter einem bestimmten Schwellenwert liegt, und sie unterstützt das Löschen von Elementen. Das Prinzip und die Umsetzung des Artikels Counting Bloom Filter sind ausführlich beschrieben und können ausführlich gelesen werden.
7. So wählen Sie die Anzahl der Hash-Funktionen und die Länge des Bloom-Filters aus
Wenn der Bloom-Filter zu klein ist, sind natürlich bald alle Bits 1 . Dann wird bei der Abfrage eines beliebigen Werts „möglicherweise vorhanden“ zurückgegeben, was den Zweck der Filterung zunichte macht. Mit zunehmender Länge eines Bloom-Filters nimmt seine Falsch-Positiv-Rate ab.
Darüber hinaus muss auch die Anzahl der Hash-Funktionen gewichtet werden. Je größer die Anzahl, desto schneller wird die Bloom-Filter-Bitposition auf 1 gesetzt und desto geringer ist die Effizienz des Bloom-Filters Wenn es zu wenig ist, ist unsere Fehlalarmrate hoch.
Wie aus der obigen Abbildung ersichtlich ist, führt eine Erhöhung der Anzahl der Hash-Funktionen k zu einer erheblichen Reduzierung der Fehlerrate p.
Keine Sorge, wir müssen tatsächlich die Werte von m und k bestätigen. Nun, wenn wir die Fehlertoleranz p und die Anzahl der Elemente n angeben, können diese Parameter mit der folgenden Formel berechnet werden:
Wir können Fehlalarme basierend auf der Größe des Filters m, der Anzahl der Hash-Funktionen k und dem berechnen Anzahl der eingefügten Elemente n Die Rate p, die Formel lautet wie folgt: Wie wählt man auf der Grundlage des oben Gesagten die für das Unternehmen geeigneten k- und m-Werte aus?
Formel:
k ist die Anzahl der Hash-Funktionen, m ist die Bloom-Filterlänge, n ist die Anzahl der eingefügten Elemente und p ist die Falsch-Positiv-Rate.
Wie man diese Formel herleitet, wird in dem Artikel behandelt, den ich auf Zhihu veröffentlicht habe. Wenn Sie interessiert sind, können Sie ihn einfach lesen.
Außerdem möchte ich hier noch einen weiteren wichtigen Punkt erwähnen. Da der einzige Zweck der Verwendung eines Bloom-Filters darin besteht, schneller zu suchen, können wir keine langsame Hash-Funktion verwenden, oder? Kryptografische Hash-Funktionen (z. B. Sha-1, MD5) sind für Bloom-Filter keine gute Wahl, da sie etwas langsam sind. Bessere Optionen für schnellere Hash-Funktionsimplementierungen sind Murmur, Fnv-Familien-Hashing, Jenkins-Hashing und HashMix.
Weitere Anwendungsszenarien
Im gegebenen Beispiel haben Sie gesehen, dass wir damit den Benutzer warnen können, wenn er ein schwaches Passwort eingibt.
Sie können den Bloom-Filter verwenden, um zu verhindern, dass Benutzer schädliche Websites besuchen.
Anstatt eine SQL-Datenbank abzufragen, um zu prüfen, ob ein Benutzer mit einer bestimmten E-Mail-Adresse existiert, können Sie zunächst den Bloom Bloom-Filter verwenden, um eine kostengünstige Suchprüfung durchzuführen. Wenn die E-Mail nicht existiert, großartig! Wenn es vorhanden ist, müssen Sie möglicherweise zusätzliche Abfragen an die Datenbank durchführen. Auf die gleiche Weise können Sie auch nach „Benutzername bereits vergeben“ suchen.
Sie können einen Bloom-Filter basierend auf der IP-Adresse Ihrer Website-Besucher verwenden, um zu überprüfen, ob die Benutzer Ihrer Website „wiederkehrende Benutzer“ oder „neue Benutzer“ sind. Ein paar Fehlalarme von „wiederkehrenden Benutzern“ können Ihnen nicht schaden, oder?
Sie können auch eine Rechtschreibprüfung durchführen, indem Sie Wörterbuchwörter mithilfe von Bloom-Filtern verfolgen.
Das obige ist der detaillierte Inhalt vonWie lautet die Algorithmusformel für die Redis-Bloom-Filtergröße?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
