Статья была выбрана Github, добро пожаловать в Star:github.com/yehongzhi

концепция

Фильтр Блума (BloomFilter) был предложен молодым человеком по имени «Блум» в 1970 году. Это очень длинный бинарный вектор, в основномИспользуется для определения того, находится ли элемент в наборе.

принцип

Прежде чем вводить принцип, давайте поговорим оХэш-функцияКонцепция чего-либо.

Наши HashMap и HashSet в Java фактически вступили в контакт с функцией hashcode().Хеш-функция — это функция, которая может преобразовывать входные данные любого размера в выходные данные определенного размера.Преобразованные данные называютсяхэш-значение.

Хеш-функции имеют следующие характеристики:

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

Фильтр Блума состоит из длинного двоичного вектора и ряда хеш-функций. Так как же фильтр Блума определяет, входит ли элемент в набор?

Предполагая, что базовая структура хранения фильтра Блума представляет собой битовый массив длиной 16, в начальном состоянии все его позиции установлены в 0.

Когда переменная добавляется в фильтр Блума, переменная сопоставляется с K точками битового массива с помощью K функций отображения, и значение этих K точек устанавливается равным 1 (при условии, что есть три функции отображения).

При запросе, существует ли переменная, нам нужно только найти соответствующие K точек с помощью тех же K функций отображения и определить, все ли значения в K точках равны 1.Если все равны 1, это означает, что он, вероятно, существует,еслиЕсли любая из K точек равна 0, она не должна существовать..

характеристика

Первый вопрос, почему все 1, скорее всего, существуют, а не обязательно существуют?

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

Итак, вот одна из характеристик фильтра Блума,Есть некоторая неточность.

Второй вопрос, может ли фильтр Блума удалять элементы?

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

Как показано на рисунке выше, если вы удалите obj1 и установите для 4, 7 и 15 значение 0, то определение того, существует ли obj2, приведет к ошибке, поскольку точка отображения 7 равна 0, а в результате obj2 не существует.

Это вторая особенность,Элементы в фильтрах Блума не могут быть удалены.

Преимущества и недостатки

преимущество:

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

недостаток:

** Должен быть определенный случай. ** Чем больше элементов в фильтре Бурона, тем выше проступок.
** Невозможно удалить элементы в фильтре Блума. ** По мере того, как время использования становится все больше и больше, потому что его нельзя удалить, в нем хранится все больше и больше элементов, все больше и больше памяти занято, и скорость ошибочной оценки становится все выше и выше, и, наконец, его необходимо сбросить. .

Применяется для проникновения в кеш

**Используется для предотвращения проникновения в кэш. **Проблема проникновения в кеш в основном связана с тем, что входящий ключ не существует в Redis, поэтому он будет напрямую затронут БД, что приведет к увеличению нагрузки на БД.

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

Основное использование здесьЕсли результат оценки фильтра Блума состоит в том, что он не существует, он не должен существовать.Эта функция, но поскольку фильтр Блума имеет определенную ошибочную оценку, нельзя сказать, что он полностью решает проблему проникновения в кеш, но может значительно облегчить проблему проникновения в кеш.

Плагин фильтра Блума

После того, как мы узнаем основной принцип фильтра Блума, теоретически мы можем сделать это сами.

После Redis 4.0 предоставляется официальная функция подключаемого модуля фильтра Блума, и фильтр Блума можно загрузить на сервер Redis в качестве подключаемого модуля для непосредственного использования.

Сначала установите Redis, в Интернете есть много руководств по установке, поэтому я не буду вдаваться в подробности. Здесь я использую версию Redis 6.0.10. После установки Redis загрузите плагин и загрузите его с помощью команды git:

git clone https://github.com/RedisBloom/RedisBloom.git

Потянув его вниз, вы получите проект RedisBloom.

Затем перейдите в папку /RedisBloom и скомпилируйте его с помощью команды make.

После завершения компиляции создается файл redisbloom.so.

При запуске Redis просто загрузите модуль фильтра Блума на сервер.

./src/redis-server --loadmodule /usr/local/RedisBloom/redisbloom.so

Наконец, используйте клиент, чтобы протестировать его.

redis-6.0.10]$ ./src/redis-cli 

127.0.0.1:6379> bf.add user sam
(integer) 1
127.0.0.1:6379> bf.add user jack
(integer) 1
127.0.0.1:6379> bf.exists user jack
(integer) 1
127.0.0.1:6379> bf.exists user tom
(integer) 0

Основные инструкции фильтра Блума следующие:

bf.add добавляет элемент в фильтр Блума
bf.exists определяет, находится ли элемент в фильтре Блума
bf.madd добавляет несколько элементов в фильтр Блума
bf.mexists определяет, находятся ли несколько элементов в фильтре Блума

127.0.0.1:6379> bf.madd user mike rose
1) (integer) 1
2) (integer) 1
127.0.0.1:6379> bf.mexists user blue mike
1) (integer) 0
2) (integer) 1

В реальной разработке Java-программы обычно используются для работы с Redis, и невозможно напрямую использовать командную строку для оценки Как работать с Java-программами?

Сначала введите зависимости, я использую SpringBoot 2.0, поэтому импортированные зависимости 3.15.0.

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson-spring-boot-starter</artifactId>
    <version>3.15.0</version>
</dependency>

Затем напишите основной метод для демонстрации.

public static void main(String[] args) throws Exception {
    Config config = new Config();
    config.useSingleServer().setAddress("redis://192.168.0.109:6379");
    RedissonClient client = Redisson.create(config);

    RBloomFilter<String> bloomFilter = client.getBloomFilter("user");
    //尝试初始化，预计元素55000000，期望误判率0.03
    bloomFilter.tryInit(55000000L, 0.03);
    //添加元素到布隆过滤器中
    bloomFilter.add("tom");
    bloomFilter.add("mike");
    bloomFilter.add("rose");
    bloomFilter.add("blue");
    System.out.println("布隆过滤器元素总数为：" + bloomFilter.count());//布隆过滤器元素总数为：4
    System.out.println("是否包含tom：" + bloomFilter.contains("tom"));//是否包含tom：true
    System.out.println("是否包含lei：" + bloomFilter.contains("lei"));//是否包含lei：false
    client.shutdown();
}

Суммировать

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

Это все, что касается этой статьи, спасибо за чтение, я надеюсь, что вы сможете что-то получить после ее прочтения.

Статьи постоянно обновляются. Wechat ищет «энтузиастов технологии Java», а отправленные технические статьи получают как можно скорее после того, как обращают на них внимание. Статьи классифицируются и включаются в github:github.com/yehongzhi, вы всегда сможете найти то, что вас интересует

Ставьте лайки, если считаете это полезным, ваши лайки — самая большая мотивация для моего творчества.~

Я программист, который изо всех сил старается запомниться. Увидимся в следующий раз! ! !

Возможности ограничены, если есть какие-то ошибки или неуместности, просьба критиковать и исправлять их, учиться и обмениваться вместе!