Bloom filters в LSM read path

Bloom filter отвечает на membership query двумя результатами:

• definitely absent — authoritative lookup можно пропустить;
• possibly present — authoritative lookup обязателен.

При корректном построении стандартный Bloom filter не даёт false negative для вставленного элемента, но допускает false positive. Это свойство не переживает произвольное удаление битов: один bit может принадлежать множеству keys. Для delete нужны immutable rebuild, tombstones или другая структура, например counting variant с собственными trade-offs.

Per-SSTable, не global selector

LSM read path сначала проверяет memtable и другие mutable structures. Затем для каждого candidate SSTable проверяется его filter. Negative пропускает конкретный file; positive разрешает index/data lookup. Один global filter «key где-то существует» не говорит, какой SSTable читать.

Сценарии

Оба file filters говорят no — оба SSTable data reads пропущены. Проверка memtable остаётся обязательной, иначе свежая запись могла бы стать ложным negative всей системы.

Positive Bloom result — лишь candidate. SSTable index/data подтверждает key и возвращает value с учётом sequence/tombstone semantics storage engine.

False positive тратит CPU/IO/latency, но authoritative lookup сохраняет correctness. Поэтому target FPR выбирают из negative lookup rate, RAM и стоимости IO.

Для ideal independent hashes p ≈ (1 - e^(-kn/m))^k, optimal k ≈ (m/n) ln 2. При m/n=10 получаем k≈6.93 и p≈0.0082, около 0.82%. Это модель, а не guarantee конкретной hash implementation.

Один миллиард элементов × 10 bits = 10 billion bits = 1.25 billion bytes ≈ 1.16 GiB до metadata/alignment. Не путайте decimal GB и binary GiB.

Cassandra lifecycle

bloom_filter_fp_chance задаёт target probability и влияет на размер filter. Более низкое значение требует больше памяти. ALTER меняет новые SSTable filters; существующие файлы получают новый filter после rewrite/compaction. Это не мгновенный глобальный switch.

Связанные темы

[CONCEPT]performance-vs-scalability

[CONCEPT]capacity-planning-deep

Первичные источники

• Bloom 1970: https://doi.org/10.1145/362686.362692
• Cassandra Bloom filters: https://cassandra.apache.org/doc/latest/cassandra/managing/operating/bloom_filters.html
• Cassandra CQL table options: https://cassandra.apache.org/doc/latest/cassandra/developing/cql/ddl.html