Count-Min Sketch: частоты в потоке и heavy hitters без хранения ключей
Count-Min Sketch простыми словами: как оценить частоту элемента в потоке за фиксированную память, выбор ширины и глубины, conservative update, топ-k, сравнение с Misra-Gries. Код на Python.
Коротко
| Параметр | Значение |
|---|---|
| Отвечает на вопрос | сколько раз встретился элемент x |
| Устройство | таблица счётчиков и хеш-функций |
| Добавление и запрос | , обычно – |
| Память | , , не зависит от числа ключей |
| Ошибка | только завышение, не больше с вероятностью |
| Слияние | поэлементная сумма таблиц |
- Каждый элемент увеличивает по одному счётчику в каждой из строк. Ответ на запрос — минимум из этих счётчиков.
- Коллизии только добавляют, поэтому оценка никогда не меньше правды. Минимум — самая честная из завышенных оценок.
- Ошибка аддитивная: от длины всего потока. Популярные элементы считаются почти точно, редкие — бессмысленно. Поэтому главное применение — heavy hitters: топ самых частых.
- В паре с кучей или словарём на кандидатов получается потоковый топ-k без хранения всех ключей.
Задача
Через систему идёт поток событий: поисковые запросы, URL, IP-адреса, хештеги. Нужно в любой момент ответить, сколько раз встретился конкретный ключ, и показать десять самых частых.
Точное решение — словарь ключ → счётчик, та же хеш-таблица, что и в задаче Top K Frequent. Оно работает, пока ключей немного. Но поток уникальных IP за сутки — сотни миллионов, поисковых запросов — миллиарды. Словарь растёт вместе с числом разных ключей, и большая часть памяти уходит на хвост, который встретился один-два раза и никому не интересен.
Хочется структуру фиксированного размера, которая хорошо считает частых и честно ошибается на редких. Это Count-Min Sketch, предложенный Грэмом Кормоудом и С. Мутукришнаном в 2003 году.
Если вам нужно не «сколько раз», а «сколько разных», это другая задача — её решает HyperLogLog. А «встречался ли вообще» — фильтр Блума.
Интуиция: одна строка счётчиков
Начнём с простого. Возьмём массив из счётчиков и одну хеш-функцию. Каждый элемент увеличивает счётчик h(x) % w. Частоту x оцениваем значением этого счётчика.
Пока ключей меньше, чем ячеек, и хеш не сталкивает их, всё точно. Когда ключей больше, в ячейку x попадают и чужие элементы. Ошибка всегда в плюс: чужие добавляют, но никто не вычитает.
Насколько большая ошибка? Остальные событий разбросаны по ячейкам случайно, поэтому в нашу ячейку в среднем попадает не больше лишних. Но это в среднем: если в ячейку x случайно попал самый популярный ключ, оценка улетит.
Решение — несколько независимых строк. В каждой своя хеш-функция, и маловероятно, что x во всех строках делит ячейку с кем-то тяжёлым. Берём минимум по строкам: хотя бы в одной коллизии почти наверняка мелкие.
Устройство
Таблица , на каждую строку своя хеш-функция .
- add(x, c): для каждой строки делаем
table[i][h_i(x)] += c. - estimate(x): возвращаем .
Для каждой строки значение в ячейке x — это плюс частоты всех, кто с ним столкнулся. Каждая строка — оценка сверху, минимум — самая точная из них.
Реализация
import hashlib import math class CountMinSketch: def __init__(self, eps, delta): self.w = math.ceil(math.e / eps) # ширина: точность self.d = math.ceil(math.log(1 / delta)) # глубина: надёжность self.table = [[0] * self.w for _ in range(self.d)] self.total = 0 def _cells(self, item): # один хеш на 128 бит -> два числа -> d «независимых» хешей digest = hashlib.blake2b(str(item).encode(), digest_size=16).digest() h1 = int.from_bytes(digest[:8], "little") h2 = int.from_bytes(digest[8:], "little") | 1 for row in range(self.d): yield row, (h1 + row * h2) % self.w def add(self, item, count=1): self.total += count for row, col in self._cells(item): self.table[row][col] += count def estimate(self, item): return min(self.table[row][col] for row, col in self._cells(item))
Про хеши. Считать разных криптографических хешей дорого, поэтому используется приём двойного хеширования (Кирш и Митценмахер): один хеш делим на две половины , и -я функция — это . Для Count-Min и фильтра Блума этого достаточно. Встроенный hash() в Python для строк рандомизируется при каждом запуске, поэтому с ним результаты не воспроизводятся, а два процесса не смогут слить свои таблицы.
Проверка на потоке
Сделаем реалистичный поток: 200 000 обращений к 50 000 страниц с распределением Ципфа — первая страница в два раза популярнее второй, в три раза популярнее третьей и так далее. Так распределены запросы, слова, просмотры и почти всё в вебе.
import random from collections import Counter random.seed(1) keys = [f"/page/{i}" for i in range(50_000)] weights = [1 / (i + 1) for i in range(len(keys))] stream = random.choices(keys, weights, k=200_000) cms = CountMinSketch(eps=0.001, delta=0.01) for key in stream: cms.add(key) exact = Counter(stream) print(f"таблица {cms.d} x {cms.w} = {cms.d * cms.w} счётчиков, ключей {len(exact)}") bound = 0.001 * len(stream) over = [cms.estimate(k) - c for k, c in exact.items()] print("занижений:", sum(o < 0 for o in over)) print("превысили eps*N:", sum(o > bound for o in over), "из", len(over), "граница", bound) for key in ["/page/0", "/page/1", "/page/9", "/page/999", "/page/40000"]: print(f"{key:12} точно {exact[key]:6} оценка {cms.estimate(key):6}")
таблица 5 x 2719 = 13595 счётчиков, ключей 28857 занижений: 0 превысили eps*N: 0 из 28857 граница 200.0 /page/0 точно 17380 оценка 17396 /page/1 точно 8764 оценка 8794 /page/9 точно 1747 оценка 1761 /page/999 точно 10 оценка 53 /page/40000 точно 0 оценка 10
Что видно:
- Ни одного занижения — так и должно быть.
- Для лидеров ошибка — доли процента: 17 396 против 17 380.
- Для страницы с 10 просмотрами оценка 53, в пять раз больше правды. Для страницы, которой в потоке нет вообще, оценка 10. Count-Min не умеет говорить «ноль».
- 13 595 счётчиков вместо словаря на 28 857 ключей. Разница пока небольшая, но таблица не вырастет и при миллиарде ключей, а словарь вырастет.
Гарантия и выбор размеров
Пусть — сумма всех добавлений. Классическая оценка:
при и .
Откуда это берётся. В одной строке ожидаемое число «чужих» событий в ячейке x не больше . По неравенству Маркова вероятность, что их больше , не больше . Строки независимы, и минимум превышает , только если превышают все строк: вероятность .
Отсюда практическое правило:
- ширина отвечает за величину ошибки: удвоили — ошибка упала вдвое;
- глубина отвечает за то, как редко гарантия нарушается: каждая лишняя строка уменьшает вероятность провала в раз.
| Счётчиков | Память при 4 байтах | ||||
|---|---|---|---|---|---|
| 0,01 | 0,01 | 272 | 5 | 1 360 | 5 КБ |
| 0,001 | 0,01 | 2 719 | 5 | 13 595 | 53 КБ |
| 0,0001 | 0,001 | 27 183 | 7 | 190 281 | 743 КБ |
Обратите внимание: ни в одной формуле нет числа разных ключей. Память зависит только от желаемой точности относительно .
Гарантия задана для одного запроса. Если спросить про сто тысяч ключей, около из них могут выйти за границу. В нашем эксперименте не вышел ни один: на распределении Ципфа Count-Min работает заметно лучше худшего случая, потому что основная масса сосредоточена в немногих ключах.
Conservative update
Простое улучшение, которое почти бесплатно уменьшает завышение. При добавлении x с текущей оценкой (минимум по строкам) новая оценка будет . Счётчики, которые уже больше , увеличивать незачем: они и так завышены за счёт чужих, и на ответ про x всё равно не влияют. Поднимаем каждый счётчик только до .
class ConservativeCMS(CountMinSketch): def add(self, item, count=1): self.total += count cells = list(self._cells(item)) target = min(self.table[r][c] for r, c in cells) + count for r, c in cells: # поднимаем только те счётчики, что ниже новой оценки self.table[r][c] = max(self.table[r][c], target)
На том же потоке:
CountMinSketch среднее завышение 15.9, максимум 90 ConservativeCMS среднее завышение 7.9, максимум 58
Ошибка упала вдвое. Плата — две вещи. Во-первых, добавление теперь читает счётчики перед записью, это дороже при конкурентном доступе. Во-вторых, ломаются удаления и слияние: таблицы двух conservative-скетчей уже нельзя просто сложить, а вычитание может дать занижение.
Heavy hitters: топ-k в потоке
Сам скетч не помнит ключей: по таблице нельзя узнать, кто популярен, только проверить конкретного кандидата. Поэтому рядом держат маленькую структуру на кандидатов. После каждого добавления оцениваем частоту элемента, и если она больше, чем у самого слабого кандидата, вытесняем слабого.
class TopK: def __init__(self, k, eps=0.001, delta=0.01): self.k = k self.cms = CountMinSketch(eps, delta) self.top = {} # кандидат -> оценка частоты def add(self, item): self.cms.add(item) est = self.cms.estimate(item) if item in self.top or len(self.top) < self.k: self.top[item] = est return weakest = min(self.top, key=self.top.get) if est > self.top[weakest]: del self.top[weakest] self.top[item] = est def result(self): return sorted(self.top.items(), key=lambda kv: -kv[1]) t = TopK(5) for key in stream: t.add(key) print(t.result()) print(exact.most_common(5))
[('/page/0', 17396), ('/page/1', 8784), ('/page/2', 6003), ('/page/3', 4409), ('/page/4', 3602)] [('/page/0', 17380), ('/page/1', 8764), ('/page/2', 5984), ('/page/3', 4390), ('/page/4', 3582)]
Состав и порядок совпали, частоты завышены на 16–20.
Поиск слабейшего здесь — min по словарю за . Для в десятки это быстрее и проще всего. Для больших берут min-кучу: вершина — слабейший кандидат. Сложность в том, что оценка кандидата растёт, а в стандартной куче нельзя обновить элемент в середине. Обычно используют ленивое удаление: кладут новую запись, а устаревшие выбрасывают, когда они всплывают на вершину.
Одна тонкость: элемент, который был вытеснен, а потом вернулся, сразу получает правильную оценку из скетча, потому что скетч помнит всё. В этом преимущество над наивным «держим только k счётчиков».
Альтернативы
Misra-Gries: детерминированный топ
Если нужны только тяжёлые элементы, а не частоты произвольных ключей, есть алгоритм Мисры–Гриса (1982). Он держит не больше счётчиков. Новый элемент получает счётчик, если есть место; если места нет, все счётчики уменьшаются на единицу, и обнулившиеся удаляются.
def misra_gries(stream, k): """Не больше k-1 счётчиков; находит всех, у кого частота > N/k.""" counters = {} for x in stream: if x in counters: counters[x] += 1 elif len(counters) < k - 1: counters[x] = 1 else: for key in list(counters): counters[key] -= 1 if counters[key] == 0: del counters[key] return counters
Гарантия детерминированная: каждый элемент с частотой больше останется в словаре, а его счётчик занижен не больше чем на . На нашем потоке при лидер получил 15 731 вместо 17 380 — занижение 1 649, в пределах порога 2 000. Ошибка в другую сторону, чем у Count-Min.
При это ровно алгоритм Бойера–Мура для элемента большинства: один кандидат и счётчик. Хороший мостик на собеседовании: «Majority Element — частный случай потоковых heavy hitters».
Близкий родственник — Space-Saving (Метвалли и др., 2005): вместо уменьшения всех счётчиков новый элемент вытесняет минимальный и наследует его значение плюс один. Его используют, когда нужен точный список топа с оценками сверху.
Минус обоих: они не отвечают на вопрос про произвольный ключ, только про тех, кто в словаре. И их сложнее сливать между машинами, хотя для Misra-Gries способ есть.
Count Sketch: без систематического сдвига
Count Sketch (Чарикар, Чен, Фарах-Колтон, 2002) добавляет к каждому элементу случайный знак в каждой строке. Чужие элементы теперь в среднем гасят друг друга, оценка строки несмещённая, а итог — медиана по строкам вместо минимума.
Count Sketch: средняя ошибка -0.1, средний модуль 7.3 Count-Min: средняя ошибка 15.9, средний модуль 15.9
Те же 5 × 2719 счётчиков: Count Sketch ошибается в обе стороны, но в среднем вдвое меньше. Для страницы с 10 просмотрами он дал 12, а Count-Min — 53. Его граница ошибки выражается через корень из суммы квадратов частот, а не через , и на тяжёлых хвостах она лучше. Цена — оценка может оказаться отрицательной или меньше правды, а это неудобно, если вы, например, решаете, банить ли IP.
Сводка
| Структура | Ошибка | Произвольный ключ | Слияние | Удаления |
|---|---|---|---|---|
| Словарь | нет | да | да | да |
| Count-Min | только вверх, | да | сумма таблиц | да, если частоты не уходят в минус |
| Count-Min + CU | только вверх, меньше | да | нет | нет |
| Count Sketch | в обе стороны, несмещённая | да | сумма таблиц | да |
| Misra-Gries | только вниз, | нет, только топ | есть алгоритм | нет |
Слияние и окна
Count-Min линеен: таблица потока A плюс таблица потока B — это таблица потока A+B. Важно только, чтобы размеры и хеш-функции совпадали.
half = len(stream) // 2 a, b = CountMinSketch(0.001, 0.01), CountMinSketch(0.001, 0.01) for key in stream[:half]: a.add(key) for key in stream[half:]: b.add(key) merged = CountMinSketch(0.001, 0.01) merged.table = [[x + y for x, y in zip(ra, rb)] for ra, rb in zip(a.table, b.table)] print("слияние совпадает:", merged.table == cms.table) # True
Отсюда две практические схемы:
- Распределённый подсчёт. Каждый сервер ведёт свой скетч, раз в минуту отправляет 50 КБ агрегатору, тот складывает. Ни одного ключа по сети.
- Скользящее окно. Держим скетч на каждую минуту и кольцевой буфер последних 60. Частота за час — сумма 60 таблиц, старая минута просто выбрасывается. Так строятся «тренды за последний час» и детекторы всплесков. Та же идея окон встречается в rate limiter.
Можно и вычитать: таблица часа минус таблица самой старой минуты. Это законно для обычного Count-Min, но не для conservative update.
Где применяется
- Мониторинг сети. Какие IP шлют больше всего пакетов, кто устроил DDoS. Скетчи считают прямо на роутерах и в программируемых коммутаторах, где памяти мегабайты.
- Тренды. Самые частые поисковые запросы, хештеги, товары за последний час.
- Кэши. Политика допуска TinyLFU оценивает частоту обращений к ключу через Count-Min с 4-битными счётчиками и пускает в кэш только то, что популярнее вытесняемого. Она используется в Java-библиотеке Caffeine. Подробнее о вытеснении — в статье про стратегии кэширования.
- Базы и движки обработки данных. В Redis есть команды
CMS.INITBYPROB,CMS.INCRBY,CMS.QUERY,CMS.MERGE(раньше — модуль RedisBloom, в новых версиях входит в Redis), а также структураTOPKдля heavy hitters. В Apache Spark —df.stat.countMinSketch(...). - NLP и машинное обучение. Частоты n-грамм в огромных корпусах, хеширование признаков.
Типичные ошибки
Ждать точности на редких ключах. Ошибка одинакова для всех. При = 10 млн и это 10 000 — для ключа с частотой 5 оценка бессмысленна. Count-Min — инструмент для тяжёлых элементов.
Путать роли и . Увеличивать глубину, чтобы уменьшить ошибку, — расточительно: ошибку определяет ширина. Глубина нужна для надёжности, 4–7 строк хватает почти всегда.
Зависимые хеши. Если все строки используют одну функцию или функции коррелируют, строк превращаются в одну. С двойным хешированием обязательно сделать ненулевым (в коде — | 1).
Разные хеши на разных машинах. Встроенный hash() в Python рандомизирован, в Java hashCode у разных версий классов может отличаться. Слить такие таблицы нельзя — и ошибку никто не заметит, оценки просто станут мусором.
Переполнение счётчиков. 32-битного счётчика хватит на 4 млрд событий. В долгоживущем скетче или при весах в байтах трафика берите 64 бита или периодически сбрасывайте.
Conservative update со слиянием или удалениями. Он ломает линейность. Если нужно складывать таблицы, используйте обычное обновление.
Count-Min вместо HyperLogLog. Сумма или число непустых ячеек не дают числа уникальных ключей. Для кардинальности — HyperLogLog.
Как это спрашивают на собеседовании
Системный дизайн. «Спроектируйте топ-10 самых популярных запросов за последний час», «трендовые хештеги», «самые просматриваемые видео в реальном времени», «найти IP, от которых идёт подозрительно много запросов». Хороший ответ строится так:
- Точное решение — словарь плюс куча. Оценить память: сотни миллионов ключей не помещаются на одну машину.
- Предложить Count-Min Sketch плюс топ-k кандидатов, назвать гарантию: только завышение, не больше .
- Посчитать размер: , — меньше мегабайта.
- Распределить: скетч на каждом сервере, агрегатор складывает таблицы. Окно — кольцо минутных скетчей.
- Сказать про ограничения: редкие ключи неточны; если нужен точный топ, второй проход по кандидатам с точным подсчётом.
Здесь пригодится навык прикидок на салфетке: интервьюер ждёт, что вы посчитаете память точного решения и скетча.
Алгоритмическая секция. Скетч не напишут как задачу, но к нему подводят follow-up вопросы:
- Top K Frequent Elements — «а если данные не помещаются в память и идут потоком?»
- Majority Element — «а если нужны все элементы с частотой больше ?» Ответ — Misra-Gries.
- «Как выбрать случайный элемент из потока?» — это уже reservoir sampling, ещё одна потоковая техника.
Вопросы вглубь:
- Почему минимум, а не среднее? (Каждая строка — оценка сверху; среднее тянет вверх самая неудачная строка.)
- Почему ошибка только в одну сторону? Можно ли сделать несмещённую? (Count Sketch.)
- Как поддержать удаление? (Вычитание работает, пока реальные частоты неотрицательны.)
- Чем Count-Min похож на фильтр Блума? (Те же хешей, только вместо битов счётчики; Блум — частный случай «частота больше нуля».)
Что запомнить
- Count-Min Sketch — таблица счётчиков: добавление увеличивает по счётчику в каждой строке, запрос берёт минимум.
- Оценка никогда не занижает и завышает не больше чем на с вероятностью ; , .
- Память не зависит от числа ключей. Хорошо считает тяжёлых, плохо — хвост.
- Скетчи складываются: распределённый подсчёт и скользящие окна почти бесплатны.
- Для топ-k нужен рядом словарь или куча на кандидатов. Если нужны только тяжёлые и детерминированно — Misra-Gries; если важна несмещённость — Count Sketch.