Фильтры Блума, HyperLogLog, Count-Min, skip list, LSM-деревья, консистентное хеширование и деревья Меркла — то, на чём построены Cassandra, Redis, RocksDB и CDN. Финал серии «Алгоритмы и структуры данных».
Листайте стрелками ← →, свайпом или кнопками внизу. В схемах нажимайте кнопки и двигайте ползунки.
«Сколько уникальных посетителей за месяц?» Точный ответ требует помнить каждого. На миллиардах ключей это сотни гигабайт — и всё это ради одного числа.
Двигайте ползунок: сколько памяти займёт множество 64-битных ID в разных структурах.
Массив из m бит и k хеш-функций. Добавить элемент — выставить в единицу k бит. Проверить — посмотреть на те же k бит.
Добавьте слова, затем проверяйте другие. Ищите ложное срабатывание.
Вероятность ложного срабатывания после n вставок:
p ≈ (1 − e−kn/m)k
лучшее k = (m/n)·ln 2
Двигайте ползунки. В схеме — формула и эксперимент на настоящем фильтре.
bloom_filter_fp_chance.bloom — один индекс на равенство по многим колонкам; ClickHouse — skip-индекс bloom_filter.
from hashlib import blake2b
from math import ceil, log
class Bloom:
def __init__(self, n, p):
self.m = ceil(-n * log(p) / log(2) ** 2)
self.k = round(self.m / n * log(2))
self.bits = bytearray(self.m // 8 + 1)
def _idx(self, item: str):
d = blake2b(item.encode()).digest()
h1 = int.from_bytes(d[:8])
h2 = int.from_bytes(d[8:16])
# k индексов из двух хешей — как в Guava
for i in range(self.k):
yield (h1 + i * h2) % self.m
def add(self, item):
for i in self._idx(item):
self.bits[i >> 3] |= 1 << (i & 7)
def __contains__(self, item):
return all(self.bits[i >> 3] >> (i & 7) & 1
for i in self._idx(item))
b = Bloom(n=1_000_000, p=0.01) # 1,2 МБ, k = 7
Фильтр Блума рассчитан на 1 млн элементов с ошибкой 1% (9,6 бита на элемент, k = 7). В него записали 3 млн. Что произошло?
BF.RESERVE … EXPANSION в Redis) или пересоздают, как SSTable при компакции.Хеш — случайные биты. Увидеть хеш, начинающийся с 10 нулей, — шанс 1 к 1024: значит, уникальных было порядка тысячи. Одна такая оценка шумная, поэтому хеши делят на m корзин по первым битам и усредняют.
В каждой корзине хранится только максимум «нулей в начале + 1» — 6 бит. Ошибка ≈ 1,04/√m. Добавляйте посетителей и повторы: повторы оценку не меняют.
PFADD/PFCOUNT, 16 384 регистра, 12 КБ, ошибка 0,81% — на любом числе элементов. Пока элементов мало, хранит разреженно, в сотни байт.uniq в ClickHouse, APPROX_COUNT_DISTINCT в BigQuery и Snowflake, approx_distinct в Trino, расширение hll для Postgres.
import redis
r = redis.Redis()
# на каждый просмотр: O(1), память не растёт
r.pfadd("uv:2026-10-09", user_id)
r.pfcount("uv:2026-10-09") # ≈ 1 284 113
# неделя = слияние дневных скетчей
days = [f"uv:2026-10-{d:02}" for d in range(3, 10)]
r.pfmerge("uv:week41", *days)
r.pfcount("uv:week41") # ≈ 5 902 447
r.memory_usage("uv:week41") # ~12 КБ
Таблица d × w счётчиков и d хешей. Событие увеличивает по одному счётчику в каждой строке. Частота — минимум из этих d счётчиков.
Пустите поток хештегов, нажмите на тег в топе — подсветятся его счётчики.
Нужна случайная выборка из k строк лога, а длина потока заранее неизвестна. Первые k берём целиком. Элемент номер i попадает в выборку с вероятностью k/i и вытесняет случайного.
import random
def reservoir(stream, k):
sample = []
for i, x in enumerate(stream, 1):
if i <= k:
sample.append(x)
elif (j := random.randrange(i)) < k:
sample[j] = x
return sample
В любой момент каждый из увиденных i элементов лежит в выборке с вероятностью ровно k/i. Так семплируют трейсы, логи и строки для статистики (ANALYZE в Postgres).
Count-Min Sketch говорит, что хештег #go встречался 1 200 раз. Что точно можно сказать о реальном числе?
Отсортированный связный список с «экспрессами». Каждый узел при вставке подбрасывает монетку: орёл — поднимается на уровень выше. Поиск идёт сверху: вправо, пока следующий ключ меньше искомого, иначе вниз.
ZADD, ZRANGEBYSCORE) — skip list плюс хеш-таблица. Memtable в RocksDB и LevelDB, ConcurrentSkipListMap в Java — лок-фри.Ищите ключи и вставляйте новые. Подсвечен путь поиска.
Запись — в отсортированную структуру в памяти (memtable) и в журнал. Заполнилась — сбрасывается на диск неизменяемым файлом SSTable. Фоновая компакция сливает файлы, выкидывая старые версии и удалённые ключи.
Чтение идёт от новых данных к старым: memtable, затем SSTable. Фильтр Блума позволяет не трогать файлы, где ключа нет. Удаление — тоже запись: «надгробие». Пишите, читайте, удаляйте и запускайте компакцию.
Правило: много записи и ключ-значение — LSM, смешанная нагрузка с диапазонами и транзакциями — B-дерево. Как устроено B-дерево — в презентации про деревья и кучи, а в живом Postgres — PostgreSQL изнутри.
hash(key) % N ломается при изменении N: почти все ключи меняют сервер, кэш пустеет разом. На кольце ключ принадлежит первому серверу по часовой стрелке — при добавлении сервера переезжает ~1/N ключей.
hash(key, server).Добавляйте и убирайте серверы в обоих режимах. Подробнее о шардировании — в презентации про данные в system design.
Кэш на 10 серверах, сервер выбирают как hash(key) % N. Добавили одиннадцатый. Какая доля ключей теперь ищется не на том сервере?
h % 10 == h % 11 — это 10 значений из 110, то есть 1/11. Остальные 91% ключей — промахи, и вся нагрузка разом идёт в базу. С консистентным хешированием переедет лишь ~1/11 ключей, ровно то, что теперь должен обслуживать новый сервер.Биты долготы и широты перемежаются: каждый бит делит клетку пополам. Близкие точки получают общий префикс, и «кто рядом» превращается в поиск по префиксу в обычном отсортированном индексе.
GEOADD — 52-битный geohash как score в sorted set (тот самый skip list). Elasticsearch, MongoDB. Quadtree делит клетки по плотности точек, Uber H3 — шестиугольники, Google S2 — кривая Гильберта.Нажмите на карту и меняйте точность. Точки — кафе вокруг 14 городов мира.
Лист — хеш блока данных, узел — хеш от хешей детей. Совпали корни — совпадает всё. Не совпали — спускаемся только в отличающиеся ветки и находим разницу за O(log n) сравнений, не пересылая данные.
nodetool repair), Dynamo, Riak: реплики сверяют деревья по диапазонам ключей.Испортите блоки на реплике B и сверяйте.
В ведре до b жетонов, они добавляются со скоростью r в секунду. Запрос забирает жетон, а если жетонов нет — получает 429. Средняя скорость ≤ r, а всплеск до b запросов проходит сразу.
def allow(self) -> bool:
now = time.monotonic()
add = (now - self.t) * self.r
self.tok = min(self.b, self.tok + add)
self.t = now
if self.tok >= 1:
self.tok -= 1
return True
return False
Хранить достаточно двух чисел: жетоны и время. В Redis это пара полей и Lua-скрипт. Так работают golang.org/x/time/rate, Guava RateLimiter, лимиты AWS и Stripe; limit_req в nginx — родственный leaky bucket.
Вероятностные структуры сливаются (Блум — OR, HLL — max, Count-Min — сумма): их считают по шардам и по часам, а потом объединяют. Это и делает их удобными в распределённых системах.
На system design эти структуры — готовые ответы на типовые подзадачи. Назовите структуру, её ошибку и цену в памяти.
# Redis: посмотреть своими глазами
PFADD uv a b c d; PFCOUNT uv → 4
MEMORY USAGE uv → ~100 Б
OBJECT ENCODING board → skiplist
GEOSEARCH cafes FROMLONLAT 37.6 55.7 \
BYRADIUS 1 km
# модуль RedisBloom
BF.RESERVE seen 0.01 1000000
CMS.INITBYPROB tags 0.001 0.01
# Cassandra: фильтры SSTable в деле
nodetool tablestats ks.t | grep -i bloom
# Bloom filter false ratio: 0.00870
# Библиотеки
Python: datasketch, pyprobables
Go: bits-and-blooms/bloom,
axiomhq/hyperloglog
Java: Guava BloomFilter,
Apache DataSketches
Точный ответ дорог. Хорошая система знает, где можно ошибиться и на сколько.