Использование фильтра Блума

Question

Я изо всех сил пытаюсь понять полезность фильтра Блума. Я понимаю его основную логику, сжатие пространства, быстрый поиск, ложные срабатывания и т. Д. Я просто не могу поместить эту концепцию в реальную ситуацию как полезную. Одним из частых приложений является использование фильтров Блума в веб-кэшировании. Мы используем фильтр Блума, чтобы определить, находится ли данный URL в кеше или нет. Почему бы нам просто не получить доступ к кешу, чтобы определить это? Если мы получили "да", нам все равно нужно перейти в кэш для получения веб-страницы (которой может не быть), но в случае "нет" мы могли бы получить тот же ответ, используя кеш (который, вероятно, оптимизирован для быстрого поиска). тем не мение?).

Answer 1

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

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

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

Надеюсь это поможет!

Answer 2

Фильтры Блума могут быть полезны при соблюдении обоих следующих условий:

• Ложное отрицание недопустимо
• Стоимость поиска дорогая по сравнению со стоимостью поиска в фильтре Блума

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

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

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

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

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

Answer 3

Проблема в том, что твой пример не так хорош.

в веб-кэше, если URL-адрес отсутствует, вам все равно придется делать дорогой вызов в сеть, поэтому сохранение доступа к диску не представляет особой проблемы. так что вы правы в этом вопросе (и комментарий Диего Баша не очень хорошо продуман, имхо).

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

Для получения дополнительной информации о фильтрах Squid и Bloom см. http://wiki.squid-cache.org/SquidFaq/CacheDigests

в противном случае, другой ответ здесь, из templatetypedef, хорош - проверка на плохие сайты - гораздо лучший пример.