Подсчёт уникальных пользователей

Проблема

Обычный способ подсчёта «уникальных пользователей» — это обработка больших логов, сортировка по идентификатору пользователя, удаление дубликатов и подсчёт. Это требует значительных вычислительных ресурсов. Кроме того, полученный результат нельзя обобщить. То есть, ежедневные подсчёты нельзя суммировать для получения еженедельных — некоторые пользователи будут учтены несколько раз.

Таким образом, проблема заключается в хранении подсчётов таким образом, чтобы позволить обобщение.

Решение

Давайте подумаем, что можно сделать с хэшем идентификатора пользователя. Хэш мог бы сопоставляться с битом в битовой строке. Значение BIT_COUNT битовой строки давало бы количество единиц, представляющих число пользователей. Но эта битовая строка должна быть огромной. Что если бы мы могли использовать более короткие битовые строки? Тогда разные идентификаторы пользователей сводились бы к одному и тому же биту. Предположим, что мы можем это решить.

Между тем, что насчёт обобщения? Ежедневные битовые строки могут быть объединены по оператору OR, чтобы получить аналогичную битовую строку для недели.

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

Увеличение значения BIT_COUNT

Достаточно случайный хэш (например, MD5) будет сводить идентификаторы пользователей к тем же битам с предсказуемой частотой. Нам нужно выяснить это и работать в обратном порядке. То есть, зная, что X процентов битов установлено, нам нужна формула, которая приблизительно показывает, сколько идентификаторов пользователей использовалось для получения этих битов.

Я смоделировал проблему, сгенерировав случайные хэши и рассчитал количество установленных битов. Затем, с помощью программного обеспечения Eureqa, я вывел формулу:

Y = 0.5456*X + 0.6543*tan(1.39*X*X*X)

Насколько она эффективна?

Формула достаточно точна. Она обычно отличается от правильного значения не более чем на 1%; в редких случаях отклонение составляет 2%.

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

Ещё одна рекомендация… Если вы производите обобщение за большой промежуток времени (например, с часовых данных до месячных), все битовые строки должны иметь одинаковую длину, и месячная строка должна быть достаточно длинной, чтобы вместить ожидаемое количество. Это, вероятно, приведёт к очень разреженным часовым битовым строкам. Следовательно, может быть целесообразно сжать часовые строки.

Postlog

Изобретено в ноябре 2013 года; опубликовано в апреле 2014 года

Будущее: Рик работает над фактическим кодом (сентябрь 2016 года). Это усложняется тем, что побитовые операции ограничены значением BIGINT. Однако с MySQL 8.0 (недавно выпущен), желаемые побитовые операции могут быть применены к BLOB, значительно упрощая мой код. Я надеюсь скоро опубликовать код до версии 8.0; код для 8.0 позже.

См. также

Рик Джеймс любезно разрешил нам использовать эту статью в базе знаний.

Сайт Рика Джеймса содержит полезные советы, инструкции, оптимизации и советы по отладке.

Исходный источник: http://mysql.rjweb.org/doc.php/uniques