Учитывая имя пользователя на странице регистрации пользователя, как мы можем узнать, было ли оно уже зарегистрировано?

Хотя запросы к индексированной базе данных помогают, они медленные и требуют сетевых вызовов.

Чтобы ускорить процесс, мы можем кэшировать список зарегистрированных имен пользователей в хранилище ключей и значений, таком как Redis.

Однако это подразумевает кэширование миллионов записей и удвоение нашего объема памяти.

Как мы можем добиться большего успеха в этой, казалось бы, тривиальной задаче?

Фильтр Блума может быть ответом, давайте проверим!

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

Фильтр Блума отвечает на один простой вопрос:

Существует ли элемент в заданном множестве?

Фильтр Блума — это вероятностная структура данных. Учитывая вопрос выше, он выводит любой из следующих ответов

• Вероятно да
• 100% Нет

И его самое большое преимущество в том, что он делает это в ПОСТОЯННОМ времени и пространстве.

Как это работает?

Фильтр Блума состоит из двух компонентов.

• Битовый массив размера N
• Несколько функций хеширования

Сначала он инициализируется как битовый массив размера N, все биты которого установлены в ноль. Предположим, что длина массива сейчас равна 10.

Добавление элемента

Добавление элемента тривиально

• Элемент с надписью «тигр» хэшируется с помощью функции хеширования.
• Сгенерированный хэш модифицируется по длине массива для получения ограниченного индекса.
• Затем индекс битового массива устанавливается равным 1.

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

Результат оценивается следующим образом:

• Если значение индекса битового массива равно 0, элемент НЕ находится в наборе.
• В противном случае предмет ВЕРОЯТНО находится в наборе

Хранение фильтра Блума

Вместо того, чтобы хранить фильтр Блума в виде массива, мы можем преобразовать его битовое представление в десятичное число.

Например, мы можем преобразовать массив, содержащий 1001119, и сохранить его в кеше.

Если список не меняется очень часто, сервер может отправить десятичное число клиенту, что позволит выполнить проверку на стороне клиента.

Можем ли мы сделать лучше?

Если хеш-функция выводит индекс 1 и для «тигра», и для «коровы», проверка на наличие «коровы» в наборе дает ответ «Да », даже если это не так .

Мы можем уменьшить вероятность ложных срабатываний с помощью следующих решений.

• Увеличить длину массива
• Увеличьте количество функций хеширования

Вместо одного индекса мы можем получить несколько индексов, используя несколько хэшей.

При добавлении элемента все полученные индексы будут установлены в 1.

Утверждается, что элемент, вероятно, находится в наборе, только если ВСЕ индексы установлены на 1.

Используя эти методы, мы могли бы значительно снизить вероятность ложных срабатываний.

Приложения

Давайте рассмотрим несколько примеров из реальной жизни.

Проверьте, существует ли имя пользователя в процессе регистрации пользователя.

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

• Medium поддерживает фильтр Блума для каждого пользователя.
• Прежде чем рекомендовать статью, Medium проверяет, существует ли идентификатор статьи в фильтре Блума пользователя.
• Пользователю рекомендуются статьи, которые точно НЕ попали в фильтр Блума.

• При доступе к URL-адресу Chrome сначала проверяет, является ли URL-адрес частью списка вредоносных программ.
• Вместо того, чтобы каждый раз запрашивать сервер Google, Google создает фильтр Блума, используя заранее определенный список вредоносных программ, и отправляет его в браузер.
• Браузер хэширует URL-адрес и выполняет перекрестную проверку с помощью фильтра Блума перед доступом к веб-сайту.

Хотя могут быть ложные срабатывания , фильтр Блума удобен, когда мы хотим определить, действительно ли элемент отсутствует в списке.

Его можно использовать в качестве первого уровня фильтрации благодаря его эффективности как во времени, так и в пространстве.

Я надеюсь, что вы найдете это полезным, и я увижу вас на следующем!