Перейти к содержимому
Последнее обновление

Приближённая дедупликация с помощью HLL

HLL (HyperLogLog) представляет собой решение для приближённой дедупликации на основе вероятностного алгоритма. С погрешностью в пределах 1%-2% оно вычисляет кардинальность (Distinct Count) огромных наборов данных с очень низкими затратами памяти и времени.

Сценарии использования​

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

Алгоритм HLL обладает следующими характеристиками:

ХарактеристикаЗначение
Пространственная сложностьO(mloglogn)
Временная сложностьO(n)
Диапазон погрешностиОколо 1%-2% (зависит от набора данных и хеш-функции)

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

  • Кому подходит: для сценариев с огромными объёмами данных, допустимой погрешностью 1%-2% и необходимостью найти баланс между производительностью запросов и затратами на хранение.
  • Как использовать: при создании таблицы задайте для столбца тип HLL и функцию агрегации HLL_UNION; при загрузке данных формируйте значения HLL с помощью HLL_HASH(); при выполнении запросов используйте для агрегации HLL_UNION_AGG().
  • Типичные задачи: сбор статистики UV, дедупликация пользователей, оценка количества уникальных устройств.

Что такое HyperLogLog​

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

Наглядное объяснение испытания Бернулли​

  • Предположим, у монеты две стороны, и при одном броске вероятность выпадения каждой стороны составляет 50%.
  • Подбрасывайте монету до выпадения орла и считайте эту последовательность одним завершённым испытанием.
  • Повторите процесс n раз, то есть до тех пор, пока орёл не выпадет n раз. Обозначим количество бросков в каждом испытании через k, а в i-м испытании через k_i.
  • Среди n испытаний обязательно найдётся максимальное количество бросков, которое обозначим k_max (например, в одном испытании потребовалось 12 бросков, прежде чем выпал орёл).

Выводы​

  • Количество бросков в каждом из n испытаний Бернулли не превышает k_max.
  • Хотя бы в одном из n испытаний Бернулли количество бросков равно k_max.

С помощью метода максимального правдоподобия зависимость между n и k_max можно оценить следующим образом: n = 2 ^ k_max.

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

Использование HLL для приближённой дедупликации​

Шаг 1: создание таблицы​

Цель: создать таблицу с агрегацией, поддерживающую дедупликацию с помощью HLL.

Ограничения:

  1. Для целевого столбца необходимо задать тип HLL и функцию агрегации HLL_UNION.
  2. Столбец типа HLL нельзя использовать в качестве столбца Key.
  3. Длину и значение по умолчанию указывать не нужно. Система сама определяет длину столбца HLL в зависимости от степени агрегации данных.

Пример:

create table test_hll(
        dt date,
        id int,
        name char(10),
        province char(10),
        os char(10),
        uv hll hll_union
)
Aggregate KEY (dt,id,name,province,os)
distributed by hash(id) buckets 10
PROPERTIES(
        "replication_num" = "1",
        "in_memory"="false"
);

Шаг 2: загрузка данных​

Цель: преобразовать исходные детальные данные в значения столбца HLL с помощью HLL_HASH() и записать их в таблицу.

Пример данных (test_hll.csv):

2022-05-05,10001,test01,Beijing,windows 
2022-05-05,10002,test01,Beijing,linux 
2022-05-05,10003,test01,Beijing,macos 
2022-05-05,10004,test01,Hebei,windows 
2022-05-06,10001,test01,Shanghai,windows 
2022-05-06,10002,test01,Shanghai,linux 
2022-05-06,10003,test01,Jiangsu,macos 
2022-05-06,10004,test01,Shaanxi,windows

Команда Stream Load​

curl --location-trusted -u root: -H "label:label_test_hll_load" \
    -H "column_separator:," \
    -H "columns:dt,id,name,province,os,uv=hll_hash(id)" -T test_hll.csv http://fe_IP:8030/api/demo/test_hll/_stream_load

Пример результата загрузки​

# curl --location-trusted -u root: -H "label:label_test_hll_load"     -H "column_separator:,"     -H "columns:dt,id,name,province,os, pv=hll_hash(id)" -T test_hll.csv http://127.0.0.1:8030/api/demo/test_hll/_stream_load

{
    "TxnId": 693,
    "Label": "label_test_hll_load",
    "TwoPhaseCommit": "false",
    "Status": "Success",
    "Message": "OK",
    "NumberTotalRows": 8,
    "NumberLoadedRows": 8,
    "NumberFilteredRows": 0,
    "NumberUnselectedRows": 0,
    "LoadBytes": 320,
    "LoadTimeMs": 23,
    "BeginTxnTimeMs": 0,
    "StreamLoadPutTimeMs": 1,
    "ReadDataTimeMs": 0,
    "WriteDataTimeMs": 9,
    "CommitAndPublishTimeMs": 11
}

Шаг 3: запрос данных​

Цель: получить результаты приближённой дедупликации с помощью функций агрегации HLL.

Примечание: напрямую запрашивать исходные значения столбцов HLL нельзя. Обращаться к ним в запросах можно только через функции агрегации HLL.

Общее количество UV​

mysql> select HLL_UNION_AGG(uv) from test_hll;
+---------------------+
| hll_union_agg(`uv`) |
+---------------------+
|                   4 |
+---------------------+
1 row in set (0.00 sec)

Эквивалентная запись:

mysql> SELECT COUNT(DISTINCT uv) FROM test_hll;
+----------------------+
| count(DISTINCT `uv`) |
+----------------------+
|                    4 |
+----------------------+
1 row in set (0.01 sec)

Количество UV по дням​

mysql> select HLL_UNION_AGG(uv) from test_hll group by dt;
+---------------------+
| hll_union_agg(`uv`) |
+---------------------+
|                   4 |
|                   4 |
+---------------------+
2 rows in set (0.01 sec)
ФункцияНазначение
HLL_UNION_AGG(hll)Функция агрегации для оценки кардинальности всех данных, соответствующих условиям запроса
HLL_CARDINALITY(hll)Оценивает кардинальность отдельного значения столбца HLL
HLL_HASH(column_name)Формирует значение типа HLL для использования при Insert или загрузке данных (пример загрузки приведён выше)
HLL_EMPTY()Создаёт пустое значение HLL для заполнения значений по умолчанию при insert или загрузке данных
Report issue