Использование HLL для приблизительного подсчета уникальных значений

Предпосылки

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

Что такое 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.

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

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

Фактически, алгоритм HLL разделяет элементы на K=2^k корзин на основе младших k битов хеша элемента. Подсчитывает максимальное значение первого появления бита 1 начиная с k+1-го бита как m₁, m₂,..., m_k, и оценивает количество неповторяющихся элементов в корзине как 2^m₁, 2^m₂,..., 2^m_k. Количество неповторяющихся элементов в наборе данных является суммированным средним количества корзин, умноженным на количество неповторяющихся элементов в корзинах: 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.

Используйте хеш-функцию murmur_hash3_32 для вычисления хеш-значения col2 как 32-битного целого числа со знаком.
Используйте 1024 корзины, коэффициент коррекции равен 0.721, и возьмите младшие 10 битов хеш-значения в качестве индекса корзины.
Игнорируйте знаковый бит хеш-значения, начните со следующего старшего бита к младшему биту и определите позицию первого появления бита 1.
Сгруппируйте вычисленные хеш-значения по корзинам и используйте агрегацию MAX для поиска максимальной позиции первого появления бита 1 в корзине.
Результат агрегации используется как подзапрос, и суммированное среднее всех оценок корзин умножается на количество корзин и коэффициент коррекции.
Обратите внимание, что количество пустых корзин равно 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://starrocks_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/starrocks/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 не нуждается в словаре, но требует, чтобы соответствующий тип данных поддерживал хеш-функцию. Даже в аналитической системе, которая внутренне не поддерживает HLL, все еще возможно использовать хеш-функцию и SQL для реализации дедупликации HLL.

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

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

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

Что такое HyperLogLog​

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

Пример​

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

Предпосылки

Что такое HyperLogLog

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

Пример

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