Считаем число уникальных объектов

2 minute read

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

Статистика

С последним счетчиком вышла загвоздка. Статистику строим на основании заказов у одного клиента (количество заказов — первый счетчик слева), а у одного клиента может быть несколько заказов. Нас интересует число уникальных клиентов. Конечно же, первая идея была сделать distinct в SQL — но distinct начинает адово втупливать на большом объеме данных (даже с правильным индексом). Поскольку фича про статистику (месяцы, годы работы с клиентами…), то почти все запросы на distinct тупят!

Count-distinct problem — вообще-то, не такая простая задачка, как кажется. Почему тупит distinct в SQL? Потому что наивный подход предполагает хранить уникальные объекты в хеш-табличке или дереве поиска, и, встречая очередной элемент, проверять, не видели ли мы его раньше. А это O(N) памяти, что не очень-то хорошо, если N большое и запросы частые.

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

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

HyperLogLog — яркий пример такого неточного алгоритма. Зацени — алгоритм может посчитать distinct на миллиардах элементов, используя всего 1.5 kb памяти, с относительной точностью 2% (стандартная ошибка среднего). Пруф! Алгоритм супер популярный, готовая реализация есть в ElasticSearch, Riak, Redis, в SQL Server не завезли :(

Что почитать:

  • My favorite algorithm (and data structure): HyperLogLog. Здесь клево разбирается идея, которая стоит за алгоритмом — на бытовом уровне. Представь, что ты с другом оказался на конференции, и вы устроили челлендж, кто познакомится с большим числом людей. У тебя и друга плохая память на лица. Как определить победителя, но не сильно заморачиваться с выписыванием паспортных данных, СНИЛС и ИНН?
  • View counting at Reddit. Практическая статья про то, как ребята из Reddit используют HyperLogLog, Redis, Kafka и Cassandra для подсчета уникальных просмотров треда. Уже только обилие buzz-word’ов должно зацепить!
  • HyperLogLog: the analysis of a near-optimalcardinality estimation algorithm. Оригинальный paper про HyperLogLog для любителей матана.

Updated:

Leave a Comment