Bloom filter
На досуге переписал свою же C-реализацию bloom filter с помощью шаблонов C++.
Если посмотреть на уже существующие варианты фильтров, например, Bloom_filter_(C) или OpenBloomFilter, то можно заметить, что для использования на больших объёмах данных они непригодны (под большими объёмами я понимаю тысячи хранилищ по несколько миллионов элементов в каждом). Проблема заключается в попытке включить в фильтр и сам функционал добавления элементов, и хранилище данных, и реализации хэш-функций. Получается красиво, изящно, но это хорошо, когда тепло и пахнет померанцем, а у нас такая философия не по климату. :-)
Для задач промышленных масштабов необходимо выполнение трёх простых условий:
1. Фильтр предоставляет функционал для расчёта параметров и заполнения битовой последовательности; ничего больше.
2. Битовые последовательности, т.е. хранилища данных, создаются независимо от фильтров.
3. Пользователь может использовать различные хэш-функции по своему усмотрению.
Что касается последнего пункта, то для C сигнатура всех функций должна быть одинакова, для C++, за счёт применения шаблонов, возможны вариации с типами аргументов.
Собственно сам фильтр можно посмотреть на github.com/mukhin/libbloom.
P.S. Подумалось, что наверное, кроме мэйла нигде так bloom filter не пользуют, чтобы сотни гигабайт данных, 24x7x365 и 150К запросов в секунду. Поэтому никому и в голову не приходит, что может не хватить памяти, например. :-)
Если посмотреть на уже существующие варианты фильтров, например, Bloom_filter_(C) или OpenBloomFilter, то можно заметить, что для использования на больших объёмах данных они непригодны (под большими объёмами я понимаю тысячи хранилищ по несколько миллионов элементов в каждом). Проблема заключается в попытке включить в фильтр и сам функционал добавления элементов, и хранилище данных, и реализации хэш-функций. Получается красиво, изящно, но это хорошо, когда тепло и пахнет померанцем, а у нас такая философия не по климату. :-)
Для задач промышленных масштабов необходимо выполнение трёх простых условий:
1. Фильтр предоставляет функционал для расчёта параметров и заполнения битовой последовательности; ничего больше.
2. Битовые последовательности, т.е. хранилища данных, создаются независимо от фильтров.
3. Пользователь может использовать различные хэш-функции по своему усмотрению.
Что касается последнего пункта, то для C сигнатура всех функций должна быть одинакова, для C++, за счёт применения шаблонов, возможны вариации с типами аргументов.
Собственно сам фильтр можно посмотреть на github.com/mukhin/libbloom.
P.S. Подумалось, что наверное, кроме мэйла нигде так bloom filter не пользуют, чтобы сотни гигабайт данных, 24x7x365 и 150К запросов в секунду. Поэтому никому и в голову не приходит, что может не хватить памяти, например. :-)
