Алгоритм HyperLogLog, или Оцениваем мощность множества за O(1)18.01.2023 14:31

Привет, Хабр! Меня зовут Максим, я учусь на третьем курсе МФТИ. Этим летом я участвовал в студенческой программе, которую проводила команда Tarantool. Если кратко, суть программы в том, чтобы самостоятельно или в команде решить исследовательскую задачу в определенный срок.

Моей задачей была реализация алгоритма HyperLogLog. Во время работы я не обнаружил русскоязычных материалов о практической реализации алгоритма, поэтому решил, что полученный мною опыт может быть полезен сообществу. Статья будет интересна людям, интересующимся алгоритмами и практическим программированием. Для понимания темы не потребуется ни специальных математических знаний, ни предварительного знакомства с алгоритмом.

Когда полезен HyperLogLog?

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

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

У алгоритма есть несколько особенностей:

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

Идея алгоритма на пальцах

Разберемся с базовой идеей работы HyperLogLog. Как я говорил ранее, алгоритм работает с потоком данных. Это значит, что HyperLogLog последовательно получает и обрабатывает элементы из потока.

Суть обработки следующая: мы получаем очередной элемент, считаем его хеш и рассчитываем в нем количество нулей, идущих подряд. ½ всех возможных хешей начинается с 1, ¼ c 01, 1/8 с 001 и так далее.

Назовем количество нулей, идущих подряд + 1 рангом хеша: $rank(hash) = clz(hash) + 1$ . Ранг характеризует редкость хеша. Логично предположить, что если мы встретили «редкий» хеш, то наше множество — «большое». Для оценки мощности множества нам достаточно знать лишь максимальный ранг в потоке.

А насколько наше множество большое? В среднем, на $2^n$ хешей встретится один хеш с рангом $n+1$ . Поэтому $estimate = 2^{max \: rank}$ . Понятно, что это довольно грубая оценка. Потому что один редкий хеш в потоке может существенно исказить оценку. Однако базовая идея такая, ее осознание поможет лучше понять работу алгоритма.

Посчитаем объем памяти, необходимый для оценки множества размером $2^{64}$ или меньше. Для представления такого множества значения хеш-функции должны быть не меньше $log_{2}2^{64} = 64$ бит. Чтобы получить оценку нам нужет только максимальный ранг, для хранения которого потребуется $log_{2}64 = 6$ бит. В общем случае для оценки множества размером $N$ потребуется $log_{2}(log_{2}(N))$ бит, этим и объясняется название алгоритма.

HyperLogLog

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

В алгоритме HyperLogLog применяется следующая стратегия разбиения на подпотоки:

Номер подпотока определяется последними битами хеша. Это число мы будем называть индексом.
Чем больше бит мы отдадим под индекс — тем точнее будет оценка, поэтому число мы будем называть параметром точности алгоритма, или просто точностью.
Регистром будем называть пару из индекса и максимального полученного им ранга.

При такой стратегии алгоритм будет описываться следующими формулами:

$m = 2^{precision}$

$standard \: error < \frac{1,04}{\sqrt{m}}$

$memory \: usage = m \times 6bit$

$estimate = \alpha \times \left ( \sum_{0}^{m-1} 2^{-rank_{i}}\right )^{-1}$

$\alpha \simeq 0,7m^{2}$

standard error — выводится с помощью нетривиальной математики. Для точности оценки в $1 \%$ достаточно отдать $14$ бит под индекс, $2^{14}=16384$ регистров.

memory usage — храним массив из $m$ регистров, индекс регистра определяется индексом в массиве, для хранения значения ранга достаточно $log_{2}(64 — precision) < 6$ бит. Для точности оценки $1 \%$ потребуется $12 288$ байт.

estimate — опять сложная математика, но по сути, среднее гармоническое с нормировочным коэффициентом.

До этого мы предполагали, что примерно ½ всех возможных хешей начинается с 1, ¼ c 01, 1/8 с 001 и так далее. Но чтобы это выполнялось, значения нашей хеш функции должны быть равномерно распределены, то есть вероятность получения любого значения хеша от $0$ до $2^{64} — 1$ должна быть одинаковой. Если это условие не будет выполнено, формула для оценки станет неверной.

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

Приведу пример. Допустим мы будем раскладывать наши хеши по очереди — первый хеш идет в первый подпоток, второй во второй и так далее. Подобное разбиение решает проблему с появлением одного редкого хеша в потоке. А если он будет повторятся? Тогда в какой-то момент он может попасть во все подпотоки и испортить статистику вообще везде.

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

Познакомившись с базовой теорией алгоритма, приступим к реализации.

Bias correction

В практической плоскости меньше всего вопросов вызывает формула $memory \: usage$ . Но формулы $estimate$ и $standard \: error$ уже не кажутся такими очевидными. Мы никак не можем проверить формулу $standard \: error$ до реализации самого алгоритма, а вот формулу оценки легко прощупать заранее.

Давайте проверим формулу оценки, как это делают физики: рассмотрим граничный случай с очевидным ответом. В нашем случае это будет пустое множество и очевидный ответ — $0$ .

Еще ни один хеш не был добавлен, значит значения всех рангов равны $0$ , а значит в знаменателе формулы оценки имеем просто сумму $1$ от $0$ до $m — 1$ .

$estimate \approx {\frac{0,7 m^2}{m}}=0,7m = 183500$ , если $precision = 18$ . Очевидно, оценка даже не близка к действительности. Не теряя надежды, давайте посмотрим как ведёт себя оценка в зависимости от фактической мощности множества:

Из графика видно, что при малых мощностях, действительно, наблюдается стабильное отклонение, но при больших мощностях ( $\approx1250000$ для $precision = 18$ ) оценка начинает сходиться к мощности множества. Точка, после которой оценка начинает сходится, на графике обозначена как bias threshold и на практике всегда меньше $5m$ .

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

Что мы можем сделать?

Как видно из графика, кривая смещения гладкая. Значит можно аппроксимировать зависимость $bias(raw \: estimate)$ каким-нибудь полиномом. Но на практике проще аппроксимировать $cardinality(raw \: estimate$ ), а затем найти кривую смещения как $bias(raw \: estimate) = raw \: estimate — cardinality(raw \: estimate)$ . В самом алгоритме будем считать сырую оценку согласно формуле из теории и вычитать смещение, если сырая оценка не превышает $bias \: threshold$ .

Применив коррекцию смещения получим следующий график:

Выглядит неплохо, мы избавились от смещения при малых мощностях, но давайте посмотрим как ведет себя погрешность:

Из графика видно, что при малых мощностях погрешность выше заявленной, но граница сходимости оценки сместилась влево и стала порядка $500000 \approx 2m$ . Это, определенно, улучшение. Но мы не решили главную проблему алгоритма, нам все еще нужно знать границу сходимости и минимальный размер множества.

Неплохая попытка, но это всё ещё выглядит, как решение для узкого круга задач.

LinearCounting

Решить проблему с небольшими мощностями нам поможет еще один вероятностный алгоритм: LinearCounting. Кратко опишу принцип его работы. Алгоритм также работает с потоком данных и применяет хеширование для рандомизации данных. Пусть имеется m возможных значений хеш функции, получив очередной элемент, вычисляем от него хеш и запоминаем, что полученный хеш появился в потоке. Пусть $m_{1}$ — число различных хешей, появившихся в потоке, тогда оценка получается согласно следующей формуле:

$estimate = m \times ln\left ( \frac{m}{(m - m_{1})} \right )$

В отличии от алгоритма HyperLogLog, алгоритм LinearCounting имеет наибольшую точность для небольших множеств, при этом эта точность выше теоретической точности алгоритма HyperLogLog. А это именно то что нам и нужно! Но при увеличении мощности множества растет и погрешность, так как возрастает вероятность коллизий.

Теперь нам нужно понять, как мы можем применить LinearCounting. Для применения алгоритма нам нужно знать число возможных значений хеш-функции, и число различных хешей, появившихся в потоке. В качестве значений хеш-функции возьмем значения индексов (их у нас $m$ ), а чтобы понять, появился ли хеш с данным индексом в потоке, достаточно посмотреть на ранг соответствующего регистра. Если мы не получали такой индекс, то ранг будет равен начальному значению 0, но если получили, его ранг будет не меньше 1, так как $rank = clz(hash) + 1 \geq 0 + 1$ .

Получается, чтобы дать оценку, нам нужно просто посчитать число регистров с нулевым рангом.

Отлично, мы теперь мы можем оценивать небольшие множества, но когда нам стоит применять LinearCouning, а когда HyperLogLog? Наиболее естественный ответ — пока LinearCouning точнее. К сожалению, алгоритм LinearCouning не имеет простой формулы для погрешности, поэтому исследуем ее эмпирически: посчитаем погрешности оценки для большого количества множеств. Аппроксимируем кривую, описывающую погрешность алгоритма. Для определенности будем фиттировать полиномом 4 степени. Определим, в какой точке $E$ его погрешность начинает превышать погрешность алгоритма HyperLogLog. Тогда для оценок меньше $E$ , будем применять алгоритм LinearCouning, а для больших — HyperLogLog.

Измерив эти границы для различных параметров точности, могу сказать, что, границу можно оценить грубо как $2m$ , это эмпирический факт, который нам понадобится в будущем.

Получим следующий график для погрешностей:

После применения вышеизложенных техник получим следующую зависимость погрешности от оценки для нашего алгоритма:

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

Но это нас не остановит и мы будем дальше улучшать алгоритм.

Sparse representation

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

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

Вместо того, чтобы хранить 64-битный хеш, мы можем хранить пару из ранга и соответствующего хешу индекса. Для ранга нам нужно 6 бит, а для индекса мы можем взять даже больше бит, чем того требует алгоритм, но не меньше. Для удобства под индекс отдадим 26 бит. Тогда пару будет удобно хранить в 32-битном числе, и она будет иметь следующую структуру: в первых 26 битах будет храниться индекс, а в последних 6 — ранг. Используя пары, мы добьемся большей точности оценки и станем экономнее расходовать память.

При этом, хранение хешей может быть не такой уже и плохой идеей. Хотя размер хеша и в два раза больше размера пары, точность такой оценки при хранении хешей будет не меньше точности алгоритма HyperLogLog с параметром точности равным 64, $error < \frac{1,04}{\sqrt{2^{64}}} \approx 2,4 \times 10^{-10}$ , точность оценки при использовании пар будет равна $\frac{1,04}{\sqrt{2^{26}}} \approx 1,27 \times 10^{-4}$ , что не так уж и плохо.

Фактическая же погрешность будет меньше, так как при при использовании разреженного представления мы можем хранить не больше $m \times \frac{bitsize(register)}{bitsize(pair)} = m \times \frac{6}{32} < m$ пар, при этом граница алгоритма LinearCouning порядка $2m$ , а значит в разреженном представлении для оценки мы всегда используем LinearCouning.

Структура разреженного представления должна быть понятна: мы просто храним в динамическом массиве пары. Давайте обсудим переход от разреженного представления к плотному:

Условие перехода — размер массива пар превышает размер массива регистров. Для перехода нужно уметь восстанавливать индекс соответствующего регистра и его ранг. Ранг уже хранится в паре, осталось восстановить индекс.

Напомню, что для расчета индекса, мы просто берем последние $precision$ бит в хеше. В разреженном представлении $precision = 26$ , значит в паре хранятся последние 26 бит оригинального хеша. Если бы мы получили этот же хеш, используя плотное представление, мы бы взяли уже последние 18 бит этого хеша. Очевидно, последние 18 бит хеша содержатся в последних 26 битах хеша. Для получения индекса регистра достаточно отбросить первые $26 — precision$ бит из индекса пары.

Применив разреженное представление, получим следующих график для погрешности алгоритма.

Как и ожидалось, оценки малых множеств оказались наиболее точными. Потом наблюдается резкий скачок, при переходе от разреженного представления к плотному, и начинается область применения алгоритма LinearCounting.Точность оценки все еще выше точности алгоритма HyperLogLog, но она растет и, достигнув погрешности алгоритма HyperLogLog, мы начинаем использовать алгоритм HyperLogLog c коррекцией, а дальше и в чистом виде.

Желающие могут ознакомиться с моей реализацией: github.com/KaitmazianMO/TSoC-HyperLogLog.

Неожиданно, операции над множествами

Алгоритм позволяет оценивать мощности не только множеств, но также и объединения множеств, не теряя при этом точности. Чтобы посчитать мощность объединения множеств A и B, нужно сопоставить каждому множеству соответствующую HyperLogLog структуру $HLL(A)$ и $HLL(B)$ . Используя эти структуры мы можем построить новую структуру $HLL(A + B)$ , содержащую объединение этих множеств. Для этого давайте рассмотрим как будет вести себя ранг одного из регистров, при добавлении элементов.

Если мы добавим все элементы из множества A, тогда ранг будет равен максимальному рангу в этом множестве, соответствующему рассматриваемому регистру, аналогично для множества B. Если же мы добавим все элементы из A и все элементы из B, тогда в регистре уже будет содержаться максимальный ранг для объединения множеств, который равен максимуму из соответствующих максимумов для множеств A и B. То есть $rank_i(A + B) = max(rank_i(A), rank_i(B))$ .

Значит при построении $HLL(A + B)$ нам нужно записать в его регистры максимальные ранги из множеств A и B. При этом погрешность оценки не изменится, так как полученная структура будет идентична структуре, в которую добавили все элементы из множеств A и B.

Для чего это может быть полезно? Мы можем быстро оценивать число элементов, удовлетворяющих сложным условиям поиска. Например, торговая площадка может оценить для пользователя, сколько ноутбуков обладает 4 или 6 или 8 ядрами, и при этом в них установлена IPS матрица и SSD диск. Если для всех условий будет заранее построена структура HLL, это оценку можно сделать почти моментально, за $O(m) = O(1)$ .

Для углубления в тему рекомендую несколько материалов, на которые я опирался при подготовке статьи и реализации алгоритма:

Скачать Tarantool можно на официальном сайте, а получить помощь — в Telegram-чате.