Фильтры Блума в Redis

Redis задняя часть база данных рептилия

Оригинальная ссылка:Джей Чен, Цао Цао/Redis/2018/…

Автор: Джей Чен

Что такое «фильтр Блума»

Фильтр Блума — это волшебная структура данных,Может использоваться для определения того, находится ли элемент в наборе. Очень распространенной функцией является использованиедедупликация. Общее требование в Crawlers: есть тысячи целевых URL-адресов веб-сайтов. Как судить, был ли любимым гусеником URL? Проще говоря, каждый раз, когда гусеничный узел собирает URL, он хранит URL в базе данных, и каждый раз приходит новый URL, он отправляется в базу данных, чтобы проверить, было ли она доступна.

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

Однако по мере того, как поисковые роботы сканируют все больше и больше URL-адресов, к базе данных необходимо обращаться один раз перед каждым запросом, и эффективность SQL-запросов для таких строк невелика. В дополнение к базе данных, использование структуры наборов Redis также может удовлетворить эту потребность, и производительность выше, чем у базы данных. Но у Redis тоже есть проблема: он потребляет слишком много памяти. На этот раз фильтр Блума вышел очень горизонтально: этот вопрос привел меня сюда.

По сравнению с базами данных и Redis использование фильтров Блума позволяет избежать проблем с производительностью и использованием памяти.

Фильтр Блума по сути являетсябитовый массив, битовый массив состоит в том, что каждый элемент массива занимает только 1 бит. Каждый элемент может быть только 0 или 1. Применение битового массива из 10 000 элементов таким образом занимает всего 10 000 / 8 = 1250 байт пространства. Фильтр Блума имеет K хэш-функций в дополнение к битовому массиву. При добавлении элемента в фильтр Блума выполняются следующие операции:

  • Выполните K вычислений для значения элемента, используя K хэш-функций, в результате чего получите K хэш-значений.
  • В соответствии с полученным хеш-значением установите значение соответствующего индекса в 1 в битовом массиве.

Например 🌰 предположим, что фильтр Блума имеет 3 хэш-функции: f1, f2, f3 и битовый массив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. Фильтры Блума могут быть добавлены в 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.

Как упоминалось выше, в фильтре Блума есть ошибка, в redis есть два значения, которые определяют точность фильтра Блума:

  • error_rate: Разрешает частоту ошибок фильтра Блума.Чем меньше значение, тем больше размер битового массива фильтра и больше занимаемое пространство.
  • initial_size: количество элементов, которые может хранить фильтр Блума. Когда фактическое количество сохраненных элементов превышает это значение, точность фильтра снижается.

В Redis есть команда для установки этих двух значений:

bf.reserve urls 0.01 100

Значение трех параметров:

  • Первое значение — это имя фильтра.
  • Второе значениеerror_rateзначение .
  • Третье значениеinitial_sizeзначение .

Одна вещь, которую следует учитывать при использовании этой команды:Имя фильтра не должно существовать до выполнения этой команды, если оно существует до выполнения этой команды, будет сообщено об ошибке:(error) ERR item exists

Категории