HyperLogLog: как считать уникальные элементы в 12 КБ памяти

HyperLogLog простыми словами: подсчёт уникальных по ведущим нулям хеша, точность 1,04/√m, слияние счётчиков, PFADD и PFCOUNT в Redis, плюс Count-Min Sketch для частот. Код на Python.

13 мин чтенияструктуры данных · системный дизайн · python

Коротко

ПараметрHyperLogLogCount-Min Sketch
Отвечает на вопроссколько разных элементовсколько раз встретился этот элемент
Памятьmm маленьких регистров, не зависит от числа элементовw×dw \times d счётчиков
ДобавлениеO(1)O(1)O(d)O(d)
Ошибкастандартная ≈1,04/m\approx 1{,}04 / \sqrt{m}, в обе сторонытолько завышает, не больше εN\varepsilon N с вероятностью 1−δ1 - \delta
Слияниеда, поэлементный максимумда, поэлементная сумма
ПримерRedis: 12 КБ, ошибка 0,81%Redis: CMS.INCRBY, CMS.QUERY
  • HyperLogLog смотрит на хеши элементов и запоминает, сколько ведущих нулей встретилось максимум. Чем больше разных элементов, тем длиннее самая длинная «серия нулей».
  • Одного такого счётчика мало, поэтому их тысячи, и оценки усредняются.
  • Главная практическая сила — слияние: уникальных за неделю можно посчитать из семи дневных счётчиков, не храня ни одного идентификатора.

Задача: сколько уникальных

Типичный вопрос на собеседовании по системному дизайну: «Сколько уникальных пользователей заходило на страницу за день? А за месяц? А по каждой из миллиона страниц?»

Точное решение очевидно — положить идентификаторы во множество и взять его размер. Это та же хеш-таблица, что и в задаче про дубликаты в массиве. Проблема в памяти: множество хранит каждый уникальный элемент. 100 миллионов 64-битных ID — это минимум 800 МБ только на сами числа, а с накладными расходами хеш-таблицы в разы больше. И такое множество нужно на каждую страницу, на каждый день.

Другие точные подходы не лучше: сортировка требует хранить всё, битовая карта работает только для плотных целочисленных ID.

При этом точный ответ обычно не нужен. Разница между 1 000 000 и 1 008 000 уникальных посетителей никого не интересует. Если согласиться на ошибку около процента, память можно сократить с гигабайтов до килобайтов. Это та же сделка, что и в фильтре Блума: точность меняется на память. Только фильтр Блума отвечает на вопрос «был ли элемент», а HyperLogLog — «сколько было разных».

Интуиция: монетки и ведущие нули

Представьте, что кто-то подбрасывал монетку сериями, пока не выпадет орёл, и говорит вам только одно: самая длинная серия решек была 10 подряд. Сколько серий он сделал?

Серия из kk решек подряд выпадает с вероятностью 2−k2^{-k}. Чтобы увидеть 10 решек, нужно в среднем около 210≈10002^{10} \approx 1000 попыток. Значит, разумная оценка — порядка тысячи.

Теперь замените монетку хешем. У хорошей хеш-функции биты ведут себя как независимые броски. Доля хешей, начинающихся с kk нулей, — 2−k2^{-k}. Если среди всех хешей максимальное число ведущих нулей равно kk, разных элементов было порядка 2k2^k.

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

Попробуем в лоб:

import hashlib def hash64(item) -> int: """64-битный хеш: детерминированный, в отличие от встроенного hash().""" data = str(item).encode() return int.from_bytes(hashlib.blake2b(data, digest_size=8).digest(), 'big') def naive_estimate(items, salt=''): max_zeros = 0 for item in items: x = hash64(salt + str(item)) zeros = 64 - x.bit_length() # ведущие нули 64-битного хеша max_zeros = max(max_zeros, zeros) return 2 ** max_zeros items = range(100_000) print([naive_estimate(items, salt=str(s)) for s in range(8)]) # [32768, 32768, 32768, 65536, 262144, 65536, 67108864, 524288]

Одни и те же 100 000 элементов, восемь разных хеш-функций (соль меняет хеш), и оценки от 32 тысяч до 67 миллионов. Порядок величины иногда угадывается, но разброс чудовищный: одно случайно «счастливое» значение хеша с кучей нулей ломает всё. Ответ к тому же всегда степень двойки.

Эту идею описали Флажоле и Мартин ещё в 1985 году. Всё дальнейшее — способы победить разброс.

Стохастическое усреднение: тысячи регистров

Очевидный способ уменьшить разброс — повторить эксперимент много раз и усреднить. Но считать для каждого элемента тысячу хешей дорого.

Трюк: используем один хеш, но первые pp бит используем как номер «корзины» (регистра), а по остальным битам считаем ведущие нули. Получается m=2pm = 2^p независимых мини-экспериментов, каждый видит примерно n/mn / m элементов. Каждый элемент обрабатывается за O(1)O(1).

хеш:  0110 1011 | 0001 0110 ...
      ^^^^^^^^^   ^^^
      номер       три нуля, первая единица на позиции 4
      регистра    → rank = 4

В регистре храним максимальный rank — позицию первой единицы (число ведущих нулей плюс один). Ранг не превышает 64, поэтому регистру хватает 6 бит.

Остаётся вопрос, как объединить mm оценок. Простое среднее арифметическое снова страдает от выбросов: один регистр с рангом 30 перетянет всё. Предшественник LogLog (Дюран и Флажоле, 2003) усреднял ранги, то есть брал среднее геометрическое оценок. HyperLogLog (Флажоле, Фюзи, Гандуэ, Менье, 2007) берёт среднее гармоническое, которое ещё сильнее подавляет большие выбросы. Отсюда и название: логарифм от логарифма (регистру нужно всего порядка log⁡2log⁡2n\log_2 \log_2 n бит), а «Hyper» — улучшение над LogLog.

Формула

Оценка числа уникальных:

E=αm⋅m2⋅(∑j=1m2−Mj)−1E = \alpha_m \cdot m^2 \cdot \Big( \sum_{j=1}^{m} 2^{-M_j} \Big)^{-1}

Здесь MjM_j — значение jj-го регистра, а αm≈0,7213/(1+1,079/m)\alpha_m \approx 0{,}7213 / (1 + 1{,}079 / m) — поправочный коэффициент, убирающий систематическое смещение (формула верна для m≥128m \ge 128).

Почему m2m^2: m/∑2−Mjm / \sum 2^{-M_j} — среднее гармоническое оценок 2Mj2^{M_j} одного регистра, а каждый регистр видел лишь n/mn / m элементов, поэтому умножаем ещё на mm.

Две поправки по краям диапазона:

  • Мало элементов. Если E≤2,5mE \le 2{,}5m и есть пустые регистры, формула врёт: многие регистры ни разу не обновлялись. Тогда используют linear counting — оценку по доле пустых регистров: mln⁡(m/V)m \ln(m / V), где VV — число нулевых регистров. Это та же математика, что и вероятность того, что бит в фильтре Блума остался нулём.
  • Очень много элементов. В исходной статье хеш 32-битный, и при nn, близком к 2322^{32}, начинаются коллизии хешей, для этого есть отдельная поправка. С 64-битным хешем до этих масштабов не дойти, поправку можно не писать.

Реализация на Python

import math class HyperLogLog: def __init__(self, p: int = 14): assert 7 <= p <= 18 self.p = p self.m = 1 << p # число регистров self.registers = bytearray(self.m) # хватит байта: ранг ≤ 64 - p + 1 self.alpha = 0.7213 / (1 + 1.079 / self.m) def add(self, item) -> None: x = hash64(item) idx = x >> (64 - self.p) # первые p бит — номер регистра rest = x & ((1 << (64 - self.p)) - 1) # остальные 64 - p бит rank = (64 - self.p) - rest.bit_length() + 1 # позиция первой единицы if rank > self.registers[idx]: self.registers[idx] = rank def count(self) -> int: z = sum(2.0 ** -r for r in self.registers) estimate = self.alpha * self.m * self.m / z zeros = self.registers.count(0) if estimate <= 2.5 * self.m and zeros: # мало элементов: точнее посчитать по пустым регистрам return round(self.m * math.log(self.m / zeros)) return round(estimate) def merge(self, other: 'HyperLogLog') -> None: assert self.p == other.p for i, r in enumerate(other.registers): if r > self.registers[i]: self.registers[i] = r hll = HyperLogLog(p=14) for i in range(1_000_000): hll.add(f'user-{i % 250_000}') # 1 млн событий, 250 000 уникальных print(hll.count()) # 248111 — ошибка 0,76% print(len(hll.registers)) # 16384 байта

Миллион событий, четверть миллиона уникальных, а вся структура занимает 16 КБ (в Redis регистры упакованы по 6 бит, поэтому там 12 КБ). Точное множество тех же строк в Python заняло бы десятки мегабайт.

Детали, на которых легко ошибиться:

  • rank считается через bit_length(): если в оставшихся 64−p64 - p битах старшая единица на позиции L, то ведущих нулей (64−p)−L(64 - p) - L, а ранг на единицу больше. Если все биты нулевые, ранг максимальный — 64−p+164 - p + 1.
  • Встроенный hash() в Python для строк рандомизирован между запусками (PYTHONHASHSEED). Для счётчиков, которые сохраняются и сливаются между процессами, он не годится — нужен детерминированный хеш.
  • Хеш должен быть хорошим. Если младшие или старшие биты распределены неравномерно, оценка систематически съезжает.

Точность и память

Стандартная ошибка HyperLogLog — примерно 1,04/m1{,}04 / \sqrt{m}. Удвоение точности стоит учетверения памяти:

pРегистров mПамять (6 бит на регистр)Стандартная ошибка
101 024768 байт3,25%
124 0963 КБ1,63%
1416 38412 КБ0,81%
1665 53648 КБ0,41%

И главное: память не зависит от числа элементов. 12 КБ хватает и на тысячу, и на миллиард уникальных.

Проверили на нашей реализации: по 20 прогонов на 100 000 уникальных элементов. Среднеквадратичная ошибка вышла 3,7% при p = 10, 1,5% при p = 12 и 0,6% при p = 14 — в согласии с теорией. «Стандартная ошибка» означает примерно следующее: в двух третях случаев промах меньше неё, но отдельные замеры могут промахнуться в два-три раза сильнее.

Слабое место: переходная зона

При p = 14 в нашем эксперименте на 45 000 элементах средняя ошибка подскочила до +1,8%, а худший прогон — до 3,7%. Это не баг кода, а известная особенность исходного алгоритма: сразу за порогом 2,5m2{,}5m, где linear counting уже выключен, сырая формула систематически завышает.

Улучшенная версия HyperLogLog++ (Heule, Nunkesser, Hall, Google, 2013) решает это и ещё пару проблем:

  • 64-битный хеш вместо 32-битного — не нужна поправка для больших nn;
  • эмпирическая таблица смещений для переходной зоны;
  • разреженное представление: пока элементов мало, хранятся только непустые регистры, и счётчик занимает гораздо меньше 12 КБ.

Redis пошёл похожим путём: у него тоже есть разреженное и плотное представления, а смещение в переходной зоне Сальваторе Санфилиппо (antirez) поначалу исправлял подобранным полиномом.

Слияние: главная практическая фича

Если два счётчика построены с одинаковыми pp и хеш-функцией, их объединение — поэлементный максимум регистров. Результат в точности равен счётчику, построенному по объединённому потоку.

a, b = HyperLogLog(), HyperLogLog() for i in range(100_000): a.add(f'u{i}') # понедельник: u0..u99999 for i in range(50_000, 150_000): b.add(f'u{i}') # вторник: u50000..u149999 a.merge(b) print(a.count()) # 149689, точно — 150 000

Из этого вытекает типичная архитектура аналитики:

  • каждый сервер считает свой HLL по своему трафику, а центральный узел их сливает;
  • храним HLL за каждый час, а уникальных за день, неделю, месяц получаем слиянием — без повторного прохода по сырым логам;
  • уникальных по группе страниц получаем слиянием их счётчиков.

С точными числами так не выйдет: «уникальные за понедельник» плюс «уникальные за вторник» не равно «уникальные за два дня», потому что одни и те же люди приходили оба дня. Пришлось бы хранить сами множества.

Пересечение HLL напрямую не умеет. Его оценивают через формулу включений-исключений: ∣A∩B∣=∣A∣+∣B∣−∣A∪B∣|A \cap B| = |A| + |B| - |A \cup B|. Работает, только если пересечение большое: абсолютная ошибка каждого слагаемого порядка процента от больших чисел, и маленькое пересечение тонет в шуме.

Где применяется

Redis. Тип HyperLogLog появился в Redis 2.8.9. Команды:

  • PFADD key el1 el2 ... — добавить элементы;
  • PFCOUNT key [key ...] — оценка числа уникальных; с несколькими ключами — оценка их объединения;
  • PFMERGE dest src1 src2 ... — сохранить объединение.

По документации каждый счётчик занимает до 12 КБ (16 384 регистра по 6 бит в плотном виде), стандартная ошибка 0,81%, оценка работает для множеств до 2642^{64} элементов. Маленькие счётчики хранятся в разреженном представлении и автоматически переводятся в плотное по мере роста. Префикс PF — в честь Филиппа Флажоле, автора алгоритма: так объяснил antirez, когда добавлял эти команды.

redis> PFADD visitors:2026-11-07 alice bob carol
(integer) 1
redis> PFADD visitors:2026-11-08 bob dave
(integer) 1
redis> PFCOUNT visitors:2026-11-07 visitors:2026-11-08
(integer) 4

Аналитические базы. В BigQuery есть семейство функций HLL_COUNT.* на основе HyperLogLog++: HLL_COUNT.INIT строит скетч, HLL_COUNT.MERGE и HLL_COUNT.MERGE_PARTIAL сливают, HLL_COUNT.EXTRACT достаёт оценку. Скетчи можно сохранять в таблицу и сливать позже — та же схема «счётчик за час, сумма за месяц». Похожие приближённые функции есть в Spark (approx_count_distinct), ClickHouse (семейство uniq), Trino (approx_distinct).

Системный дизайн. Уникальные посетители коротких ссылок (см. дизайн сокращателя ссылок), уникальные поисковые запросы, число разных IP за окно для обнаружения аномалий, оценка числа разных ключей перед выбором стратегии шардирования или размера хеш-таблицы.

Count-Min Sketch: частоты вместо уникальных

HyperLogLog отвечает «сколько разных». Соседний вопрос — «сколько раз встретился вот этот» — решает Count-Min Sketch (Кормоуд и Мутукришнан).

Устройство

Таблица из dd строк по ww счётчиков и dd хеш-функций, по одной на строку.

  • Добавление: в каждой строке увеличиваем счётчик в столбце h_i(x).
  • Запрос: смотрим те же dd счётчиков и берём минимум.

Каждый счётчик хранит частоту x плюс частоты всех элементов, которые попали с ним в ту же ячейку. Коллизии только добавляют, поэтому каждый счётчик — оценка сверху, а минимум — самая точная из них. Отсюда главное свойство: Count-Min никогда не занижает, только завышает. Это зеркальная аналогия с фильтром Блума, который никогда не говорит «нет» про добавленный элемент.

Гарантия и размеры

Если NN — общее число добавлений, то при

w=⌈e/ε⌉,d=⌈ln⁡(1/δ)⌉w = \lceil e / \varepsilon \rceil, \quad d = \lceil \ln(1/\delta) \rceil

оценка с вероятностью не меньше 1−δ1 - \delta превышает истинную частоту не больше чем на εN\varepsilon N. Ширина отвечает за величину ошибки, глубина — за вероятность, что она будет большой.

class CountMinSketch: def __init__(self, eps: float = 0.001, delta: float = 0.01): 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)] def _columns(self, item): h = hashlib.blake2b(str(item).encode(), digest_size=16).digest() h1 = int.from_bytes(h[:8], 'big') h2 = int.from_bytes(h[8:], 'big') | 1
    # d «разных» хешей из двух: h1 + i·h2
    return [(h1 + i * h2) % self.w for i in range(self.d)]

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

def estimate(self, item) -> int:
    return min(self.table[row][col]
               for row, col in enumerate(self._columns(item)))

Проверим на потоке, где половина событий — 20 популярных страниц, а половина — длинный хвост из миллиона редких:

```python
import random
from collections import Counter

rnd = random.Random(1)
# 200 000 событий: половина — 20 популярных страниц, половина — длинный хвост
stream = [f'hot{rnd.randrange(20)}' if rnd.random() < 0.5
          else f'url{rnd.randrange(1_000_000)}' for _ in range(200_000)]
exact = Counter(stream)

cms = CountMinSketch(eps=0.001, delta=0.01)
for url in stream:
    cms.add(url)

print(cms.w, cms.d, len(exact))   # 2719 5 95289
for url, true in exact.most_common(3):
    print(url, true, cms.estimate(url))
# hot9 5100 5130
# hot3 5090 5123
# hot16 5085 5115
over = [cms.estimate(u) - c for u, c in exact.items()]
print(min(over), max(over), sum(over) / len(over))
# 13 45 29.54602315062599
print(sum(o > 0.001 * len(stream) for o in over))   # превысили ε·N = 200
# 0

13 595 счётчиков на 95 289 разных ключей. Завышение у каждого ключа от 13 до 45, гарантированная граница εN=200\varepsilon N = 200 ни разу не превышена. Для популярных страниц ошибка меньше процента. А вот для редких ключей, встретившихся один раз, оценка «около 30» бесполезна: Count-Min хорошо считает тяжёлых и плохо — хвост. Ошибка аддитивная, а не относительная.

Где применяется

  • Heavy hitters и топ-k в потоке. Count-Min плюс куча на k элементов: после каждого добавления оцениваем частоту и обновляем кучу. Это потоковая версия задачи Top K Frequent, когда словарь всех ключей не помещается в память.
  • Кэши. Политика TinyLFU (кэш Caffeine в Java) хранит приближённые частоты в подобном скетче, подробнее — в статье про LFU-кэш.
  • Сетевой мониторинг и rate limiting по большому числу ключей: сколько запросов было от этого IP.
  • Redis. Команды CMS.INITBYDIM, CMS.INITBYPROB, CMS.INCRBY, CMS.QUERY, CMS.MERGE, CMS.INFO из модуля вероятностных структур (раньше RedisBloom в Redis Stack, сейчас документация относит их к Redis Open Source).

Популярное улучшение — conservative update: при добавлении увеличиваем только те счётчики, которые равны текущему минимуму. Ошибка заметно падает, но удалять элементы (отрицательные инкременты) после этого нельзя.

Сравнение вероятностных структур

СтруктураВопросОшибкаСлияние
Фильтр Блумабыл ли элементложные «да», не бывает ложных «нет»OR битов
HyperLogLogсколько разных±1,04/√m, в обе сторонымаксимум регистров
Count-Min Sketchсколько раз этот элементтолько завышает, ≤ εNсумма счётчиков

Все три держатся на одной идее: хеш превращает элементы в случайные биты, и о большом множестве можно судить по маленькой статистике этих битов.

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

Ожидать точный ответ на маленьких числах. Для 50 элементов HLL даст около 50, но сравнивать «48 против 51» бессмысленно. На малых объёмах проще держать точное множество, и HLL++ с Redis делают это неявно через разреженное представление.

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

Плохой или рандомизированный хеш. Встроенный hash() для целых в Python возвращает само число: hash(5) == 5. Последовательные ID дадут не случайные, а очень предсказуемые биты, и оценка развалится. Для строк hash() меняется между запусками. Используйте криптографический или хороший некриптографический хеш (MurmurHash, xxHash).

Пересечения через HLL. Включения-исключения дают большую ошибку, если пересечение мало по сравнению с множествами.

Count-Min для редких элементов. Ошибка εN\varepsilon N одинакова для всех ключей. Для ключа с частотой 3 она может быть в десять раз больше самой частоты.

Как это спрашивают на собеседовании

На алгоритмической секции реализацию HLL обычно не просят. Зато на системном дизайне вопрос «а как считать уникальных?» — почти обязательный дополнительный вопрос к задачам про аналитику, ссылки, ленты и рекламу. Хороший ответ:

  1. Точное решение — множество на каждый ключ и период. Оценить память и показать, что она растёт линейно.
  2. Предложить HyperLogLog: фиксированные 12 КБ на счётчик, ошибка около 1%, PFADD и PFCOUNT в Redis.
  3. Сказать про слияние: часовые счётчики сливаются в дневные и месячные, счётчики с разных серверов — в общий.
  4. Если спрашивают частоты или топ-k по огромному потоку — Count-Min Sketch плюс куча.

Ещё один частый дополнительный вопрос — «почему именно ведущие нули?». Короткий ответ: у равномерного хеша kk ведущих нулей встречаются с вероятностью 2−k2^{-k}, поэтому максимум растёт как log⁡2n\log_2 n и позволяет оценить nn. Дубликаты дают тот же хеш и максимум не меняют.

Что запомнить

  • HyperLogLog оценивает число уникальных по максимальному числу ведущих нулей хеша в каждом из mm регистров.
  • Оценки регистров объединяются средним гармоническим с поправкой αm\alpha_m; для малых nn — linear counting.
  • Стандартная ошибка 1,04/m1{,}04/\sqrt{m}; в Redis m=16 384m = 16\,384, 12 КБ и 0,81%.
  • Память не зависит от числа элементов, счётчики сливаются поэлементным максимумом.
  • Count-Min Sketch считает частоты: минимум по dd строкам, никогда не занижает, ошибка не больше εN\varepsilon N с вероятностью 1−δ1 - \delta.
  • Обе структуры — про большие потоки, где точный ответ слишком дорог, а ошибка в процент никому не мешает.

Потренироваться в спокойной обстановке

Все задачи