Was ist ein Bloomfilter? Wie verwende ich es in Redis?

Der Bloom-Filter ist eine magische Datenstruktur. Dieser Artikel vermittelt Ihnen ein detailliertes Verständnis der Bloom-Filter und stellt vor, wie Sie Bloom-Filter in Redis verwenden.

Was ist „Bloom-Filter“

Bloom-Filter ist eine magische Datenstruktur, kann verwendet werden, um zu bestimmen, ob sich ein Element in einer Menge befindet . Eine sehr häufig verwendete Funktion ist das Entfernen von Duplikaten. Eine häufige Anforderung bei Crawlern: Es gibt Tausende von Ziel-Website-URLs. Wie kann festgestellt werden, ob ein Crawler eine bestimmte URL favorisiert hat? Einfach ausgedrückt: Jedes Mal, wenn der Crawler eine URL sammelt, kann er die URL in der Datenbank speichern. Jedes Mal, wenn eine neue URL eintrifft, fragt er in der Datenbank ab, ob zuvor darauf zugegriffen wurde. [Verwandte Empfehlung: Redis-Video-Tutorial]

select id from table where url = 'https://jaychen.cc'

Da der Crawler jedoch immer mehr URLs crawlt, muss vor jeder Anfrage einmal auf die Datenbank zugegriffen werden, und die SQL-Abfrageeffizienz für solche Zeichenfolgen ist nicht hoch. Zusätzlich zur Datenbank kann diese Anforderung auch durch die Verwendung der festgelegten Struktur von Redis erfüllt werden, und ihre Leistung ist besser als die der Datenbank. Aber Redis hat auch ein Problem: Es verbraucht zu viel Speicher. Zu diesem Zeitpunkt erscheint der Bloom-Filter sehr horizontal: Lassen Sie mich diese Frage beantworten.

Im Vergleich zu Datenbanken und Redis können durch die Verwendung von Bloom-Filtern Leistungs- und Speichernutzungsprobleme effektiv vermieden werden.

Der Bloom-Filter ist im Wesentlichen ein Bit-Array Ein Bit-Array bedeutet, dass jedes Element des Arrays nur 1 Bit belegt. Jedes Element kann nur 0 oder 1 sein. Auf diese Weise nimmt die Anwendung eines Bitarrays mit 10.000 Elementen nur 10.000/8 = 1.250 B Speicherplatz ein. Der Bloom-Filter verfügt neben einem Bit-Array auch über K-Hash-Funktionen. Wenn ein Element zum Bloom-Filter hinzugefügt wird, werden die folgenden Vorgänge ausgeführt:

• Verwenden Sie K-Hash-Funktionen, um K-Berechnungen für den Elementwert durchzuführen und K-Hash-Werte zu erhalten.
• Setzen Sie entsprechend dem erhaltenen Hash-Wert den entsprechenden Indexwert im Bit-Array auf 1.

Angenommen, der Bloom-Filter verfügt über drei Hash-Funktionen: f1, f2, f3 und ein Bit-Array arr. Jetzt müssen wir https://jaychen.cc in den Bloom-Filter einfügen: arr。现在要把 https://jaychen.cc 插入布隆过滤器中：

• 对值进行三次哈希计算，得到三个值 n1, n2, n3。
• 把位数组中三个元素 arr[n1], arr[n2], arr[3] 置为 1。

当要判断一个值是否在布隆过滤器中，对元素再次进行哈希计算，得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

看不懂文字看下面的灵魂画手的图解释

看了上面的说明，必然会提出一个问题：当插入的元素原来越多，位数组中被置为 1 的位置就越多，当一个不在布隆过滤器中的元素，经过哈希计算之后，得到的值在位数组中查询，有可能这些位置也都被置为 1。这样一个不存在布隆过滤器中的也有可能被误判成在布隆过滤器中。但是如果布隆过滤器判断说一个元素不在布隆过滤器中，那么这个值就一定不在布隆过滤器中。简单来说：

• 布隆过滤器说某个元素在，可能会被误判。
• 布隆过滤器说某个元素不在，那么一定不在。

这个布隆过滤器的缺陷放到上面爬虫的需求中，可能存在某些没有访问过的 URL 可能会被误判为访问过，但是如果是访问过的 URL 一定不会被误判为没访问过。

Redis 中的布隆过滤器

redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 module 来使用 redis 中的布隆过滤器。但是这不是最简单的方式，使用 docker 可以直接在 redis 中体验布隆过滤器。

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom
> docker exec -it bloomfilter redis-cli

redis 布隆过滤器主要就两个命令：

• bf.add 添加元素到布隆过滤器中：bf.add urls https://jaychen.cc。
• bf.exists 判断某个元素是否在过滤器中：bf.exists urls https://jaychen.cc

Hashen Sie den Wert dreimal, um drei Werte n1, n2, n3 zu erhalten.

Setzen Sie die drei Elemente arr[n1], arr[n2], arr[3] im Bitarray auf 1. 🎜🎜🎜Wenn Sie feststellen möchten, ob sich ein Wert im Bloom-Filter befindet, führen Sie erneut eine Hash-Berechnung für das Element durch. Bestimmen Sie nach Erhalt des Werts, ob jedes Element im Bit-Array 1 ist. Wenn alle Werte 1 sind , dann geben Sie diesen Wert an Wenn im Bloom-Filter ein anderer Wert als 1 vorhanden ist, bedeutet dies, dass sich das Element nicht im Bloom-Filter befindet. 🎜🎜🎜Wenn Sie den Text nicht verstehen können, schauen Sie sich bitte die Erklärung des Seelenmalers unten an🎜🎜🎜🎜🎜Nach dem Lesen der obigen Erklärung stellt sich unweigerlich die Frage: Je mehr Elemente eingefügt werden, desto mehr Positionen werden im Bit-Array festgelegt 1. Wenn für ein Element, das sich nicht im Bloom-Filter befindet, nach der Hash-Berechnung der erhaltene Wert im Bit-Array nachgeschlagen wird, ist es möglich, dass diese Positionen auch auf 1 gesetzt sind. Ein solches Objekt, das im Bloom-Filter nicht vorhanden ist, kann auch fälschlicherweise als im Bloom-Filter befindlich eingeschätzt werden. Wenn der Bloom-Filter jedoch feststellt, dass ein Element nicht im Bloom-Filter enthalten ist, darf dieser Wert nicht im Bloom-Filter enthalten sein. Einfach ausgedrückt: 🎜🎜🎜Wenn der Bloom-Filter sagt, dass ein bestimmtes Element vorhanden ist, kann es sein, dass es falsch eingeschätzt wird. 🎜🎜Wenn der Bloom-Filter sagt, dass ein Element nicht vorhanden ist, dann darf es nicht vorhanden sein. 🎜🎜🎜Der Fehler dieses Bloom-Filters liegt in den oben genannten Anforderungen des Crawlers. Es kann sein, dass einige nicht besuchte URLs fälschlicherweise als besuchte URLs eingestuft werden, aber wenn es sich um besuchte URLs handelt, werden sie definitiv nicht als besuchte URLs eingestuft. t besucht. 🎜

🎜Bloom-Filter in Redis🎜🎜🎜Die von Redis hinzugefügte Modulfunktion kann in Form eines Moduls zu Redis hinzugefügt werden, sodass Sie Redis 4.0 oder höher verwenden können Sie können den Bloom-Filter in Redis verwenden, indem Sie module🎜 laden. Dies ist jedoch nicht die einfachste Möglichkeit, Bloom-Filter direkt in Redis zu erleben. 🎜

bf.reserve urls 0.01 100

🎜redis Bloom-Filter hat hauptsächlich zwei Befehle: 🎜🎜🎜bf.add Elemente zum Bloom-Filter hinzufügen: bf.add urls https://jaychen.cc . 🎜🎜bf.exists Bestimmt, ob ein Element im Filter ist: bf.exists urls https://jaychen.cc. 🎜🎜🎜Wie oben erwähnt, gibt es Fehleinschätzungen im Bloom-Filter. In Redis gibt es zwei Werte, die die Genauigkeit des Bloom-Filters bestimmen: 🎜

• error_rate：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。
• initial_size：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。

redis 中有一个命令可以来设置这两个值：

bf.reserve urls 0.01 100

三个参数的含义：

• 第一个值是过滤器的名字。
• 第二个值为 error_rate 的值。
• 第三个值为 initial_size 的值。

使用这个命令要注意一点：执行这个命令之前过滤器的名字应该不存在，如果执行之前就存在会报错：(error) ERR item exists

更多编程相关知识，请访问：编程入门！！

Das obige ist der detaillierte Inhalt vonWas ist ein Bloomfilter? Wie verwende ich es in Redis?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!