Pull to refresh

Comments 16

Чтобы добавить элемент в фильтр Блума

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

Вероятно, что надо просто посмотреть заполнены ли все требуемые биты

Всё правильно, но в образовательной статье это стоит написать явно )

Можно реализовать "да нет наверно" :-)

Отличная статья! Давно хотел разобраться с этим фильтром, но как-то времени не хватало.

Фильтры Блума, это хорошая структура с красивой математикой, однако, на современных ЦП они являются неэффективными с точки зрения производительности на больших объемах данных. Причин тому две:

  1. Необходимо вычисление большого количества хэш-функций, что создаёт большое количество ситуаций branch-mispredict.

  2. Случайный доступ к одному биту в большом массиве повторяется для каждой хэш-функции. Это генерирует большое количество ситуаций cache-miss и доступов в память, что очень медленно. Это неэффективно расходует пропускную способность шины памяти, т.к. ради одного бита мы читаем из памяти ~256 байт (а то и больше).

Гораздо более эффективно на современных ЦП работает простая хэш-таблица с linear-probing для разрешения коллизий, которая содержит не сами ключи, а их хэши (сигнатуры), посчитанные второй хэш-функцией.

Итого, имеем всего две хэш-функции. Одна для вычисления смещения в массиве сигнатур. Вторая для вычисления самой сигнатуры.

В приведенном выше примере:

Допустим, существует 1 000 000 вредоносных ссылок по 20 символов каждая,
что составляет 20 МБ. Однако, если мы готовы принять вероятность ошибки
в 0,0001% (1 на миллион), можно использовать фильтр Блума. Это позволит
хранить те же данные всего в 3,59 МБ.

С такой структурой нам потребуется всего 3,27 MB для хранения 1 000 000 ключей и обеспечения вероятности ошибки в 0,0001% при заполнении таблицы в 75% и длине сигнатуры 22 бита.

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

П.С.

Спасибо фильтрам Блума, но, им пора на пенсию!

Где про это почитать или пример использования не подскажите?

На самом деле, отдельных статей на эту тему я не видел. Вероятно, потому, что это просто частный случай хэш-таблицы. Причем, один из самых тривиальных по построению.

Для анализа вероятностей с минимальными изменениями работает математика, описанная здесь:

https://preshing.com/20110504/hash-collision-probabilities/

Для реализации и понимания механизма работы достаточно вот этого:

https://ru.wikipedia.org/wiki/Линейное_зондирование

Используется тривиальное зондирование с шагом 1. С учетом того, что нам не требуется (в силу невозможности реализации) удаление ключа из таблицы и изменение её размера, реализуются только упрощенная вставка и поиск. Оба алгоритма тривиальны и представляют собой простой цикл.

На практике я встречал (и сам писал код) для частного случая с фиксированной длиной сигнатуры в 32 бита. В этом случае не надо возиться с битовой арифметикой и алгоритмы становятся совсем тривиальными. 32 бита дают вероятность ошибки примерно в 0,0000001% (один на миллиард), что более чем достаточно для большинства сценариев, и, в качестве бонуса, допускают атомарную вставку.

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

Дополнительно, т.к. результатом поиска/вставки является не только признак успеха, но и индекс в массиве сигнатур, то, структуру, дополнительно, можно использовать как отображение (map), используя этот индекс для доступа к данным в другом массиве. Это хорошо подходит для организации всевозможных кэшей, in-memory key-value хранилищ, баз данных и индексов. Можно использовать везде, где требуется высокая производительность и работа с большими объемами данных.

Например, для реализации операции Hash Join при выполнении запроса в БД.

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

Ваш аргумент именно про производительность вставки (и даже проверки).

Структура, которую я описал выше, при прочих равных (и при условии правильного подбора fill factor и длины сигнатуры), может давать меньшую вероятность ошибки, занимать меньше места в памяти, и показывать лучшую производительность, чем фильтры Блума как на вставке, так и на проверке.

Все вместе и одновременно.

Причем, это самая простая в реализации альтернатива фильтрам Блума.

Помимо этого, есть более сложные и еще более эффективные варианты с точки зрения потребления памяти, сравнимые по производительности на проверке:

https://en.wikipedia.org/wiki/Cuckoo_filter

https://arxiv.org/abs/1912.08258

Но, там вставка медленная.

В последнем примере как-то явно в тексте не говорится, что речь идёт про удаление несуществующего элемента "response", и именно из-за этого и возникает проблема, о которой идёт речь. Приходится догадываться об этом из строк кода.

Поясните плз. неграмотному, как получались такие короткие хеши на 2-й картинке из sha1(160бит) sha256(256) ...

Мы берем хэш-значение "foo" для каждой из 3 хэш-функций и умножаем его по модулю на количество бит в фильтре Блума. При делении на 32 получаем остаток по модулю. Хэш-функции sha1, sha256 и sha512 дают нам значения 27, 15 и 16 соответственно.

Возможно, имелось в виду "делим по модулю"?

Sign up to leave a comment.