HyperLogLog

В «Войне и мире» 436 069 слов, а разных — 47 585. Чтобы сосчитать их точно, нужно помнить все уже встреченные слова: одни только буквы займут около 785 КБ. А если слова — это посетители сайта за год, и их миллиарды? HyperLogLog отвечает на вопрос «сколько разных» иначе: он не помнит ни одного слова, а хранит несколько сотен маленьких чисел и по ним оценивает ответ. Нажмите «Пуск»: роман течёт словами через регистры, а сверху растут две линии — точное число разных слов и оценка.

При 64 регистрах — 48 байтах — оценка гуляет вокруг правды на десяток процентов. Переключите на 1024 регистра, 768 байт: линии почти сливаются. Над графиком — хеш текущего слова: первые биты (подсвечены) выбирают регистр, а дальше считается, сколько нулей идёт до первой единицы. Регистр помнит самую длинную такую серию. Это вся информация, которую HyperLogLog хранит.

Идея

Представьте, что человек весь день бросал монету и сказал вам только одно: самая длинная серия орлов подряд, которую он видел, — двенадцать. Сколько раз он бросал? Серия из 12 орлов случается примерно один раз на 2¹² = 4096 попыток, значит, бросков было порядка нескольких тысяч. Хеш слова — это 32 честных броска монеты: биты хорошего хеша выглядят случайными и независимыми. Одно и то же слово всегда даёт одни и те же биты, поэтому повторы ничего не добавляют — считаются только разные слова.

Хешируем каждый элемент. Первые p бит хеша выбирают один из m = 2^p регистров, а в остальных битах находим позицию первой единицы — ранг. Регистр хранит наибольший ранг из попавших в него элементов. Если в регистр попало около n/m разных элементов, его значение близко к log₂(n/m). Оценка — α_m·m², делённое на сумму 2^−M_j по регистрам: среднее гармоническое значений 2^M_j, умноженное на m и на поправочный множитель.

Почему много регистров, а не один? Одна самая длинная серия — слишком шумная мера: если повезло и серия вышла на две позиции длиннее, оценка ошиблась вчетверо. Разбив поток на m независимых частей и усреднив, мы уменьшаем ошибку в √m раз. Почему среднее гармоническое, а не обычное? Регистры, которым повезло, дают огромные 2^M_j, а среднее гармоническое к таким выбросам почти нечувствительно — в этом отличие HyperLogLog от его предшественника LogLog, где регистры усреднялись в показателе.

Насколько точно

Доказательство Флажоле и соавторов занимает десятки страниц и опирается на тонкий анализ, поэтому здесь — проверка. Ниже все 47 585 разных слов романа сосчитаны сто раз, каждый раз с другим зерном хеша, то есть со своими «бросками монеты». Каждая точка — ошибка одного прогона, полоса — ±1,04/√m.

Около двух третей точек внутри полосы — как и должно быть для одного стандартного отклонения. При 1024 регистрах полоса — ±3,25 %, при 16 384 — ±0,81 %: в 16 раз больше памяти даёт вчетверо меньшую ошибку. Память при этом смешная: регистру хватает 6 бит, потому что серия нулей в 32-битном хеше не длиннее 32. 16 384 регистра — 12 КБ, и столько же они занимали бы для миллиарда разных элементов.

Когда разных элементов мало

Формула рассчитана на то, что в каждый регистр что-то попало. Пока разных элементов меньше, чем регистров, многие регистры пусты, и формула сильно завышает: для одного-единственного элемента и 1024 регистров она даёт около 739. На этот случай есть поправка из другой задачи — о шарах и корзинах. Если n шаров бросить в m корзин наугад, пустыми останутся примерно m·e^−n/m корзин. Значит, по числу пустых регистров V можно оценить n ≈ m·ln(m/V). Этот приём называется линейным счётом, и HyperLogLog переключается на него, когда оценка не больше 2,5·m и пустые регистры ещё есть. Посмотрите на начало первой сцены: оценка точна уже с первых слов именно благодаря ему.

Объединение — максимум

У наброска есть свойство, ради которого HyperLogLog и используют в распределённых системах. Если два потока посчитаны двумя набросками с одинаковым хешем, то набросок их объединения — поэлементный максимум регистров: каждый элемент попал бы в тот же регистр с тем же рангом. Поэтому серверы могут считать каждый своё, а потом складывать наброски; дни можно объединять в недели, недели — в год, и ошибка не накапливается. В листинге ниже две половины романа посчитаны отдельно: сумма их оценок даёт 62 545 — каждое общее слово посчитано дважды, — а максимум по регистрам даёт 47 761 при точных 47 585.

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

Код

Тот же хеш MurmurHash3, что в сценах, на всём тексте романа из песочницы: оценки при 64, 1024 и 16 384 регистрах и объединение двух половин.

Ошибки этого прогона — +7 %, +1,8 % и +1,0 % — укладываются в типичные 13 %, 3,25 % и 0,81 %, хотя последняя чуть больше одного стандартного отклонения: это одна оценка, а не среднее. Регистр выбирают старшие биты хеша, ранг считается в младших — bit_length в Python и bits.Len32 в Go дают длину числа, и первая единица стоит сразу за нулями, которые до этой длины не дотягивают.

Сколько это стоит

Добавление элемента — один хеш и одно сравнение, O(1). Оценка — проход по регистрам, O(m), объединение двух набросков — тоже O(m). Память — m регистров по 6 бит независимо от того, сколько элементов прошло. Точный подсчёт требует памяти, пропорциональной числу разных элементов: хеш-множество из 47 585 слов — сотни килобайт, а из миллиарда идентификаторов — десятки гигабайт. Сравните с фильтром Блума: он отвечает «был ли этот элемент» и тратит биты на каждый элемент, HyperLogLog отвечает только «сколько было разных» и не растёт вовсе.

Где работает

Redis. Команды PFADD, PFCOUNT и PFMERGE хранят HyperLogLog с 16 384 регистрами: до 12 КБ на ключ и стандартная ошибка 0,81 %. Префикс PF, как написал автор Redis Сальваторе Санфилиппо, — в честь Филиппа Флажоле. Для маленьких множеств Redis хранит набросок в сжатом виде и расширяет его по мере роста.

Аналитика. Функция APPROX_COUNT_DISTINCT в Google BigQuery построена на HyperLogLog++ — варианте, который в 2013 году описали инженеры Google: 64-битный хеш, эмпирическая поправка смещения для средних чисел и разреженное представление для малых. Отчёты «уникальные посетители за месяц» в системах веб-аналитики считают так же: набросок за каждый день хранится, а за любой период собирается максимумом.

Базы данных. Планировщику запроса нужно знать, сколько разных значений в столбце, чтобы выбрать порядок соединения таблиц. Точный подсчёт по большой таблице дорог, а набросок обновляется на ходу.

История

Идея оценивать число разных элементов по битам хешей принадлежит Филиппу Флажоле и Найджелу Мартину: в 1985 году они описали вероятностный подсчёт, где отслеживается, какие позиции первой единицы уже встречались. В 2003 году Марианна Дюран и Флажоле предложили LogLog с регистрами и средним в показателе, а в 2007 году Флажоле, Эрик Фюзи, Оливье Гандуэ и Фредерик Мёнье — HyperLogLog со средним гармоническим и ошибкой 1,04/√m. Флажоле умер в 2011 году; через три года команды HyperLogLog в Redis получили его инициалы.

Задачи

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