data · intermediate · 4d
Фильтр Блума
Собери пространственно-эффективное вероятностное множество, отвечающее на запросы членства за O(1) с настраиваемой вероятностью ложных срабатываний, — и разберись, почему ложных отрицаний в нём быть не может принципиально.
Результат
Фильтр Блума, хранящий добавленные элементы с нулём ложных отрицаний, удерживающий вероятность ложных срабатываний в пределах математически предсказанной границы для выбранного размера битового массива и числа хеш-функций, и открывающий fill ratio, чтобы оператор мог видеть, когда фильтр насыщается.
Этапы
0/6 · 0%- 01Построй битовый массив и внедри хеш-функции
Ядро фильтра Блума — плоский битовый массив из m бит: не Set, не Map, не массив булевых значений, а компактное представление, где каждый бит стоит один бит ОЗУ, а не целый байт или заголовок объекта. В JavaScript/TypeScript идиоматическое хранилище — Uint8Array, где бит i живёт по байту i>>3, позиция бита i&7 (установка через |=, проверка через &). Число хеш-функций k — не свойство фильтра, а семейства инъектируемых функций: принимай массив хеш-функций в конструкторе, чтобы тесты могли передавать быстрые детерминированные функции без обращения к крипто. Это разделение важно по двум причинам: (1) оно делает корректность фильтра доказуемой в изоляции — ты контролируешь каждый выход хеша в тесте; (2) оно отражает реальную практику, где Murmur3 или xxHash с разными seed'ами дёшево дают k функций. Вырази размер битового массива в байтах (деление с потолком на 8) и открой m (всего бит) и k (число хеш-функций) для математики следующего этапа.
Критерии готовности- Фильтр хранится в Uint8Array из ceil(bits/8) байт; установка бита i и проверка бита i корректны для произвольного i без ошибок на единицу (проверено прямым тестом на уровне бит).
- Хеш-функции передаются через конструктор — никакого глобального хеша — и фильтр открывает `m` (число бит) и `k` (число хеш-функций) как читаемые свойства.
Самопроверка
Покажи, что бит i устанавливается и проверяется по байту floor(i/8), бит i%8 — senior-ревьюер проверяет отсутствие boolean-массива и Set, а также что две разные хеш-функции, попадающие в один индекс бита, идемпотентны (установка уже установленного бита ничего не меняет).
- 02Реализуй add: запусти все k хешей и установи все k бит
Добавление строки в фильтр означает вычисление каждой из k хеш-функций, отображение каждого результата на индекс бита через взятие по модулю m и установку этого бита в 1. Взятие по модулю не бесплатно: если результаты хешей — 32-битные знаковые целые, остаток от деления отрицательного числа на m будет отрицательным в JavaScript (в отличие от Python), поэтому надо сначала замаскировать до беззнакового (h >>> 0) или использовать Math.abs — выбери одно и придерживайся. Порядок обхода k бит не важен, так как все k бит должны быть установлены в любом случае, а чтение частично-установленного ключа во время добавления другого в однопоточном движке невозможно. На этом этапе фильтр только хранит — запросов на членство ещё нет. Важный инвариант, который надо зафиксировать сейчас: после `add(s)` для каждой хеш-функции h_i бит (h_i(s) % m) равен 1.
Критерии готовности- После `add(s)` каждая битовая позиция (h_i(s) % m) для i от 0 до k-1 установлена в 1 — проверяется обращением к каждой позиции напрямую, а не только через `has()`.
- Отрицательные результаты хеша обрабатываются корректно: (h(s) % m) всегда является неотрицательным индексом в [0, m-1], проверяется хеш-функцией, которая может возвращать отрицательные значения.
Самопроверка
Пройди `add('hello')` с двумя инъектированными хеш-функциями, возвращающими -3 и 15 на m=10 бит: senior-ревьюер проверяет, что результат взятия по модулю неотрицателен (7 и 5, а не -3 и 5), и что обе битовые позиции установлены до возврата функции.
- 03Реализуй has: проверка всех k бит и гарантия ложных срабатываний
`has(s)` возвращает true тогда и только тогда, когда все k битовых позиций для s установлены. Если хотя бы один бит равен 0, элемент точно никогда не добавлялся — это гарантия отсутствия ложных отрицаний, и она абсолютна, не вероятностна: бит может только перейти от 0 к 1, никогда от 1 к 0 (в стандартном фильтре). Ложное срабатывание возникает, когда все k бит оказываются равны 1 из-за других элементов, занявших эти позиции, — фильтр не может отличить это от настоящего члена. Senior-инженер должен уметь точно формулировать оба случая: «has вернул false ⟹ элемент точно отсутствует; has вернул true ⟹ элемент, вероятно, присутствует (вероятность FP ≈ (1−e^{−kn/m})^k)». На этом этапе ты также подтверждаешь, что реализация действительно соблюдает инвариант отсутствия ложных отрицаний — добавь 50 строк, проверь has для всех 50, утверди все true. Тест FP появится в этапе 4, когда будет математика размеров.
Критерии готовности- Каждый элемент, добавленный через `add(s)`, найден через `has(s)` — ноль ложных отрицаний — доказано на не менее 50 различных строках.
- Ты можешь письменно сформулировать асимметрию: «false от has гарантирует отсутствие; true от has означает вероятное присутствие с вероятностью FP, ограниченной формулой размеров», — и указать на тест, демонстрирующий каждую сторону.
Самопроверка
Senior-ревьюер спрашивает: если ты добавил элемент A, а элемент B совпадает со всеми k битовыми позициями A, вернёт ли `has(B)` true? Покажи, что реализация возвращает true (корректное поведение FP), и объясни, почему это не баг, а фундаментальный компромисс структуры между пространством и точностью.
- 04Выведи m и k из целевой ёмкости и вероятности FP
Фильтр Блума имеет три настраиваемых параметра: m (биты), k (хеш-функции), n (ожидаемые элементы). Зная n и целевую вероятность ложных срабатываний p, оптимальные m и k выводятся из: m = -n·ln(p)/(ln2)² и k = (m/n)·ln2. Эти формулы не магия — они получаются дифференцированием выражения вероятности FP (1−e^{−kn/m})^k по k и m. Senior-инженер должен уметь вывести или хотя бы проверить их численно: для n=1000 элементов и p=0.01 (1%), m≈9585 бит (~1,2 КБ), k≈7. Занижение m в 2 раза удваивает вероятность FP; уменьшение k вдвое часто экономит мало места, но утраивает FP-rate. Создай вспомогательную функцию `optimalParams(n, p)`, возвращающую {m, k}, добавь тест-проверку того, что реальная FP-rate на 1000 отсутствующих ключей не превышает 2×p для вычисленных параметров, и запиши, что происходит с FP-rate, когда фильтр превышает расчётную ёмкость n, — потому что именно это насыщение является наиболее распространённым производственным сбоем.
Критерии готовности- `optimalParams(n, p)` возвращает m = ceil(-n*ln(p)/ln(2)^2) и k = round((m/n)*ln(2)), и ты можешь показать вывод формулы или численную проверку для n=1000, p=0.01.
- Тест вставляет n элементов и проверяет 1000 отсутствующих ключей; наблюдаемая доля FP не превышает 2×p, и ты задокументировал кривую деградации FP при превышении n на 50% вставленных элементов.
Самопроверка
Senior-ревьюер спрашивает, что происходит с реальной FP-rate при вставке 2n элементов в фильтр, рассчитанный на n: покажи численно, что (1−e^{−k·2n/m})^k значительно превышает p, и назови производственное смягчение (увеличить m заранее, ротировать фильтр, использовать counting/scalable вариант из следующего этапа).
- 05Расширь до counting- или scalable-варианта
Стандартный фильтр Блума имеет два фундаментальных ограничения: нельзя удалять элементы (декремент общего бита портил бы элементы, которые его разделяют), и он не может расти — как только m и k зафиксированы, FP-rate монотонно растёт с ростом n. Counting-фильтр заменяет каждый бит маленьким счётчиком (обычно 4 бита), так что `remove(s)` возможен через декремент; это решает удаления, но не рост. Scalable-фильтр (SBF) решает рост, объединяя в цепочку серию стандартных фильтров с геометрически уменьшающимися целевыми FP-rate, чтобы общая FP-rate оставалась ограниченной: членство положительно, если хоть один подфильтр вернул true, а добавления идут в текущий подфильтр до превышения целевого fill ratio, после чего создаётся новый. Реализуй хотя бы один из этих вариантов и протестируй добавленный инвариант: counting-фильтр → после add+remove, has возвращает false; scalable-фильтр → FP-rate остаётся под общим порогом даже после вставки 10× начальной ёмкости n.
Критерии готовности- Реализован хотя бы один вариант (counting или scalable); для counting: после add и remove `has` возвращает false; для scalable: после вставки 5× ёмкости FP-rate на 1000 отсутствующих ключей остаётся под 2× целевого уровня.
- Ты можешь объяснить, почему стандартный фильтр не поддерживает ни одну из возможностей (общие биты делают удаление небезопасным; фиксированные m/k делают рост невозможным без насыщения) и что каждый вариант отдаёт взамен.
Самопроверка
Для counting-варианта: можно ли удалить элемент, который никогда не добавлялся? Покажи, что происходит (счётчик уходит ниже 0 или переполняется, портя фильтр), и объясни, почему counting-фильтр требует от вызывающих не удалять не-члены — это инвариант, который производственный counting-фильтр должен обеспечивать или документировать.
- 06Открой fill ratio, сделай бенчмарк и напиши памятку о компромиссах
Фильтр Блума бесполезен без наблюдаемости: нужно знать, насколько он насыщен, прежде чем FP-rate незаметно деградирует. `fillRatio()` возвращает долю установленных бит (popcount битового массива, делённый на m) — значения выше 0,5 сигнализируют, что фильтр приближается к расчётной ёмкости и FP-rate растёт. Popcount в JavaScript можно делать побитово или через таблицу поиска для производительности; для фильтра 100 КБ наивный цикл хорош, но при 10 МБ это измеримо. Сделай бенчмарк add и has при трёх масштабах (10 К, 100 К, 1 М элементов) и запиши байт/элемент против FP-rate против пропускной способности add. Затем напиши короткую памятку о компромиссах: когда выбирать фильтр Блума вместо hash-сета (постоянная память независимо от n, ценой вероятности FP), когда counting-фильтр вместо стандартного (нужны удаления, ценой 4× пространства), когда cuckoo-фильтр вместо него (меньше FP при том же пространстве, O(1) удаления, немного сложнее реализовать и менее изучен). Эта памятка — разница между «я реализовал фильтр Блума» и «я знаю, когда к нему обращаться».
Критерии готовности- `fillRatio()` корректно возвращает 0.0 на пустом фильтре и монотонно растёт при добавлении элементов, и ты можешь показать точную реализацию popcount (а не просто подсчёт установленных бит в цикле, который учитывал бы и неустановленные).
- Бенчмарк фиксирует байт/элемент и пропускную способность add/has на не менее чем двух масштабах, а памятка о компромиссах называет не менее трёх конкретных случаев использования, где фильтр Блума выигрывает у hash-сета, и один, где он проигрывает.
Самопроверка
Senior-ревьюер спрашивает: при каком fillRatio наблюдаемая FP-rate превышает 2× расчётного целевого уровня для твоего k? Вычисли его из формулы (1−fillRatio)^k и покажи точку пересечения — именно это число должен отслеживать оператор для алерта, а не произвольный порог 80%.
Стартер
- README.md
- src/bloom.ts
- test/bloom.test.ts
Распакуй, реализуй заглушки, затем гоняй тесты, пока не позеленеют: bun test
Рубрика
| Джуниор | Миддл | Сеньор | |
|---|---|---|---|
| Корректность хеширования и битового массива | Членство хранится в boolean-массиве или Set; хеш-функции жёстко закодированы, а не инъектированы. Коллизии битовых индексов между разными хеш-функциями не обрабатываются — вторая хеш-функция, устанавливающая уже установленный бит, может засчитываться как новый элемент. | Фильтр хранится в Uint8Array с корректной индексацией байт/бит (бит i по байту i>>3, позиция i&7). Хеш-функции инъектированы, отрицательные результаты хешей маскируются до беззнаковых перед взятием по модулю. `add` устанавливает все k бит; `has` проверяет все k бит и возвращает false при первом 0. | Ты можешь доказать, что отсутствие ложных отрицаний — инвариант конструкции на битовом OR (бит, установленный в 1, никогда не может быть сброшен, поэтому k позиций сохранённого элемента остаются установленными навсегда), и вычислить точную FP-rate для данного fill ratio как (1−fillRatio)^k — не приближение, а точную формулу с использованием наблюдаемой доли установленных бит, так что rate эмпирически проверяем для любого состояния фильтра. |
| Математика ложных срабатываний и размеры | m и k выбраны методом проб и ошибок или скопированы из примера. FP-rate для выбранных параметров не вычисляется, и нет проверки того, что фильтр остаётся в пределах заданного бюджета FP по мере добавления элементов. | `optimalParams(n, p)` корректно вычисляет m = ceil(-n·ln(p)/ln(2)²) и k = round((m/n)·ln(2)); тест подтверждает, что наблюдаемая FP-rate на 1000 отсутствующих ключей остаётся ниже 2×p для вычисленных параметров с n вставками. | Ты можешь аналитически вывести m и k (минимизировать (1−e^{−kn/m})^k по k; приравнять производную к нулю; восстановить m из этого k и p), численно показать, что происходит с FP-rate при переполнении фильтра сверх расчётной ёмкости n, и назвать порог fill-ratio, при котором FP-rate превышает 2×p для твоего k — это пороговое значение для алерта оператора, а не произвольные 80% заполнения. |
| Масштабирование и варианты (counting/scalable) | Реализован только стандартный фильтр; на вопрос об удалении элемента ответ — «пересобрать фильтр». Рост сверх n не обсуждается. | Реализован и протестирован хотя бы один вариант: counting-фильтр с работающим remove(), при котором has() возвращает false после add+remove для того же элемента; или scalable-фильтр, связывающий подфильтры и удерживающий FP-rate ниже целевого при 5× ёмкости. | Ты можешь сформулировать, когда counting лучше стандартного (рабочие нагрузки с частым удалением, где 4× пространства приемлемо), когда scalable лучше counting (неограниченный объём записи при фиксированном бюджете памяти), и когда cuckoo-фильтр лучше обоих (та же FP-rate при вдвое меньшем числе бит, O(1) удаление). Памятка о компромиссах называет конкретную систему (например, CDN negative-cache, фильтр чтения базы данных, конвейер дедупликации) для каждого варианта и объясняет, почему там стандартный фильтр неверен. |
Эталонный разбор (спойлер)
Почему отсутствие ложных отрицаний абсолютно, а не вероятностно: фильтр только устанавливает биты из 0 в 1, никогда из 1 в 0. Как только бит установлен, он остаётся установленным на всё время жизни фильтра, поэтому каждая битовая позиция, внесённая `add(s)`, навсегда остаётся равной 1. `has(s)` проверяет все k позиций на 1 — если хотя бы одна равна 0, эта позиция никогда не была установлена ни одним предыдущим add, поэтому s точно никогда не добавлялся. Случай FP — единственное неопределённое направление: все k позиций оказались равны 1 из-за других элементов.
Формула FP (1−e^{−kn/m})^k — приближение, предполагающее независимость позиций хешей; на практике с хорошим семейством хешей это плотно. Ключевой момент: показатель k·n/m — ожидаемое число раз, которое устанавливается любой данный бит; по мере роста этого отношения (насыщение фильтра) FP-rate стремится к 1. Именно поэтому fill ratio выше 0,5 — предупреждающий знак: при k=7 и fillRatio=0,5 FP-rate составляет примерно (0,5)^7 ≈ 0,78% — уже близко к бюджету 1% — а при fillRatio=0,7 превышает 1,6%.
Counting-фильтры платят 4× по пространству относительно стандартных фильтров (4-битные счётчики вместо 1-битных флагов), но дополнительные биты дают безопасное удаление. Опасность underflow счётчика реальна: удаление элемента, который никогда не добавлялся, декрементирует счётчик, установленный другим элементом, портя будущие запросы членства для того элемента. Производственные counting-фильтры должны либо обеспечивать инвариант (отслеживать членство внешне), либо документировать, что remove() может вызываться только для элементов, заведомо присутствующих.
Scalable-фильтр Блума обменивает ограниченную память на неограниченный бюджет вставок: каждый подфильтр нацелен на долю p₀·r^i общего FP-бюджета (r < 1, обычно 0,5), так что геометрический ряд суммируется до p₀/(1−r). Стоимость по пространству растёт логарифмически с n, а не линейно — это лучше, чем пересобирать больший статический фильтр, но хуже, чем единственный предварительно оптимизированный фильтр для предсказуемого n. Когда n известно, единственный оптимальный статический фильтр превосходит SBF как по пространству, так и по времени запроса.
Почему фильтры Блума появляются на системной границе, а не внутри неё: фильтр заменяет дорогостоящие проверки членства (поиск по диску, сетевой round trip, запрос к базе данных) дешёвой вероятностной предпроверкой, которая устраняет заведомых не-членов. FP-rate определяет, как часто дорогостоящая проверка всё же срабатывает для не-членов. При 1% FP-rate и 99% запросов к не-членам лишь 0,99% всех запросов уходят на дорогостоящий путь вместо 99% — сокращение в 100 раз. Это оправдано по пространству только если дорогостоящая проверка хотя бы в 100 раз медленнее проверки фильтра, что чтение с диска (100–10 000 мкс) почти всегда обеспечивает.
Сделай по-сеньорски
- Замени инъектируемые хеш-функции на double-hashing: генерируй все k позиций из двух базовых хешей h1 и h2 по формуле pos_i = (h1 + i*h2) % m. Покажи, что это столь же эффективно, как k независимых хешей для большого m, но стоит всего две оценки хеша на элемент, и сделай бенчмарк прироста пропускной способности на фильтре из 1М элементов.
- Реализуй cuckoo-фильтр как альтернативу и сравни его с фильтром Блума при той же вероятности ложных срабатываний: измерь биты/элемент, поддержку удалений и пропускную способность поиска. Покажи конкретный сценарий (высокая частота удалений, целевой FP < 3%), где cuckoo выигрывает по всем метрикам.
- Сделай scalable-фильтр пригодным для продакшена: сериализуй и десериализуй всю цепочку (битовые массивы + метаданные k/m) в Buffer, чтобы фильтр можно было сохранять между перезапусками. Убедись, что десериализованный фильтр даёт те же результаты has() и fillRatio, что и оригинал.
- Используй фильтр Блума для ускорения симулированного поиска по диску: элементы на «диске» дороги (симулированная задержка 1 мс); запросы, отбиваемые фильтром, отклоняются мгновенно; измерь сокращение симулированных дисковых I/O при 1% FP-rate против 0,1% и объясни компромисс задержки и пространства в коротком отчёте о производительности.