✖

HyperLogLog: як дуже точно оцінити кількість унікальних значень

Kapitoly: Linear Counting, Min Value, LogLog, HyperLogLog

Серія про алгоритми оцінки кількості унікальних значень у мультимножині продовжується статтею про алгоритм HyperLogLog, що є state of the art. Усі ідеї, на яких він ґрунтується, походять від описаного раніше LogLog, тож якщо хочеш читати далі, переконайся, що LogLog ти добре розумієш.

Алгоритм LogLog мав дві головні проблеми:

Викиди

Підсумкова оцінка LogLog дуже чутлива до викидів — значень, які дуже далеко від решти. Зазвичай буває так, що більшість максимальних довжин нульових суфіксів для кожної групи приблизно однакові, скажімо, лежать між 12 і 15, а тоді бабах — і один нульовий суфікс має довжину 27. Така велика різниця псує підсумкову оцінку кількості унікальних значень, бо класичне середнє арифметичне з цим справляється кепсько. По суті, спрацював той самий принцип, що й тоді, коли кілька топменеджерів і директорів своїми високими зарплатами піднімають середню зарплату в країні.

Автори алгоритму намагалися вирішити це так: позбувалися викидів і не враховували в середньому кілька найбільших максимумів, але це було не надто гарне рішення. Пізніше вони спробували інший підхід: замість середнього арифметичного взяли середнє гармонійне, яке має набагато кращі властивості, коли є значення, віддалені від середнього.

Дуже погані результати для малої кількості унікальних значень

LogLog дає жахливі результати, коли потрібно оцінити кількість унікальних значень у малих мультимножинах. Якщо в мультимножині є лише кілька унікальних елементів, LogLog поверне безглуздо велику оцінку. Автори вирішили це хитро: коли на вході мультимножина з малою кількістю унікальних значень, алгоритм LogLog не застосовують, а застосовують зовсім інший, а саме старий знайомий Linear counting. Гаразд, але як зрозуміти, що на вході мультимножина з малою кількістю унікальних значень, якщо цієї кількості ми якраз і не знаємо?

Дозволимо LogLog оцінити кількість унікальних елементів, і коли з'ясується, що ця оцінка відносно мала, відкинемо її й порахуємо знову алгоритмом Linear counting. Швидко нагадаємо, як працює Linear counting. На початку виділяємо нульовий (бітовий) масив наперед заданого розміру, зазвичай степеня двійки. Проходимо по всіх елементах мультимножини, обчислюємо їхній хеш і перетворюємо його на ціле число i від 0 до довжини масиву мінус 1. За індексом i у масиві записуємо одиницю. Наприкінці підраховуємо кількість нулів і одиниць у масиві та за простою формулою оцінюємо кількість унікальних значень.

Але алгоритм LogLog не використовує жодного бітового масиву, куди він «записував» би обчислені хеші. Замість цього він використовує масив, у якому зберігає максимальні довжини суфіксів. Масив може виглядати, наприклад, так:

[2, 5, 9, 0, 5, 4, 4, 0]

де кожне число позначає максимальну довжину нульового суфікса в певній групі обчислених хешів. Ненульове значення на i-й позиції тоді неодмінно означає, що серед значень мультимножини існує елемент, чий (трибітовий) хеш дорівнює i. Іншими словами, цей масив можна перетворити на бітовий масив для Linear counting: нулі залишаємо, а будь-яке додатне число замінюємо одиницею. З попереднього масиву ми отримали б бітовий масив:

[1, 1, 1, 0, 1, 1, 1, 0]

Тепер можемо застосувати алгоритм Linear counting і оцінити кількість унікальних значень за його допомогою.

Є, однак, одна заковика. Ми записуємо в масив максимальний нульовий суфікс, але що, коли в якійсь групі всі хеші закінчуються одиницею? Якщо, наприклад, як ідентифікатор групи, до якої належить хеш, ми використовуємо останні три біти, то довжина нульового суфікса хеша «01001100» дорівнювала б нулю — адже вектор «01001» закінчується одиницею. У масив максимумів за індексом 4 (1002=410) ми б записали нуль. А в алгоритмі Linear counting це виглядало б так, ніби ми не знайшли значення, хеш якого дорівнює чотирьом, а це неправда.

Тому змінимо алгоритм так, щоб він записував у масив максимумів не довжину найдовшого нульового суфікса, а індекс «першої одиниці справа» (для порядку: індексуємо з одиниці), що те саме, що додати до довжини нульового суфікса одиницю. Завдяки цьому нуль за індексом i означає, що жодне значення не має хеша i, і такий масив можна використати для Linear counting.

Реалізація HyperLogLog

Крок за кроком:

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

Функція alpha повертає поправку для обчисленої оцінки; це ми вже знаємо з минулого разу, тільки в HyperLogLog alpha має інше значення залежно від кількості груп.

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

Функція, що повертає кількість нульових бітів у кінці числа.

def count_maxims(values, k):
    num_buckets = 2 ** k  
    max_zeroes = [0] * num_buckets

    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

Функція, яка проходить по всіх значеннях, розподіляє їх на num_buckets груп і для кожної групи обчислює індекс першої одиниці справа (довжину максимального нульового суфікса плюс один).

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

Трохи змінена функція для обчислення за алгоритмом Linear counting.

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

Головна функція, що все це поєднує. Спершу обчислює оцінку за допомогою зміненого LogLog, замість середнього арифметичного на четвертому рядку використовує середнє гармонійне, а наприкінці застосовує корекцію у вигляді Linear counting, якщо обчислена оцінка менша за 2,5-кратну кількість груп (тоді ми очікуємо, що стандартна оцінка LogLog буде гіршою, ніж якби ми скористалися Linear counting), і якщо в масиві максимумів є принаймні один нуль (масив, у якому самі одиниці, у Linear counting використати не можна, див. попередню статтю). А які результати HyperLogLog?

Запустимо тестовий код, який оцінить кількість унікальних значень у множинах, де їх послідовно 10, 100, …, 1 000 000:

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

Результати:

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

Бачимо, що результати завжди відхиляються від правильного менш ніж на відсоток. І це добре!

Подальші вдосконалення HyperLogLog

HyperLogLog отримав ще кілька цікавих вдосконалень. Одна з проблем, що лишилися, — висока вимогливість до пам'яті. Звучить дивно, адже минулого разу ми вихваляли вимоги до пам'яті до небес і підрахували, що для зберігання масиву максимумів досить 768 байтів. Але проблема виникає, якщо потрібно рахувати кількість унікальних значень не в одній величезній мультимножині, а паралельно в кількох мільйонах малих або якщо ці обчислені масиви максимумів хочеш зберігати в базі даних для якихось пізніших маніпуляцій.

Якби ми, наприклад, одночасно рахували кількість унікальних значень в одному мільярді мультимножин, при поточній реалізації нам знадобилося б 1 000 000 000 разів по 768 байтів, тобто 768 ГБ. З одного боку, це непогано… але з другого, HyperLogLog можна реалізувати краще.

Розріджене подання (sparse)

Уявімо, що ми задали k=12, тобто використовуємо 12 бітів для ідентифікації груп і отримуємо 212 різних груп хешів. На початку алгоритму треба виділити масив довжиною 4096 (див. рядок 3 функції count_maxims). Припустімо, що наша мультимножина має три різні елементи. Це означає, що в масиві ми встановимо значення у трьох різних місцях, а решта 4093 значень лишаться нульовими — ці 4093 ми просто ніяк не використали. Не дуже ефективно, правда?

Щоб не мати масиву, який здебільшого нульовий і невикористаний, але все одно займає цінний шмат пам'яті, на початку можна зберігати значення як пари [індекс, значення]. Приклад для кращого розуміння. Цей масив

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

можна значно ефективніше щодо пам'яті подати як дві пари:

[0, 7], [4, 12]

Замість того щоб мати в пам'яті виділену купу невикористаного місця, можемо поступово виділяти лише те місце, яке справді потрібне. Таке подання називаємо sparse (розріджене). Проте в певний момент це подання займало б більше пам'яті, ніж звичайний масив, — тоді розріджене подання можна без втрати інформації перетворити на звичайний масив.

Зміщення (offsets)

Практика показала, що всі значення в масиві приблизно однакові. Масив максимумів зазвичай виглядає, наприклад, так:

[12, 13, 11, 13, 15, 12, 14, 11, 12, …, 13, 14, 11]

Усі значення лежать десь навколо числа 13. Ще одна стратегія зменшення розміру такого масиву — відняти від кожного елемента якесь фіксоване значення й запам'ятати його. Можна відняти, наприклад, вісімку:

[4, 5, 3, 5, 7, 4, 6, 3, 4, …, 5, 6, 3]

Тепер кожне значення в масиві займає менше пам'яті: у першому масиві потрібно зберігати числа від 0 до 15, для чого треба 4 біти, а для другого вистачає 3 бітів, бо зберігаємо лише числа від 0 до 7. Звісно, це передбачає реалізацію масиву на рівні окремих бітів. Коли захочемо прочитати значення з масиву, доведеться додати до них назад запам'ятане число.

…і купа інших вдосконалень. Дослідження в цій галузі тривають, тож нас, безперечно, чекають ще цікаві ідеї. Наступного разу поговоримо про об'єднання та перетин векторів HyperLogLog, а в недалекому майбутньому розповімо, чому може бути корисно зберігати мільярди векторів HyperLogLog.

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