Ефективний count distinct

Вибір кількості унікальних значень за певний проміжок часу – не дуже часте завдання. У .io нам потрібно визначати кількість унікальних користувачів, які заходили на сайт за будь-який час.

Звичайно, є дуже просте рішення на основі звичайного SQL. Достатньо зберігати у просту таблицю унікальні id користувачів та час їх входу:

Тоді рішення виглядатиме так:

# Звичайна вибірка count distinct у Mysql

Однак це рішення працює досить повільно навіть на невеликих таблицях (мільйони записів).

# Дуже повільно, і це на 2.5млн записів у таблиці

Сумарна кількість аудиторії, яку ми вважаємо, — близько 50 млн. осіб на добу, тому нас це не влаштувало.

MySQL та count(distinct)

Mysql не дуже добре підходить для вирішення задач. Але спробувати варто. Щоб усе запрацювало швидше, можна зробити кілька оптимізації.

1. Правильний індекс

Mysql все одно буде сканувати всі рядки із запиту для визначення унікальних id. Колонка часу допоможе їх суттєво скоротити. Тому вона має йти першою в індексі:

2. Квант часу

У нашому випадку мінімальний проміжок часу для підрахунку значень не може бути меншим за день. Немає сенсу зберігати в один день більше одного запису для кожного користувача. Значить колонку часу потрібно робититипу dateі ставитиунікальний індекс:

# Колонка time має тип date, тепер кожен день буде тільки один запис з унікальним ID

Vertica та count(distinct)

Ця векторна база добре оптимізована під агрегатні вибірки. Однак підрахунок кількості за вибраним проміжком часу працює всього в 2-3 рази швидше, ніж MySQL.

# Незначно швидше, ніж Mysql

approximate_count_distinct()

Vertica підтримує агрегатну функцію approximate_count_distinct() , яка вважає кількість унікальних значень приблизно. Вона працює на порядок швидше за звичайний запит, проте має помилку близько 1%:

Redis та HyperLogLog

Redis має спеціальне сховищеHyperLogLog. Воно дозволяє зберігати туди ключі, а потім отримувати кількість унікальних ключів у цьому сховищі. Обмеження в тому, що список збережених ключів дістати неможливо. Перевага в тому, що одне таке сховище займає всього 12 Кб, здатне зберігати 264 елементів і повертає результат з похибкою всього 0.8%.

Пристрій HyperLogLog

HyperLogLog – це ймовірнісний алгоритм для підрахунку унікальних елементів.

Принцип алгоритму можна пояснити простим прикладом із життя. Уявіть, що ви деякий час підкидали монету, підраховуючи кількість безперервних послідовних випадів решки. Якщо у вас вийшла послідовність довжиною всього в 3 решки поспіль, можна припустити, що ви підкидали монетку не дуже довго. З іншого боку, якщо у вас вийшло 15, то, можливо, ви витратили більшу частину дня.

Але якщо вам пощастило, і з першого разу вийшла послідовність з 10 решок, після чого ви припинили це безглузде заняття, то приблизна думка про витрачений час буде вкрай невірною. Щоб збільшити точність апроксимації, потрібно буде повторити експреімент, але цього разу використовувати 10 монет і 10 аркушів паперу, на яких ви записуватимете найдовші послідовності рішок, що випали. Таким чином судження про витрачений час буде набагато точнішим.

HyperLogLog обчислює хеш кожного нового елемента. Частина цього хеша (у двійковомупредставлення) використовується для індексу регістру (поділяємо безліч нулів та одиниць на m-число підмножин, наші пари монета+аркуш паперу). А інша частина використовується для підрахунку довжини послідовності перших нулів і максимального значення цієї послідовності (довжина послідовності рішок, що випали). Імовірність послідовності n+1 нулів дорівнює половині ймовірності послідовності довжиною n.

кількість

Тому використовуючи значення різних регістрів, які прив'язані до максимальних нулів послідовностей для даного підмножини, HyperLogLog здатний забезпечити наближену потужність множини з високою точністю. Якщо є m-підгруп та n-елементів, тоді в кожній групі в середньому буде n/m унікальних елементів, а середня по всіх підгрупах дає досить точну оцінку значення log2(n/m).

Підрахунок унікальних значень

У найпростішому випадку достатньо зберігати всі значення в елемент HLL:

# Функція pfcount поверне кількість унікальних значень у ключику hll, побачимо 1

Тут ми зберегли ключ "hll" 1 елемент (число 1) і вивели кількість унікальних елементів. Додамо ще кілька елементів в цей же ключик:

# Тепер на екрані побачимо 3

Як і слід, ми отримали результат 3 (тобто всього 3 унікальні елементи записані в цьому ключі).

І найголовніше - цей підхід працює на 3-4 порядки швидше, ніж аналогічне рішення на основі SQL.

Тимчасові фільтри

І все-таки, стандартного рішення недостатньо. Нам необхідно мати можливість вибирати період для підрахунку унікальних значень. На цей випадок Redis вміє робити склеювання ключів HLL прямо під час вибірки:

# Вибірка поверне 5 - кількість унікальних елементів відразу в двох ключах HLL

Для вибірки можна використовувати будь-якекількість ключів hll. А нам необхідно отримувати кількість унікальних користувачів щодня. Отже, для вирішення достатньо зберігати ідентифікатор користувача HLL ключ при відвідуванні ним сторінки. Назва ключа міститиме суфікс - дату відвідування:

# Збереження інформації про відвідування за день

Тепер потрібно вибрати кількість унікальних користувачів за будь-який проміжок часу. Для цього потрібно склеїти всі ключі за дати всередині цього проміжку:

# Результатом буде кількість унікальних відвідувачів у проміжку з 10.06 по 13.06 2016 року

Найголовніше

SQL кошти погано справляються з підрахунком унікальних значень. Особливо якщо потрібно фільтрувати список. На невеликих обсягах даних достатньо використовувати правильні індекси MySQL. На обсягах понад 1 млн записів слід обміркувати можливість використання сховища HyperLogLog у Redis.

Прості та швидкі варіанти перенесення ключів Redis на інший сервер.

Як будуються по-справжньому великі системи на основі MySQL

2 приклад денормалізації для оптимізації бази даних

Як вирішувати типові завдання за допомогою NoSQL

Типи та способи застосування реплікації на прикладі MySQL

Основні поняття про шардінг та реплікацію

Пошук за великою кількістю тексту

Розподіл бази даних на кілька незалежних баз

Підвищення швидкості роботи запитів з MySQL Handlersocket

Що таке індекси в MySQL та як їх використовувати для оптимізації запитів

Перевірка роботи Mysql під навантаженням Sysbench

Як робити перерозподіл даних між серверами

Введення в hash-таблиці, основні методи боротьби з колізіями

Поділ таблиць даних на різні вузли

Рекомендації щодо налаштування Redis дляоптимізації ресурсів та підвищення стабільності на виробничому сервері

Найгірші практики під час роботи над зростаючими проектами

Правильне налаштування Mysql під навантаження та не тільки. Оновлено.

Оптимізація посторінкового виведення даних

Аналіз повільних запитів (профілювання) у MySQL за допомогою Percona Toolkit

Простий спосіб вибрати індекси для MySQL

Включення та робота з логом повільних запитів у Mysql

DROP INDEX у Mysql

Перегляд профілю запитів Mysql

5 параметрів, які варто оптимізувати в MySQL для Wordpress