Как решается задача подсчета

 

Мы воспользуемся блестящим блогом {21} и начнем с метода К‑Minimum Values [ K‑ минимальные величины]. Идея очень проста. Допустим, значения, которые надо посчитать, равномерно разбросаны в каком‑то интервале. В нашем примере с номерами карточек от 01 до 50 и их непредсказуемым использованием это предположение вполне разумно. Теперь давайте не будем запоминать все увиденные значения, а запомним лишь несколько самых маленьких.

Возьмем снова пример с кредитными картами, где трансакций было 30, а разных карт – 22. Мы можем запомнить, скажем, всего пять самых маленьких значений. В данном случае это номера 01, 02, 05, 08 и 10. Пять значений в интервале от 1 до 10. Значит, сколько разных значений мы встретим в интервале от 1 до 50? Интервал в пять раз длиннее, значения разбросаны равномерно. Стало быть, всего значений будет

 

5 (значений) × 5 (интервалов) = 25 (значений)

 

примерно двадцать пять. Поскольку число 10 находится на самой границе интервала, делается коррекция. Для большей точности в данном случае пользуются формулой

 

 

Это, конечно, не равняется точному ответу 22, но достаточно близко к нему. При этом нам пришлось запомнить только 5 значений, а не 22.

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

Можно ли сделать лучше? Оказывается, можно. Настоящую революцию в мире счетчиков совершил французский математик Филипп Флажоле. Его результаты были опубликованы в 2007 году в статье {22}, а сейчас широко применяются в системах обработки данных, в том числе BigQuery Google и Redis компании Amazon.

 

HyperLogLog‑счетчики

 

Филипп Флажоле и соавторы предложили новый метод подсчета под названием HyperLogLog.

LogLog означает, что по сравнению с числом объектов нам нужно очень маленькое количество оперативной памяти. Под LogLog здесь понимают двойной логарифм по основанию 2, и это на самом деле очень маленькое число. Например, при миллиарде объектов двойной логарифм будет

 

log₂(log₂(1000 000 000)) ≈ 4,9,

 

то есть порядка 5 битов памяти – всего пять нулей и единиц!

Приставка Hyper использована тоже не просто так. Идею подобного метода Флажоле предлагал и раньше, но предыдущие версии давали слишком грубые результаты.

Метод HyperLogLog сильно улучшил точность, что позволило применить его на практике.

Как и в методе К‑Minimum Values, Флажоле исходил из предположения, что записи в базе данных можно представить в виде разбросанных случайным образом чисел. На практике это действительно так, потому что каждой записи, будь то число, имя, адрес или название, присваивается так называемое хеш‑значение. Это последовательность из нулей и единиц одинаковой небольшой длины. Если две записи совпадают (например, одно и то же название повторяется два раза), то и их хеш‑значения совпадают. Например, хеш‑значения длины 8 для разных веб‑магазинов могут выглядеть примерно как в табл. 7.1. Мы выделили жирным шрифтом название, которое повторяется два раза:

 

Таблица 7.1. Фиктивный пример хеш‑значений веб‑магазинов

 

На практике обычно применяют хеш‑значения длины 32 или 64. Хеш‑значения генерируются с помощью специальных программ, так называемых хеш‑функций, весьма нетривиальным образом. Усмотреть связь между изначальной записью и ее хеш‑значением фактически невозможно. Поэтому можно считать, что хеш‑значения присваиваются случайным образом. И метод К‑Minimum Values, и метод Флажоле пользуются не самими записями, а их хеш‑значениями.

Напомним, что по методу К‑Minimum Values нужно запомнить несколько самых маленьких хеш‑значений. Флажоле пошел еще дальше, предложив запоминать только число нулей в начале хеш‑значения.

Для примера опять возьмем хеш‑значения длины 8. Допустим, нам попалось хеш‑значение

 

00001011

 

Последовательности, у которых в начале ровно четыре нуля, встречаются не очень часто, в среднем одна на 32. Если мы наткнулись на такую последовательность, то можно предположить, что в среднем мы видели 32 разных хеш‑значения, то есть число объектов – примерно 32. Что, если мы видели еще больше нулей, скажем пять?

 

00000101

 

Такие последовательности еще более редки, одна на 64, то есть объектов примерно 64! Разве не гениально?

Идея очень простая. Чем больше нулей, тем реже встречаются такие хеш‑значения. Если какому‑то объекту случайно досталось очень редкое хеш‑значение, значит, объектов было много.

Запомнить при этом нужно только одно число – самое большое количество нулей, которое мы видели, например 4. Для этого достаточно минимального объема памяти. Если нам попалось хеш‑значение, у которого нулей больше, например 5, мы выкидываем из памяти 4 и запоминаем 5[22].

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

В HyperLogLog для улучшения точности добавлено много хитрых приемов. Хеш‑значения разбиваются на регистры, оценка считается в каждом регистре отдельно, а потом усредняется специальным образом. Кроме этого, учитывается коррекция, когда объектов очень мало или, наоборот, очень много. Подробно об этом можно прочитать в блоге {23}. Там можно даже запустить программу и посмотреть, как метод работает.

На практике стараются достичь еще более высокой точности. Собственно, об этом статья сотрудников Google {24}, о которой мы упоминали выше. Она так и называется «HyperLogLog на практике». Например, авторы уделили особое внимание коррекции при маленьком числе объектов. Грубо говоря, если клиент в состоянии посчитать объекты вручную, то и компьютер должен давать абсолютно правильный ответ.

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