HyperLogLog: подсчёт уникальных приближённо

HyperLogLog отвечает на вопрос «сколько здесь уникальных значений» приблизительно, но с фиксированными ~12 КБ памяти — даже если значений миллиарды.

HyperLogLog (HLL) — вероятностная структура для оценки кардинальности (числа уникальных элементов). В Redis это команды PFADD, PFCOUNT, PFMERGE; цена — около 0.81% относительной погрешности при постоянном расходе памяти ≈ 12 КБ на счётчик.

Bitmap из прошлого урока считает уникальных точно, но требует плотных числовых id и места до максимального смещения. А если нужно посчитать уникальные IP-адреса за сутки, уникальные поисковые запросы или просмотры страниц, где значений десятки миллионов и они — произвольные строки? Хранить их все в SET — это сотни мегабайт. HyperLogLog решает ровно эту задачу: он не хранит элементы, он хранит лишь «отпечаток» статистики и по нему оценивает их количество.

Зачем нужен приближённый счёт

Для аналитики точность до единицы обычно не важна: разница между «1 002 311» и «1 000 000» уникальных посетителей не меняет ни одного решения. Зато важна цена. SET на миллион 16-байтовых строк — это десятки МБ и растёт линейно. HLL же фиксирован: ~12 КБ и для тысячи, и для миллиарда уникальных. Поменять «абсолютно точно, но дорого» на «±0.81%, но почти бесплатно» — выгодная сделка для счётчиков охвата.

PFADD и PFCOUNT

PFADD key element [element ...] добавляет элементы в счётчик и возвращает 1, если внутреннее состояние изменилось (то есть, скорее всего, элемент был новым). PFCOUNT key возвращает оценку числа уникальных. Команды названы с префиксом PF в честь Филиппа Флажоле (Philippe Flajolet), автора алгоритма.

PFADD visits:2026-06-27 user:alice user:bob user:carol   # => 1
PFADD visits:2026-06-27 user:alice                        # => 0 (уже была)
PFCOUNT visits:2026-06-27                                 # => 3 (оценка)

Заметьте: повторное добавление user:alice вернуло 0 — состояние не поменялось. Как и bitmap, HLL по сути считает уникальные, а не события.

PFMERGE: объединение счётчиков

PFMERGE dest src1 src2 ... сливает несколько HLL в один так, что результат оценивает кардинальность объединения множеств. Это аналог BITOP OR, но для приближённого счёта. Так из дневных охватов получают недельный без двойного счёта тех, кто заходил в несколько дней.

PFADD visits:mon u1 u2 u3
PFADD visits:tue u2 u3 u4
PFMERGE visits:week visits:mon visits:tue   # объединение
PFCOUNT visits:week                         # => 4 (u1..u4), а не 6

Можно посчитать объединение и на лету, не создавая ключ: PFCOUNT visits:mon visits:tue с несколькими аргументами вернёт оценку их объединения.

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

Идея алгоритма красива. Каждый элемент прогоняют через хэш-функцию, получая псевдослучайную последовательность бит. Смотрят, сколько идёт ведущих нулей. Длинная серия нулей маловероятна для одного значения, но чем больше разных элементов вы прогнали, тем выше шанс встретить редкую серию. Если где-то наблюдалось k ведущих нулей, элементов было примерно 2**k.

Один такой счётчик жутко шумит. Поэтому HLL делит хэш на две части: первые биты выбирают одну из множества «корзин» (регистров — в Redis их 16384), а в каждой корзине хранится максимум ведущих нулей среди попавших туда элементов. Финальную оценку получают, усредняя корзины гармоническим средним. Усреднение и гасит шум до тех самых ~0.81%. Соберём упрощённую версию на стандартной библиотеке Python (hashlib):

import hashlib

def hll_estimate(items, p=14):
    m = 1 << p                       # число корзин (16384 при p=14, как в Redis)
    registers = [0] * m
    for it in items:
        h = int(hashlib.sha1(str(it).encode()).hexdigest(), 16)
        idx = h & (m - 1)            # первые p бит — номер корзины
        rest = h >> p
        rank = 1                     # позиция первой единицы = ведущие нули + 1
        while rest & 1 == 0 and rank <= 64:
            rank += 1
            rest >>= 1
        if rank > registers[idx]:
            registers[idx] = rank
    alpha = 0.7213 / (1 + 1.079 / m)            # поправочный коэффициент
    indicator = sum(2.0 ** -r for r in registers)
    return round(alpha * m * m / indicator)     # гармоническое усреднение

data = range(100_000)
real = len(set(data))
approx = hll_estimate(data)
print(f"Реально уникальных: {real}")
print(f"Оценка HLL:         {approx}")
print(f"Погрешность:        {abs(approx - real) / real * 100:.2f}%")

Вывод:

Реально уникальных: 100000
Оценка HLL:         99765
Погрешность:        0.24%

Сто тысяч элементов мы оценили в 99 765 — мимо всего на 0.24%, и при этом не сохранили ни одного из них: в памяти живёт лишь массив маленьких счётчиков по корзинам. Именно так Redis укладывает оценку любой кардинальности в фиксированные ~12 КБ.

Когда брать HLL, а когда нет

Частые ошибки

• Ждать точного ответа. PFCOUNT возвращает оценку. Для биллинга, лимитов и любых решений «по одному элементу» это недопустимо — берите SET.
• Спрашивать про членство. HLL не отвечает «есть ли X внутри» — он хранит только статистику, а не элементы. Нет аналога SISMEMBER.
• Перебор с числом ключей. Каждый HLL — это ~12 КБ. Заводить отдельный счётчик на каждую минуту на годы вперёд тоже накладно; продумайте гранулярность.
• Складывать PFCOUNT руками. Сумма двух PFCOUNT переоценит объединение из-за общих элементов. Для объединения всегда PFMERGE (или PFCOUNT с несколькими ключами).
• Сравнивать побайтно. Два HLL с одинаковым множеством могут иметь разное внутреннее представление; сравнивать их сырые строки бессмысленно.

Итоги

• HyperLogLog оценивает число уникальных элементов с погрешностью ~0.81% при постоянных ≈ 12 КБ памяти.
• PFADD добавляет, PFCOUNT оценивает, PFMERGE объединяет счётчики без двойного счёта.
• Алгоритм считает ведущие нули в хэшах по множеству корзин и усредняет их гармоническим средним — элементы при этом не хранятся.
• Берите HLL для охвата/уникальных по произвольным ключам; для точного счёта — SET или bitmap, для проверки членства — только SET.