Вот почему алгоритм HyperLogLog стал моим новым фаворитом.

1656683171 vot pochemu algoritm hyperloglog stal moim novym favoritom

Алекс Надолин

1*ij4OThN8DISD0zwH-7UlWQ
Фото Ника Хиллиера на Unsplash

Время от времени я сталкиваюсь с концепцией, которая настолько проста и мощна, что мне жаль, что я открыл такую ​​невероятную и красивую идею.

Я открыл себе HyperLogLog (HLL) пару лет назад и влюбился в него сразу после того, как прочитал, как redis решил добавить структуру данных HLL.

Идея HLL очень проста, но очень мощна. Именно это делает его широко распространенным алгоритмом, который используют такие гиганты Интернета, как Google и Reddit.

Сбор номеров телефонов

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

0*oIVPnmV6cE4mAbaK

В конце мероприятия ко мне подходит Томми со своей цифрой – скажем, 17 – и я говорю ему, что пообщался с 46 людьми.

Очевидно, что я победитель, но Томми разочарован, поскольку он думает, что я считал тех же людей несколько раз. Он считает, что видел, как я общался только с 15-20 людьми.

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

В конце следующей конференции мы встречаемся с очень длинным списком имен и угадайте что? Томми имел на пару больше встреч, чем я! Мы смеемся, и, обсуждая наш подход к подсчету уникальных, Томми приходит к замечательной идее:

«Алекс, знаешь что? Мы не можем ходить с ручкой и бумагой и искать список имен, это действительно непрактично! Сегодня я общался с 65 разными людьми, и перечислять их имена на этой бумаге было настоящим мучением. Я трижды сбился со счета и пришлось начинать с нуля!

«Да, я знаю, но есть ли у нас альтернатива?»

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

«Подожди, Томми, ты едешь слишком быстро! Замедлите секунду и приведите пример…»

«Конечно, просто спросите у каждого последние 5 цифр, ладно? Предположим, они соответствуют «54701». Начального нуля нет, поэтому самой длинной последовательностью начальных нулей является 0. Следующее лицо, с которым вы разговариваете, скажет «02561» – это ноль в начале! Итак, ваша самая длинная последовательность теперь равна 1».

«Ты начинаешь понимать меня…»

«Да, значит, если мы разговариваем с несколькими людьми, вероятность того, что самая длинная нулевая последовательность будет 0. Но если мы разговариваем, возможно, с 10 людьми, у нас больше шансов, что это будет 1».

«Теперь представьте, что вы скажете мне, что ваша самая длинная нулевая последовательность – это 5 – вы, пожалуй, общались с тысячами людей, чтобы найти кого-то из 00000 в номере телефона!»

«Чувак, ты проклятый гений!»

И вот как важно работает HyperLogLog, друзья мои.

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

Это создает невероятное преимущество перед отслеживанием каждого элемента в наборе. Это невероятно эффективный способ подсчитать уникальные значения относительно высокой точности.

«Алгоритм HyperLogLog может оценивать мощности, превышающие 10⁹ с относительной точностью (стандартная ошибка) 2%, используя только 1,5 Кб памяти»

Фанджин Ян Быстро, дешево и на 98% правильно: оценка кардинальности больших данных

Поскольку я могу слишком упрощать, давайте рассмотрим некоторые детали HLL.

Детальнее HLL

HLL является частью семейства алгоритмов, направленных на оценку кардинальности, иначе известную как «проблема разного подсчета». Как можно эффективно подсчитать количество уникальных объектов в наборе данных?

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

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

IP address of the viewer: 54.134.45.789
HLL hash: 010010101010101010111010...

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

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

В оригинальной статье есть еще несколько деталей о том, что означает хорошая функция хеширования для HLL:

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

Подсчитываемые элементы относятся к определенной области данных D, мы предполагаем, что задана хеш-функция, h : D → {0, 1}∞; то есть мы ассимилируем хешированные значения до бесконечных двоичных строк {0, 1}∞ или эквивалентно действительным числам единичного интервала.

[…]

Мы постулируем, что хэш-функция была разработана таким образом, что хешированные значения очень напоминают унифицированную модель случайности, а именно, биты хешированных значений считаются независимыми и имеют каждую вероятность [0.5] возникновение».

Филипп Флажоле HyperLogLog: анализ почти оптимального алгоритма оценки мощности

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

Возвращаясь к нашему примеру, представьте, что первое лицо, с которым вы разговариваете на конференции, говорит вам, что его номер заканчивается на 00004 – джекпот!

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

Не бойтесь больше, поскольку эту проблему HLL родил для решения.

Не многие знают, что Филипп Флажоле, один из идей HLL, долгое время занимался проблемами оценки кардинальности. Достаточно долго придумать алгоритм Флажоле-Мартина в 1984 году и (супер-)LogLog в 2003 году.

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

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

Вместо того чтобы брать последние 5 цифр телефонного номера, мы берем 6 из них. Теперь мы сохраняем самую длинную последовательность начальных нулей вместе с первой цифрой («ведро»).

Это значит, что наши данные будут выглядеть так:

Input:708942 --> in the 7th bucket, the longest sequence of 0s is 1518942 --> in the 5th bucket, the longest sequence of 0s is 0500973 --> in the 5th bucket, the longest sequence of 0s is now 2900000 --> in the 9th bucket, the longest sequence of 0s is 5900672 --> in the 9th bucket, the longest sequence of 0s stays 5
Buckets:0: 01: 02: 03: 04: 05: 26: 07: 18: 09: 5
Output:avg(buckets) = 0.8

Как видите, если бы мы не использовали сегменты, мы бы использовали 5 как самую длинную последовательность нулей. Это негативно повлияет на нашу оценку.

Хотя я упростил математику по сегментам (это не просто среднее значение), вы можете полностью понять, насколько этот подход имеет смысл.

Интересно наблюдать, как Флажоле обращается к дисперсии в своих произведениях:

«Хотя мы имеем оценку, которая уже достаточно хорошая, ее можно значительно улучшить. Дюран и Флажоле заметили, что отдаленные значения в значительной степени снижают точность оценки; Выбрасывая наибольшие значения перед усреднением, можно повысить точность.

В частности, выбросив 30% ведер с наибольшими значениями и усредняя лишь 70% ведер с меньшими значениями, точность можно повысить с 1,30/кв.м (м) до 1,05/кв.м (м)! Это означает, что наш предыдущий пример с 640 байт состояния и средней ошибкой 4% теперь имеет среднюю ошибку примерно 3,2%, без дополнительного увеличения пространства.

Наконец, основной вклад Flajolet и других в статью HyperLogLog заключается в использовании другого типа усреднения, взяв среднее гармоническое вместо только что применявшегося среднего геометрического. Делая это, они могут снизить ошибку до 1,04/sqrt(m), опять же, не требуя увеличения состояния».

Ник Джонсон — Повышение точности: SuperLogLog и HyperLogLog

HLL в дикой природе

Итак, где мы можем найти применение HLL? Два замечательных веб-примера:

  • BigQuery для эффективного подсчета уникальных в таблице (APPROX_COUNT_DISTINCT())
  • Reddit, где используется для подсчета количества уникальных просмотров публикации

В частности, посмотрите, как HLL влияет на запросы в BigQuery:

SELECT COUNT(DISTINCT actor.login) exact_cntFROM `githubarchive.year.2016`6,610,026 (4.1s elapsed, 3.39 GB processed, 320,825,029 rows scanned)
SELECT APPROX_COUNT_DISTINCT(actor.login) approx_cntFROM `githubarchive.year.2016`6,643,627 (2.6s elapsed, 3.39 GB processed, 320,825,029 rows scanned)

Второй результат приближен (с частотой ошибок ~0,5%), но занимает долю времени.

Короче говоря: HyperLogLog отличный!

Теперь вы знаете, что это такое и когда его можно использовать, так что выходите и делайте с ним невероятные вещи!

Дальнейшее чтение

Впервые опубликовано на odino.org (13 января 2018 г.).

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *