Подсчет толпы: HyperLogLog простыми словами

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

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

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

Конечно, вы можете просто вести список всех посещаемых IP-адресов и подсчитывать их в конце дня? Что ж, вы можете, но если вы получаете сотни миллионов посетителей в день, в какой-то момент вам не хватит места для хранения всех этих IP-адресов.

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

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

С одного взгляда

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

Ваш собственный торговый центр

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

Сколько уникальных платежеспособных клиентов было в данный вторник в нашем самом декадентском магазине Sportland?

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

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

Если мы экстраполируем это на весь торговый центр, мы быстро столкнемся с проблемами. Sportland может сообщить о 400 клиентах, а Shoe Palace - о 300. В сумме получается 700 клиентов - но что, если 200 человек пойдут и в Sportland, и в Shoe Palace? В этом случае нам нужно настроить на 400 + 300−200 = 500 клиентов! Выше мы говорили, что отклонение на 1 или 2 - это нормально - имеет ли это значение, когда допустимая погрешность такая? Но здесь мы переоценили на 20%! Это неприемлемо.

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

Нам нужен способ однозначно идентифицировать каждого покупателя и подсчитывать их только один раз во всех магазинах. К счастью, мы уже можем это сделать, записав номер их кредитной карты при оплате. (По сомнительным соображениям гигиены Shopopolis не принимает наличные.)

Мы собираемся сделать предположение, что все 16 чисел на карточке полностью случайны и равномерно распределены.

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

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

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

Вероятностный подсчет

Давайте познакомимся с главным секретом HyperLogLog: вероятностями.

Если номер кредитной карты случайный, какова вероятность того, что последняя цифра будет нулем? Цифра может быть 0, 1, 2, 3, 4, 5, 6, 7, 8 или 9 - есть 10 возможных вариантов, а это означает, что есть 1 шанс из 10, что это 0. Мы можем рассуждать из этого, что если номер карты заканчивается на 0, всего мы, вероятно, видели не менее 10 человек. [1]

Давайте сделаем еще один шаг: каковы шансы, что число оканчивается на 00? Это та же проблема, что и выше, за исключением того, что мы переходим от 00 к 99. Таким образом, вероятность того, что карта оканчивается на 00, составляет 1 из 100. Это означает, что мы видим карту, заканчивающуюся на 00, мы, вероятно, видели около 100 клиенты!

Вернуться к кассирам

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

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

В конце концов, наш ранее упомянутый Джимм складывает все эти оценки и делит их на количество досок. Теперь это среднее значение является нашей оценкой для уникальных платежеспособных клиентов. [2]

Обратите внимание, как это потребовало очень небольшой работы от кассиров и Джимма. Но теперь у нас есть вероятностный ответ. Мы обменяли точность на память и скорость.

Результаты ковширования

Что, если в очень тихом магазине, в котором всего 1 покупатель весь день, окажется карточка с номером, заканчивающаяся на 00000, что приведет к неверному расчету?

Здесь мы можем использовать технику, называемую ведением, чтобы сгладить подобные выбросы. Мы делаем 10 «ведер», по одной на каждую возможную начальную цифру номера карты.

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

Пора вынести мусор

Группирование не только дает нам более плавный ответ, но и позволяет незаметно улучшить наш результат.

Выбросы (например, карточка с 5 нулями в конце) могут нанести ущерб нашим оценкам. Как только мы соберем все сегменты вместе, но прежде, чем мы получим среднее значение, Джимм выбросит самые большие 30% оценок. Доказано, что это увеличивает точность примерно на 25%! [3]

Кстати, что, если у данных нет хорошо пронумерованных идентификаторов, как у кредитных карт?

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

Используя двоичную систему (основание 2) вместо денари (основание 10, то, что используют номера кредитных карт), наша точность снова улучшается, поскольку проблема, упомянутая в сноске [1], больше не существует.

В заключение

Благодаря HyperLogLog наши кассиры могут легко сохранять оценку того, сколько уникальных клиентов у них было за день. Объединив эти результаты, Shopopolis может сделать быстрые и точные оценки для использования в будущем планировании.

HyperLogLog позволяет нам очень точно (хотя и несовершенно) подсчитывать огромное количество отдельных элементов с очень небольшим использованием памяти или процессора. Он также хорошо подходит для распространения во многих местах, как это видно по многочисленным магазинам.

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

Сноски

Это не совсем так. На самом деле, просмотр 10 уникальных карт дает нам только 65% шанс увидеть 0 в конце. Эта проблема исчезает при использовании двоичного кода (база 2) вместо базы 10.

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

3. В частности, отбрасывая 30% сегментов с наибольшими значениями и усредняя только 70% сегментов с меньшими значениями, точность может быть улучшена с 1.30/sqrt(m) до только 1.05/sqrt(m)! Я лично не буду делать вид, что понимаю, почему это так, но вы можете узнать больше и взглянуть на математику, лежащую в основе этого, на http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation