25 марта 2010 г.

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

Сегодня случайно нашел в одной из папок Google Chrome пару интересных файлов:
  • Safe Browsing Bloom
  • Safe Browsing Bloom Filter 2
Вывод: Хром использует фильтры Блума для предварительной оценки того, является ли веб сейт, на который вы пойдете, вредоносным ;) Хорошая находка!

Поясню, как это работает:
  • URL приводится к каноническому виду.
  • Вычисляются N его "длинных" хешей (скорее всего, 64 битных).
  • Значение каждого хеша умножается на скейл-фактор, таким образом получаются N адресов битов в массиве данных, называемом фильтром Блума.
  • Фильтр построен так, что если все эти биты - единички, сайт с большой вероятностью вредоносный (в этом случае происходит его достоверная верификация - видимо, путем запроса к соотв. сервису Google); иначе он гарантированно "безопасный" (гарантировано - = его 100% нет в БД вредоносных сайтов).
  • Более подробное описание фильтов Блума - здесь.
Эффективность сего метода заключается в том, что:
  • Размер такого фильтра заметно меньше любой другой структуры, которая могла бы дать ответ на подобный вопрос точно. Например, если бы это был set (структура данных), его длина была бы ~ равна суммарной длине URL всех  вредоносных сайтов, входящих в него. А блум-фильтр, дающий ложнопозитивные ответы с вероятностью всего 1% (ложнонегативных он не дает вообще), потребует в среднем 9.6 бита на каждый URL, т.е. порядка 1 байта! Фильтры Хрома в сумме занимают порядка 18Мб - и если они действительно построены для обеспечения такой вероятности ложнопозитивных ответов, это значит, что они содержат информацию о ~ 1 миллионе вредоносных сайтов!
  • Такой фильтр позволяет Хрому обращаться к сервисам верификации практически только тогда, когда пользователь действительно идет на вредоносный сайт. Ну не замечательно ли? ;)
P.S. Я сразу обратил внимание на эту пару файлов потому, что у нас в Xtensive.Indexing есть их отличная реализация, а в Xtensive.Core - API для вычисления 64-битных хешей, позволяющий блум-фильтрам получать нужное количество 64-битных хешей (вернее, нужное количество значений уникальных 64-битных хеш-функций) как для встронных, так и для ваших собственных типов (для каждого собственного типа, понятно, потребуется написать Hasher, но это весьма просто, т.к. хешеры уже реализованы для CLR-типов).

P.P.S. Как вы уже поняли, с сегодняшнего дня я буду "разбавлять" свой русский политико-киношный блог переводами постов из своего же английского промо-программистского ;) В ближайших планах - перевод цикла статей об оптимизациях, используемых в ORM-решениях: "Может ли ORM сделать ваше приложение более производительным?".

2 комментария:

  1. Ага!!! Нашли че придумать!! Этот Safe Browsing Bloom занимает 250 мб на жестком диске и и 250 мб столько же в другой директории. итого = 500 мб для браузера - полнейшая тупость. Самое главное эти файлы тупо не удаляются.

    ОтветитьУдалить
  2. Проверил, у меня сейчас 7 Мб ;)

    ОтветитьУдалить