Comments 16
Чтобы добавить элемент в фильтр Блума
Не заметил дальше по тексту объяснения того, как проверяется наличие элемента в множестве.
Можно реализовать "да нет наверно" :-)
Отличная статья! Давно хотел разобраться с этим фильтром, но как-то времени не хватало.
Фильтры Блума, это хорошая структура с красивой математикой, однако, на современных ЦП они являются неэффективными с точки зрения производительности на больших объемах данных. Причин тому две:
Необходимо вычисление большого количества хэш-функций, что создаёт большое количество ситуаций branch-mispredict.
Случайный доступ к одному биту в большом массиве повторяется для каждой хэш-функции. Это генерирует большое количество ситуаций 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", и именно из-за этого и возникает проблема, о которой идёт речь. Приходится догадываться об этом из строк кода.
В oracle используется для join Вероятностный bloom filter
И approx_count_distinct думаю на схожих принципах работает.
Поясните плз. неграмотному, как получались такие короткие хеши на 2-й картинке из sha1(160бит) sha256(256) ...
Есть занимательная статья о неочевидных подводных камнях фильтра Блума: https://blog.cloudflare.com/when-bloom-filters-dont-bloom
Мы берем хэш-значение "foo" для каждой из 3 хэш-функций и умножаем его по модулю на количество бит в фильтре Блума. При делении на 32 получаем остаток по модулю. Хэш-функции sha1, sha256 и sha512 дают нам значения 27, 15 и 16 соответственно.
Возможно, имелось в виду "делим по модулю"?
Фильтр Блума