Версия: 2.0.x

Использование HLL для приблизительного count distinct

Предпосылки

В реальных сценариях нагрузка на дедупликацию данных возрастает по мере увеличения объёма данных. Когда размер данных достигает определённого уровня, стоимость точной дедупликации становится относительно высокой. В этом случае пользователи обычно используют приблизительные алгоритмы для снижения вычислительной нагрузки. HyperLogLog (HLL), который будет представлен в этом разделе, является приблизительным алгоритмом дедупликации с превосходной пространственной сложностью O(mloglogn) и временной сложностью O(n). Более того, погрешность результата вычислений может контролироваться на уровне около 1%-10%, в зависимости от размера набора данных и используемой hash-функции.

Что такое HyperLogLog

HyperLogLog — это приблизительный алгоритм дедупликации, который потребляет очень мало места для хранения. Тип HLL используется для реализации алгоритма HyperLogLog. Он содержит промежуточные результаты вычисления HyperLogLog и может использоваться только как тип столбца-индикатора для таблиц данных.

Поскольку алгоритм HLL включает много математических знаний, мы проиллюстрируем его на практическом примере. Предположим, мы разрабатываем рандомизированный эксперимент A, то есть независимо повторяем подбрасывание монеты до первого выпадения орла; записываем количество подбрасываний монеты до первого орла как случайную величину X, тогда:

X=1, P(X=1)=1/2
X=2, P(X=2)=1/4
...
X=n, P(X=n)=(1/2)ⁿ

Мы используем тест A для построения рандомизированного теста B, который заключается в N независимых повторениях теста A, генерируя N независимых одинаково распределённых случайных величин X₁, X₂, X₃, ..., X_N. Берём максимальное значение случайных величин как X_max. Используя оценку максимального правдоподобия, оценочное значение N равно 2^X_max.

Теперь мы моделируем вышеуказанный эксперимент с использованием hash-функции на заданном наборе данных:

Тест A: Вычисляем hash-значение элементов набора данных и преобразуем hash-значение в двоичное представление. Записываем появление bit=1, начиная с младшего бита двоичного представления.
Тест B: Повторяем процесс теста A для элементов набора данных теста B. Обновляем максимальную позицию "m" первого появления бита 1 для каждого теста;
Оцениваем количество неповторяющихся элементов в наборе данных как m².

Фактически, алгоритм HLL разделяет элементы на K=2^k bucket на основе младших k битов hash-значения элемента. Подсчитывает максимальное значение первого появления бита 1, начиная с k+1-го бита, как m₁, m₂,..., m_k, и оценивает количество неповторяющихся элементов в bucket как 2^m₁, 2^m₂,..., 2^m_k. Количество неповторяющихся элементов в наборе данных — это суммированное среднее количества bucket, умноженное на количество неповторяющихся элементов в bucket: N = K(K/(2^-m₁+2^-m₂,..., 2^-m_K)).

HLL умножает поправочный коэффициент на результат оценки, чтобы сделать результат более точным.

Обратитесь к статье https://gist.github.com/avibryant/8275649 о реализации алгоритма дедупликации HLL с помощью SQL-операторов Selena:

SELECT floor((0.721 * 1024 * 1024) / (sum(pow(2, m * -1)) + 1024 - count(*))) AS estimate
FROM(select(murmur_hash3_32(c2) & 1023) AS bucket,
     max((31 - CAST(log2(murmur_hash3_32(c2) & 2147483647) AS INT))) AS m
     FROM db0.table0
     GROUP BY bucket) bucket_values

Этот алгоритм дедуплицирует col2 таблицы db0.table0.

Использует hash-функцию murmur_hash3_32 для вычисления hash-значения col2 как 32-битного знакового целого числа.
Использует 1024 bucket, поправочный коэффициент 0.721, и берёт младшие 10 битов hash-значения как индекс bucket.
Игнорирует знаковый бит hash-значения, начинает со следующего старшего бита к младшему биту и определяет позицию первого появления бита 1.
Группирует вычисленные hash-значения по bucket и использует агрегацию MAX для нахождения максимальной позиции первого появления бита 1 в bucket.
Результат агрегации используется как подзапрос, и суммированное среднее всех оценок bucket умножается на количество bucket и поправочный коэффициент.
Обратите внимание, что количество пустых bucket равно 1.

Вышеуказанный алгоритм имеет очень низкую погрешность при большом объёме данных.

Это основная идея алгоритма HLL. Если вас интересует, обратитесь к статье о HyperLogLog.

Как использовать HyperLogLog

Чтобы использовать дедупликацию HyperLogLog, вам нужно установить тип целевого столбца-индикатора как HLL и агрегатную функцию как HLL_UNION в операторе создания таблицы.
В настоящее время только Aggregate-таблица поддерживает HLL как тип столбца-индикатора.
При использовании count distinct для столбцов типа HLL Selena автоматически преобразует его в вычисление HLL_UNION_AGG.

Пример

Сначала создайте таблицу со столбцами HLL, где uv — агрегированный столбец, тип столбца — HLL, и агрегатная функция — HLL_UNION.

CREATE TABLE test(
        dt DATE,
        id INT,
        uv HLL HLL_UNION
)
DISTRIBUTED BY HASH(ID);

Примечание: При большом объёме данных лучше создать соответствующую rollup-таблицу для часто выполняемых HLL-запросов

Загрузите данные с помощью Stream Load:

curl --location-trusted -u <username>:<password> -H "label:label_1600997542287" \
    -H "column_separator:," \
    -H "columns:dt,id,user_id, uv=hll_hash(user_id)" -T /root/test.csv http://selena_be0:8040/api/db0/test/_stream_load
{
    "TxnId": 2504748,
    "Label": "label_1600997542287",
    "Status": "Success",
    "Message": "OK",
    "NumberTotalRows": 5,
    "NumberLoadedRows": 5,
    "NumberFilteredRows": 0,
    "NumberUnselectedRows": 0,
    "LoadBytes": 120,
    "LoadTimeMs": 46,
    "BeginTxnTimeMs": 0,
    "StreamLoadPutTimeMs": 1,
    "ReadDataTimeMs": 0,
    "WriteDataTimeMs": 29,
    "CommitAndPublishTimeMs": 14
}

Режим Broker Load:

LOAD LABEL test_db.label
 (
    DATA INFILE("hdfs://<hdfs_host>:<hdfs_port>/user/selena/data/input/file")
    INTO TABLE `test`
    COLUMNS TERMINATED BY ","
    (dt, id, user_id)
    SET (
      uv = HLL_HASH(user_id)
    )
 );

Запрос данных

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

SELECT HLL_UNION_AGG(uv) FROM test;

Этот оператор эквивалентен

SELECT COUNT(DISTINCT uv) FROM test;

Запрос uv за каждый день

SELECT COUNT(DISTINCT uv) FROM test GROUP BY ID;

Предостережения

Как выбрать между Bitmap и HLL? Если кардинальность набора данных составляет миллионы или десятки миллионов, и у вас есть несколько десятков машин, используйте count distinct. Если кардинальность составляет сотни миллионов и требуется точная дедупликация, используйте Bitmap; если приемлема приблизительная дедупликация, используйте тип HLL.

Bitmap поддерживает только TINYINT, SMALLINT, INT и BIGINT. Обратите внимание, что LARGEINT не поддерживается. Для других типов наборов данных, которые нужно дедуплицировать, необходимо построить словарь для сопоставления исходного типа с целочисленным типом. Построение словаря сложно и требует компромисса между объёмом данных, частотой обновления, эффективностью запросов, хранением и другими факторами. HLL не требует словаря, но требует, чтобы соответствующий тип данных поддерживал hash-функцию. Даже в аналитической системе, которая не поддерживает HLL внутренне, всё ещё возможно использовать hash-функцию и SQL для реализации дедупликации HLL.

Для обычных столбцов пользователи могут использовать функцию NDV для приблизительной дедупликации. Эта функция возвращает приблизительную агрегацию результатов COUNT(DISTINCT col), и базовая реализация преобразует тип хранения данных в тип HyperLogLog для вычисления. Функция NDV потребляет много ресурсов при вычислении и поэтому не очень подходит для сценариев с высокой параллельностью.

Если вы хотите выполнять анализ поведения пользователей, вы можете рассмотреть IntersectCount или пользовательские UDAF.

Предпосылки​

Что такое HyperLogLog​

Как использовать HyperLogLog​

Пример​

Предостережения​

Предпосылки

Что такое HyperLogLog

Как использовать HyperLogLog

Пример

Предостережения