Série o algoritmech na odhadování počtu unikátních hodnot v multimnožině pokračuje článkem o state of the art algoritmu HyperLogLog. Nicméně veškeré myšlenky, které stojí za tímto algoritmem vychází z dříve popsaného LogLogu, takže pokud chcete číst dál, ujistěte se, že znáte dobře LogLog.

Algoritmus LogLog měl dva hlavní problémy:

Outliery

Výsledný odhad LogLogu je velmi náchylný na outliery, hodnoty, které jsou velmi vzdálené od ostatních hodnot. Typicky se totiž stává, že většina maximálních délek nulových prefixů pro každou skupinu je přibližně stejná, například se pohybuje mezi 12 a 15, ale pak buch — a jeden nulový suffix má délku 27. Tenhle velký rozdíl udělá nepořádek ve výsledném odhadu počtu unikátů, protože klasický aritmetický průměr si s tím moc dobře neporadí. V podstatě zafungoval stejný princip, jako když pár top manažerů a ředitelů zvedne průměrnou mzdu v republice svými vysokými mzdami.

Autoři algoritmu se to snažili řešit tím, že se outlierů zbavovali a do průměru nezapočítali několik nejvyšších maxim, ale to nebylo příliš dobré řešení. Později zkusili jiný postup — místo aritmetického průměru použili průměr harmonický, který má daleko lepší vlastnosti v případě, kdy máme hodnoty, které jsou vzdálené od průměru.

Velmi špatné výsledky pro malé kardinality

LogLog má příšerné výsledky, má-li odhadovat kardinalitu malých multimnožin. Pokud máme v multimnožině několik málo unikátních prvků, vrátí nám LogLog nesmyslně velký odhad. Autoři to vyřešili fikaně — v případě, kdy máme na vstupu multimnožinu s nízkou kardinalitou, nepoužije se algoritmus LogLog, ale použije se úplně jiný algoritmus, a sice starý známý Linear counting. No jo, ale jak poznáme, že máme na vstupu multimnožinu s malou kardinalitou, když kardinalitu právě neznáme?

Necháme LogLogem odhadnout počet unikátních prvků a když zjistíme, že tento odhad je relativně nízký, odhad zahodíme a spočítáme ho znovu algoritmem Linear counting. V rychlosti si připomeneme, jak Linear counting funguje. Na začátku alokujeme nulové (bitové) pole o nějaké předem dané velikosti, typicky mocnina dvojky. Projdeme všechny prvky multimnožiny, spočítáme jejich hash a ten převedeme na celé číslo i z intervalu 0 až délka pole minus 1. Na index i pak v poli uložíme jedničku. Nakonec spočítáme počet nul a jedniček v poli a pomocí jednoduchého vzorce odhadneme kardinalitu.

Algoritmus LogLog ale žádné bitové pole, do kterého by si „ukládal“ vypočítané hashe, nepoužívá. Místo toho používá pole, ve kterém si uchovává maximální délky suffixů. Pole může vypadat například takto:

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

přičemž každé číslo označuje maximální délku nulového suffixu v dané skupině vypočítaných hashů. Nenulová hodnota na i-té pozici pak ale nutně znamená, že mezi hodnotami v multimnožině existuje prvek, jehož (tříbitový) hash je roven i. Jinými slovy, toto pole můžeme převést na bitové pole pro linear counting tak, že nuly ponecháme a jakékoliv kladné číslo převedeme na jedničku. Z předchozího pole bychom tak dostali bitové pole:

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

Nyní můžeme aplikovat algoritmus Linear counting a odhadnout kardinalitu pomocí něj.

Má to ovšem jeden háček. My do pole ukládáme maximální nulový suffix, jenomže co když v nějaké skupině hodnot končí všechny hashe na jedničku? Pokud například použijeme poslední tři bity jako identifikátor skupiny, do které hash patří, pak by délka nulového suffixu tohoto hashe „01001100“ byla nula — protože vektor „01001“ končí na jedničku. Do pole maxim bychom tak na index 4 (100₂=4₁₀) uložili nulu. V algoritmu linear counting by se to ale projevilo tak, že jsme nenašeli hodnotu, která by měla za hash čtyřku, což není pravda.

Proto upravíme algoritmus tak, aby neukládal do pole maxim délku nejdelšího nulového suffixu, ale aby ukládal index „první jedničky zprava“ (pro pořádek — indexujeme od jedničky), což je totéž, jako bychom k délce nulového suffixu přičetli jedničku. Tím dosáhneme toho, že nula na indexu i znamená, že žádná hodnota nemá hash rovnou i a takové pole pak můžeme použít pro linear counting.

Implementace HyperLogLogu

Hezky postupně:

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

Funkce alpha vrací korekci pro vypočítaný odhad, to už známe z minula, pouze v případně HyperLogLogu má alpha jinou hodnotu v závislosti na počtu skupin.

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

Funkce, která vrací počet nulových bitů na konci čísla.

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

Funkce, která projde všechny hodnoty, rozdělí je num_buckets skupin a pro každou skupinu vypočítá index první jedničky zprava (délku maximálního nulového suffixu plus jedna).

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

Lehce upravená funkce pro výpočet algoritmu 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

Hlavní funkce, která to vše dává dohromady. Nejdříve vypočte odhad pomocí upraveného LogLogu, místo aritmetického průměru použije na čtvrtém řádku harmonický průměr a nakonec aplikuje korekci v podobě Linear countingu, pokud je vypočítaný odhad menší než 2,5 násobek počtu skupin (v tuto chvíli očekáváme, že bude standardní odhad LogLogu horší než kdyby se použil Linear counting) a pokud je v poli maxim alespoň jedna nula (pole, ve kterém jsou samé jedničky nemůžeme v Linear countingu použít, viz předchozí článek). A jaké jsou výsledky HyperLogLogu?

Spustíme testovací kód, který nám odhadne kardinalitu množin, které mají postupně kardinalitu 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)

Výsledky:

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

Vidíme, že výsledky jsou vždy odchýlené od správného výsledky o méně než procento. A to je dobré!

Další vylepšení HyperLogLogu

HyperLogLog se dočkal několika dalších zajímavých vylepšení. Jedním ze zbývajících problémů je vysoká paměťová náročnost. To zní dost divně, když jsme si minule paměťovou náročnost vychvalovali do nebes a spočítali jsme si, že na uložení pole maxim nám stačí 768 bajtů. Jenomže problém nastává, pokud chcete počítat kardinalitu ne jedné obrovské multimnožiny, ale paralelně několika milionů malých multimnožin nebo pokud si tyto vypočítané pole maxim chcete uchovávat v databázi na nějaké pozdějí čachry machry.

Pokud bychom například počítali současně kardinalitu jedné miliardy multimnožin, potřebovali bychom při současné implementaci 1 000 000 000 krát 768 bajtů, což je 768 GB. Na jednu stranu to není špatné … ale na druhou stranu jsme schopni HyperLogLog implementovat lépe.

Sparse reprezentace

Představme si, že nastavíme k=12, tj. použijeme 12 bitů pro identifikaci skupin a dostaneme tudíž 2¹² různých skupin hashů. Na začátku algoritmu musíme alokovat pole o délce 4096 (viz řádek 3 funkce count_maxims). A dejme tomu, že naše multimnožina má tři různé prvky. To znamená, že do pole na tři různá místa nastavíme nějakou hodnotu a zbylých 4093 hodnot v poli zůstane nulových, zbylých 4093 jsme zkrátka nijak nepoužili. To není moc efektivní, že?

Abychom se vyhnuli tomu, že budeme mít pole, které bude z větší částí nulové a nepoužité, ale které přesto zabírá cenný kus paměti, můžeme na začátku hodnoty ukládat jako dvojice [index, hodnota]. Příklad pro lepší pochopení. Toto pole

[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]

můžeme daleko paměťově efektivněji reprezentovat jako dvě dvojice:

[0, 7], [4, 12]

Místo toho, abychom měli v paměti alokovanou hromadu nevyužitého místo, můžeme postupně alokovat jen to místo, které opravdu potřebujeme. Této reprezentaci říkáme sparse. Nicméně v jednu chvíli by takto reprezentace byla paměťově náročnější než právě uložení do pole — pak můžeme sparse reprezentaci převézt na klasické pole bez ztráty informace.

Offsety

Praxe ukázala, že se všechny hodnoty v poli jsou zhruba stejné. Pole maxim běžně vypadá například takto:

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

Všechny hodnoty se pohybují někde kolem čísla 13. Další ze strategií, jak zmenšit velikost takového pole, je odečíst od každého prvku nějakou fixní hodnotu a tu si zapamatovat. Můžeme odečíst například osmičku:

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

V tuto chvíli spotřebuje každá hodnota v poli menší množství v paměti — v prvním poli potřebujeme ukládat čísla od 0 do 15, na což potřebujeme 4 bity, zatímco na druhé pole nám stačí 3 bity, protože ukládáme jen čísla od 0 do 7. Samozřejmě to předpokládá implementaci pole na úrovni jednotlivých bitů. Ve chvíli, kdy budeme chtít hodnoty z pole přečíst, musíme k nim zpátky přičíst poznamenanou hodnotu.

…a hromada dalších vylepšení. Výzkum v této oblasti stále ještě běží, takže se jistě můžeme těšit na další zajímavé nápady. My si příště povíme něco o sjednocení a průniku HyperLogLog vektorů a někdy v blízké budoucnosti si povíme, proč se nám může hodit ukládat si miliardy HyperLogLog vektorů.

Odkazy a zdroje

• Celou mou implementaci si můžete prohlédnout na GitHubu.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — původní článek, ve kterém byl představen HyperLogLog.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — Vylepšená verze původního HyperLogLogu, například o zmíněnou sparse reprezentaci.