HyperLogLog: сколько разных, если помнить только нули

Если ты объяснишь, почему повторы не влияют на оценку, зачем нужны группы и гармоническое среднее и как объединить две сводки - листай до «Теперь сам».

Как думаешь, можно ли посчитать разных, не запоминая никого

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

Ответь себе до чтения: можно ли дать ответ с точностью около процента, храня 12 килобайт и ни одного идентификатора? Можно. Для этого нужно запоминать о посетителях не «кто», а одно-единственное свойство: насколько редкое значение хеша среди них встретилось.

На что это похоже

Наблюдатель записывает самую длинную серию орлов подряд, которую кто-либо выбросил в начале своей игры. Каждый игрок бросает монету до первой решки, один раз в жизни: если он подойдёт снова, у него выйдет та же серия.

Серия из десяти орлов выпадает у одного игрока из тысячи. Если наблюдатель видел такую серию, игроков, скорее всего, было около тысячи; если самая длинная серия - три, их было около восьми. Сколько раз подходил каждый игрок, неважно: его серия от этого не меняется. Наблюдатель помнит одно небольшое число и по нему судит о количестве людей.

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

Механизм: от минимума к серии нулей

Шаг первый: хеш как случайное число. Хорошая хеш-функция превращает каждый элемент в число, которое выглядит как случайная точка на отрезке от 0 до 1, - и одинаковые элементы дают одну и ту же точку. n разных элементов - это n случайных точек, сколько бы раз каждый ни повторялся.

Шаг второй: минимум. Наименьшая из n случайных точек на отрезке в среднем равна 1 / (n + 1): точки делят отрезок на n + 1 кусок, в среднем одинаковых. Значит, по минимуму v можно оценить n ≈ 1/v − 1. Хранить нужно одно число. Оценка получается очень шумной: минимум легко оказывается в несколько раз меньше или больше среднего. Точнее работает k-я по малости точка vₖ: оценка (k − 1) / vₖ, для неё нужно хранить k наименьших хешей.

Шаг третий: порядок вместо значения. Хранить k хешей по 64 бита расточительно, если нужен только порядок величины минимума. Запишем хеш в двоичном виде. Число, которое начинается с r − 1 нулей и затем единицы, меньше 2^(−(r−1)) - это и есть грубая запись его величины. Назовём r рангом хеша: номер позиции первой единицы. Ранг 1 у половины хешей, ранг 2 у четверти, ранг r - у доли 1/2ʳ. Наибольший ранг среди n разных элементов близок к log₂ n, и чтобы его записать, хватает пяти-шести бит - как в счётчике Морриса, хранится логарифм.

Шаг четвёртый: много ячеек. Один наибольший ранг даёт оценку с точностью до степени двойки и с большим разбросом. HyperLogLog заводит m = 2ᵖ ячеек. Первые p битов хеша выбирают ячейку, по остальным считается ранг, и ячейка хранит наибольший ранг, который в неё пришёл. В каждую ячейку попадает около n/m разных элементов, так что 2 в степени содержимого ячейки - грубая оценка n/m.

Шаг пятый: объединение. Оценки по ячейкам усредняют, но не арифметически: одна ячейка, в которую случайно пришёл очень большой ранг, испортила бы арифметическое среднее. Берут гармоническое среднее - количество, делённое на сумму обратных величин; в нём большие выбросы почти не весят:

оценка = α · m² / (2^(−M₁) + 2^(−M₂) + … + 2^(−M_m))        α ≈ 0,7213 / (1 + 1,079 / m)

Mⱼ - содержимое ячейки j; постоянная α убирает смещение, найденное авторами алгоритма. В рабочем диапазоне относительная стандартная ошибка асимптотически близка к 1,04 / √m.

Правило

HyperLogLog с m = 2ᵖ ячейками: первые p битов хеша - номер ячейки, ранг остатка хеша - номер позиции его первой единицы; ячейка хранит наибольший ранг. Оценка числа различных элементов - α · m² / Σ 2^(−Mⱼ) без коррекции смещена при малом числе элементов: там используют число пустых ячеек. В рабочем диапазоне относительная стандартная ошибка приблизительно 1,04 / √m. Это стандартное отклонение, а не гарантированный предел ошибки. Повторы элемента не меняют сводку. Две сводки одного размера с одной хеш-функцией объединяются поэлементным максимумом, и результат равен сводке объединения множеств. Удалять элементы нельзя.

Разбор: оценка по минимуму и по пятидесятой точке

Две тысячи разных ключей. Хеш - случайное дробное число от генератора, засеянного ключом и «солью»: пять разных значений соли дают пять независимых хеш-функций. Для каждой печатаются две оценки: по наименьшему хешу и по пятидесятому по малости.

import random

def hesh(klyuch, sol):
    random.seed(klyuch * 100 + sol)
    return random.random()

n = 2000
k = 50
for sol in range(5):
    znacheniya = []
    for klyuch in range(n):
        znacheniya.append(hesh(klyuch, sol))
    znacheniya = sorted(znacheniya)
    po_minimumu = round(1 / znacheniya[0] - 1)
    po_k_mu = round((k - 1) / znacheniya[k - 1])
    print(po_minimumu, po_k_mu)

2001 1745
2086 2056
14537 2129
2238 2007
735 2014

Истинное число - 2000. Оценка по одному минимуму дала в третьей строке 14 537, в пятой - 735: ошибка в семь раз в одну сторону и почти втрое в другую. Оценка по пятидесятой точке во всех пяти опытах лежит между 1745 и 2129. Чем больше точек участвует в оценке, тем меньше значит везение одной из них; для k точек относительная ошибка около 1/√k.

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

Разбор: HyperLogLog на 256 ячейках

Хеш - 32 случайных бита. Старшие 8 битов - номер ячейки, младшие 24 - остаток. Ранг остатка считается через длину его двоичной записи: если остаток занимает L битов из 24, перед ним 24 − L нулей, и первая единица стоит на месте 24 − L + 1. Для нулевого остатка, в котором единицы нет вовсе, формула даёт 25 - на единицу больше длины остатка.

import random

p = 8
m = 1 << p
registry = [0] * m
alfa = 0.7213 / (1 + 1.079 / m)

def dobavit(klyuch):
    random.seed(klyuch)
    h = random.getrandbits(32)
    nomer = h >> (32 - p)
    hvost = h & ((1 << (32 - p)) - 1)
    rang = (32 - p) - hvost.bit_length() + 1
    if rang > registry[nomer]:
        registry[nomer] = rang

def ocenka():
    summa = 0
    for r in registry:
        summa = summa + 2 ** (-r)
    return alfa * m * m / summa

klyuch = 0
for otmetka in [1000, 5000, 20000]:
    while klyuch < otmetka:
        dobavit(klyuch)
        klyuch = klyuch + 1
    e = ocenka()
    print(otmetka, round(e), round((e - otmetka) / otmetka * 100, 1))

for klyuch in range(5000):
    dobavit(klyuch)
print(round(ocenka()), max(registry), round(1.04 / m ** 0.5 * 100, 1))

1000 1030 3.0
5000 4615 -7.7
20000 19240 -3.8
19240 14 6.5

Столбцы первых трёх строк: сколько разных ключей добавлено, оценка, ошибка в процентах. Ошибки - 3,0%, −7,7% и −3,8% при расчётной стандартной ошибке 6,5%; она напечатана последним числом.

Четвёртая строка: первые пять тысяч ключей добавлены повторно, и оценка не изменилась - 19 240. Повтор приносит тот же хеш, а значит, тот же ранг в ту же ячейку. Наибольший ранг во всей сводке - 14, так что каждой ячейке хватает четырёх бит: вся сводка для двадцати тысяч ключей - 128 байт.

Граница формулы - малые количества. Пока элементов меньше, чем ячеек, большинство ячеек пусты, и формула завышает. Тогда оценку берут из другого источника - из доли пустых ячеек. Каждый из n разных элементов минует данную ячейку с вероятностью 1 − 1/m, все вместе - с вероятностью (1 − 1/m)ⁿ, а это, как в модели шаров и корзин, близко к e^(−n/m). Ячейка пуста с такой вероятностью, и если пустых ячеек V, то n ≈ m · ln(m / V). Реализации переключаются на эту формулу, когда основная оценка меньше 2,5 · m.

Что ломается без этого

Складывают суточные оценки. Десять тысяч уникальных в понедельник и двенадцать во вторник не дают двадцати двух за два дня: кто-то приходил оба дня. Правильно - объединить две сводки поэлементным максимумом и оценить результат.

Плохой хеш. Вся конструкция опирается на то, что биты хеша ведут себя как случайные. Если в качестве хеша взять сам номер посетителя, выданный по порядку, ранги перестанут подчиняться закону 1/2ʳ, и оценка может ошибаться в разы.

Пересечение маленьких множеств вычитанием. Размер пересечения получают как |A| + |B| − |A ∪ B|. Каждое слагаемое известно с ошибкой около процента от своей величины, и если пересечение мало по сравнению с множествами, ошибка превышает ответ.

Ожидают точного числа. Два запроса к одной сводке дадут одно и то же, но это число - оценка. Счёт денег, билетов и голосов на ней не строят.

Зачем это в работе

Счётчики уникальных в аналитике. В Redis это команды PFADD, PFCOUNT и PFMERGE; сводка занимает 12 килобайт и даёт стандартную ошибку 0,81%. В аналитических базах данных функции приближённого счёта различных значений - APPROX_COUNT_DISTINCT и её родственники - во многих системах работают на этой же структуре.

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

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

Теперь сам

1. Остаток хеша в восьми битах - 00010110. Чему равен его ранг?
2. Сводка на 1024 ячейки. Какова относительная стандартная ошибка?
3. Сколько ячеек нужно для ошибки не больше 1%, если число ячеек - степень двойки?
4. Две сводки по четыре ячейки: [3, 1, 4, 2] и [2, 5, 1, 2]. Какой будет сводка объединения?
5. По сводкам: в понедельник 10 000 разных посетителей, во вторник 12 000, в объединённой сводке 15 000. Сколько посетителей пришли в оба дня?