Поредицата за алгоритмите за оценка на броя на уникалните стойности в мултимножество продължава със статията за state of the art алгоритъма HyperLogLog. Всички идеи, които стоят зад този алгоритъм, обаче произлизат от описания по-рано LogLog, така че ако искаш да четеш нататък, увери се, че познаваш добре LogLog.

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

Аутлайъри

Окончателната оценка на LogLog е много чувствителна към аутлайъри (outliers), стойности, които са много далеч от останалите стойности. Обикновено се случва повечето максимални дължини на нулевите суфикси за всяка група да са приблизително еднакви, например да се движат между 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-тата позиция обаче непременно означава, че сред стойностите в мултимножеството съществува елемент, чийто (3-битов) хеш е равен на i. С други думи, този масив можем да преобразуваме в битово поле за linear counting така, че нулите оставяме, а всяко положително число преобразуваме в единица. От предишния масив бихме получили битовото поле:

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

Сега можем да приложим алгоритъма Linear counting и с него да оценим кардиналността.

Има обаче един проблем. Ние запазваме в масива максималния нулев суфикс, но какво става, ако в някоя група всички хешове завършват на единица? Ако например използваме последните три бита като идентификатор на групата, към която принадлежи хешът, то дължината на нулевия суфикс на хеша „01001100“ би била нула — защото векторът „01001“ завършва на единица. В масива на максимумите бихме записали на индекс 4 (100₂=4₁₀) нула. В алгоритъма 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 GB. От една страна, не е лошо … но от друга страна, можем да реализираме HyperLogLog по-добре.

Sparse представяне

Нека си представим, че задаваме k=12, т.е. използваме 12 бита за идентификация на групите и получаваме следователно 2¹² различни групи хешове. В началото на алгоритъма трябва да заделим масив с дължина 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. В един момент обаче това представяне би станало по-скъпо откъм памет от запазването в масив — тогава можем да преобразуваме sparse представянето в класически масив без загуба на информация.

Отмествания (offset)

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

[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 вектори.

Връзки и източници

• Цялата ми реализация можеш да разгледаш в GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — първоначалната статия, в която е представен HyperLogLog.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — Подобрена версия на първоначалния HyperLogLog, например със споменатото sparse представяне.