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

Простой интуитивный подход

Для начала упростим нашу задачу и предположим, что наши данные - это равномерно распределенные в заранее известном интервале целые числа. Попробуем сгенерировать несколько наборов данных с одинаковым числом уникальных случайных чисел в каждом наборе. Пусть в каждом наборе будет 7 уникальных случайных чисел равномерно распределенных в интервале [0, 65535] (16 бит), сгенерируем 20 таких наборов:

В последней строке мы вычислили среднее значение в каждом столбике. Посмотрим на поведение чисел в каждом столбике. От набора к набору числа в отдельно взятом столбце менялись довольно сильно, но их среднее в конце-концов сходится ко вполне конкретному числу. Средние значения по столбцу имеют тенденцию с одинаковым расстоянием друг от друга заполнять весь интервал [0, 65535]. Как несложно заметить, среднее значение в первом столбце равно примерно шагу разбиения интервала [0, 65535] на равные части. Таким образом, если бы кто-то сгенерировал похожую таблицу и сказал бы нам среднее значение первого столбца, то мы бы могли оценить число уникальных элементов, которое было в каждом наборе. Для этого мы бы просто длину интервала (65535) поделили бы на шаг разбиения (среднее значение первого столбца равное 9226.95) и отняли единицу (потому что если колбасу разрезать на две равных части, разрез будет один, а не два). В нашем случае получается оценка в \( \frac { 65535 }{ 9226.95 } - 1 = 6.01 \) уникальных элементов в каждой выборке. Понятно, что чем больше выборок, тем точнее будет оценка.

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

Бит-паттерны

Представим наши случайные данные в виде двоичных чисел. Чем меньше число, тем больше в его двоичном представлении старших битов установлено в ноль:

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

\[ \underbrace { \frac { 1 }{ 2 } \times \cdots \times \frac { 1 }{ 2 } }_{ k } =\frac { 1 }{ { 2 }^{ k } } \]

Т.е. в среднем каждые \( { 2 }^{ k } \) раз старшие k битов будут установлены в ноль. Это позволяет нам грубо с точностью до степени двойки определять число уникальных элементов в выборке.

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

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

\[ { 2 }^{ 2.9 }=7.46 \]

Т.е. от средней арифметической оценки мы перешли к средней геометрической. Эта оценка является смещенной и требует дополнительного умножения на “константу Чапаева”, которая зависит от числа выборок.

Таким образом, вместо минимальных чисел в выборке, мы используем максимальное число старших битов установленных в ноль. Это позволит нам в дальнейшем сэкономить на памяти, т.к., например, вместо того, чтобы хранить 32-битное минимальное число, мы будем хранить максимальное число старших битов установленных в ноль, для чего достаточно 5 бит (\( 32 = { 2 }^{ 5 } \)). На самом деле, как несложно заметить, вместо подсчета числа старших битов установленных в ноль, можно считать число младших битов установленных в ноль - вероятности получаются одинаковыми.

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

Хеширование и стохастическое усреднение

Хоть у нас и есть одна большая выборка с неслучайными данными, возникает естественное желание создать искусственное отображение этих неслучайных данных в несколько (чем больше, тем лучше) выборок со случайными данными. Если говорить точнее, то мы хотим придумать такие хеш-функции \[ { f }_{ 1 }, { f }_{ 2 }, \dots , { f }_{ s } \] каждая из которых отображала бы первоначальную выборку с неслучайными данными в выборку со случайными данными, равномерно распределенными на каком-то интервале фиксированной длины (важно, чтобы значения всех функций были в одном интервале, чтобы потом ничего не нормировать). Таким образом у нас бы было s выборок со случайными данными, с примерно одинаковым числом случайных данных (в виду возможных коллизий) в каждой выборке и мы смогли бы тогда легко оценить число уникальных элементов, как мы это делали выше.

То, что мы хотим сделать, теоретически невозможно, но Дональд Кнут в третьем томе своей книги “Искусство программирования” (Вильямс, 2000) нас обнадеживает:

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

При наличии s таких хеш-функций, мы бы могли завести массив на s элементов (по элементу на каждую хеш-функцию), где каждый элемент массива \( r_i \) будет представлять максимальное число старших битов установленных в ноль среди полученных хеш-значений данной хеш-функции. Тогда число уникальных элементов можно было бы оценить, как

\[ constant\cdot { 2 }^{ \overline { R } } \]

где

\[ \overline { R } =\frac { 1 }{ s } \sum _{ i=1 }^{ s }{ { r }_{ i } } \]

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

Например, выберем k=4 (т.е. результирующих выборок будет \( m={ 2 }^{ 4 }=16 \)), и для какого-то элемента выборки, хеш-значение оказывается равным 1011100110101011 (16-битная хеш-функция, n=16) в двоичном представлении: \[ \underbrace { 1011 }_{ k=4 } \underbrace { 100110101011 }_{ n-k=12 } \] Это будет означать, что мы сгенерировали 12-битный хеш b100110101011=2475, который попадает только в выборку b1011=11, если нумеровать выборки с нуля.

Таким образом каждый элемент исходной выборки попадает случайным образом только в одну из m выборок, в то же время все m выборок, в виду случайности распределения, заполняются равномерно примерно одинаковым числом элементов, поэтому прежнюю оценку числа уникальных элементов необходимо умножить на m, чтобы оценить не просто число уникальных элементов в каждой отдельной выборке, а в целом, сколько было в первоначальной:

\[ constant\cdot m\cdot { 2 }^{ \overline { R } }=constant\cdot { 2 }^{ k }\cdot { 2 }^{ \overline { R } } \]

Алгоритм LogLog

Последняя формула, которую мы получили выше, является оценочной функцией в алгоритме LogLog. Единственным отличием является то, что вместо числа нулей в старших битах, там вычисляется позиция \( \rho (x) \) первого ненулевого старшего бита, т.е. на единицу большее значение, так что \( \rho (1)=1 \), \( \rho (001)=3 \) и т.д. Ну и, соответственно, “константа Чапаева” немного меняется в зависимости от числа выборок. Весь алгоритм выглядит так:

1. Выбираем число k такое, что \( m={ 2 }^{ k } \) будет числом выборок, между которыми распределяться все хеш-значения. От этого числа будет зависеть точность оценки.
2. Инициализируем массив из m элементов нулями: \( { M }^{ (1) },\dots ,{ M }^{ (m) } \)
3. Для каждого элемента первоначальной выборки вычисляем хеш (в двоичном виде): \[ x={ \left<{ b }_{ 1 }{ b }_{ 2 }\dots\right> }_{ 2 } \] определяем номер выборки, как значение первых k бит в системе счисления с основанием 2: \[ j:=1 + { \left< { b }_{ 1 }\dots { b }_{ k } \right> }_{ 2 } \] и обновляем соответствующий элемент массива: \[ { M }^{ (j) }:=\max { \left( { M }^{ (j) },\rho ({ b }_{ k+1 }{ b }_{ k+2 }\dots ) \right) } \]
4. Вычисляем оценку числа уникальных элементов как \[ E:={ \alpha }_{ m }\cdot m\cdot { 2 }^{ \frac { 1 }{ m } \sum _{ j=1 }^{ m }{ { M }^{ (j) } } } \] \[ { \alpha }_{ m }\sim { \alpha }_{ \infty }-\frac { 2{ \pi }^{ 2 }+{ \ln^{2}{2} } }{ 48m } \] \[ { \alpha }_{ \infty }={ e }^{ -\gamma }\frac { \sqrt { 2 } }{ 2 } \doteq 0.397011808 \] где \( \gamma \) - постоянная Эйлера. На практике константа \( \alpha_m \) может быть заменена на \( \alpha_\infty \) при \( m\ge64 \).

Стандартная ошибка оценки по алгоритму LogLog составляет \( \approx \frac { 1.30 }{ \sqrt { m } } \). Таким образом при m=256 и m=1024 стандартная ошибка составляет соответственно 8.1% и 4.1% от истинного числа уникальных элементов. Как мы помним, нам достаточно 5 бит для каждого из m элементов массива, поэтому при m=1024 используемая память будет составлять 5120 бит или 640 байт, что довольно неплохо, для стандартной ошибки в 4.1%.

Увеличиваем точность: алгоритмы SuperLogLog и HyperLogLog

Ученые Durand и Flajolet пришли к выводу, что можно еще улучшить алгоритм, если перед усреднением выбросить 30% элементов с наибольшими значениями и усреднить оставшиеся 70% значений, в таком случае стандартная ошибка оценки уменьшается с \( \frac { 1.30 }{ \sqrt { m } } \) до \( \frac { 1.05 }{ \sqrt { m } } \). Это значит, что при m=1024 и используемой при этом памяти 640 байт стандартная ошибка уменьшается с 4.1% до 3.28%. Так появился алгоритм SuperLogLog.

Следующим значительным вкладом Flajolet было использование гармонического среднего, вместо среднего геометрического, в результате чего возник алгоритм HyperLogLog, в котором стандартную ошибку оценки удалось уменьшить до \( \frac { 1.04 }{ \sqrt { m } } \). Хотя в целом алгоритм и очень похож на LogLog, но HyperLogLog немного более сложен, т.к. использует гармоническое среднее и требует дополнительных коррекций для больших и малых оценок уникальных элементов.

Практический вариант алгоритма HyperLogLog, который пригоден для оценки числа уникальных элементов лежащего в интервале \( \left[ 0,10^9 \right] \) с использованием количества выборок \( m=2^4,\dots ,2^{16} \) и 32-битной хеш-функцией представлен ниже:

1. Выбираем число k=4..16 такое, что \( m={ 2 }^{ k } \) будет числом выборок, между которыми распределяться все хеш-значения.
2. Определяем константы: \( \alpha_{16}=0.673 \), \( \alpha_{32}=0.697 \), \( \alpha_{64}=0.709 \), \( \alpha_m=0.7213/{\left(1+{1.079}/{m}\right) } \) при \( m\ge 128 \).
3. Инициализируем массив из m элементов нулями: \( { M }^{ (1) },\dots ,{ M }^{ (m) } \)
4. Для каждого элемента первоначальной выборки вычисляем хеш (в двоичном виде): \[ x={ \left<{ b }_{ 1 }{ b }_{ 2 }\dots{ b }_{ 32 } \right> }_{ 2 } \] определяем номер выборки, как значение первых k бит в системе счисления с основанием 2: \[ j:=1 + { \left< { b }_{ 1 }\dots { b }_{ k } \right> }_{ 2 } \] и обновляем соответствующий элемент массива: \[ { M }^{ (j) }:=\max { \left( { M }^{ (j) },\rho ({ b }_{ k+1 }{ b }_{ k+2 }\dots{ b }_{ 32 } ) \right) } \] где \( \rho(x) \) - позиция первого ненулевого старшего бита: \( \rho (1)=1 \), \( \rho (001)=3 \), \( \rho(\underbrace{0\dots0}_{n})=n+1 \)
5. Вычисляем “сырую” оценку числа уникальных элементов как \[ E:={ \alpha }_{ m }\cdot { m }^{ 2 }\cdot { \left( \sum _{ j=1 }^{ m }{ { 2 }^{ -{ M }^{ (j) } } } \right) }^{ -1 } \]
   • Если \( E\le\frac{5}{2}m \), то пусть \( V \) - число регистров \( M^{(j)} \) равных нулю, тогда при \( V\neq0 \) \[ E^{ * }:=m\cdot \ln { \frac { m }{ V } } \] иначе \( E^{ * }:= E \) (коррекция малых оценок)
   • Если \( E\le\frac{1}{30}{2}^{32} \), то \( E^{ * }:= E \) (коррекция средних оценок)
   • Если \( E>\frac{1}{30}{2}^{32} \), то \[ E^{*}:=-{2}^{32}\ln{\left(1-{E}/{{2}^{32}}\right) } \] (коррекция больших оценок)
6. Возвращаем \( E^{*} \) - скорректированную оценку числа уникальных элементов

Параллельные вычисления и объединение результатов

Одним несомненным преимуществом алгоритмов семейства LogLog является то, что их можно легко распараллеливать. В самом деле, если посмотреть на 4-ый шаг алгоритма HyperLogLog, то несложно заметить, что можно разбить первоначальную выборку на несколько более мелких и выполнить 4-ый шаг отдельно для каждой из них. После этого полученные массивы легко объединить в один, оставляя максимальное значение соответствующих регистров. Главное, чтобы применялась одна и та же хеш-функция и число выборок m было одинаковым. Тогда результат, как несложно заметить, будет точно таким же, как если бы мы производили оценку только по первоначальной выборке.

Кстати, это же свойство помогает нам легко объединять независимые оценки друг с другом. Предположим, у нас есть n оценок числа уникальных посетителей страниц товаров \( P_1, P_2, \dots, P_n \). Если мы хотим узнать сколько имеется всего уникальных пользователей, которые посетили хотя бы один из группы интересующих нас товаров, мы можем легко это сделать просто объединив массивы регистров соответствующих товаров. При этом понятно, что пользователь, который посетил страницы всех товаров, будет учтен как один.

Точно также, если у нас есть группа серверов в кластере, предоставляющих какой-то сервис, можно независимо на каждом сервере считать, например, число уникальных пользователей, а затем объединять результаты всех серверов, чтобы определить, скольких уникальных пользователей обслуживал весь кластер (ведь один уникальный пользователь мог обслуживаться несколькими серверами в кластере). Ну и на этой основе можно сделать какие-то простые предупреждающие тригеры. Например, если число уникальных пользователей за единицу времени сильно увеличилось, то либо бизнес пошел в гору, либо вас досят. :) И как мы уже знаем, для этого не нужно держать всех уникальных пользователей в памяти, достаточно буквально килобайта данных (ну или больше, если нужна точность, например, при 64 килобайтах стандартная ошибка будет составлять 0.4%).