Представим задачу: хайлоад-сервис гонит поток данных — логи, IP-адреса, ID пользователей, миллиарды записей в сутки. Ваша задача — посчитать количество уникальных посетителей за неделю.

Первым решением может показаться завести HashSet и кидать туда ключи, а в конце посмотреть размер. Решение неплохое, но когда речь заходит о миллиардах записей — память будет слабым местом. Один IP-адрес (4 байта) как ключ в HashSet потянет за собой накладные расходы на ноды, указатели и хеши. На практике один элемент сжирает не меньше 50–100 байт. Поток в миллиард уникальных записей потребует под сотню гигабайт оперативной памяти. Это дорого, а если инстансов десять — то просто нереально.

Но существует алгоритм, который способен решить эту задачу примерно в 1.5 килобайта памяти с погрешностью около 2%? Без хранения самих данных и гигантских кластеров. Достаточно одного прохода по потоку и пары битовых трюков — именно так и работает HyperLogLog, алгоритм родом из математической статистики, который перевернул подход к подсчёту уникальности в Big Data.

HyperLogLog используют в Redis, BigQuery, ClickHouse, Presto. В этой статье мы разберем и реализуем этот алгоритм на C, а также узнаем его предысторию.

---

❯ Probabilistic Counting

Прежде чем нырять в код HyperLogLog, сделаем шаг назад. В основе всех вероятностных алгоритмов подсчёта лежит удивительно простая идея, которую в 1985 году предложили Флажоле и Мартин.

Если мы хешируем каждый элемент в случайное 64-битное число, то чем больше уникальных элементов мы уже увидели, тем выше вероятность, что среди их хешей найдется число с очень длинной последовательностью ведущих нулей. И эта суть сохранена до сих пор, HyperLogLog будет использовать идею, что вероятность того, что случайный хеш начинается как минимум с нулей, равна . Например, шанс встретить хеш с 30 ведущими нулями — примерно одна миллиардная ().

Обычно как пример берут подбрасывание монетки. Я не буду изменять традициям, и также давайте представим что мы бросаем монету. Вероятность выпадения орла — , двух орлов подряд — , девяти орлов подряд — . Если вы увидели последовательность из 9 орлов, вы с высокой вероятностью сделали больше 500 бросков.

С хешами — та же история. Вероятность встретить хеш, начинающийся с 9 нулей, равна . Если мы нашли такой хеш — скорее всего, уникальных элементов не меньше нескольких сотен. Если нашли 30 нулей подряд — их уже миллиард.

Работает это так, ибо хорошая хеш-функция распределяет биты равномерно. Вероятность конкретного паттерна из нулей и единиц — чистая степень двойки. Мы не храним сами элементы — только наблюдаем за случайностью их хешей.

Этот наивный метод называется Probabilistic Counting. У него есть одна огромная проблема: чудовищная дисперсия. Если вам случайно попался хеш с 30 нулями, ваша оценка улетит в миллиарды, даже если вы обработали всего сто элементов.

Нужно усреднять! Но как усреднять то, что может взлетать на порядки? Ответ пришёл через 18 лет — в 2003 году.

❯ LogLog

В 2003 году Дюран и Флажоле предложили весьма красивое решение проблемы выбросов. Все гениальное просто, так что и здесь решение оказалось несложным — разделение хеша на две части и использование корзин (регистров). Когда счетчик не один, а много, каждый из них наблюдает за своей частью данных, а в конце мы просто приводим среднее арифметическое.

Представьте, что 64-битный хеш — это длинная полоска битов. Вы режете её на две части:

1. Первые битов — это номер корзины (регистра). Всего у вас будет корзин.

2. Оставшиеся битов — это некая «полезная нагрузка», на которой вы будете искать ведущие нули.

Давайте возьмем, что (8 корзин). Пусть хеш элемента равен 101100101110...:

Каждая корзина хранит одно число — максимальную длину ведущих нулей, которую она когда-либо видела в своём остатке. Только максимум, потому что нас интересует самая редкая случайность.

К концу обработки в корзине №5 будет лежать число 5 — максимальная длина ведущих нулей, встреченная среди всех элементов, чей хеш начинался с 101.

Но почему это работает?

У нас есть независимых наблюдателей, и если в одной корзине произошла аномалия (скажем, rank = 40), остальные корзин дают нормальные значения. При усреднении выброс потеряет свою разрушительную силу дисперсии.

Формула оценки LogLog выглядит так:

Где:

• — значение в -й корзине (максимальный ранг)

• — количество корзин

• — корректирующий множитель ()

Разберём формулу по частям. Допустим, вы усреднили все ранги и получили 10, и тогда — это ваша «типичная» кардинальность в расчёте на одну корзину. Умножаете на корзин — получаете общую оценку.

Но почему алгоритм называется LogLog? Почему логарифм, и почему двойной? Если просто, в алгоритме фигурирует логарифм от логарифма.

Вдумайтесь: если у вас миллиард уникальных элементов, ожидаемый максимальный ранг будет около . А само значение в регистре — это и есть ранг. То есть вы храните не сами элементы и даже не их количество, а логарифм количества.

Но ведь — это число. Какой тут второй логарифм? А вот какой: количество регистров обычно выбирают от 16 до 65536. Это до . Число бит, нужное для хранения одного регистра — это бит.

Получается:

1. Первый логарифм: сам ранг — это

2. Второй логарифм: количество бит на регистр — это

Итоговая память: бит. Для и до миллиарда это около бит КБ. Алгоритм использует память, которая растёт как двойной логарифм от кардинальности.

Вроде бы все хорошо и прекрасно. Но внимательный читатель заметил, что мы разбираем HyperLogLog, значит где-то LogLog имеет погрешность.

И эта погрешность таится в арифметическом среднем. Вроде все логично — сложили все , поделили на , но здесь как раз и есть скрытый недостаток.

Вспомните, что ранг — это степень двойки в оценке. Если вы ошиблись на 1 в ранге, то оценка изменится в два раза. Арифметическое среднее на таких экспоненциальных величинах работает плохо.

Представьте две корзины со значениями 10 и 20. Арифметическое среднее , . Но правильное усреднение должно быть ближе к геометрическому: — совпало? Это случайность. А вот если значения 14 и 30: среднее , миллиона. Настоящее среднее должно быть около миллиона — близко, но теперь представьте, что одна корзина показывает 30, а остальные 16383 показывают 10.

Арифметическое среднее: , . Умножаем на около 16.8 миллионов. А реальная кардинальность, если 16383 корзины видят 10 ( элементов каждая) — примерно 16 миллионов. Оценка завышена на 5% из-за одного выброса.

Звучит не страшно? Но если выброс будет 40 вместо 30, искажение вырастет. А в Probabilistic Counting с одной корзиной выброс 40 означал бы оценку триллион вместо реальной тысячи. LogLog уже намного лучше, но всё ещё чувствителен.

Проще говоря, недостаток LogLog — это систематическая ошибка при малых кардинальностях ().

Проблема остаётся: арифметическое среднее и экспоненциальные величины — плохие друзья. Нужно что-то более устойчивое к выбросам. Именно эту проблему решил HyperLogLog в 2007 году, заменив арифметическое среднее на гармоническое в пространстве обратных степеней двойки.

❯ HyperLogLog

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

В 2007 году Флажоле с соавторами опубликовали HyperLogLog — алгоритм с небольшим изменением, которое сильно бустануло точность. Ключевое открытие звучит неожиданно просто: замените арифметическое среднее на гармоническое в пространстве обратных степеней двойки.

В чём здесь магия? Когда регистр получает аномально высокий ранг (например, 30), его вклад в арифметическое среднее — это 30, что заметно сдвигает сумму. А в гармоническом варианте его вклад — это , то есть примерно одна миллиардная. Такой регистр просто перестаёт влиять на итоговую сумму, словно его и не было. Выбросы автоматически нейтрализуются самой природой гармонического усреднения.

Формула оценки HyperLogLog выглядит так:

Где — корректирующий множитель, который зависит от количества регистров и вычисляется по формуле:

Для разных значений используются заранее вычисленные константы, но в общем случае подходит эта формула.

Однако гармоническое усреднение — это только половина решения. Вторая проблема LogLog заключалась в систематической ошибке при малых кардинальностях (когда количество уникальных элементов меньше ). Причина проста: если многие регистры ещё пусты (их значение равно 0), то , и такие регистры дают одинаковый вклад в сумму, искажая оценку.

HyperLogLog решает и эту проблему с помощью трёхуровневой коррекции:

1. Малые кардинальности (оценка ): если есть пустые регистры, используется линейная оценка , где — количество пустых регистров. Это даёт значительно более точный результат, чем сырая формула.

2. Средние кардинальности: сырая оценка работает отлично.

3. Очень большие кардинальности (близкие к ): применяется дополнительная коррекция, учитывающая, что пространство хешей конечно.

Благодаря этим улучшениям стандартная ошибка HyperLogLog составляет:

Сравните с LogLog, у которого ошибка была примерно . Разница кажется небольшой, но на практике она означает, что для достижения той же точности HyperLogLog требует почти на треть меньше памяти. При (16 КБ) ошибка составляет около 0.81% — то есть на 100 миллионах уникальных элементов вы ошибётесь примерно на 800 тысяч, а не на пару миллионов.

В итоге, HyperLogLog использует гармоническое среднее против выбросов, а коррекцию — против систематической ошибки при малых .

И теперь, когда мы поняли концепцию, можно перейти к реализации на C.

❯ Реализация на C

Сам алгоритм (без учета хеш-алгоритма) обходится примерно в 100 строк кода, а памяти требуется ровно столько, сколько нужно для хранения регистров — 16 384 байта при выбранной нами точности .

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

Я взял MurmurHash3 — современную некриптографическую хеш-функцию, которая известна своей скоростью и отличным распределением. В реализации представлен 64-битный вариант этой функции, адаптированный специально для HyperLogLog.

static inline uint64_t murmur3_fmix64(uint64_t k) {
    k ^= k >> 33;
    k *= 0xff51afd7ed558ccdULL;
    k ^= k >> 33;
    k *= 0xc4ceb9fe1a85ec53ULL;
    k ^= k >> 33;
    return k;
}

static inline uint64_t murmur3_64(const void* key, size_t len, uint64_t seed) {
    const uint8_t* data = (const uint8_t*)key;
    const int nblocks = len / 16;
    uint64_t h1 = seed;
    uint64_t h2 = seed;

    const uint64_t c1 = 0x87c37b91114253d5ULL;
    const uint64_t c2 = 0x4cf5ad432745937fULL;

    const uint64_t* blocks = (const uint64_t*)data;

    for (int i = 0; i < nblocks; i++) {
        uint64_t k1 = blocks[i * 2];
        uint64_t k2 = blocks[i * 2 + 1];

        k1 *= c1;
        k1 = (k1 << 31) | (k1 >> 33);
        k1 *= c2;
        h1 ^= k1;
        h1 = (h1 << 27) | (h1 >> 37);
        h1 += h2;
        h1 = h1 * 5 + 0x52dce729;

        k2 *= c2;
        k2 = (k2 << 33) | (k2 >> 31);
        k2 *= c1;
        h2 ^= k2;
        h2 = (h2 << 31) | (h2 >> 33);
        h2 += h1;
        h2 = h2 * 5 + 0x38495ab5;
    }

    const uint8_t* tail = data + nblocks * 16;
    uint64_t k1 = 0;
    uint64_t k2 = 0;

    switch (len & 15) {
        case 15:
            k2 ^= (uint64_t)tail[14] << 48;
        case 14:
            k2 ^= (uint64_t)tail[13] << 40;
        case 13:
            k2 ^= (uint64_t)tail[12] << 32;
        case 12:
            k2 ^= (uint64_t)tail[11] << 24;
        case 11:
            k2 ^= (uint64_t)tail[10] << 16;
        case 10:
            k2 ^= (uint64_t)tail[9] << 8;
        case 9:
            k2 ^= (uint64_t)tail[8];
            k2 *= c2;
            k2 = (k2 << 33) | (k2 >> 31);
            k2 *= c1;
            h2 ^= k2;
        case 8:
            k1 ^= (uint64_t)tail[7] << 56;
        case 7:
            k1 ^= (uint64_t)tail[6] << 48;
        case 6:
            k1 ^= (uint64_t)tail[5] << 40;
        case 5:
            k1 ^= (uint64_t)tail[4] << 32;
        case 4:
            k1 ^= (uint64_t)tail[3] << 24;
        case 3:
            k1 ^= (uint64_t)tail[2] << 16;
        case 2:
            k1 ^= (uint64_t)tail[1] << 8;
        case 1:
            k1 ^= (uint64_t)tail[0];
            k1 *= c1;
            k1 = (k1 << 31) | (k1 >> 33);
            k1 *= c2;
            h1 ^= k1;
    }

    h1 ^= len;
    h2 ^= len;
    h1 += h2;
    h2 += h1;

    h1 = murmur3_fmix64(h1);
    h2 = murmur3_fmix64(h2);
    h1 += h2;
    h2 += h1;

    return h1;
}

Эта функция обрабатывает входные данные блоками по 16 байт, перемешивая биты с помощью умножений и сдвигов. На выходе мы получаем 64 бита, которые ведут себя как равномерно случайные — идеальное сырьё для нашего вероятностного алгоритма.

Кстати, этот алгоритм в виде ГПСЧ я описывал в одной из своих статей.

Сама структура HyperLogLog удивительно проста — это массив 8-битных регистров:

#define HLL_P 14
#define HLL_M (1 << HLL_P)  // 16384
#define HLL_SEED 0xadc83b19adc83b19ULL

typedef struct {
    uint8_t registers[HLL_M];
} HyperLogLog;

Почему uint8_t? Максимальный ранг, который мы можем получить, — это 64 минус количество битов, отданных под индекс регистра. При максимальный ранг равен 50. Восьми битов (диапазон 0–255) более чем достаточно. Если бы мы захотели использовать , то максимальный ранг стал бы 48 — всё равно влезает в uint8_t.

Инициализация сводится к обнулению всех регистров и подготовке таблицы обратных степеней двойки:

static double* inv_pow2_table = NULL;

static void hll_init_inv_pow2(void) {
    static int initialized = 0;
    if (initialized) return;
    for (int i = 0; i < 64; i++) {
        inv_pow2_table[i] = 1.0 / (double)(1ULL << i);
    }
    initialized = 1;
}

void hll_init(HyperLogLog* hll) {
    memset(hll->registers, 0, HLL_M);
    hll_init_inv_pow2();
}

Таблица inv_pow2_table хранит предвычисленные значения для от 0 до 63. Это небольшое ускорение: вместо того чтобы каждый раз вычислять степень двойки при оценке, мы просто берём готовое значение из массива.

Функция ранга — это то место, где битовые трюки встречаются с математикой (версия у меня упрощенная, rho(w) = 1 + clz((w << p) | (1ULL << (p-1)))):

static inline uint8_t hll_rank(uint64_t hash, uint8_t p) {
    uint64_t rest = hash << p;
    if (rest == 0) {
        return 64 - p + 1;
    }
    return __builtin_clzll(rest) + 1;
}

Разберём, что здесь происходит. На входе у нас есть 64-битный хеш. Первые битов мы уже использовали для определения индекса корзины, поэтому они нас больше не интересуют. Мы сдвигаем хеш влево на позиций, отбрасывая эти биты. В оставшихся битах мы ищем позицию первого единичного бита.

Функция __builtin_clzll (count leading zeros) — это встроенная инструкция процессора, которая считает количество ведущих нулей в 64-битном числе. Большинство современных компиляторов (GCC, Clang) поддерживают её. Если бы мы писали код для Visual Studio, пришлось бы использовать __lzcnt64 или реализовывать эту операцию через битовые операции, но встроенная инструкция работает за один такт и значительно ускоряет алгоритм.

Особый случай — когда после сдвига все биты обнулились. Это означает, что в оставшихся битах не было ни одной единицы. Тогда ранг равен (все биты нулевые, плюс единица за то, что мы «перешли» за границу).

Добавление элемента — это три простых шага: хеширование, определение индекса, обновление регистра.

void hll_add(HyperLogLog* hll, const char* element) {
    uint64_t hash = murmur3_64_string(element, HLL_SEED);
    uint32_t index = hash >> (64 - HLL_P);
    uint8_t rank = hll_rank(hash, HLL_P);
    if (rank > hll->registers[index]) {
        hll->registers[index] = rank;
    }
}

Обратите внимание на вычисление индекса: hash >> (64 - HLL_P). Это эффективный способ взять старшие битов хеша. При мы сдвигаем 64-битное число вправо на 50 позиций, оставляя только 14 старших битов. Получается число от 0 до 16383 — идеальный индекс в массиве.

Функция hll_rank получает тот же самый хеш, но работает с ним иначе: она использует биты после сдвига, как мы разобрали выше.

Функция оценки — самая объёмная часть, но она просто реализует трёхуровневую коррекцию, о которой мы говорили в теоретической части:

uint64_t hll_estimate(const HyperLogLog* hll) {
    double sum = 0.0;
    int zero_registers = 0;

    for (int i = 0; i < HLL_M; i++) {
        sum += inv_pow2_table[hll->registers[i]];
        if (hll->registers[i] == 0) zero_registers++;
    }

    double raw = hll_alpha() * (double)((uint64_t)HLL_M * HLL_M) / sum;

    if (raw <= 2.5 * HLL_M) {
        if (zero_registers > 0) {
            return (uint64_t)((double)HLL_M * log((double)HLL_M / (double)zero_registers));
        }
        return (uint64_t)raw;
    }

    return (uint64_t)raw;
}

Обратите внимание на использование inv_pow2_table[registers[i]] — мы заранее вычислили для всех возможных . Это ускоряет подсчёт суммы, избавляя от вычисления степеней на лету.

Множитель hll_alpha() зависит от точности и вычисляется по формуле или по таблице:

static double hll_alpha(uint8_t p, uint32_t m) {
    switch (p) {
    case 4:  return 0.673;
    case 5:  return 0.697;
    case 6:  return 0.709;
    case 7:  return 0.715;
    case 8:  return 0.718;
    case 9:  return 0.719;
    case 10: return 0.720;
    case 11: return 0.7205;
    default: return 0.7213 / (1.0 + 1.079 / (double)m);
    }
}

Для () формула даёт:

Это значение близко к пределу , к которому стремится при росте .

Одно из важнейших свойств HyperLogLog — возможность объединять результаты. Если у вас есть два потока данных, обработанных независимо, вы можете слить их структуры и получить оценку для объединённого потока. Операция предельно проста: для каждого регистра берётся максимум из двух значений.

void hll_merge(HyperLogLog* dest, const HyperLogLog* src) {
    for (int i = 0; i < HLL_M; i++) {
        if (src->registers[i] > dest->registers[i]) {
            dest->registers[i] = src->registers[i];
        }
    }
}

Эта операция делает HyperLogLog идеальным для распределённых систем: каждый сервер может независимо обрабатывать свой поток, а затем центральный узел объединяет все структуры за линейное время от количества регистров.

Для проверки работы алгоритма нам понадобилась функция генерации случайных строк и тестовое приложение. Генератор использует стандартный rand() для создания строк заданной длины из букв и цифр:

static char* gen_random_string(size_t length) {
    static const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    char* str = malloc(length + 1);
    for (size_t i = 0; i < length; i++) {
        str[i] = charset[rand() % (sizeof(charset) - 1)];
    }
    str[length] = '\0';
    return str;
}

В функции main мы генерируем 100 000 уникальных строк, добавляем их в структуру HyperLogLog, а затем выводим оценку и сравниваем её с реальным количеством. Это позволяет нам убедиться, что алгоритм работает в пределах заявленной погрешности.

Наша реализация использует __builtin_clzll — это расширение GCC и Clang. Для компиляции под Visual Studio потребуется заменить эту функцию на __lzcnt64 или реализовать подсчёт ведущих нулей через битовые операции. Также мы используем memset и математические функции из стандартной библиотеки.

Выбор точности: размер структуры и погрешность. Мы выбрали как хороший компромисс: 16 КБ памяти и погрешность около 1–2%. Если вам нужна большая точность, можно увеличить до 16 (64 КБ, погрешность около 0.8%), а если память критична — уменьшить до 10 (1 КБ, но погрешность вырастет до 3–4%).

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

Итоговая реализация доступна по этой ссылке в моем репозитории.

❯ Вывод

Итак, запускаем код

Precision (p): 14
Registers (m): 16384
Memory: 16384 bytes
Actual unique:  100000
HLL estimate:   99777
Error:          0.22%

Idempotency check: 99777
Merge estimate: 99777

Погрешность составила всего 0.22% — это даже меньше теоретической оценки в 0.81% для данного количества регистров. Такой результат объясняется тем, что теоретическая ошибка — это среднеквадратичное отклонение, а на конкретной выборке случайных данных можно получить как меньшее, так и большее значение. В нашем случае случайность сыграла в пользу точности.

Обратите внимание на проверку идемпотентности: повторный вызов hll_estimate дал тот же результат, что и первый. Это важное свойство — оценка детерминирована и не зависит от того, сколько раз вы её запрашиваете.

Проверка слияния также прошла успешно: мы разделили 100 000 элементов на две равные части, обработали их независимо в двух структурах HyperLogLog, а затем слили их в одну. Оценка после слияния (99777) совпала с оценкой исходной структуры, в которую добавлялись все элементы последовательно. Это подтверждает, что операция слияния корректна и не вносит дополнительной ошибки.

Теперь посмотрим, как алгоритм ведёт себя на миллионе уникальных элементов:

Precision (p): 14
Registers (m): 16384
Memory: 16384 bytes
Actual unique:  1000000
HLL estimate:   991202
Error:          0.88%

Idempotency check: 991202
Merge estimate: 991202

При увеличении кардинальности на порядок (со 100 тысяч до 1 миллиона) погрешность выросла до 0.88%, что всё ещё находится в пределах теоретической оценки в 0.81% с учётом естественной вариативности. Важно отметить, что структура данных при этом не изменилась — те же 16 384 регистра, те же 16 КБ памяти. Алгоритм одинаково эффективно работает как для сотен тысяч, так и для миллионов элементов, и даже для миллиардов — размер структуры остаётся фиксированным.

Это и есть главная сила HyperLogLog: память не зависит от количества обработанных элементов. Вы можете пропустить через него терабайт логов, и он всё так же будет занимать 16 КБ. Единственное, что влияет на размер, — это желаемая точность, которая определяется количеством регистров.

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

❯ Графики

Я решил дополнительно провести тесты с измененными константами и нарисовать графики. Я провел серию тестов с изменением параметра точности (от 10 до 16) и размера входного множества (unique_count от 10k до 1M). Полный набор сырых данных доступен по этой ссылке.

Для ошибка чуть выше теоретической из-за случайности, для — аномально низкая

Графики наглядно показывают свойства HyperLogLog вместе с особенностями реализации. Слияние корректное, ошибка при объединении двух структур идентична ошибке прямого подсчета. Также есть классическая зависимость: удвоение памяти (рост на 1) снижает стандартную ошибку примерно в раз. При (16 KB) ошибка стабильно уходит ниже 1% для любых размеров множеств.

При кривые ошибок становятся пологими и близкими к нулю, независимо от кардинальности входных данных (будь то 10k или 1M элементов). Это подтверждает, что HyperLogLog действительно масштабируется, используя фиксированный объем памяти.

В итоге лучшим выбором для продакшена будет или .

---

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

---

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩