предисловие
Привет всем, ямаленький мальчик собирает улиток. Сегодня поговорим о классическом вопросе интервью, что такое фильтр Блума? Какая польза?
- Общественный номер: маленький мальчик собирает улиток
проникновение в кеш
откликпроникновение в кешпроблема, мы можем использоватьФильтр Блума. Давайте сначала рассмотрим точки знаний о проникновении в кеш:
Общее использование кеша: чтение запросов, сначала проверьте кеш, кэш имеет значение значения, возвращается напрямую; кэш не нанята, перейдите в базу данных, затем обновите значение базы данных в кэш, возврат.
проникновение в кеш: Относится к запросу определенных данных, которые не существуют. Поскольку кеш не попал, их необходимо запросить из базы данных. Если данные не могут быть найдены, они не будут записаны в кеш. Это приведет к не- существующие данные должны запрашиваться в базе данных каждый раз, когда они запрашиваются, а затем оказывать давление на базу данных.
Предположим, нам нужно проверить информацию о продукте, и приходит запрос на запрос, мы сначалаИдантификационный номер продуктаПерейдите непосредственно к кешу для проверки, если нет, проверьте базу данных еще раз. если есть сейчасмного запросовЗаходите, а они все запрашивают несуществующий product ID, потом эти запросы все пойдут в базу, а база может зависнуть, как только возникнет давление. Мы можем добавить промежуточный уровень перед запросом уровня базы данных, чтобы уменьшить нагрузку на базу данных.Если он не существует, мы не будем проверять базу данных.
Большие данные суждения
Этот промежуточный слой не используетсяHashMapХорошо? Звучит хорошо, временная сложность HashMap может достигать O (1), но поскольку данные HashMap находятся в памяти, если большой объем данных намного превышает память сервера, то HashMap нельзя использовать, вы можете использоватьФильтр Блумачтобы сделать эту буферизацию.
Что такое фильтр Блума
Фильтр Блума — это структура данных небольшого размера, состоящая из длинного двоичного вектора и набора функций сопоставления хэшей, которая используется для определения того, находится ли элемент в наборе с лучшей эффективностью использования пространства и временем запроса.Общий алгоритм намного лучше. , но недостатком является то, что он имеет определенный процент ложных распознаваний и его трудно удалить.
Каков принцип работы фильтра Блума?Предположим, у нас есть множество A с n элементами. использоватьk хэшейфункция, которая преобразует каждый элемент в AкартаДля разных позиций в массиве B длиной a бит все двоичные числа в этих позициях устанавливаются равными 1. Если проверяемый элемент отображается с помощью k хэш-функций, то находятся двоичные числа в его k позициях.все 1, этот элемент, скорее всего, принадлежит множеству A, иначене должен принадлежать множеству A.
Давайте рассмотрим простой пример, предположим, что множество A имеет 3 элемента, которые {d1,d2,d3}. Существует 1 хэш-функция, котораяHash1. Теперь сопоставьте каждый элемент A с массивом B длиной 16 бит.
Теперь мы сопоставляем d1, предполагая, что Hash1(d1) = 2, мы изменим сетку с нижним индексом 2 в массиве B на 1 следующим образом:
мы сейчас ставимd2Он также отображается, предполагая Hash1 (d2) = 5, мы также меняем сетку с индексом 5 в массиве B на 1 следующим образом:
Затем мы кладемd3Он также отображается, предполагая, что Hash1 (d3) также равен 2, это также сетка с индексом 2 и индексом 1:
Следовательно, чтобы подтвердить, находится ли элемент dn в множестве A, нам нужно только вычислить нижний индекс индекса, полученный Hash1(dn), поскольку он равен 0, это означает, что этот элементнет в наборе А, что, если нижний индекс индекса равен 1? этот элементвозможныйявляется элементом А. Потому что вы видите, что значения нижнего индекса, полученные d1 и d3, могут быть равны 1, или они могут отображаться другими числами Фильтр Блума существует.недостаток: будет существоватьхэш-коллизияВызываются ложные срабатывания, и возникает ошибка в суждении.
какуменьшить эту ошибкуШерстяная ткань?
- Делайте больше сопоставлений хеш-функций, чтобы уменьшить вероятность коллизии хэшей.
- В то же время увеличение битовой длины массива B может увеличить диапазон данных, генерируемых хеш-функцией, и снизить вероятность коллизии хэшей.
Добавляем еще один Hash2хеш-картаФункция, предполагающая, что Hash2(d1)=6, Hash2(d3)=8, они не будут конфликтовать, как показано ниже:
Несмотря на тоОшибка, мы можем обнаружить, что фильтр Блума неПолные данные не сохраняются, он просто вычисляет позицию, используя ряд функций хэш-карты, а затем заполняет двоичный вектор. еслиЕсли количество большое, фильтр Блума проходитВозьмите очень маленькую частоту ошибок в обмен на большую экономию места для хранения, это все еще довольно дешево.
В настоящее время существуют библиотеки классов с открытым исходным кодом для фильтров Блума, такие какБиблиотека Google Guava, библиотеке классов Algebird от Twitter, вы можете сделать это на кончиках ваших пальцев или реализовать свой собственный дизайн на основе растровых изображений, поставляемых с Redis.
Наконец
Всем спасибо, если найдете что-то полезное, ставьте палец вверх, спасибо. Мой публичный номер: Маленький мальчик, который собирал улиток. Если вам интересно, вы можете следить