Comments 31
Можно кратное введение для тех, кто не в теме: где применяется данный фильтр, и почему его стоит писать на С++?
Фильтр Блума позволяет очень эффективно определить, «видел» ли фильтр некие данные. Фильтр может давать ложноположительные срабатывания (не видел, но говорит, что видел), но никогда на дает ложноотрицательных (если фильтр говорит, что не видел, значит 100% не видел).
Используется, например, в базах данных при поиске страниц. Через фильтр прогоняется какой-нибудь идентификатор страницы, и если фильтр говорит, что «видел» его, то страница в памяти, иначе — на диске. Фильтр он в том смысле, что «фильтрует» запросы к диску.
Используется, например, в базах данных при поиске страниц. Через фильтр прогоняется какой-нибудь идентификатор страницы, и если фильтр говорит, что «видел» его, то страница в памяти, иначе — на диске. Фильтр он в том смысле, что «фильтрует» запросы к диску.
Меня мучает такой вопрос, а чем он эффективнее простого битового массива + установка бита по одной хеш-функции?
Меньше ложноположительных срабатываний.
Грубо: пусть у вас массив, скажем, на 20'000 битов. Если он «увидит» 1000 элементов с одной хорошей хеш-функцией, то он пропустит новый элемент с вероятностью 1/20.
Если же вы построили блум-фильтр на 10 функций, то даже если в этом массиве будет установлена половина битов (а больше ну никак не выйдет), то каждая функция будет давать ложноположительное срабатывание с вероятностью 1/2 — но зато все вместе они датут отсеивание с 99.9% вероятностью! А 1/1000 — это гораздо лучше, чем 1/20, согласитесь.
Чем больше у вас функций — тем больше выигрыш, но и тем больше памяти нужно для эффективной работы и тем медленнее работает фильтр.
Грубо: пусть у вас массив, скажем, на 20'000 битов. Если он «увидит» 1000 элементов с одной хорошей хеш-функцией, то он пропустит новый элемент с вероятностью 1/20.
Если же вы построили блум-фильтр на 10 функций, то даже если в этом массиве будет установлена половина битов (а больше ну никак не выйдет), то каждая функция будет давать ложноположительное срабатывание с вероятностью 1/2 — но зато все вместе они датут отсеивание с 99.9% вероятностью! А 1/1000 — это гораздо лучше, чем 1/20, согласитесь.
Чем больше у вас функций — тем больше выигрыш, но и тем больше памяти нужно для эффективной работы и тем медленнее работает фильтр.
Очень просто. У Вас есть миллиард объектов. Вам нужно найти объект, удовлетворяющий заданным условиям (состоянию). Прежде чем начать поиск, при помощи фильтра Блума Вы можете определить (с определенной вероятностью), что этот объект есть в этом наборе. Или его там нет. Читал, что фильтр Блума использует Google.
Фильтр Блума компактно хранит множество элементов и позволяет проверять принадлежность заданного элемента к множеству, с фолспозитивами, но без фолснегативов. C++ потому что это структура данных предназначена для чего-то высокопроизводительного, относительно больших объемов данных, а обычно такие вещи требуют плюсов.
Примеры из вики:
Прокси-сервер Squid использует фильтры Блума для опции cache digests.
Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных.
Компьютерные программы для проверки орфографии.
Биоинформатика.
Примеры из вики:
Прокси-сервер Squid использует фильтры Блума для опции cache digests.
Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных.
Компьютерные программы для проверки орфографии.
Биоинформатика.
В добавление к уже отписавшимся IvaYan, Komei, khim, afend69, RPG18, Whiteha, bsisoft, Biga: например, для распределённых хеш таблиц, всем известный DHT в emule, DC++, BitTorrent, Tox и других p2p протоколах, использует фильтр Блума.
Вот спецификация для DHT в BitTorrent, там на живом примере показано как используется фильтр Блума для замены потенциально гигантского списка нод (даже пространство IPv4 велико, а IPv6 вообще огромно). Т. е.создаётся очень компактная коллекция, запрос к которой с очень высокой вероятностью скажет существует ли искомая нода и со 100% вероятностью ответит что нода не существует.
На C++ потому что язык сочетает в себе скорость, универсальность и хорошую масштабируемость (на нём можно хорошо написать что угодно и ПО для стиральной машины для контроллера со 100 байт ОЗУ и 1 МГц процессором и приложения для, например, десктопа или смартфона или для вычислительного кластера с тысячами CPU и многими ТБ памяти), удобства (из-за наличия шаблонов, стандартной библиотеки и прочего, ну и писать на нём можно быстрее и безопаснее при сравнении с C, а низкоуровневый доступ, в т. ч. сырые указатели (прямой доступ к памяти) использовать только там где нужно), наличии уже кучи библиотек для всего и вся. В купе ко всему перечисленному C++ даёт не просто высокую производительность, но ещё и надёжно прогнозируемую поскольку не содержит сборщика мусора в ядре языка, по этой же причине RAII из коробки отлично и предсказуемо работает для любых объектов, а не только для памяти, что позволяет писать более компактный код и точно ничего не забыть ибо деструктор закроет файл, сокет и освободит любой другой ресурс сразу же даже в случае исключения, а не во время отложенной сборки мусора.
P.S. энное время назад плотно занимался разработкой FlylinkDC++ (Ёжик в тумане), оттого «в теме» про DHT.
Вот спецификация для DHT в BitTorrent, там на живом примере показано как используется фильтр Блума для замены потенциально гигантского списка нод (даже пространство IPv4 велико, а IPv6 вообще огромно). Т. е.создаётся очень компактная коллекция, запрос к которой с очень высокой вероятностью скажет существует ли искомая нода и со 100% вероятностью ответит что нода не существует.
На C++ потому что язык сочетает в себе скорость, универсальность и хорошую масштабируемость (на нём можно хорошо написать что угодно и ПО для стиральной машины для контроллера со 100 байт ОЗУ и 1 МГц процессором и приложения для, например, десктопа или смартфона или для вычислительного кластера с тысячами CPU и многими ТБ памяти), удобства (из-за наличия шаблонов, стандартной библиотеки и прочего, ну и писать на нём можно быстрее и безопаснее при сравнении с C, а низкоуровневый доступ, в т. ч. сырые указатели (прямой доступ к памяти) использовать только там где нужно), наличии уже кучи библиотек для всего и вся. В купе ко всему перечисленному C++ даёт не просто высокую производительность, но ещё и надёжно прогнозируемую поскольку не содержит сборщика мусора в ядре языка, по этой же причине RAII из коробки отлично и предсказуемо работает для любых объектов, а не только для памяти, что позволяет писать более компактный код и точно ничего не забыть ибо деструктор закроет файл, сокет и освободит любой другой ресурс сразу же даже в случае исключения, а не во время отложенной сборки мусора.
P.S. энное время назад плотно занимался разработкой FlylinkDC++ (Ёжик в тумане), оттого «в теме» про DHT.
Скажите, а Вам приходилось на практике применять фильтр Блума? Если несложно, поясните где и как Вы его использовали?
Могу поделиться своим примером.
Есть сервер сообщений для игры. Обычный pub-sub, то есть клиент коннектится к серверу, подписывается на каналы и ждёт сообщений. Запущено несколько экземпляров сервера для балансировки. Сервера соединяются друг с другом и сообщают, у кого какие подписки, чтобы не бродкастить все сообщения на все сервера. Тут и применяется блум-фильтр: сами идентификаторы подписок не хранятся, есть только несколько бит в блум-фильтре. Используется модификация блум-фильтра — со счётчиком, но работает абсолютно так же.
Есть сервер сообщений для игры. Обычный pub-sub, то есть клиент коннектится к серверу, подписывается на каналы и ждёт сообщений. Запущено несколько экземпляров сервера для балансировки. Сервера соединяются друг с другом и сообщают, у кого какие подписки, чтобы не бродкастить все сообщения на все сервера. Тут и применяется блум-фильтр: сами идентификаторы подписок не хранятся, есть только несколько бит в блум-фильтре. Используется модификация блум-фильтра — со счётчиком, но работает абсолютно так же.
А кеширование — вы когда-либо использовали? Вот Блум Фильтр — это, грубо говоря, «кеш для кешей»: так как вы храните на один элемент данных только пару-тройку бит, то вы можете точно сказать — стоит вам ходить в кеш или нужно напрямую идти в «медленное» хранилище. Идея кажется дикой — но только до тех пор пока кеш у вас один. Если же кеширующих серверов становится много — вот тогда важно знать какой из них чего знает (и знает ли вообще хоть кто-нибудь хоть чего-нибудь).
Добавьте тэг: фильтр Блума. Чтобы было доступно тут:
https://habrahabr.ru/search/?q=%5B%D1%84%D0%B8%D0%BB%D1%8C%D1%82%D1%80%20%D0%B1%D0%BB%D1%83%D0%BC%D0%B0%5D&target_type=posts
https://habrahabr.ru/search/?q=%5B%D1%84%D0%B8%D0%BB%D1%8C%D1%82%D1%80%20%D0%B1%D0%BB%D1%83%D0%BC%D0%B0%5D&target_type=posts
Вот что Мейерс пишет про std::vector:
«Vector как контейнер STL обладает лишь двумя недостатками. Во-первых, это вообще не контейнер STL. Во-вторых, он не содержит bool.»
«Vector как контейнер STL обладает лишь двумя недостатками. Во-первых, это вообще не контейнер STL. Во-вторых, он не содержит bool.»
Можно это считать алгоритмом кластеризации (в некотором смысле)?
«Стоит отметить, что std::vector является намного более эффективной специализацией» — очень спорное утверждение. Требует меньше памяти — да. Но скорость доступа меньше, чем, например, у vector за счет объекта-провайдера, возвращаемого operator[].
Объект провайдер современные реализации легко выкидывают, это не беда. Беда в том, что на платформе где это важнее всего (почти весь TOP500 — это x86, ведь так?) он не использует операции, которые могли бы его сделать реально быстрым (компилятор про них не знает, а реализацию на asm'е некому сделать).
Кстати неплохая идея для того, кто хочет лучше разобраться с C++: потратить пару вечеров и сделать приличную реализацию vector<bool>… а потом потратить ещё пару месяцев, чтобы убедить разработчиков GCC его включить к себе в библиотеку :-)
Сделать парочку бенчмарков, померить скорость… есть желающие?
Кстати неплохая идея для того, кто хочет лучше разобраться с C++: потратить пару вечеров и сделать приличную реализацию vector<bool>… а потом потратить ещё пару месяцев, чтобы убедить разработчиков GCC его включить к себе в библиотеку :-)
Сделать парочку бенчмарков, померить скорость… есть желающие?
Уже делали.
Вот например статья Ховарда Хиннанта (автора libc++).
Где-то была и оптимизированная реализация, кажется ввиде патча к одной из стандартных библиотек, кажется как раз libc++, но я что-то не могу найти.
Вот например статья Ховарда Хиннанта (автора libc++).
Где-то была и оптимизированная реализация, кажется ввиде патча к одной из стандартных библиотек, кажется как раз libc++, но я что-то не могу найти.
Оптимизированную версию делали и не раз. Я сам лично делал и использовал отпимизированную версию в паре своих проктов — это как раз не фокус.
Фокус в том, чтобы сделать оптимизированную версию совместимую с std::vector<bool> и продвинуть её в GCC/Clang (ну или, если вы мазохист, в MSVC).
Дело в том, что в STL — весьма много разновсяких требований, а в x86 (да и в других процессорах) — много разных интересных функций (к примеру тот же find: использовать прямо вот так __builtin_ctz там нельзя, так как результат не определён, но если мы пишем под GCC/Clang, то мы можем вспомнить что у нас есть ассемблер, а в нём — реакция на нуль вполне разумна: BSF/BSR флаг Z выставляют правильно), так что есть где порезвиться и поразвлекаться при создании всего этого (опять-таки при наличии SSE4.2/AVX2 есть PTEST — но для него нужно увеличивать минимальные размеры std::vector<bool>).
В общем с технической точки зрения там ничего страшного и/или сложного нет, а вот если попытаться это продвинуть в стандартную библиотеку… вот это — уже для мазохистов…
Фокус в том, чтобы сделать оптимизированную версию совместимую с std::vector<bool> и продвинуть её в GCC/Clang (ну или, если вы мазохист, в MSVC).
Дело в том, что в STL — весьма много разновсяких требований, а в x86 (да и в других процессорах) — много разных интересных функций (к примеру тот же find: использовать прямо вот так __builtin_ctz там нельзя, так как результат не определён, но если мы пишем под GCC/Clang, то мы можем вспомнить что у нас есть ассемблер, а в нём — реакция на нуль вполне разумна: BSF/BSR флаг Z выставляют правильно), так что есть где порезвиться и поразвлекаться при создании всего этого (опять-таки при наличии SSE4.2/AVX2 есть PTEST — но для него нужно увеличивать минимальные размеры std::vector<bool>).
В общем с технической точки зрения там ничего страшного и/или сложного нет, а вот если попытаться это продвинуть в стандартную библиотеку… вот это — уже для мазохистов…
std::vector<bool> ведь упразднять хотят, и вообще он немало проблем родил. Смысл его куда-то продвигать?
> Стоит отметить, что std::vector является намного более эффективной специализацией std::vector,…
Не уловил разницы между std::vector и std::vector, видимо упущено что-то типа?
Не уловил разницы между std::vector и std::vector, видимо упущено что-то типа?
Товарищи… ну нельзя же так переводить…
У вас
«С помощью фильтра Блума 4.3MБ и 13 хэш-функции, вставляя элементы 1.8МБ приняли примерно 189 наносекунд для каждого элемента на средней производительности ноутбуке.»
Должно быть
«C 4.3-Мбайтным фильтром Блума и 13 хэш-функциями при добавлении 1.8 миллионов элементов среднее время вставки одного элемента составило приблизительно 189 наносекунд на моем ноутбуке.»
(Оригинал — With a 4.3MB Bloom filter and 13 hash functions, inserting 1.8M items took roughly 189 nanoseconds per element on my laptop.)
P.S. И всё равно за статью большое спасибо :)
У вас
«С помощью фильтра Блума 4.3MБ и 13 хэш-функции, вставляя элементы 1.8МБ приняли примерно 189 наносекунд для каждого элемента на средней производительности ноутбуке.»
Должно быть
«C 4.3-Мбайтным фильтром Блума и 13 хэш-функциями при добавлении 1.8 миллионов элементов среднее время вставки одного элемента составило приблизительно 189 наносекунд на моем ноутбуке.»
(Оригинал — With a 4.3MB Bloom filter and 13 hash functions, inserting 1.8M items took roughly 189 nanoseconds per element on my laptop.)
P.S. И всё равно за статью большое спасибо :)
Sign up to leave a comment.
Как написать фильтр Блума в C ++