Linear Counting: як оцінити кількість унікальних значень

4. 10. 2022

Kapitoly: Linear Counting, Min Value, LogLog, HyperLogLog

Як порахувати кількість унікальних значень у певному наборі даних, якщо цих даних справді дуже багато? Наприклад, у нас може бути сервіс, який вимірює кількість унікальних користувачів на великому сайті або навіть на цілому домені .com/.org/.whatever чи щось таке.

Наївний підхід

Ну добре, що тут думати: просто пройдемо по даних і кожне значення збережемо рівно один раз у якійсь зручній структурі даних. На Python це можна було б написати приблизно так (код навмисно зайво багатослівний):

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

Працює. Гаразд, але що, коли дані — це унікальні ідентифікатори v4 довжиною 36 символів, а унікальних ідентифікаторів буде, скажімо, десять мільйонів? Ну… програма все одно обчислить правильне значення, але скільки пам'яті вона займе? Спробуймо порахувати. Для простоти припустимо, що uuid зберігаємо справді як рядок із 36 символів. Один uuid займає 36 байтів, десять мільйонів ідентифікаторів займають 360 МБ.

Це чимало, визнаймо. Якби унікальних ідентифікаторів було сто мільйонів, ми вже дійшли б до гігабайтів зайнятої пам'яті. І це ми рахуємо лише те, що займають самі дані. Додайте ще накладні витрати, які потрібні, наприклад, Python чи JavaScript, і до гігабайтів можна дійти навіть з десятьма мільйонами ідентифікаторів:

Такого ти не хочеш. Як із цього вибратися?

Можна спробувати якось ефективніше зберігати самі ідентифікатори, можна замість Python узяти C, що суттєво зменшить вимоги до пам'яті, але все одно це буде не те, і така програма однаково займатиме неймовірну кількість місця. Лишається поставити собі запитання: чи нам справді потрібно знати достеменно, що унікальних значень рівно 9 563 618? Чи щось зміниться, якщо ми отримаємо 9 547 666? Якщо ти відповідаєш, що зміниться і що потрібна точність, — будь ласка, роби як хочеш. В іншому разі давай розглянемо підходи, які дають змогу оцінити кількість унікальних значень у наборі даних якомога точніше, найшвидше і з мінімальними вимогами до пам'яті.

Хеш-функція — наш порятунок

Розглянемо хеш-функцію, яка отримує на вході рядок, а на виході повертає якесь n-бітове число. Якщо тобі звичніші хеш-функції, що «повертають рядок», просто уяви, що цей рядок далі перетворюється на число, у цьому немає нічого складного. Кількість бітів показує, наскільки велике це число. 8-бітова функція повертає число, що займає вісім бітів, а у вісім бітів можна вмістити 2⁸ різних значень, зазвичай це цілі числа від 0 до 255. Далі працюватимемо з 24-бітовою хеш-функцією. Така функція повертає 2²⁴ різних значень, тобто 16 777 216.

Замість того щоб зберігати самі значення, зберігатимемо їхні 24-бітові хеші. Щоб зберегти десять мільйонів 24-бітових хешів, потрібно 30 МБ. Це на порядок краще, ніж попередні 360 МБ. Код міг би виглядати так:

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

Функція hash — це вбудована функція Python, яка повертає ціле число, а функція nhash показує наївну реалізацію n-бітової хеш-функції. Розуміти, як вона працює, не обов'язково, бо вона все одно працює неправильно: результат цієї функції не вміщується у 24 біти, але зараз це не важливо, мені йдеться про принцип.

Далі йде функція count_unique_using_nhash, яка рахує унікальні значення. Вона проходить по всіх значеннях, обчислює їхній хеш і зберігає його у змінній found, якщо там цього значення ще немає.

Проблема такого підходу в тому, що хеш-функція може повернути для різних рядків однаковий checksum — може виникнути колізія. Чим більше таких колізій, тим менш точний результат ми отримуємо. Функція count_unique_using_nhash майже завжди поверне меншу кількість унікальних значень, ніж є насправді.

А яку хеш-функцію вибрати? Насправді це не так важливо, але загалом рекомендують якийсь варіант MurmurHash.

Бітові мапи

Пам'ятаєш заняття з основ програмування мовою C? Якщо так, то бітові мапи ти знаєш. Як їх можна використати?

Ідею окреслимо на масиві. Нам не обов'язково зберігати обчислені checksum, ми можемо створити масив довжиною 2²⁴ і всі його елементи ініціалізувати нулями. Коли ми натрапляємо на якийсь checksum — а це число! — то в масив за індексом checksum записуємо одиницю, тим самим позначаючи, що такий checksum ми вже знайшли. Кількість унікальних елементів тоді приблизно дорівнюватиме кількості одиниць у цьому масиві. Код міг би виглядати так:

def count_unique_using_array(values):
    # список довжиною 2^24, ініціалізований самими нулями
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Проте використовувати масив у цьому випадку дуже затратно щодо пам'яті, бо в кожну комірку нам потрібно записувати або одиницю, або нуль. Замість цього можна скористатися бітовим масивом. Щоб ти розумів: ціле число (integer) можна зберегти, наприклад, у 32 бітах. Якщо перевести число 354 у двійкову систему числення, отримаємо 101100010. Число 354 у комп'ютері як 32-бітовий integer було б збережене (на подробиці не зважаємо) так:

00000000 00000000 00000001 01100010

Це досить зручний формат, який ми можемо використати, чи не так? Адже у нашій функції ми хочемо зберігати лише одиниці й нулі, а тепер з'ясували, що звичайне число — це не що інше, як купа нулів і одиниць (як, зрештою, і все в комп'ютері…). Отже, за допомогою бітових операторів можна зберегти одиницю так, щоб вона справді займала один біт.

Повернімося до нашої функції з масивом. Якби ми переписали її на бітові масиви, для 24-бітової хеш-функції нам вистачило б бітового масиву розміром 2²⁴ бітів, а це 2 МіБ. Чудове покращення!

Якщо використати 32-бітову хеш-функцію, яка має 2³² різних вихідних значень, тобто 4 294 967 296, нам знадобився б бітовий масив розміром у півгігабайта. Це зовсім непогано, адже так ми можемо рахувати унікальні значення аж до мільярдів.

Linear Counting

Я вже згадував, що, використовуючи хеш-функцію, ми отримуємо лише оцінку кількості унікальних значень. Ця оцінка тим менш точна, чим ближче кількість унікальних значень до кількості різних вихідних значень хеш-функції. Логічно, що коли в наборі даних п'ять мільярдів унікальних значень, 24-бітовою хеш-функцією їх просто не порахувати.

Проте оцінку, яку ми обчислюємо за допомогою хеш-функцій, можна далі уточнити. Для цього використовують просту ідею: чим більше унікальних значень у наборі даних, тим імовірніше, що з часом виникатимуть колізії. (Колізія — це коли два різні входи мають однаковий вихід хеш-функції, однаковий checksum.) Тепер трохи рахуватимемо, тому введемо кілька позначень:

Працюватимемо з n-бітовою хеш-функцією h.
Кількість усіх можливих виходів функції h тоді дорівнює 2ⁿ. Позначимо її літерою m, тобто m=2ⁿ.
Бітовий масив, у який ми записуватимемо, які checksum знайдено, позначимо великою літерою A. Масив A має довжину m.
Коли наш алгоритм пройде весь набір даних, деякі значення в бітовому масиві дорівнюватимуть нулю, а деякі — одиниці. Нас насамперед цікавитиме частка «кількість нулів, поділена на довжину масиву», яка показує відносну частку нулів у бітовому масиві. На початку ця частка дорівнює 1, бо масив ініціалізовано самими нулями. Якби нулів і одиниць було порівну, частка дорівнювала б одній другій тощо. Це значення позначимо Z і обчислимо як Z = кількість нулів / m.

Тепер справедливо таке: чим більше значення Z, тим впевненіші ми, що наша оцінка кількості унікальних значень точна. Якщо, наприклад, ми пройдемо порожній набір даних, у бітовому масиві залишаться самі нулі, і Z дорівнюватиме одиниці — отже, ми цілком певні, що в нашому наборі даних унікальних елементів стільки, скільки одиниць у бітовому масиві, тобто нуль.

Якщо Z дорівнює 0,99, це означає, що бітовий масив заповнений одиницями на одну соту. 99 % масиву містить нулі. Це ще добре: ймовірно, під час обчислення було не надто багато колізій, і виправлення буде потрібне мінімальне або взагалі ніяке. Але якщо Z дорівнює 0,05, то лише 5 % масиву залишилися нульовими, і, найімовірніше, ми натрапили на дуже багато колізій — потрібне буде велике виправлення.

Як же обчислити це виправлення? Допоможе логарифм — функція, що має такий вигляд:

Нас цікавить червона частина на проміжку (0; 1]. Якщо на осі x відкладати значення Z, то чим більше Z, тим ближче значення y до нуля. І навпаки: чим менше Z, тим менше буде значення y. Остаточну оцінку отримаємо, помноживши це число на -m. Зверни увагу: для достатньо малого Z ми отримаємо число, яке навіть менше за -1, а помноживши його на -m, одержимо оцінку, більшу за m: ми оцінили, що кількість унікальних значень більша за кількість усіх можливих checksum, які може видати хеш-функція h.

Повна формула для обчислення кількості p унікальних значень виглядала б так:

$$\Large p=-m\cdot \ln Z$$

Реалізація (без бітових масивів, лише зі звичайними масивами) могла б виглядати так:

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log тут — натуральний логарифм з основою e
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

У функції linear_counting ми спершу обчислюємо першу оцінку за допомогою попереднього алгоритму, що використовує n-бітову хеш-функцію. Потім обчислюємо частку нулів у масиві й виправляємо оцінку за формулою. Логарифм у коді — натуральний. Змінна nonunique_values містить number_of_unique_values унікальних рядків, тож у цьому прикладі в списку nonunique_values десять тисяч унікальних значень. Дивний код на шостому рядку робить так, щоб у масиві було більше однакових значень: просто в кінець списку додаємо той самий список, і кожне значення в масиві трапляється двічі. А далі рахуємо. Ідеально функція мала б повернути, що в списку десять тисяч унікальних значень. Вивід:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

Оскільки щоразу генерується інший список nonunique_values, результати при кожному виклику відрізнятимуться. Ми використали 16-бітову хеш-функцію. Бачимо, що перша оцінка з функції count_unique_using_array була такою: у списку 9289 унікальних значень. Корекцією ми уточнили її до 10 017, і це вже цілком пристойно: наша оцінка більша лише на 0,17 %, тоді як раніше була менша на 7,11 % — це доволі багато.

Якби ми взяли «більшу» хеш-функцію, наприклад 24-бітову, отримали б точніший результат:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

Уже сама початкова оцінка була нормальна, а уточнення дало рівно десять тисяч. Для прикладу спробуймо мільйон унікальних ідентифікаторів, тобто number_of_unique_values = 1000000. З 24-бітовою хеш-функцією отримаємо такі результати:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

Непогано. До того ж, якщо реалізувати це як бітовий масив, він займе лише згадані два мегабайти (плюс те, що з'їсть сама мова). Як на мене, доволі добре. But we can do better! Much better. Але вже наступного разу.

А поки що можеш прочитати статтю A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Або перейти до наступної частини серії: алгоритм Min Value.

« Попередня: Автомат → регулярний вираз

Наступна: Min Value »