Создание веб-сайта с большими объемами данных было нормой в течение последних нескольких лет. В то время как регистрация была важной функцией, которую должен иметь веб-сайт, поддержка функции поиска с огромным объемом данных является проблемой для такого инженера, как я. Однако поиск Google показал нам, как простой алгоритм может улучшить производительность их поиска. Фильтр Блума – это одна из вероятностных структур данных, позволяющая свести к минимуму затраты времени и места на функции поиска.
Первоначальный поиск можно выполнить, просматривая все существующие данные. Мы все знаем, что это займет много времени, поскольку данные продолжают увеличиваться каждый день с миллионами записей. Hash map может решить эту проблему с помощью мгновенного поиска, но это требует затрат. Как насчет миллионов записей, и их количество увеличивается с каждым днем? Пространство и ресурсы для управления хеш-картой начнут показывать влияние.
Случаи применения
- Илон хочет зарегистрировать новый Gugglo Mail, учитывая, что в Gugglo Mail миллиарды зарегистрированных пользователей с разными адресами электронной почты. Gugglo Mail может проверять каждый раз, когда Элон вводит, чтобы узнать, доступно ли электронное письмо или нет. Выполнение полного сканирования миллиардов существующих электронных писем, безусловно, не лучшая идея. Как улучшить поиск доступности электронной почты?
- У Маска есть популярный веб-сайт, на котором каждый день публикуется несколько новостей. У Маска есть идея порекомендовать несколько новых пользователю, который подписывается на его сайт. Проблема возникла, когда появились миллиарды новостей и миллионы пользователей. Как отследить, какие новости не были рекомендованы каждому конкретному пользователю?
- Рив, как служба безопасности, хочет убедиться, что все непродуктивные сайты заблокированы в его компании. Каждый день его сотрудник посещает множество сайтов. Он хочет убедиться, что сайты можно отфильтровать с миллиардами веб-сайтов, которые, как он точно знает, непродуктивны. Как он может легко это фильтровать?
Фильтр Блума
Фильтр Блума — это вероятностная структура данных, которая может помочь в этих случаях использования. Он может проверить принадлежность данных к списку и выдать результат либо «Возможно, существует», либо «Нет». Фильтр Блума может гарантировать отсутствие данных в списке, но не уверен, существуют ли они на самом деле или нет — скорее всего, они существуют, но нельзя быть уверенным на 100%. Вот почему фильтр Блума называется вероятностным, и с этим преимуществом приходится жертвовать быстрым поиском.
Как это работает
Фильтр Блума состоит из 3 основных компонентов.
- Массив битов с 0 или 1 размером
n - Некриптографическая хеш-функция, такая как FMV или Murmur, которая принимает ввод и возвращает число.
- Семена; список случайных чисел, которые будут использоваться хэш-функцией
Возьмем пример n = 10 со значением по умолчанию 0.
И семена как [23, 41, 59]
Давайте побежим за словом, скажем foo
str = "foo" seeds = [23, 41, 59] // Go through all seeds fHash(str, seeds[0]) = 32 fHash(str, seeds[1]) = 59 fHash(str, seeds[2]) = 7 //Because the result is higher than the n that we declare, we need to mod it fHash(str, seeds[0]) = 32 mod 10 = 2 fHash(str, seeds[1]) = 59 mod 10 = 9 fHash(str, seeds[2]) = 7 mod 10 = 7
Как видите, нам нужен mod результат, чтобы убедиться, что он имеет индекс в нашем массиве. Давайте пометим наш массив foo
Затем добавим еще одно новое слово, скажем, bar
str = "bar" seeds = [23, 41, 59] // Go through all seeds fHash(str, seeds[0]) = 13 fHash(str, seeds[1]) = 97 fHash(str, seeds[2]) = 20 //Because the result is higher than the n that we declare, we need to mod it fHash(str, seeds[0]) = 13 mod 10 = 3 fHash(str, seeds[1]) = 97 mod 10 = 7 fHash(str, seeds[2]) = 20 mod 10 = 0
Мы можем добавить новый результат в наш массив (обратите внимание, что 7 уже в массиве, мы можем его игнорировать)
Теперь займемся сканированием. Чтобы выполнить сканирование или поиск, нам нужно запустить слово с хэш-функцией и теми же семенами. Давайте запустим несколько образцов:
- Foo
Запуск хеш-функции с теми же начальными значениями возвращает 3 значения: {2, 9, 7}. Проверив массив на наличие индекса {2, 9, 7}, мы увидели, что ни одно из значений не содержит0, что означает, что Foo, вероятно, существует в фильтре Блума. - Baz
Запуск хеш-функции с теми же начальными значениями возвращает 3 значения: {5, 3, 8}. Проверяя массив на наличие индексов {5, 3, 8}, мы увидели, что значения 5 и 8 содержат0, что означает, что можно сказать Нет, конечно, что Баз никогда не добавлял в фильтр Блума. - Qux
Запуск хэш-функции с теми же начальными значениями возвращает 3 значения: {0, 9, 2}. Проверив массив на наличие индекса {0, 9, 2}, мы увидели, что ни одно из значений не содержит0, что означает, что Qux, вероятно, присутствует в фильтре Блума. Несмотря на то, что мы знаем, что Qux никогда не добавляется в фильтр Блума, именно здесь возникает вероятность.
Проблема
Как видно из предыдущего примера, Qux дает ложноположительный результат. Причина в столкновении флага с фильтром Блума, мы ничего не можем с этим поделать. Однако мы можем минимизировать риски, либо увеличив размер n (битового массива), либо увеличив начальные значения. И то, и другое уменьшит вероятность столкновения.
Предостережения
Есть несколько предостережений, которые необходимо знать перед использованием фильтра Блума.
- Удаление данных
Вы не можете удалить ни одно слово, которое было внутри фильтра Блума. Причина в том, что вы можете также удалить какое-то другое слово, удалив определенные слова, поскольку массив является общим для данных. - Ложноположительные результаты
Вы должны заранее определить размер массива. Небольшой размер массива увеличит количество ложноположительных результатов. Добавление большего количества элементов также увеличит количество ложноположительных результатов. Способ покрыть этот случай — разработать стратегию сброса фильтра Блума или использовать масштабируемый фильтр Блума.
Redis как фильтр Блума
В настоящее время Redis стал основным ресурсом веб-сайтов. Он предлагает отличное кэширование, а также многократное использование, даже для фильтра Блума. Мы можем использовать Redis для всех процессов фильтра Блума.
Инициализировать
Начнем с инициализации фильтра Блума внутри Redis.
# BF.RESERVE key_name error_rate capacity BF.RESERVE test_bloom 0.01 10000
Мы можем начать с вызова BF.RESERVE, он устанавливает фильтр Блума. У него есть значения по умолчанию, но лучше настроить под свои нужды. Требуется key_name для ключа Redis, допустимый коэффициент ошибок от 0 до 1 процента (0,05 = 5%) и количество слов, которые мы хотим поместить внутрь как емкость.
Запуск резерва с error_rate и емкостью автоматически создаст начальные числа и разрядность массива битов. Нам даже не нужно считать и думать о семенах, хеш-функции и ширине массива, просто нужно учитывать допустимую частоту ошибок и сколько данных нам нужно поместить внутрь.
Добавлять
Чтобы добавить новые слова в фильтр Блума в Redis, достаточно просто позвонить
# BF.ADD key_name word BF.ADD test_bloom foo BF.ADD test_bloom bar # BF.MADD test_bloom word word ... BF.MADD test_bloom foo bar baz
Мы можем вызвать Add, чтобы добавить новое слово в фильтр Блума, или Madd (Multiple add), чтобы добавить несколько слов в одну команду.
Существуют
Чтобы проверить, находится ли слово внутри фильтра Блума в Redis, мы можем вызвать его с помощью
# BF.EXISTS key_name word BF.EXISTS test_bloom foo BF.EXISTS test_bloom bar # BF.MEXISTS test_bloom word word ... BF.MEXISTS test_bloom foo bar baz
Он вернет 0 или 1.
- 0 как не существовало
- 1 как вероятно существовал
И это все, что вам нужно знать, как использовать фильтр Блума в Redis. Redis абстрагировал то, что осталось за сценой, и нам больше не нужно учитывать систему.
