So implementieren Sie den Redis BloomFilter Bloom-Filter

Bloom-Filter-Konzept

Ein Mann namens Bloom schlug 1970 den Bloom-Filter (englischer Name: Bloom Filter) vor. Es handelt sich tatsächlich um einen langen binären Vektor und eine Reihe zufälliger Zuordnungsfunktionen. Mithilfe von Bloom-Filtern lässt sich ermitteln, ob sich ein Element in einer Sammlung befindet. Sein Vorteil besteht darin, dass die Speicherplatzeffizienz und die Abfragezeit viel höher sind als beim allgemeinen Algorithmus, sein Nachteil besteht jedoch darin, dass er eine gewisse Fehlerkennungsrate und Schwierigkeiten beim Löschen aufweist.

Bloom-Filter-Prinzip

Das Prinzip des Bloom-Filters besteht darin, dass beim Hinzufügen eines Elements zur Menge das Element durch K-Hash-Funktionen in K Punkte in einem Bit-Array abgebildet und auf 1 gesetzt wird. Beim Abrufen müssen wir nur prüfen, ob diese Punkte alle 1 sind, um (ungefähr) zu wissen, ob sie in der Menge enthalten sind: Wenn einer dieser Punkte 0 hat, darf das überprüfte Element nicht vorhanden sein, wenn sie alle 1 sind. dann das überprüfte Element Höchstwahrscheinlich. Dies ist die Grundidee des Bloom-Filters.

Der Unterschied zwischen Bloom Filter und Single-Hash-Funktion Bit-Map besteht darin, dass Bloom Filter k Hash-Funktionen verwendet und jede Zeichenfolge k Bits entspricht. Dadurch wird die Wahrscheinlichkeit von Konflikten verringert.

Cache-Penetration , zum Beispiel hat die ID der Datenbank jetzt: 1, 2, 3

Dann verwenden Sie ID: 1. Als Beispiel hat er nach dreimaligem Hashing im obigen Bild die drei Stellen, an denen der ursprüngliche Wert 0 war, in geändert 1

Wenn die Daten zur Abfrage eingehen und der Wert der ID 1 ist, hashe ich 1 dreimal und stelle fest, dass die Werte der drei Hashes genau mit den drei Positionen oben übereinstimmen, was bewiesen werden kann dass es 1 im Filter gibt und umgekehrt. Wenn es anders ist, bedeutet das, dass es nicht existiert. Wo ist dann das Anwendungsszenario? Im Allgemeinen verwenden wir es, um einen Cache-Ausfall zu verhindern. Vereinfacht gesagt beginnt die ID Ihrer Datenbank mit 1 und erhöht sich dann von selbst. Dann weiß ich, dass Ihre Schnittstelle anhand der ID abgefragt wird, daher verwende ich für die Abfrage negative Zahlen. Zu diesem Zeitpunkt habe ich festgestellt, dass sich keine derartigen Daten im Cache befanden, und ich habe in der Datenbank nachgesehen und nichts gefunden. Eine Anfrage sieht so aus: Was ist mit 100, 1.000 oder 10.000? Ihre Datenbank ist im Grunde nicht in der Lage, damit umzugehen. Wenn Sie feststellen, dass keine solchen Daten vorhanden sind, ist es nicht besser, sie einfach zurückzugeben das ist leer?

Dieses Ding funktioniert so gut, was sind also die Nachteile? Ja, sehen wir uns weiter die Mängel des Bloom-Filters an. Der Grund, warum Bloom-Filter zeitlich und räumlich effizienter sein können, liegt darin, dass die Genauigkeit der Beurteilung und die Bequemlichkeit des Löschens beeinträchtigt werden. Obwohl der Container möglicherweise nicht enthalten ist Elemente, die gefunden werden sollten, aber aufgrund der Hash-Operation sind die Werte dieser Elemente in k Hash-Positionen alle 1, sodass es zu Fehleinschätzungen kommen kann. Durch die Einrichtung einer Whitelist zum Speichern von Elementen, die möglicherweise falsch eingeschätzt werden, kann die Fehleinschätzungsrate reduziert werden, wenn der Bloom-Filter eine Blacklist speichert.

Löschen ist schwierig. Ein im Container platziertes Element wird an den k-Positionen des Bit-Arrays auf 1 abgebildet. Beim Löschen kann es nicht einfach direkt auf 0 gesetzt werden, da dies die Beurteilung anderer Elemente beeinflussen kann. Sie können den Counting Bloom Filter

FAQ

1 verwenden. Warum mehrere Hash-Funktionen verwenden?

Wenn nur eine Hash-Funktion verwendet wird, kommt es häufig zu Konflikten beim Hash selbst. Wenn beispielsweise für ein Array mit einer Länge von 100 nur eine Hash-Funktion verwendet wird, beträgt die Konfliktwahrscheinlichkeit beim Hinzufügen des zweiten Elements nach dem Hinzufügen eines Elements 1 % und die Konfliktwahrscheinlichkeit beim Hinzufügen des dritten Elements 2 %... Wenn jedoch zwei Elemente verwendet werden, beträgt die Kollisionswahrscheinlichkeit 1 %. Nach dem Hinzufügen eines Elements verringert sich die Konfliktwahrscheinlichkeit beim Hinzufügen des zweiten Elements auf 4 zu 10.000 (vier mögliche Konfliktsituationen). Die Gesamtzahl der Situationen beträgt 100 x 100

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Redis BloomFilter Bloom-Filter. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!