Вероятностные структуры: Bloom filter, HyperLogLog, Count-Min Sketch

Все структуры, которые мы разбирали до сих пор, объединяет одно свойство: они точны. Хеш-таблица либо содержит ключ, либо нет. Дерево отрезков возвращает ровно ту сумму, что лежит на отрезке. За точность приходится платить памятью — минимум порядка объёма самих данных.

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

Статья предполагает, что вы понимаете хеш-функции и требования к ним и модель стоимости с амортизацией.

Зачем вообще жертвовать точностью

Разберём конкретную задачу, чтобы почувствовать масштаб. Веб-сервис хочет знать: сколько уникальных посетителей было сегодня? Событий — 5 млрд, уникальных ID — около 300 млн, каждый ID это UUID (16 байт).

• Точное решение — множество. HashSet на 300 млн 16-байтовых ключей: сами ключи 4.8 ГБ, плюс накладные расходы таблицы (указатели, хеши, load factor) — в реальности 15–40 ГБ. Считать нужно ещё и по 200 сегментам (страна × устройство × канал) — умножаем.
• HyperLogLog — 12 КиБ на сегмент, 2.4 МБ на все 200. Ошибка ~0.8 %.

Разница в шесть порядков. Вопрос «а нужна ли нам точность до одного человека в числе 300 млн» после этого отвечает сам себя: 300 041 232 и 302 500 000 приведут к одному и тому же продуктовому решению. Это и есть главный критерий применимости: вероятностные структуры уместны там, где ответ используется для принятия решения с грубой гранулярностью, или там, где ошибка исправляется на следующем шаге. И категорически неуместны там, где ответ — это факт (баланс счёта, права доступа, начисление денег).

Формально почти все эти структуры решают задачи из модели потоковой обработки (streaming): элементы приходят по одному, памяти сильно меньше, чем элементов, каждый элемент можно посмотреть один раз. В этой модели точные ответы на большинство вопросов доказуемо требуют Ω(n) памяти — поэтому приближение это не лень, а единственный выход.

Три структуры из заголовка — базовые представители первых трёх ветвей. Разобравшись с ними, остальные читаются как вариации.

Bloom filter: «точно нет» или «возможно, да»

Интуиция

Задача: поддерживать множество и отвечать на вопрос «есть ли здесь x?», не храня сами элементы. Идея Бёртона Блума (1970): возьмём битовый массив длины m, изначально нулевой, и k независимых хеш-функций. Чтобы добавить элемент — посчитаем k хешей и выставим k соответствующих битов в единицу. Чтобы проверить — посчитаем те же k хешей и посмотрим на биты.

• Хотя бы один бит нулевой → элемента точно нет. Потому что если бы его добавляли, все его биты стояли бы.
• Все биты единичные → элемент возможно есть. Возможно — потому что эти биты могли выставить другие элементы, каждый свой.

Асимметрия ошибок фундаментальна: ложноотрицательных ответов не бывает никогда, ложноположительные бывают с контролируемой вероятностью. Именно эта асимметрия делает структуру полезной: Bloom filter ставят перед дорогой проверкой как дешёвый фильтр, отсеивающий заведомые промахи.

Псевдокод

ADD(x):
    for i = 1..k:
        bits[ h_i(x) mod m ] = 1

CONTAINS(x):
    for i = 1..k:
        if bits[ h_i(x) mod m ] == 0:
            return NO            # гарантированно нет
    return MAYBE                 # возможно есть

Математика: сколько бит и сколько хешей

Это редкий случай, когда параметры структуры выводятся аналитически, а не подбираются. Вероятность, что конкретный бит остался нулевым после n вставок по k хешей (всего kn установок бита), равна (1 − 1/m)^(kn) ≈ e^(−kn/m). Ложноположительный ответ — это когда все k проверяемых битов оказались единицами:

p ≈ (1 − e^(−kn/m))^k

Минимизируя по k (дифференцируем логарифм), получаем оптимальные параметры:

k_opt = (m/n)·ln 2 ≈ 0.693·(m/n)
m     = −n·ln p / (ln 2)² ≈ 1.44·n·log₂(1/p)

Три следствия, которые стоит запомнить наизусть:

1. При оптимальном k ровно половина битов единичные. Это удобный признак здоровья фильтра в проде: если единиц заметно больше 50 % — фильтр переполнен, ошибка уже выше проектной.
2. Стоимость ~1.44·log₂(1/p) бит на элемент, независимо от размера элемента. 1 % ошибки → ~9.6 бита на элемент; 0.1 % → ~14.4 бита. Хранить ли 16-байтовые UUID или 200-байтовые URL — не важно, цена одна.
3. Теоретический минимум для такой задачи — log₂(1/p) бит на элемент, то есть Bloom проигрывает оптимуму примерно 44 % (Carter et al., 1978; Pagh, Pagh & Rao, SODA 2005). Именно этот зазор закрывают cuckoo- и ribbon-фильтры.

Обратите внимание: m зависит от ожидаемого n. Bloom filter не умеет расти — при превышении n ошибка растёт катастрофически быстро, а сообщить о переполнении он не может. Ёмкость нужно планировать заранее (или использовать scalable-варианты, см. ниже).

Реализация

Наивная реализация требует k независимых хеш-функций — это дорого. Кирш и Митценмахер показали (Less Hashing, Same Performance, 2008), что достаточно двух хешей, а остальные получаются линейной комбинацией g_i(x) = h₁(x) + i·h₂(x), — асимптотически ложноположительная вероятность не ухудшается. Это стандартный приём во всех промышленных реализациях.

import math
import hashlib


class BloomFilter:
    """Классический фильтр Блума с двойным хешированием (Kirsch–Mitzenmacher)."""

    def __init__(self, capacity: int, error_rate: float = 0.01):
        # m = -n·ln(p) / (ln 2)^2 — оптимальное число бит
        self.m = max(8, math.ceil(-capacity * math.log(error_rate) / (math.log(2) ** 2)))
        # k = (m/n)·ln 2 — оптимальное число хеш-функций
        self.k = max(1, round((self.m / capacity) * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)   # ceil(m/8) байт
        self.capacity = capacity
        self.count = 0

    def _positions(self, key: bytes):
        """Один вызов blake2b даёт 128 бит; режем на два независимых хеша."""
        digest = hashlib.blake2b(key, digest_size=16).digest()
        h1 = int.from_bytes(digest[:8], "little")
        h2 = int.from_bytes(digest[8:], "little") | 1   # нечётность: h2 != 0
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, key: bytes) -> None:
        for pos in self._positions(key):
            self.bits[pos >> 3] |= 1 << (pos & 7)      # pos // 8, pos % 8
        self.count += 1

    def __contains__(self, key: bytes) -> bool:
        # all() выходит на первом нулевом бите — промах обычно дешевле попадания
        return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self._positions(key))

    def health(self) -> tuple[float, float]:
        """Диагностика для мониторинга: (текущая вероятность FP, доля единичных бит).
        У здорового фильтра на проектной ёмкости доля единиц ≈ 0.5."""
        fp = (1 - math.exp(-self.k * self.count / self.m)) ** self.k
        return fp, sum(bin(b).count("1") for b in self.bits) / self.m

Сложность. add и contains — O(k) операций, то есть O(1) относительно n, и это честная константа, а не амортизация. Память — O(m) = O(n·log(1/p)) бит. На практике k обычно 3–10. Но есть нюанс производительности, не видный в асимптотике: k случайных обращений к битовому массиву — это до k промахов кэша. Для фильтра на 100 МБ каждая проверка стоит ~7 обращений в DRAM. Решение — blocked Bloom filter: сначала одним хешем выбираем блок размером с кэш-линию (64 байта), и все k бит ставим внутри него. Один промах кэша вместо семи, ценой чуть худшей ложноположительной вероятности (Putze, Sanders & Singler, 2007). Так устроены фильтры в RocksDB, Impala, ClickHouse.

Что фильтр Блума не умеет

Удалять. Погасить биты нельзя: они общие с другими элементами, и сброс создал бы ложноотрицательные ответы — а это разрушает единственную твёрдую гарантию структуры. Обходные пути:

• Counting Bloom filter — вместо бит счётчики по 4 бита; add инкрементирует, remove декрементирует. Память ×4, и счётчик может переполниться (при 4 битах — на 16, что редко, но возможно; после переполнения счётчик «залипает»).
• Cuckoo filter (Fan et al., CoNEXT 2014) — хранит короткие отпечатки (fingerprints) в кукушкиной хеш-таблице с двумя позициями. Поддерживает удаление, локален по памяти, и при p < 3 % занимает меньше места, чем Bloom. Плата: вставка может провалиться при высокой заполненности, а удалять можно только реально вставленные элементы.

Считать элементы, объединять фильтры разной конфигурации, перечислять содержимое. Объединение (OR битов) и пересечение (AND) работают только при одинаковых m и k; причём AND даёт фильтр с ложноположительной вероятностью выше, чем у честного фильтра пересечения — частая ошибка. Расти. Если n заранее неизвестно, берут Scalable Bloom Filter: цепочку фильтров с геометрически убывающей допустимой ошибкой, где при переполнении добавляется новый уровень, а проверка идёт по всем уровням.

Эта схема — суть всех продовых применений: корректность обеспечивает источник, фильтр отвечает только за экономию. Если у вас нет такого «источника истины» за фильтром, дважды подумайте, можно ли вообще применять Bloom.

HyperLogLog: мощность множества за 12 килобайт

Интуиция: длина серии нулей как счётчик

Как оценить количество различных элементов, ничего не храня? Возьмём хорошую хеш-функцию — её выход выглядит как равномерно случайные биты, и вероятность, что хеш начинается ровно с j нулей, равна 2^(−j−1). Значит, если среди всех увиденных хешей максимальная серия ведущих нулей равна R, то мы, скорее всего, видели около 2^R различных элементов. Повторы не влияют: одинаковый элемент даёт одинаковый хеш и не меняет максимум. Это уже даёт оценку мощности за O(log log n) бит — отсюда и название семейства.

Аналогия: человек рассказывает, что подбрасывал монету и максимальная серия «орлов подряд» была 10 — вы оцениваете число серий примерно в 2¹⁰ ≈ 1000, не зная самих бросков, только рекорд. Проблема ровно там же, где и в аналогии: дисперсия чудовищная, одна «удачливая» строка сдвигает оценку вдвое. Флажоле и Мартин (1985) предложили усреднять по многим независимым наблюдателям.

Стохастическое усреднение и гармоническое среднее

Вместо k хеш-функций (дорого) используем один хеш и делим его битовую строку: старшие p бит — номер «наблюдателя» (регистра), остальные — материал для подсчёта нулей. Получаем m = 2^p подпотоков, каждый со своим максимумом. Это стохастическое усреднение.

Прорыв HyperLogLog (Flajolet, Fusy, Gandouet, Meunier, 2007) — усреднять не арифметически, а гармонически:

E = α_m · m² / Σ_{j=1..m} 2^(−M[j])

Гармоническое среднее подавляет выбросы (один аномально большой регистр почти не влияет на сумму обратных величин), и стандартная ошибка падает до 1.04/√m. Отсюда таблица параметров — по ней и выбирают p в проде:

Каждый регистр хранит максимум ρ, а ρ для 64-битного хеша не превышает ~64 — влезает в 6 бит. Память не зависит от мощности вообще: 12 КиБ считают и тысячу, и десять миллиардов уникальных значений.

Реализация

import math
import hashlib


class HyperLogLog:
    """HyperLogLog на 64-битном хеше с linear counting для малых мощностей."""

    def __init__(self, p: int = 14):
        assert 4 <= p <= 18, "p вне разумного диапазона"
        self.p = p
        self.m = 1 << p
        self.reg = bytearray(self.m)          # по байту на регистр (учебно; в проде 6 бит)
        self.q = 64 - p                       # сколько бит остаётся под ρ
        # Константа смещения α_m из статьи Flajolet et al.
        self.alpha = {16: 0.673, 32: 0.697, 64: 0.709}.get(
            self.m, 0.7213 / (1 + 1.079 / self.m)
        )

    def add(self, key: bytes) -> None:
        x = int.from_bytes(hashlib.blake2b(key, digest_size=8).digest(), "little")
        j = x >> self.q                        # старшие p бит — номер регистра
        w = x & ((1 << self.q) - 1)            # младшие q бит — «хвост»
        # ρ = позиция первой единицы в хвосте, считая слева от 1
        rho = (self.q - w.bit_length() + 1) if w else (self.q + 1)
        if rho > self.reg[j]:                  # регистр хранит МАКСИМУМ
            self.reg[j] = rho

    def count(self) -> int:
        z = sum(2.0 ** -r for r in self.reg)   # сумма обратных величин
        estimate = self.alpha * self.m * self.m / z
        zeros = self.reg.count(0)
        # На малых мощностях "сырая" оценка сильно смещена — переключаемся
        # на linear counting: считаем по доле пустых регистров.
        if zeros > 0 and estimate <= 2.5 * self.m:
            return round(self.m * math.log(self.m / zeros))
        return round(estimate)

    def merge(self, other: "HyperLogLog") -> None:
        """Объединение множеств = поэлементный максимум регистров."""
        assert self.p == other.p, "нельзя объединять HLL с разными p"
        for j in range(self.m):
            if other.reg[j] > self.reg[j]:
                self.reg[j] = other.reg[j]

Сложность. add — O(1) (один хеш, одно чтение, одна запись). count — O(m), но m константа и считается редко; в проде оценку кешируют и пересчитывают лениво. merge — O(m).

Свойство, ради которого HLL и живёт в аналитике

merge — поэлементный максимум — делает HLL коммутативным, ассоциативным и идемпотентным моноидом. Практические следствия огромны:

• Считаем HLL по часам — можем сложить в сутки, в месяц, в год. Без пересчёта сырых данных.
• Считаем HLL на 500 машинах независимо — сливаем в одну без координации. Идеальный reduce в MapReduce/Spark.
• Повторная обработка того же батча (retry, at-least-once доставка) не искажает результат — идемпотентность.

Ни HashSet, ни семплирование такого набора свойств не дают. Именно поэтому HLL — стандартный тип в аналитических хранилищах, а не экзотика.

Чего HLL не умеет

• Пересекать множества точно. Формально |A ∩ B| = |A| + |B| − |A ∪ B|, и все три слагаемых HLL даёт. Но это разность близких больших чисел: если A и B по 100 млн с ошибкой 0.8 % (±800 тыс.), а пересечение реально 1 млн — ошибка перекрывает ответ целиком. Никогда не считайте пересечение через inclusion-exclusion на HLL. Для этого берут Theta sketch из Apache DataSketches: он поддерживает и разности, и пересечения с осмысленными границами ошибки.
• Убирать элементы — максимум не откатывается. И отвечать на «а был ли элемент x»: HLL хранит мощность, не принадлежность; для этого — Bloom.
• Давать гарантию на конкретный запрос. 0.81 % — это стандартное отклонение, а не жёсткая граница: примерно в 5 % случаев ошибка превысит 1.6 %, и это нормально. Не стройте алертов на «дельта HLL больше 1 %».

HLL++ и что реально стоит в проде

Google в статье HyperLogLog in Practice (EDBT 2013) описал набор инженерных доработок, ставших де-факто стандартом:

• 64-битный хеш вместо 32-битного — снимает коррекцию для больших мощностей и коллизии хешей при n > 10⁹.
• Эмпирическая коррекция смещения вместо грубого порога linear counting — таблицы поправок, снятые с симуляций.
• Разреженное представление: пока уникальных мало, хранится не массив регистров, а компактный отсортированный список пар (индекс, ρ). Пустой HLL занимает десятки байт, а не 12 КиБ. Именно поэтому в Redis PFADD на новом ключе почти ничего не стоит по памяти — переход к плотному представлению происходит автоматически (antirez о реализации).

Count-Min Sketch: частоты в потоке

Задача

Bloom отвечает «есть/нет», HLL — «сколько всего разных». Третий типовой вопрос: сколько раз встречался элемент x? И производный от него, обычно более ценный: какие элементы встречаются чаще всего (heavy hitters, top-k). Точный ответ — счётчик на каждый ключ, то есть память O(числа различных ключей). В потоке из IP-адресов, поисковых запросов или URL это неприемлемо.

Устройство

Count-Min Sketch (Cormode & Muthukrishnan, 2005) — двумерная таблица счётчиков d × w и d независимых хеш-функций, по одной на строку.

• add(x, c): в каждой строке i прибавляем c к ячейке [i][h_i(x)].
• estimate(x): берём минимум по всем строкам.

Почему минимум работает. Каждая ячейка содержит настоящую частоту x плюс «шум» от всех ключей, столкнувшихся с ним в этой строке. Шум всегда неотрицателен (для потоков без удалений), поэтому любая ячейка — оценка сверху. Минимум — наименее зашумлённая из d оценок. Вероятность, что все d строк оказались зашумлёнными одновременно, экспоненциально мала по d.

Гарантия формулируется так: при w = ⌈e/ε⌉ и d = ⌈ln(1/δ)⌉

f(x) ≤ f̂(x) ≤ f(x) + ε·‖f‖₁     с вероятностью не менее 1 − δ

где ‖f‖₁ — суммарное количество всех обработанных элементов. Читать это надо внимательно: ошибка пропорциональна размеру всего потока, а не частоте конкретного ключа. Для ключа с частотой в миллион при потоке в миллиард и ε = 0.001 добавка доходит до миллиона — то есть оценка может удвоиться; для ключа с частотой 5 оценка вообще бессмысленна. Отсюда главный вывод: CMS хорош для тяжёлых элементов и бесполезен для хвоста распределения. Это не дефект реализации, это ровно то, что структура обещает.

Реализация

import math
import hashlib
import heapq


class CountMinSketch:
    """Count-Min Sketch: оценка частот сверху с гарантией eps * N при вероятности 1-delta."""

    def __init__(self, epsilon: float = 1e-4, delta: float = 1e-5):
        self.w = math.ceil(math.e / epsilon)      # ширина: точность
        self.d = math.ceil(math.log(1 / delta))   # глубина: надёжность
        self.table = [[0] * self.w for _ in range(self.d)]
        self.total = 0                            # ||f||_1

    def _columns(self, key: bytes):
        digest = hashlib.blake2b(key, digest_size=16).digest()
        h1 = int.from_bytes(digest[:8], "little")
        h2 = int.from_bytes(digest[8:], "little") | 1
        return [(h1 + i * h2) % self.w for i in range(self.d)]

    def add(self, key: bytes, count: int = 1) -> None:
        self.total += count
        for row, col in enumerate(self._columns(key)):
            self.table[row][col] += count

    def add_conservative(self, key: bytes, count: int = 1) -> None:
        """Conservative update: поднимаем счётчики только до нужного минимума.
        Гарантия сверху сохраняется, а фактическая ошибка заметно меньше."""
        cols = self._columns(key)
        current = min(self.table[r][cols[r]] for r in range(self.d))
        self.total += count
        target = current + count
        for r in range(self.d):
            if self.table[r][cols[r]] < target:
                self.table[r][cols[r]] = target

    def estimate(self, key: bytes) -> int:
        return min(self.table[r][c] for r, c in enumerate(self._columns(key)))

    # Слияние скетчей одинаковой геометрии — поячеечное сложение таблиц,
    # поэтому CMS так же удобен в MapReduce, как HLL.


class HeavyHitters:
    """CMS не помнит ключи — top-k требует отдельной кучи кандидатов."""

    def __init__(self, k: int, sketch: CountMinSketch):
        self.k, self.sketch = k, sketch
        self.heap: list[tuple[int, bytes]] = []   # min-heap по оценке
        self.in_heap: set[bytes] = set()

    def offer(self, key: bytes, count: int = 1) -> None:
        self.sketch.add_conservative(key, count)
        est = self.sketch.estimate(key)
        if key in self.in_heap:                    # обновляем оценку на месте
            self.heap = [(est, k) if k == key else (e, k) for e, k in self.heap]
            heapq.heapify(self.heap)
        elif len(self.heap) < self.k:
            heapq.heappush(self.heap, (est, key)); self.in_heap.add(key)
        elif est > self.heap[0][0]:                # вытесняем самого лёгкого
            _, evicted = heapq.heapreplace(self.heap, (est, key))
            self.in_heap.discard(evicted); self.in_heap.add(key)

    def top(self) -> list[tuple[bytes, int]]:
        return [(k, e) for e, k in sorted(self.heap, reverse=True)]

Сложность. add и estimate — O(d), то есть O(log(1/δ)) и константа относительно потока. Память — O(w·d) = O((1/ε)·log(1/δ)) счётчиков. При ε = 10⁻⁴, δ = 10⁻⁵: w ≈ 27 183, d = 12 → ~326 тыс. счётчиков (2.6 МБ при 8 байтах, 1.3 МБ при 4). Заметьте: точность стоит линейно, надёжность — логарифмически. Увеличивать d дёшево, w — дорого; типичная ошибка новичка — раздувать d до 20 «для надёжности», не тронув w, и удивляться, что ошибка не упала.

Родственники и когда какой

• Conservative update (в коде выше) — не увеличивает счётчик выше необходимого. Ломает часть теоретического анализа, но на практике снижает ошибку в разы. Используется почти везде.
• Count-Sketch (Charikar, Chen, Farach-Colton, 2002) — вместо +1 прибавляет ±1 по второй хеш-функции, а оценка берётся как медиана. Оценка несмещённая (может быть и меньше, и больше), а ошибка масштабируется как ε·‖f‖₂, а не ‖f‖₁. При тяжёлом хвосте (‖f‖₂ ≪ ‖f‖₁) это существенно точнее. Плюс Count-Sketch корректно работает с удалениями (turnstile-поток), а CMS с удалениями теряет гарантию «оценка сверху».
• Space-Saving — не скетч, а алгоритм с ограниченным словарём; для чистой задачи top-k обычно точнее CMS при той же памяти, и RedisBloom TOPK реализует именно его. Правило выбора: «покажи 100 самых частых запросов» → Space-Saving; оценки частот произвольных ключей и слияние скетчей с разных узлов → CMS.

Сравнение и выбор

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

Алгоритм выбора, если коротко:

1. Нужен точный ответ или ответ определяет деньги/доступ? → точная структура (хеш-таблица, дерево Фенвика), скетчи не рассматриваем.
2. Данные помещаются в память с запасом ×3? → точная структура. Скетч усложняет систему, и оправдан только когда точный вариант не помещается или не масштабируется.
3. Вопрос «видел ли я это раньше», и есть куда сходить за истиной при «да»? → Bloom / Cuckoo.
4. Вопрос «сколько разных», нужна агрегация по срезам и времени? → HyperLogLog.
5. Вопрос «кто самый частый»? → Space-Saving или CMS + куча.

Как это работает в проде

LSM-дерево: Bloom перед диском

Самое массовое применение фильтра Блума — движки хранения на LSM-деревьях (RocksDB, LevelDB, Cassandra, ScyllaDB, HBase). Данные лежат в десятках отсортированных файлов (SSTable); чтение ключа в худшем случае требует заглянуть в каждый. Каждый SSTable несёт свой Bloom filter в памяти — и промахи отсекаются без ввода-вывода.

Расчёт выгоды прямой: 10 бит на ключ в памяти экономят ~99 % дисковых чтений при промахах. Для базы с миллиардом ключей это 1.25 ГБ RAM против сотен тысяч лишних IOPS. Настройка в RocksDB — bits_per_key (документация), в Cassandra — bloom_filter_fp_chance на таблицу (документация). RocksDB с 2021 года предлагает также Ribbon filter (arxiv:2103.02515) — на 30 % компактнее Bloom при той же ошибке, ценой более дорогого построения; разумный выбор для холодных нижних уровней, где фильтр строится раз и читается вечно.

Аналитика: HLL как тип данных

• Redis: PFADD / PFCOUNT / PFMERGE — HLL встроен в ядро, 12 КиБ на ключ максимум, стандартная ошибка 0.81 % (redis.io).
• BigQuery: APPROX_COUNT_DISTINCT, а также явные HLL_COUNT.INIT / MERGE / EXTRACT — можно материализовать скетчи в таблице и агрегировать их потом (Google Cloud docs).
• ClickHouse: uniqHLL12, uniqCombined, uniq (документация), плюс тип AggregateFunction(uniq, ...) для хранения частично агрегированного состояния в materialized view.
• Spark / Presto / Trino: approx_count_distinct, под капотом HLL++ или Theta sketch.

Типичный продовый паттерн: пишем HLL-скетчи по (час × сегмент) в таблицу, а отчёты за любой период строим слиянием. Пересчёт годового отчёта — секунды вместо часов, и сырые логи можно удалять по retention.

-- ClickHouse: храним частично агрегированное состояние, а не сырые события
CREATE MATERIALIZED VIEW daily_uniques
ENGINE = AggregatingMergeTree() ORDER BY (day, country)
AS SELECT toDate(ts) AS day, country, uniqState(user_id) AS users_state  -- скетч
FROM events GROUP BY day, country;

-- Отчёт за произвольный период: скетчи сливаются, сырьё не читается
SELECT country, uniqMerge(users_state) AS users
FROM daily_uniques
WHERE day BETWEEN '2026-01-01' AND '2026-06-30'
GROUP BY country ORDER BY users DESC;

Сеть, безопасность, кеши

• Обнаружение тяжёлых потоков на маршрутизаторах: CMS по (src, dst) выявляет elephant flows и участников DDoS без хранения таблицы всех соединений.
• Кеш-серверы: политика вытеснения TinyLFU (в Caffeine, Go ristretto) использует CMS со счётчиками по 4 бита и периодическим делением всех счётчиков пополам («старение»), чтобы решать, стоит ли новый элемент вытеснения старого. Это редкий случай, когда скетч встроен в саму механику структуры, а не подпирает её снаружи.
• Дедупликация событий: Bloom filter на ID сообщений за окно в N минут отсекает повторы в at-least-once очередях. Ложное срабатывание = потерянное сообщение — поэтому здесь фильтр ставят только там, где потеря допустима, либо подтверждают походом в хранилище.
• Проверка утёкших паролей: Bloom filter на сотни миллионов скомпрометированных хешей помещается в сотни мегабайт; ложное срабатывание всего лишь просит пользователя выбрать другой пароль.
• RedisBloom (документация) даёт готовые BF.* (Bloom), CF.* (Cuckoo), CMS.*, TOPK.* и TDIGEST.* — быстрый способ попробовать всё это, ничего не реализуя.

Отдельно поучительный антипример: в Bitcoin BIP37 фильтры Блума применялись, чтобы лёгкий клиент запрашивал у узла «свои» транзакции, не раскрывая адресов. Оказалось, что по последовательности запросов адреса восстанавливаются с высокой вероятностью — приватность утекла (BIP37, впоследствии заменён на BIP157/158). Урок: ложноположительные ответы не являются автоматически механизмом приватности.

Типичные ошибки

• Игнорировать ложные срабатывания в логике корректности. «Один процент — это же мало». На потоке 100 тыс. запросов в секунду один процент — тысяча ошибок в секунду. Спросите себя: что происходит с каждой из этой тысячи? Если ответ «пользователь получает неверные данные» — структура выбрана неверно.
• Проектировать фильтр Блума под неверное n. Фильтр на миллион, заполненный десятью миллионами, даёт не 1 %, а десятки процентов ложных срабатываний — и молча. Мониторьте health() (см. код): доля единичных бит выше 0.6 это красный флаг.
• Считать пересечение через HLL. Разность больших чисел съедает ответ. Используйте Theta sketch или MinHash.
• Строить алерты на дельте приближённой метрики. «Уникальных упало на 1.2 %» при стандартной ошибке 0.81 % — это шум, а не инцидент. Порог алерта должен быть в разы больше ошибки метрики.
• Путать быстрый хеш и стойкий. SHA-256 на каждый элемент потока — потерянная производительность (берите xxHash, MurmurHash3, blake2). Но если ключи приходят от недоверенного пользователя, слабый хеш с известным сидом открывает алгоритмическую атаку: злоумышленник подбирает ключи, забивающие один столбец CMS или завышающие ложные срабатывания Bloom. Лечится случайным сидом на процесс — той же логикой, что и защита от HashDoS в хеш-таблицах.
• Верить оценкам CMS для редких ключей. Ошибка пропорциональна всему потоку: для ключа с частотой 3 при потоке 10⁹ вы получите шум, а не число.
• Не версионировать формат скетча. HLL с разным p, CMS с разной геометрией, Bloom с разными m/k несовместимы для слияния, а миграция «пересчитаем всё» на исторических данных может быть физически невозможна.
• Применять скетч там, где хватает точной структуры. Самая частая ошибка из всех: скетч добавляет параметр, ошибку, формат сериализации и целый класс тонких багов. Если множество влезает в память — берите множество.

Мини-итог

• Вероятностные структуры меняют точность на память, получая сублинейную или константную память там, где точное решение требует линейной. Это не микрооптимизация, а смена класса решений.
• Bloom filter: односторонняя ошибка («точно нет» / «возможно, да»), ~1.44·log₂(1/p) бит на элемент, O(k) на операцию, нет удаления. Живёт перед дорогим источником истины.
• HyperLogLog: мощность множества за O(log log n) памяти, ошибка ~1.04/√m, слияние через максимум — коммутативное, ассоциативное, идемпотентное. Основа распределённой аналитики уникальных.
• Count-Min Sketch: оценка частот сверху с ошибкой ε·‖f‖₁, память O((1/ε)·log(1/δ)). Точен для тяжёлых элементов, бесполезен для хвоста; сам ключи не помнит — нужна отдельная куча.
• Общее правило: применяйте скетч, когда (а) точный вариант не помещается или не масштабируется, (б) ошибка либо исправляется следующим шагом, либо не влияет на решение, и (в) вы можете внятно ответить, что происходит при каждом ложном срабатывании.

Источники

• Burton Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors, CACM 1970: doi.org/10.1145/362686.362692
• Broder & Mitzenmacher, Network Applications of Bloom Filters: A Survey: eecs.harvard.edu; Kirsch & Mitzenmacher, Less Hashing, Same Performance: eecs.harvard.edu
• Putze, Sanders & Singler, Cache-, Hash- and Space-Efficient Bloom Filters, WEA 2007: doi.org/10.1007/978-3-540-68552-4_9
• Fan, Andersen, Kaminsky & Mitzenmacher, Cuckoo Filter: Practically Better Than Bloom, CoNEXT 2014: cs.cmu.edu; Dillinger & Walzer, Ribbon filter: arxiv.org/abs/2103.02515
• Flajolet & Martin, Probabilistic Counting Algorithms for Data Base Applications, JCSS 1985: doi.org/10.1016/0022-0000(85)90041-8
• Flajolet, Fusy, Gandouet & Meunier, HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, AofA 2007: algo.inria.fr
• Heule, Nunkesser & Hall, HyperLogLog in Practice, EDBT 2013: research.google
• Cormode & Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch and its Applications: dimacs.rutgers.edu
• Charikar, Chen & Farach-Colton, Finding Frequent Items in Data Streams, ICALP 2002: cs.princeton.edu
• Broder, On the Resemblance and Containment of Documents (MinHash), 1997: doi.org/10.1109/SEQUEN.1997.666900; Dunning, The t-digest: arxiv.org/abs/1902.04023
• Apache DataSketches — промышленная библиотека скетчей: datasketches.apache.org; RedisBloom — те же структуры как команды Redis: redis.io; RocksDB Bloom Filter — практика настройки bits_per_key: github.com/facebook/rocksdb/wiki

Что дальше

Скетчи решают проблему объёма: как ответить на вопрос, не храня данные. Остаются два измерения, которые мы ещё не трогали, — время и параллелизм. Что если нужно обратиться не к текущей версии структуры, а к её состоянию час назад? И что если по одной структуре одновременно работают шестнадцать потоков, а блокировка на каждую операцию убивает всю производительность?

Следующая статья: Персистентные и конкурентные структуры данных — разберём разделение структуры (path copying), персистентные списки и деревья, lock-free стеки и очереди, проблему ABA, hazard pointers и epoch-based reclamation, а также то, почему неизменяемость и конкурентность оказались двумя сторонами одной идеи.

Общая карта трека — в обзоре.