Probabilistic Data Structures Overview

Зачем

Когда поток событий мерится миллиардами в день, а вопрос про эти события сводится к «сколько уникальных», «видели ли X», «как часто встречается» или «какой p99» — точные структуры (HashSet, HashMap, sorted array) перестают помещаться в RAM ни одной разумной ноды.

• 1B уникальных users × 8 байт uint64 = 8 GB только под id, без overhead на pointers/strings.
• 100M distinct hashtags + counter = десятки GB на одном Flink job.
• Все latency samples за день для percentile = миллиарды float64 = немыслимо.

Дальше начинаются грязные паллиативы: шардировать RAM на сто нод, переливать в Redis cluster, поднимать ClickHouse на все запросы. Дорого, медленно, оперативно нагружено.

Probabilistic data structures (PDS, sketches) меняют точность на память на порядки: десятки KB на структуру вместо GB, с известной теоретической ошибкой (FPR 1%, ε relative error 0.81%). Дополнительно — почти все sketches streaming (single-pass, поток можно не перечитывать) и mergeable (склеить два sketch с разных нод в один союз).

Главный сигнал, что нужен sketch: «approximate is fine» + «размер растёт быстрее, чем RAM». Если оба true — берите sketch и экономьте порядок-два памяти и инфраструктуры.

Mental model

Sketch — это lossy compression для конкретного типа запроса. Ты не хранишь сырьё; ты хранишь ответ на «сколько уникальных», «видели ли», «как часто», «какой percentile» с известной погрешностью.

Выбор sketch начинается не с данных, а с вопроса. «Уникальные» → HyperLogLog. «Видели ли» → Bloom. «Сколько раз» / «top-K» → Count-Min Sketch. «Percentile» → t-digest. Структуру не подбирают под dataset — её подбирают под query.

Ключевые свойства, которые делают семейство практичным:

1. Bounded error — ошибка не «возможно» а измеряема и закладывается в design. Известна формулой, не наблюдается постфактум.
2. Sublinear или constant memory — HLL держит 12 KB на любую кардинальность от 100 до 10 миллиардов. Точная альтернатива линейна по N.
3. O(1) update — на каждое событие ~hash + bit/counter update. Можно держать в hot path streaming job без затыков.
4. Mergeable (почти все продакшен-sketches) — merge(A, B) даёт sketch союза множеств без re-aggregation сырья. Это критично для distributed compute: shard локально, merge на координаторе.
5. One-sided error у многих структур — Bloom никогда не даёт false negative («NO» = гарантия), CMS никогда не underestimate. Это разный риск-профиль, и его нужно осознанно класть в design.

Что на диаграмме

На канвасе — family overview: один клиент (event stream / query) подключён ко всем пяти каноническим sketches (Bloom, Cuckoo, HyperLogLog, Count-Min Sketch, t-digest) в одной группе и к трём exact baselines (HashSet, HashMap counter, sorted array) в другой. Цель раскладки — показать вопрос-в-вопрос: для каждого sketch внизу лежит exact-эквивалент, который пришлось бы заменить.

Edges подписаны интерфейсами: add / contains? для Bloom/Cuckoo, PFADD для HLL (Redis-style), inc(key) для CMS, add(value) для t-digest. Это API на стороне клиента — то, что разработчик реально пишет в job-е.

На ноде bloom висит ADR-001 — развёрнутое решение «Probabilistic vs Exact: когда менять точность на память». Это якорь страницы: переключение между семью сценариями player-а наполняет ADR конкретикой.

Сценарии

▶Walkthrough: overview (not found)

Family overview одной картинкой. Каждая структура отвечает на свой тип вопроса — пять разных вопросов, пять разных sketches. Закрепляем правило: выбор начинается с вопроса, не с данных. И финальный штрих — все пять mergeable, поэтому в distributed compute (Flink, Spark, ClickHouse coordinator) каждый shard строит локальный sketch, а координатор делает дешёвый merge без пересылки raw events.

▶Walkthrough: dedup-bloom (not found)

Bloom перед expensive lookup — самый канонический use case. Naive HashSet на 1B URLs × 32 байта = 32 GB, нерентабельно. Bloom при m = 10n, k = 7 укладывается в ~1.2 GB на 1B URLs с FPR 1%. Алгоритм lookup: 7 hash + 7 bit reads ~100ns. Если хоть один бит = 0 → «точно нет» (no false negative — гарантия). Если все 1 → «вероятно есть, проверь диск». Win — 99% reads отсеяны за 100ns probe вместо 150μs disk seek. Используется в Cassandra/RocksDB Bloom per SSTable, Chrome Safe Browsing, BigTable, Akamai cache. Если нужен delete (TTL/eviction) → Cuckoo filter: та же FPR, плюс deletion, ~25% меньше памяти на низких FPR.

▶Walkthrough: count-distinct-hll (not found)

HyperLogLog для cardinality — count distinct в постоянных 12 KB. Naive HashSet на 1B unique users = 16 GB на metric per day per dim — нерентабельно даже на жирных инстансах. HLL: hash(x) → первые p бит выбирают bucket, в остатке считаем leading zeros (rho); registers[bucket] = max(registers[bucket], rho). Update O(1). Estimate: α_m × m² × harmonic_mean(2^registers), O(m) на query. Размеры: m = 4096 → 3 KB → ε ≈ 1.6%; m = 16384 → 12 KB → ε ≈ 0.81%. Главное свойство: 100 событий, 1M, 1B — HLL остаётся constant 12 KB. Mergeable через element-wise max(A.registers, B.registers) → distributed rollup без raw events. Production: Redis PFCOUNT, BigQuery APPROX_COUNT_DISTINCT, ClickHouse uniqHLL12, Snowflake/Redshift, Druid.

▶Walkthrough: heavy-hitters-cms (not found)

Count-Min Sketch для top-K и frequency. Hot keys в кэше, top trending hashtags, DDoS top IPs. Naive HashMap{key → count} на 1B distinct keys × 32 байта = десятки GB. CMS: 2D матрица d rows × w columns; обычно d = 4, w = 2¹⁷ → ~2 MB. Update: для каждой row i инкрементируем matrix[i][hash_i(key) % w]. Query: count(key) = min(matrix[i][hash_i(key) % w]). CMS только overestimate — никогда не underestimate из-за collisions; для honest top-K это терпимо. Trick для top-K: CMS + min-heap размером K хранит текущие лидеры без точного хранения всех counters. Production: Cloudflare DDoS top-K queries, hot key detection в Redis cluster, trending hashtags. Современные варианты — HeavyKeeper / SpaceSaving — дают лучшую точность.

▶Walkthrough: percentile-tdigest (not found)

t-digest для percentile (p50/p95/p99/p999). Naive sorted array всех samples — O(N) memory, O(log N) insert; не масштабируется на streaming. t-digest: иерархические centroid clusters с variable resolution (плотно на хвостах, разреженно в середине). Add: insert sample → merge в ближайший centroid если capacity позволяет. Query: quantile(q) = интерполяция centroids по cumulative weight. Размер ~5 KB per sketch (compression=100), bounded relative error 1-2%. Killer feature: точнее на p99/p999, чем в середине — ровно то, что нужно для SLA monitoring. Mergeable: sum centroids → service mesh aggregation per region. Production: Datadog APM percentiles, Elastic, ClickHouse quantileTDigest, AWS CloudWatch, Druid. Альтернатива — DDSketch (Datadog): bounded relative error guarantee.

▶Walkthrough: compare-tradeoffs (not found)

Trade-offs всех пяти одной таблицей: space, time, accuracy, mergeable. Правило выбора: «видели ли» → Bloom/Cuckoo; «сколько уникальных» → HLL; «сколько раз / top-K» → CMS; «p99» → t-digest. Anti-patterns: точность критична (финансы) → НЕ probabilistic; маленький dataset → overhead не оправдан. И финал: эти структуры стакаются. Реальный Flink job для site analytics держит Bloom для dedup + HLL для unique visitors + CMS для top hot keys + t-digest для percentile latency — всё в одной machine state, всё mergeable между shards.

Trade-offs (ADR развёрнуто)

ADR-001 на ноде bloom фиксирует решение «probabilistic vs exact». Распакуем компоненты.

Контекст. Точные структуры (HashSet, HashMap, sorted index) дают exact answer, но требуют память O(N). На масштабах billions per day:

• HashSet на 1B unique strings × 32 байта = 32 GB на ноду только под id.
• HashMap{key → count} на 1B distinct keys = десятки GB.
• sorted array всех latency samples за день = миллиарды float64.

Точные структуры не mergeable в общем случае — distributed aggregation требует пересылки raw данных между shards. Streaming use case (Kafka → Flink job) физически не может re-read поток для второго прохода.

Решение. Использовать probabilistic data structures когда: (1) кардинальность велика (>10M элементов на dimension), (2) допустима известная ошибка (1% FPR / 0.81% relative error), (3) нужен mergeable property для distributed compute, (4) streaming single-pass. Выбор внутри family строго по вопросу:

Вопрос	Sketch	Размер	Ошибка	Mergeable
«Видели ли X?»	Bloom	~10 bits/element для ε=1%	FPR, no false negative	OR
«Видели X? + delete»	Cuckoo	~7 bits/element для ε=1%	FPR + occasional evict fail	union (сложнее)
«Сколько уникальных?»	HyperLogLog	12 KB const	ε ≈ 1.04/√m ≈ 0.81%	element-wise max
«Сколько раз X встречался?»	Count-Min Sketch	~2 MB (d=4, w=2¹⁷)	only overestimate	element-wise sum
«Какой p99?»	t-digest	~5 KB per sketch	1-2% relative, точнее на хвостах	merge centroids

Что получаем. Память сокращается на 2-3 порядка: 32 GB HashSet → 12 KB HLL (500 000×), 30 GB HashMap counter → 2 MB CMS (15 000×). Update в hot path — O(1) на event. Distributed rollup — дешёвый merge вместо передачи raw events. Streaming single-pass работает «бесплатно».

Что платим. Известная ошибка (1% FPR / 0.81% relative) — это дизайн-параметр, не баг. Нужно осознанно положить её в SLO: «counter может быть ±1%». Для finance/medical/regulatory это запрещено. Некоторые структуры one-sided (Bloom only false positive, CMS only overestimate) — нужно правильно интерпретировать «NO»/«небольшое значение». Параметры (m, k, d, w, compression) выбираются заранее, ошибка в n (ожидаемая мощность) на 2× раздувает реальную ε.

Production референсы. Cassandra и RocksDB — Bloom per SSTable. Redis — HLL/Bloom/Cuckoo first-class. ClickHouse — uniqHLL12 + quantileTDigest + bloom_filter index. BigQuery — APPROX_COUNT_DISTINCT / APPROX_QUANTILES / APPROX_TOP_COUNT. Datadog / Prometheus exemplars — t-digest для APM percentiles. Druid — sketches first-class в столбцах (HLL, Theta, Quantiles). Apache DataSketches (Yahoo) — каноническая production library.

Реальные системы

• Google Bigtable — Bloom per SSTable, paper OSDI 2006. Канонический референс паттерна skip-expensive-lookup.
• Apache Cassandra — Bloom per SSTable, Merkle trees для anti-entropy repair, Count-Min Sketch внутри row cache eviction. Ручка bloom_filter_fp_chance per table.
• Redis — HyperLogLog (PFADD/PFCOUNT/PFMERGE), Bloom filter (BF.RESERVE/BF.ADD/BF.EXISTS), Cuckoo filter, Count-Min Sketch, Top-K (HeavyKeeper) — всё через RedisBloom module.
• ClickHouse — uniqHLL12, quantileTDigest, quantileTDigestWeighted, bloom_filter index, tokenbf_v1 для full-text-prefilter.
• BigQuery — APPROX_COUNT_DISTINCT (HLL++), APPROX_QUANTILES (KLL), APPROX_TOP_COUNT (SpaceSaving).
• Snowflake — Bloom + Cuckoo filters per micro-partition для skip при query pruning.
• Druid — HLL, Theta sketch, Quantiles sketch first-class в column store.
• Apache DataSketches (Yahoo) — production-grade library: HLL, Theta (set ops), KLL (quantiles), Frequent Items, Tuple sketches.
• Cloudflare — Count-Min Sketch для top-K DNS queries и DDoS detection.
• Akamai — Bloom filter перед origin для cache miss optimization (~10% origin traffic).
• Chrome Safe Browsing — клиентский Bloom для known-malicious URLs; positive → API call в Google, negative → пропускаем молча.
• Bitcoin SPV (BIP 37) — клиент шлёт Bloom фул-ноде, та фильтрует irrelevant tx. Спойлер: privacy issue, deprecated в bitcoin core.
• Ethereum — каждый блок содержит 2048-bit bloom для logs; clients ищут блоки с relevant events без full scan.
• Datadog / Prometheus exemplars / AWS CloudWatch — t-digest или DDSketch для APM percentile aggregation per region.
• Apache Spark / Flink — HLL и CMS в built-in aggregations (approx_count_distinct, frequency counting).

Anti-patterns

• Использовать sketch там, где нужна exact accuracy. Финансовые транзакции, инвентарь, бронирование, медицинские данные, регуляторные отчёты — 1% FPR / 1% relative error означает 1% ошибочных списаний / двойных бронирований / искажённых отчётов. Используйте exact structures с unique constraints.
• Sketch на маленьком dataset (<10K элементов). Overhead конструкции, hash вычислений, cache misses не оправдан. HashSet/HashMap выиграют по памяти и скорости. Sketch начинает побеждать с миллионов элементов.
• Игнорировать one-sided error при интерпретации. Bloom NEVER false negative — «NO» = гарантия. Если код трактует «YES» как гарантию, логика сломана. CMS никогда не underestimate — если код ожидает точное значение, а не верхнюю границу, тоже сломано.
• Неправильно выбранные параметры n/m/k. Промах в 2× по ожидаемой мощности раздувает FPR/ε в разы. Например, Bloom рассчитан на 100M, а реально вставили 200M — FPR с 1% уезжает к 10-30%.
• bloom_filter_fp_chance = 0 в Cassandra. Это выключает bloom (FPR 100%, всегда seek), а не делает его идеальным. Частая ошибка.
• Sketch в DB как BLOB с lookup'ом через query. SQL round-trip на каждый probe убивает win. Sketch должен жить в RAM процесса, который его проверяет.
• Adversarial input на known hash seeds. Если злоумышленник знает seed, может сконструировать ключи с гарантированным FPR (Bloom DoS) или искажённой top-K (CMS poisoning). Защита — keyed hash (SipHash) или Cuckoo с random seeds.
• Несовместимый merge. Sketches mergeable только если построены с одинаковыми параметрами (m, k, hash functions, seeds). Попытка merge HLL с разным p или CMS с разной w даст мусор.
• Sketch вместо range query / sort. Sketches про set / frequency / cardinality, не про порядок. «Топ 100 по value» через CMS = ок. «Все элементы между X и Y» — нужен tree/index, не sketch.
• Не мониторить fill rate. Bloom при n_actual >> n_design или CMS при сильно превышенной нагрузке деградируют. Без алертов на FPR / ε ошибка незаметно уезжает.

Когда НЕ использовать

Sketch — не серебряная пуля. Не берите его, если:

• Точность критична — финансы, медицина, регуляторика, инвентарь, бронирование. Exact structures (HashSet, B-tree, unique constraint).
• Dataset мал (<10K элементов на dimension). HashSet/HashMap проще и быстрее.
• Нужны range queries / sort / порядок. Sketches не сохраняют порядок. Берите tree/skip list/sorted index.
• Нужен payload, а не aggregate. Sketch отвечает yes/no, count, cardinality, percentile — не возвращает исходные элементы. Если нужно «достать обратно» — нужен ассоциативный store.
• Adversarial input при отсутствии keyed hash. Открытый bloom выдаёт паттерн интересов (BIP 37 privacy issue). Открытый CMS можно poison-нуть. Если защита от атаки критична и нет keyed hash — exact.
• Workload mostly-positive для Bloom. Win Bloom — на mostly-negative нагрузке (отсев expensive lookup). Если 99% запросов реально найдены, Bloom только добавляет latency.
• Real-time exact percentile required (не «approximate fine»). Например, регуляторный SLA по точному p99.9 — нужно sorted array или приближение с гарантированно меньшей ошибкой (KLL с заданным bound).

Дальше читать

Концепты и кейсы в курсе:

• [CONCEPT]bloom-filters — глубже про membership: формулы FPR, tuning, scalable bloom, Counting Bloom, конкретный LSM-tree use case.
• [CONCEPT]hyperloglog — глубже про cardinality: registers, harmonic mean, HLL++ bias correction, merge.
• [CONCEPT]count-min-sketch — глубже про frequency: матрица, top-K через min-heap, HeavyKeeper.
• [CONCEPT]cuckoo-filters — Bloom с deletion: cuckoo hashing, fingerprints, evict failure.
• [CONCEPT]merkle-trees — identity check / diff (probabilistic в hash-collision смысле).
• [CONCEPT]caching-strategies — Bloom как gate перед cache.

Foundational papers:

• Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors (1970) — оригинал Bloom filter, ACM DL.
• Flajolet et al., HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (2007) — INRIA PDF.
• Cormode & Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch and its Applications (2005).
• Fan et al., Cuckoo Filter: Practically Better Than Bloom (2014).
• Dunning, Computing Extremely Accurate Quantiles Using t-Digests (2019).

Production docs и libraries:

• Apache DataSketches — production-grade Yahoo library.
• RedisBloom commands — managed API для Bloom/Cuckoo/HLL/CMS/Top-K.
• RocksDB Bloom Filter wiki — реальные tuning recipes.
• ClickHouse uniqHLL12 / quantileTDigest — production reference.
• BigQuery APPROX_* functions.

Книги:

• Andrii Gakhov, Probabilistic Data Structures and Algorithms for Big Data Applications (2019) — современный systematic обзор всех структур.
• Leskovec, Rajaraman, Ullman, Mining of Massive Datasets — Ch. 3-4 про sketching в stream processing.
• Kleppmann, Designing Data-Intensive Applications, Ch. 3 — упоминание Bloom в LSM context.

Talks и tutorials:

• Andy Pavlo CMU DB lectures — sketching topic в курсе Database Systems.
• Strata / Velocity recordings про analytics sketches.
• "Sketch of the Day" series — AK Tech blog (исторический), https://research.neustar.biz/category/sketch-of-the-day/.