Вероятностные структуры: Bloom-фильтры и компания — когда эффективны, когда нет

Иногда точный ответ не нужен — нужен быстрый и почти точный, за копейки памяти. «Этот ключ точно отсутствует?», «сколько примерно уникальных посетителей?», «какие элементы встречаются чаще всего?» — на такие вопросы вероятностные структуры отвечают, тратя в разы меньше памяти, чем точные, ценой контролируемой ошибки. Bloom-фильтр за килобайты скажет «точно нет» или «возможно да»; HyperLogLog посчитает миллиарды уникальных в паре килобайт. Но у этой сделки есть обратная сторона, и понимать, где она выгодна, а где — ловушка, важнее, чем знать сами алгоритмы.

Это флагманская статья про вероятностные структуры данных: что они дают, где реально эффективны и где применять их — ошибка.

В статье

• Сделка: память и скорость в обмен на точность
• Мембершип-фильтры: «точно нет» или «возможно да»
• Кардинальность и частоты
• Где реально эффективны
• Когда только вредят (антипаттерны)
• Практика: прикидка и код
• Живой стенд: результаты
• Как выбирать
• Источники

Сделка: память и скорость в обмен на точность

Точная структура данных — hash-set, счётчик, B-дерево — хранит информацию так, чтобы ответ был безошибочным при любом запросе. За это платим памятью: чтобы точно знать, встречался ли элемент, нужно где-то хранить сам элемент (или его полноценный хеш) — на миллион ключей это буквально миллион записей. Вероятностная структура меняет правила игры: она хранит не элементы, а их след — несколько бит на элемент вместо десятков байт, — и соглашается иногда ошибаться взамен. Экономия при этом не «в разы», а на порядки: в стенде к этой статье Bloom-фильтр на миллион ключей занимает около 1170 КБ против ~62500 КБ у точного множества той же мощности — почти 53-кратная экономия памяти за контролируемую погрешность.

Ключевое слово — «контролируемую». У вероятностных структур ошибка не хаотична, она принадлежит одному из двух классов, и путать их нельзя. Первый класс — односторонняя ошибка: структура может соврать только в одну сторону. Bloom-фильтр на вопрос «есть ли элемент?» иногда отвечает «да» на то, чего не было (false positive), но никогда не отвечает «нет» на то, что было (false negative) — это фундаментальное свойство конструкции, а не следствие удачной настройки. Count-Min Sketch устроен зеркально: он оценивает частоту элемента и может завысить её, но никогда не занизит — оценка снизу невозможна по построению. Второй класс — двусторонняя ошибка с дисперсией: HyperLogLog оценивает число уникальных элементов, и эта оценка колеблется вокруг истинного значения то в плюс, то в минус — типичное отклонение около 1%, но без гарантии, в какую сторону промахнётся конкретный запуск.

Разница между классами определяет, где вероятностную структуру вообще можно ставить. Одностороннюю ошибку легко встроить в систему безопасно: если Bloom-фильтр перед диском иногда скажет «возможно есть» про несуществующий ключ, следующий шаг (реальный поиск) просто подтвердит отсутствие — лишняя работа, но не неверный ответ пользователю. А вот если бы фильтр мог сказать «точно нет» про существующий ключ, он бы прятал данные — это уже не оптимизация, а порча корректности, и именно поэтому конструкция Bloom-фильтра исключает false negative как класс. Двусторонняя ошибка требует другого подхода к применению: раз оценка HyperLogLog может как завысить, так и занизить число уникальных посетителей, её нельзя использовать там, где решение зависит от строгого порога («заблокировать после ровно 1000 попыток») — но она прекрасно годится для дашборда, где «примерно 2.4 млн уникальных» несёт всю нужную информацию. Итог простой: «почти точно» достаточно там, где неточность не распространяется дальше (следующий шаг её либо исправляет, либо ей всё равно) и где важен порядок величины, а не последняя значащая цифра; и недопустимо там, где на ошибке основано решение с необратимыми последствиями — деньги, доступ, безопасность. Дальше в статье будет отдельный раздел именно про такие антипаттерны.

Мембершип-фильтры: «точно нет» или «возможно да»

Задача мембершип-фильтра — ответить на вопрос «встречался ли этот элемент?», не храня сами элементы. Классический Bloom-фильтр решает её битовым массивом длиной m и k независимыми хеш-функциями: при вставке элемента выставляются в единицу k битов по его k хешам, при проверке — смотрят, все ли эти k битов уже единицы. Если хоть один ноль — элемента точно не было: битовый массив не мог случайно оказаться заполнен именно в этой комбинации позиций, если элемент туда не вставляли. А вот если все k битов оказались единицами — это может быть честное совпадение (элемент вставляли), а может быть и коллизия: чужие элементы вместе выставили в единицу ровно те позиции, которые нужны нашему. Отсюда и асимметрия гарантий: false negative невозможен структурно, false positive — возможен и растёт вместе с заполнением битового массива. Чем больше элементов вставлено при фиксированном m, тем больше единиц в массиве, тем выше шанс случайного совпадения — при разумно подобранных параметрах (в стенде — цель 1%, факт 1.01%) это управляемо, но если недооценить будущее число элементов на порядок, фильтр перестаёт защищать вообще — FP-rate взлетает почти до 100% (в стенде — до 99.5% при десятикратном занижении n), то есть фильтр вырождается в «всегда да» и теряет смысл. Прикидке параметров под целевой FP и ожидаемое n будет посвящён отдельный практический раздел.

Из этой же конструкции вытекает главное ограничение Bloom-фильтра: из него нельзя ничего удалить. Бит, выставленный в единицу, общий для многих элементов — если сбросить его при удалении одного, можно случайно создать false negative для всех остальных, которые на этот бит тоже полагались, а такого структура категорически не допускает. Counting Bloom filter снимает это ограничение самым прямым способом: вместо одного бита на позицию хранится счётчик. Вставка увеличивает счётчики на единицу, удаление — уменьшает, а «занят ли бит» проверяется как «счётчик больше нуля». Плата за это — память: счётчики (обычно 4 бита или байт на позицию вместо одного бита) увеличивают размер структуры в разы по сравнению с обычным Bloom при том же числе позиций.

Cuckoo filter решает ту же задачу — удаление с поддержкой — иначе: вместо счётчиков он хранит короткие отпечатки (fingerprints) элементов в таблице, устроенной по схеме cuckoo hashing (каждый элемент может жить в одной из двух корзин, и при коллизии «вытесняет» соседа в его альтернативную корзину). Удаление тривиально — стереть отпечаток; проверка — поискать отпечаток в обеих возможных корзинах. При этом при сопоставимом целевом FP-rate Cuckoo обычно компактнее классического Bloom, а не только Counting Bloom — в стенде к этой статье это тоже будет видно в конкретных цифрах памяти и throughput; здесь важен порядок выбора: Bloom — если удаление не нужно и нужна максимальная простота; Counting Bloom — если удаление нужно, а память не критична; Cuckoo — если нужно и удаление, и компактность. Точные измерения памяти, throughput и FP-rate для всех трёх — в разделе результатов ниже.

Кардинальность и частоты

Вопрос «сколько здесь уникальных элементов» на первый взгляд требует хранить все уникальные элементы хотя бы один раз — иначе как отличить повтор от новинки? HyperLogLog (HLL) обходит это ограничение статистическим трюком: он не хранит элементы, а следит за распределением хешей, точнее — за самой длинной серией нулевых бит, встреченной в потоке хешей, разбитых по регистрам. Интуиция в двух словах: чем больше различных значений прогнали через хеш-функцию, тем вероятнее среди них встретится «редкое» значение с длинной последовательностью нулей в начале, а по этой вероятности можно оценить обратно, сколько различных значений было. Регистров — фиксированное небольшое число, поэтому память константна и не растёт с количеством элементов: в стенде HLL занимает около 16 КБ как на миллионе элементов, так и на десяти миллионах, при стандартной ошибке в пределах 1% (в измерениях — от −0.08% до −0.86% в зависимости от N). Это и есть главное практическое следствие: HLL можно держать в памяти для метрики с миллиардами уникальных значений, не думая о росте потребления. Отдельное удобство HLL — merge: два независимо посчитанных HLL-регистра можно слить в один без потери точности относительно честного объединения множеств, что напрямую решает задачу распределённого подсчёта (посчитать уникальных на каждом шарде отдельно, потом слить результаты) — в стенде слияние двух наборов по 500 тысяч элементов даёт оценку с ошибкой того же порядка, что и прямой подсчёт.

Count-Min Sketch отвечает на смежный, но другой вопрос: не «сколько уникальных», а «сколько раз встретился вот этот конкретный элемент» — то есть оценивает частоты и помогает найти heavy hitters (самые частые элементы потока). Устроен он как матрица счётчиков width × depth: каждый элемент хешируется depth независимыми функциями в depth ячеек (по одной на строку), при инкременте увеличиваются все depth ячеек, а оценка частоты — минимум по ним. Минимум — не случайный выбор: коллизии с другими элементами могут только увеличить счётчик в ячейке, поэтому взять минимальную из нескольких независимых ячеек — способ отфильтровать чужой вклад и подобраться к истине сверху: выбрать самую тесную из нескольких завышенных оценок. Отсюда и односторонний характер ошибки: Count-Min Sketch может переоценить частоту (чужой трафик добавился в общую ячейку), но никогда не занизит её — это симметрично false-positive-only гарантии Bloom-фильтра, только в мире счётчиков, а не множеств. Величина переоценки прямо зависит от размера матрицы: в стенде при скромных width=500, depth=3 завышенными оказываются 756 из 1000 контрольных ключей (максимальное завышение — 500%), а при width=8000, depth=7 — ни одного (0 из 1000), при этом «горячий» ключ с настоящей частотой 80000 во всех конфигурациях оценивается точно как 80000, потому что настолько частый элемент доминирует над коллизиями в любом случае. Разница между «дешёвой» и «дорогой» конфигурацией — это, по сути, тот же компромисс память/точность, что и у Bloom-фильтра, только применённый к счётчикам, а не к битам присутствия.

Рядом с HLL и Count-Min стоит ещё пара структур, которые в этой статье не разбираются подробно, но стоит знать об их существовании. MinHash оценивает похожесть двух множеств (Jaccard-подобие) по компактной сигнатуре — минимальным значениям хешей — без сравнения множеств напрямую; это основа для приблизительного поиска дубликатов и похожих документов в больших коллекциях. Top-k / Space-Saving — структуры, которые вместо оценки частоты произвольного элемента сразу поддерживают список «k самых частых» с ограниченной памятью, что часто удобнее Count-Min, если интересны именно лидеры, а не частота конкретного элемента. Обе структуры решают ту же сделку — компактность за приблизительность, — но для других вопросов, и здесь упомянуты только для полноты картины.

Где реально эффективны

Общая черта всех сценариев ниже — вероятностная структура стоит не вместо точного механизма, а перед ним, как дешёвый фильтр, который отсекает большинство «неинтересных» случаев и пропускает дальше только те, что действительно требуют дорогой проверки.

Самый показательный пример — LSM-деревья в базах вроде Cassandra, ScyllaDB и RocksDB. LSM-хранилище со временем накапливает множество SSTable-файлов на диске, и наивный поиск ключа означает перебор всех файлов — каждый такой перебор стоит операции чтения с диска. Bloom-фильтр строится на каждый SSTable и хранится в памяти: перед тем как читать файл, движок спрашивает у фильтра «может ли этот ключ быть здесь?» — и если ответ «точно нет», файл вообще не трогают. Поскольку false negative у Bloom-фильтра структурно невозможен, эта оптимизация безопасна: ни один существующий ключ не потеряется, а вот число реальных чтений с диска падает в разы, потому что для большинства файлов ключа там заведомо нет. Это ровно тот случай, где мембершип-фильтр экономит не память, а I/O — самый дорогой ресурс в LSM-архитектуре. Подробнее про то, как это устроено на практике в конкретных key-value и document хранилищах, — в статье про transactions-kv (ScyllaDB/Cassandra), а общая механика индексов, ускоряющих поиск на диске, разобрана в статье про индексы БД.

Похожий трюк работает в кэшах и CDN — только вместо чтения с диска дорогая операция — это поход к источнику данных. Проблема, которую здесь решают, называется cache penetration: если запрашивать несуществующий ключ, кэш честно отвечает «промах», и запрос летит дальше — в базу или на origin-сервер, — а тот тоже не находит данные. Если такие запросы к несуществующим ключам массовые (например, злоумышленник целенаправленно перебирает ID), источник данных заваливается бесполезной нагрузкой. Bloom-фильтр перед кэшем, построенный по множеству реально существующих ключей, отвечает «точно нет» ещё до похода к источнику — и весь паразитный трафик отсекается на самом дешёвом уровне.

Дедупликация в потоковой обработке — ещё один сценарий, где не нужно знать что именно уже видели, важно только видели ли. Стриминговый пайплайн, который должен обработать каждое событие ровно один раз, обычно не может позволить себе хранить полный набор идентификаторов всех когда-либо обработанных событий — это неограниченно растущее множество. Bloom-фильтр (или его вариант с ограниченным по времени окном, если старые записи можно забывать) даёт ответ «это событие уже обрабатывалось» с контролируемой вероятностью ошибки, а не абсолютной гарантией, но для большинства пайплайнов ложное «уже видели» (и, как следствие, пропуск дубликата) — куда более дешёвая цена, чем неограниченный рост памяти на хранение истории.

Антиспам-системы и блеклисты URL используют вероятностную структуру как первый, самый дешёвый барьер перед дорогой проверкой. Проверить URL или отправителя по внешней репутационной базе, антивирусной сигнатуре или ML-модели — операция с заметной задержкой и стоимостью; прогонять через неё каждый запрос нецелесообразно. Bloom-фильтр, построенный по известным вредоносным адресам, мгновенно отсеивает подавляющее большинство безобидного трафика («точно не в блеклисте»), и только редкие кандидаты с «возможно да» уходят на полную проверку. Здесь та же логика, что и в LSM-БД: дешёвый фильтр не заменяет точный механизм, а резко сокращает число обращений к нему.

Наконец, аналитика уникальных значений — область, где вместо мембершип-фильтров работают структуры кардинальности. Посчитать точное число уникальных посетителей сайта или уникальных IP за сутки означает хранить множество всех увиденных значений — при миллиардах событий это гигабайты состояния ради одного числа. HyperLogLog решает задачу в те же несколько килобайт независимо от масштаба потока. В Redis это выглядит как три команды: PFADD visitors:2026-07-24 user123 добавляет элемент в HLL-структуру, PFCOUNT visitors:2026-07-24 возвращает оценку кардинальности, а PFMERGE visitors:month visitors:day1 visitors:day2 ... сливает несколько HLL без потери точности относительно честного объединения множеств — прямое применение merge-свойства, о котором шла речь выше. ClickHouse предлагает похожую функцию uniq (и её вариацию uniqHLL12) прямо в SQL-запросах над таблицами фактов, где точный count(distinct ...) был бы неприемлемо дорогим по памяти на больших объёмах. Подробнее о структурах данных Redis, включая HLL и его соседей по инструментарию in-memory вычислений, — в статье inmemory-redisготовится, с 22 сентября.

Когда только вредят (антипаттерны)

Вероятностные структуры — это всегда сделка, и там, где условия сделки не выполняются, они не экономят, а создают проблемы на пустом месте.

Первое и самое очевидное ограничение — домены, где false positive недопустим в принципе. Биллинг, где ложное «этот платёж уже обработан» означает потерянные деньги; проверки доступа, где ложное «пользователь в белом списке» означает утечку прав; дедупликация транзакций, где повторный дебет — это инцидент, а не мелкая неточность. Во всех этих случаях цена одной ошибки перевешивает всю экономию на памяти, и вероятностная структура здесь противопоказана — нужна точная, пусть и более дорогая по ресурсам.

Второе — малые множества. Вся экономия Bloom-фильтра берётся из того, что на элемент тратится несколько бит вместо десятков байт полноценной записи. На множестве в сотню или тысячу элементов эта экономия исчезающе мала в абсолютных цифрах, а обычный hash-set при этом проще в реализации, даёт точный ответ без всякого FP-rate и по скорости не уступает Bloom-фильтру — вычисление нескольких хешей и проверка нескольких битов не бесплатны, и на маленьких структурах, целиком помещающихся в кэш процессора, hash-set может оказаться даже быстрее. Здесь вероятностная структура не столько вредна, сколько просто не нужна — измерение из стенда к этой статье в практическом разделе ниже покажет это на конкретных цифрах памяти и throughput.

Третье — дорогой «второй шаг» после положительного ответа фильтра. Вся экономия от Bloom-фильтра предполагает, что подтверждение «возможно да» стоит немного дороже, чем сам фильтр, — лишнее чтение с диска, лишний запрос к источнику. Но если этот следующий шаг сам по себе дорог — например, вызов внешнего платного API, тяжёлый сетевой round-trip до другого дата-центра, или блокирующая операция с заметной задержкой, — а FP-rate фильтра не пренебрежимо мал, то доля ложных срабатываний начинает генерировать заметную долю бесполезных дорогих операций. В такой конфигурации выигрыш от фильтра съедается стоимостью false positive, и его нужно либо ужесточать (больше памяти, ниже FP-rate), либо не использовать вовсе.

Четвёртое — необходимость удалений при использовании обычного Bloom-фильтра. Как объяснялось выше, классический Bloom принципиально не поддерживает удаление отдельных элементов — сброс общего бита может создать false negative для других элементов, а это структура категорически исключает. Если предметная область требует не только добавлять, но и убирать элементы (например, кэш с TTL, где нужно явно забывать протухшие ключи), классический Bloom-фильтр здесь — неверный выбор; нужен Counting Bloom filter или Cuckoo filter, которые поддерживают удаление ценой памяти или чуть более сложной структуры.

Пятое — избыточность там, где точный быстрый индекс уже есть. Если данные и так лежат в структуре с O(1) или O(log n) точным поиском — например, в хорошо построенном hash-индексе, который целиком помещается в память, — добавление Bloom-фильтра перед ним не даёт выигрыша: экономить уже не на чем, а лишний слой лишь добавляет сложность и ещё один источник (хоть и маленькой) ошибки. Вероятностная структура оправдана там, где точная проверка дорога; если она и так дёшева, сделка не нужна.

Шестое, и на практике самое коварное, — неверная прикидка параметров при конструировании фильтра. Bloom-фильтр рассчитывается под ожидаемое число элементов n и целевой FP-rate; если реальное число вставленных элементов окажется существенно больше заложенного при расчёте размера битового массива, заполненность фильтра растёт неконтролируемо, и с ней растёт FP-rate — не линейно, а стремительно. В стенде к этой статье недооценка n всего в 10 раз (посчитали параметры под 100 тысяч элементов, а вставили миллион) поднимает FP-rate почти до 100% — конкретно до 99.5%: фильтр на практике отвечает «возможно да» почти на любой запрос, включая заведомо отсутствующие ключи, и полностью теряет смысл как фильтр — вся экономия на дисковых чтениях, запросах к источнику или дорогой проверке в этот момент обнуляется, а система просто не замечает деградации, пока кто-то не измерит реальный FP-rate под боевой нагрузкой. Иллюстрация этого эффекта и разбор, как оценивать параметры правильно, — в практическом разделе ниже.

Практика: прикидка и код

Параметры Bloom-фильтра не подбираются на глаз — они считаются из трёх чисел: ожидаемого количества элементов n, желаемого размера битового массива m и числа хеш-функций k. При фиксированных n и m существует оптимальное количество хешей, минимизирующее FP-rate: k = (m/n)·ln2. Интуиция простая — слишком мало хешей, и каждый элемент помечает мало битов, но проверка слишком грубая; слишком много хешей, и каждый элемент сам забивает битовый массив единицами быстрее, чем нужно. Оптимум — где эти два эффекта уравновешены. При таком k вероятность ложноположительного срабатывания оценивается формулой FP ≈ (1 − e^(−kn/m))^k: чем плотнее заполнен массив (больше n при фиксированном m), тем ближе показатель степени e^(−kn/m) к нулю, а вся скобка — к единице, то есть FP растёт. Отсюда и практический рецепт выбора параметров: задать целевой FP и ожидаемое n, а m и k вывести из формул (большинство библиотек, включая bits-and-blooms/bloom и Guava, делают это за вызывающего — на входе n и целевой FP, на выходе готовый битовый массив нужного размера с уже подобранным числом хешей). Именно поэтому ошибка в оценке n так дорого стоит: она не сдвигает параметры немного, а меняет фактическую плотность заполнения массива, а с ней — и FP-rate, причём нелинейно, как показано в разделе про антипаттерны выше.

Считать k независимых хешей на каждой вставке и проверке дороже, чем кажется — особенно если k доходит до 7–10 на высоких требованиях к FP. Реальные реализации почти никогда не запускают k разных хеш-функций. Вместо этого применяется двойное хеширование (double hashing): вычисляются всего два независимых хеша h1 и h2, а остальные k−2 получаются комбинацией h_i(x) = h1(x) + i·h2(x) mod m. Работает это благодаря тому, что для целей Bloom-фильтра не нужна криптографическая независимость хешей — достаточно, чтобы позиции битов были распределены равномерно и не коррелировали явно друг с другом в пределах одного элемента, а линейная комбинация двух хороших хешей с разными «шагами» даёт для этого достаточную энтропию на практике. Экономия ощутима: вместо k вызовов хеш-функции — два, а остальное — дешёвая арифметика.

Ниже — фрагмент реального стенда к этой статье: замер фактического FP-rate на Go (bits-and-blooms/bloom) и на Java (Guava BloomFilter), оба воспроизводят один и тот же эксперимент — построить фильтр под известное n и целевой FP, вставить n реальных ключей и прогнать запросы по заведомо отсутствующим.

// measureBloomFP строит фильтр под sizedFor элементов и целевой FP,
// добавляет n РЕАЛЬНЫХ ключей ("present-<i>"), затем делает queries запросов
// по заведомо ОТСУТСТВУЮЩИМ ключам ("absent-<i>") и считает долю false positive.
func measureBloomFP(n, queries uint, targetFP float64, sizedFor uint) (float64, uint) {
	f := bloom.NewWithEstimates(sizedFor, targetFP)
	for i := uint(0); i < n; i++ {
		f.Add([]byte("present-" + strconv.FormatUint(uint64(i), 10)))
	}
	var fpCount uint
	for i := uint(0); i < queries; i++ {
		if f.Test([]byte("absent-" + strconv.FormatUint(uint64(i), 10))) {
			fpCount++
		}
	}
	return float64(fpCount) / float64(queries), f.Cap()
}

bloom.NewWithEstimates(sizedFor, targetFP) — это ровно та точка, где библиотека сама решает уравнения k = (m/n)·ln2 и FP ≈ (1 − e^(−kn/m))^k относительно m и k, получив на входе только sizedFor (ожидаемое n) и targetFP. Разница между вызовом с sizedFor = n и с намеренно заниженным sizedFor = n/10 в стенде — это и есть демонстрация деградации FP из раздела про антипаттерны: тот же код, тот же фильтр, только неверная оценка n на входе в конструктор.

static void bloom() {
    int n = 1_000_000, queries = 1_000_000;
    double fpp = 0.01;
    BloomFilter<String> bf =
        BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8), n, fpp);
    for (int i = 0; i < n; i++) bf.put("present-" + i);
    int fp = 0;
    for (int i = 0; i < queries; i++) if (bf.mightContain("absent-" + i)) fp++;
    System.out.printf(Locale.ROOT, "Guava Bloom: target=%.4f  expectedFpp=%.4f  actual=%.4f%n",
        fpp, bf.expectedFpp(), (double) fp / queries);
}

Guava решает ту же задачу, но даёт удобный побочный эффект: метод expectedFpp() возвращает теоретическую оценку FP-rate, посчитанную из фактического числа вставленных элементов и параметров фильтра, — это можно сравнивать прямо в рантайме с actual, полученным честным прогоном запросов, без обращения к внешним формулам вручную.

Теория из формул — это ожидание, а не гарантия для конкретного набора данных: реальные ключи не всегда хешируются так же равномерно, как модель предполагает, а границы применимости расчёта легко нарушить неверной оценкой n. Поэтому прикидку параметров стоит всегда проверять прогоном на реальной или приближённой к реальной нагрузке — вставить ожидаемое количество ключей, прогнать запросы по заведомо отсутствующим и сравнить фактическую долю false positive с целевой. Оба фрагмента выше — не выдержки для иллюстрации, а работающий код: полный стенд с этим и соседними экспериментами (HyperLogLog, Count-Min Sketch, на Go и Java) лежит в digital-cookbook, probabilistic/ — там же лежит и код измерения деградации FP при заниженной оценке n, на которую этот раздел и раздел про антипаттерны опираются.

Живой стенд: результаты

Все числа ниже — не оценки по формулам, а замеры с реального стенда: Go (bits-and-blooms/bloom, axiomhq/hyperloglog, seiflotfy/cuckoofilter) и Java (Guava BloomFilter, stream-lib HyperLogLogPlus/CountMinSketch), без Docker — обычные бинарники на конкретной машине. Код обоих стендов — в digital-cookbook, probabilistic/; ниже — только результаты и их разбор.

Первые два столбца почти неразличимы — потому что фильтр, посчитанный под правильное n, работает ровно так, как обещает формула: план 1%, факт 1.01%. Третий столбец — тот же фильтр, тот же код, единственная разница — при конструкторе указали n в 10 раз меньше реального. FP-rate не увеличился в 10 раз (было бы 10%), а взлетел почти до единицы: 99.53%. Это и есть нелинейность из раздела про антипаттерны — фильтр на практике отвечает «возможно да» почти на любой запрос, включая заведомо отсутствующие ключи, и как фильтр перестаёт что-либо экономить.

Разрыв на графике — не «в разы», а на порядки, причём для обеих структур одновременно: Bloom-фильтр экономит 53× по сравнению с точным множеством той же мощности (1170 КБ против 62500 КБ), а HyperLogLog — почти в 1000 раз по сравнению с точным подсчётом уникальных (около 16 КБ против 15625 КБ на том же миллионе значений). У HLL картина ещё жёстче в динамике: замер на N=10 000 000 даёт ту же память ≈16 КБ (16392 Б) при ошибке −0.858%, тогда как точный подсчёт вырос бы до ≈156250 КБ — HLL-структура не растёт с числом элементов вообще, а точная растёт линейно. Слияние двух независимо посчитанных HLL по 500 тысяч элементов даёт оценку 1 002 391 при истинных 1 000 000 (ошибка +0.239%) — то есть merge не портит точность относительно честного объединения множеств.

Count-Min Sketch: цена экономии в переоценке

Count-Min Sketch никогда не занижает частоту, но насколько он завышает — целиком зависит от размера матрицы width × depth. Три конфигурации на одном потоке (1000 контрольных ключей + один «горячий» ключ с истинной частотой 80000):

Горячий ключ во всех трёх конфигурациях оценивается точно — 80000 против 80000: настолько частый элемент доминирует над случайными коллизиями при любом размере матрицы. А вот редкие ключи страдают от тесной матрицы напрямую: при 500×3 три четверти контрольных ключей завышены, местами впятеро; при 8000×7 — ни одного завышенного из тысячи. Это тот же компромисс память/точность, что у Bloom-фильтра, только применённый к счётчикам.

Throughput: порядок величины по структурам

Однопоточные вставка и запрос, один и тот же стенд (Go):

Абсолютные цифры — с одного прогона на одной машине и заметно колеблются от прогона к прогону (разброс порядка 10–20%), поэтому важен не десятичный знак, а порядок и относительное соотношение: Cuckoo в этом замере обгоняет Bloom почти вдвое на вставке (1.86×) и чуть больше чем вдвое на запросе (2.17×), а HLL — самая быстрая структура из трёх, потому что обновляет всего один регистр на вставку вместо нескольких битов по нескольким хешам.

Cuckoo filter vs Bloom filter: память и удаление

При сопоставимом целевом FP (~0.01) на одном и том же миллионе ключей:

Cuckoo здесь компактнее классического Bloom (1024 КБ против 1170 КБ) и вдобавок поддерживает удаление — что для обычного Bloom-фильтра структурно исключено. Это ровно тот случай из раздела про мембершип-фильтры: если нужно и удаление, и компактность, Cuckoo — предпочтительный выбор перед Counting Bloom filter, которому лишние счётчики на позицию обходятся дороже по памяти.

Как выбирать

Все структуры этой статьи решают одну и ту же сделку — память и скорость в обмен на контролируемую ошибку, — но отвечают на разные вопросы. Выбор начинается не со структуры, а с вопроса: что именно нужно узнать и какая ошибка (и в какую сторону) допустима. Только когда это зафиксировано, имеет смысл смотреть, какая структура эту ошибку даёт дешевле всего. Порядок «сначала структура, которая понравилась или на слуху, потом подгонка задачи под неё» — источник большинства антипаттернов из раздела выше.

Табличная логика сводится к одному правилу: сначала — вопрос и допустимая ошибка (её тип, направление, масштаб), и только потом — структура, которая эту ошибку даёт дешевле точного варианта. Если на входе не сформулировано, какая ошибка приемлема и в какую сторону, любой выбор структуры — случаен, а «дешёвая» вероятностная структура рискует превратиться в источник трудноуловимого бага вместо оптимизации.

Источники

Первоисточники алгоритмов:

• Burton H. Bloom, «Space/Time Trade-offs in Hash Coding with Allowable Errors», Communications of the ACM, 1970 — оригинальная статья о Bloom-фильтре.
• Bin Fan, Dave G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, «Cuckoo Filter: Practically Better Than Bloom», CoNEXT, 2014 — конструкция Cuckoo filter.
• Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier, «HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm», AofA, 2007 — оригинальный HyperLogLog.
• Stefan Heule, Marc Nunkesser, Alexander Hall, «HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm», Google, EDBT, 2013 — HLL++ и практические поправки для малых и очень больших кардинальностей.
• Graham Cormode, S. Muthukrishnan, «An Improved Data Stream Summary: The Count-Min Sketch and its Applications», Journal of Algorithms, 2005 — оригинальная работа по Count-Min Sketch.

Документация библиотек стенда:

• bits-and-blooms/bloom — Go, классический Bloom filter (bloom.NewWithEstimates).
• axiomhq/hyperloglog — Go, HyperLogLog/HLL++.
• seiflotfy/cuckoofilter — Go, Cuckoo filter.
• Guava BloomFilter — Java, Bloom filter с expectedFpp().
• stream-lib — Java, HyperLogLogPlus и CountMinSketch.

Стенд к статье: digital-cookbook, probabilistic/ — полный код всех экспериментов на Go и Java, версии зафиксированы в go.mod и pom.xml.

Читать дальше на платформе:

• Индексы БД: типы и устройство — как устроен точный поиск, который Bloom-фильтр прикрывает перед диском в LSM-хранилищах.
• transactions-kv: Redis, MongoDB, ScyllaDB — практика key-value и документных хранилищ, где Bloom-фильтры и HLL встроены нативно (PFADD/PFCOUNT/PFMERGE).
• inmemory-redis: структуры данных Redisготовится, с 22 сентября — HyperLogLog и соседние структуры Redis в контексте in-memory вычислений.