Programio

Sjednocení Hyperloglogu

Ukážeme si, jak efektivně použít HyperLogLog k tomu, abychom spočítali počet unikátních návštěv pro nějaký web za různá časová období, a to včetně různých zpřesňujících údajů, jako je použitý prohlížeč, OS a podobně. Jednou z výhod algoritmu HyperLogLog totiž je, že můžeme bez ztráty informace sjednotit vektory, které drží maxima. Jinými slovy, pokud přes HyperLogLog spočítáme počet unikátních uživatelů v sobotu a pak v neděli, můžeme snadno spočítat počet unikátních uživatelů o víkendu.

Nejprve si ujasněme, proč by to vůbec měl být problém a proč si nemůžeme uložit počet unikátních návštěv pro nějaký den a pak je jen jednoduše sečíst. Příklad:

Date Uniques
2014-12-24 1000
2014-12-25 2000

Vidíme, že 24. jsme měli na webu 1000 unikátních návštěvníků a 25. jsme měli 2000, ale nemůžeme z toho odvodit, že jsme za oba dny měli na webu 3000 unikátních návštěvníků, protože někteří návštěvníci mohli přijít v obou dnech a my bychom je takto započítali dvakrát, což je chyba.

Jak to řešit? Jeden ze způsobů je, že si do tabulky uložíme všechny návštěvy; vždy si uložíme datum a unikátní identifikátor uživatele.

Date UUID
2014-12-24 2ff8c295
2014-12-24 7f127ff5
2014-12-24 2ff8c295
2014-12-24 a809a39e
2014-12-25 c9fd54ed
2014-12-25 11b500ac
2014-12-25 ba9e5c22
2014-12-25 2ff8c295

Z takto uložených dat můžeme snadno vyfiltrovat řádky jen z těch dnů, které nás zajímají a pak spočítat počet unikátních hodnot v druhém sloupečku. Můžeme to spočítat přesně nebo můžeme použít HyperLogLog, to už záleží na nás. Problém je, že musíme mít uložené opravdu všechny unikátní identifikátory, což nemusí být úplně levná záležitost, protože se – na rozdíl třeba od data – nedají dost dobře komprimovat.

A v tuto chvíli přichází na řadu HyperLogLog, který tento svízel snadno vyřeší.

Stručný popis HyperLogLogu

V rychlosti si zopakujeme základní kostru algoritmu HyperLogLog. Pokud si to plusminus pamatujete, přeskočte k další kapitole, pokud vůbec nevíte, o čem je řeč, začněte prvním článkem.

  1. Na vstupu máme nějakou multimnožinu S (množina, ve které se mohou některé hodnoty opakovat).
  2. Pro každou hodnotu x z S spočítáme n-bitový hash h(x). Tutu hash dále rozdělíme: označme hlastk(x) posledních k bitů hashe h(x) a hfirstn-k(x) prvních n-k bitů hashe h(x) (tj. odstraníme z hashe posledních k bitů).
  3. Rozdělíme prvky S do 2k disjunktních multimnožin, kde k je vstupní parametr algoritmu. Prvek x bude v multimnožině Si právě tehdy, když hlastk(x) = i.
  4. Pro každý prvek x spočítáme délku nulového suffixu hashe hfirstn-k(x). Tuto hodnotu označíme jako trailing_zeroes(x).
  5. Označme mi maximální hodnotu funkce trailing_zeroes(x) pro prvky x z multimnožiny Si.
  6. Do pole M si na index i zapíšeme hodnotu mi+1. Tj. pole M představuje vektor, kde na indexu i je maximální délka nulového suffixu plus jedna ze všech hashů ve skupině Si.

Sjednocení vektorů HyperLogLogu

Důležitý je vektor M, ve kterém jsou uloženy maximální délky nulových suffixů. Pokud ho známe, dokážeme z něj vypočítat odhad kardinality původní multimnožiny S. Ať už pomocí algoritmu LogLog, HyperLogLog nebo nějaké vylepšené verze HyperLogLogu.

Otázka zní: nemohli bychom do tabulky místo počtu unikátních návštěv uložit vektor M pro daný den a když bychom chtěli vypočítat počet unikátů pro více dnů, tak jen tyto vektory nějak sjednotit a vypočítat odhad? Asi není úplně velké překvapení, že přesně to lze udělat. A jde to udělat velmi snadno!

Mějme dvě multimnožiny S1, S2 a jejich HyperLogLog vektory M1, M2. Sjednocením těchto vektorů získáme nový vektor M, který získáme ho takto:

M[i] = max(M1[i], M2[i])

Jednoduchý příklad: nechť M1=[5, 7, 6, 7, 8, 5, 5, 4] a M2=[6, 7, 9, 2, 5, 5, 5, 7]. Pak dostaneme:

1
M1=[5, 7, 6, 7, 8, 5, 5, 4]
M2=[6, 7, 9, 2, 5, 5, 5, 7]
---------------------------
 M=[6, 7, 9, 7, 8, 5, 5, 7]

Tento nový vektor M můžeme použít pro výpočet odhadu počtu unikátních hodnot multimnožiny S1 ∪ S2.

Proč to funguje? Musí platit, že oba vektory vznikly se stejným parametrem k – což poznáme tak, že ty vektory jsou stejně dlouhé. Vraťme se k předchozímu příkladu a podívejme se na poslední sloupeček (4 a 7). Tato čísla reprezentují maximální délku nulového suffixu zvýšenou o jedna ve skupině 7 (je to 8. sloupec, ale indexujeme od nuly).

To znamená, že v multimnožině S1 existuje hodnota, jejíž hash má poslední tři bity rovny 111 (=7 v desítkové soustavě) a suffix má tři nuly. Může jít například o hash 011001000111. V multimnožině S2 zase musí existovat hodnota, jejíž hash končí na 111 a suffix má šest nul, například hash 111000000111.

Počítáme-li kardinalitu S1 ∪ S2, pak v sedmé skupině budou hashe 011001000111 a 110000000111 (a všechny ostatní hashe z dané skupiny – ale ty už budou mít vždy kratší nulový suffix než jeden z těchto dvou hashů, takže nás nezajímají). Nejdelší nulový suffix musí být roven nejdelšímu nulovému suffixu buď z multimnožiny S1 nebo S2. V tomto případě to bude z S2. Při počítání M1 ∪ M2 tak stačí vzít maximum z obou odpovídajících hodnot.

Agregujeme!

A jak tuto krásnou vlastnost využijeme? Nebudeme do tabulky ukládat všechny unikátní identifikátory, ani nebudeme ukládat pouze výslednou kardinalitu. Pro každý den si uložíme vypočítaný HyperLogLog vektor M:

Date HyperLogLog Vector
2014-12-24 [5, 7, 6, 7, 8, 5, 5, 4]
2014-12-25 [6, 7, 9, 2, 5, 5, 5, 7]
2014-12-26 [6, 9, 5, 5, 5, 9, 9, 7]
2014-12-27 [5, 7, 8, 8, 7, 4, 6, 9]
2014-12-28 [5, 9, 7, 7, 5, 4, 7, 5]
2014-12-29 [7, 8, 4, 9, 8, 4, 4, 9]
2014-12-30 [9, 7, 9, 7, 7, 6, 5, 4]
2014-12-31 [4, 6, 4, 5, 6, 8, 5, 8]

Pokud budeme chtít vypočítat počet unikátních návštěv na Štědrý den, vytáheneme si daný vektor [5, 7, 6, 7, 8, 5, 5, 4] a dopočítáme odhad. Pokud chceme znát počet unikátů od 24. do 26., vezmeme tři vektory, sjednotíme je a dopočítáme:

1
[5, 7, 6, 7, 8, 5, 5, 4]
[6, 7, 9, 2, 5, 5, 5, 7]
[6, 9, 5, 5, 5, 9, 9, 7]
------------------------
[6, 9, 9, 7, 8, 9, 9, 7]

Identicky pro všechny ostatní kombinace.

Můžeme pochopitelně přidávat další dimenze. Pokud potřebujeme znát počet unikátních uživatelů z daného dne, ale jen ty, kteří mají Chrome, přidáme sloupec:

Date Browser HyperLogLog Vector
2014-12-24 FireFox [5, 4, 5, 5, 3, 3, 5, 5]
2014-12-24 Chrome [3, 3, 3, 5, 2, 5, 3, 2]
2014-12-24 IE [4, 2, 2, 5, 2, 4, 4, 2]
2014-12-24 Safari [2, 1, 4, 1, 3, 2, 3, 4]
2014-12-24 Opera [0, 0, 0, 0, 0, 0, 0, 0]
2014-12-25 FireFox [3, 5, 5, 2, 3, 3, 4, 4]
2014-12-25 Chrome [3, 3, 2, 4, 4, 5, 5, 3]
2014-12-25 IE [5, 5, 5, 2, 3, 4, 4, 5]
2014-12-25 Safari [4, 1, 3, 4, 3, 1, 3, 3]
2014-12-25 Opera [0, 0, 0, 0, 0, 1, 0, 0]

Výhodou budou detailnější statistiky, nevýhodou bude to, že když budeme chtít znát počet unikátů za jeden den bez dalších omezení, stejně budeme muset sjednocovat několik vektorů. Čím více dimenzí budeme mít, tím více vektorů budeme muset sjednocovat, protože tím více řádků v tabulce bude.

To může být problém, protože i když jsme si minule uváděli, že datová náročnost HyperLogLogu je nízká, pro k=10 je to 768 bajtů, s přibývajícími dimenzemi roste počet kombinací, které mohou nastat a velmi rychle roste počet řádků a tedy i počet HLL vektorů, které musíme ukládat. Naštěstí platí, že čím více dimenzí, tím menší počet unikátních uživatelů, kteří tuto specifickou kombinaci splňují.

Už v předchozím článku jsem uváděl několik tipů, jak snížit velikost HyperLogLog vektoru. Pokud si s tím hodně pohrajete, bude HLL vektor přiměřeně malý, pro malé multimnožině klidně i několik málo desítek bajtů. Ve výsledku je to docela OK a prakticky vždy je to méně náročné, než poctivě ukládat všechna IDéčka.

Průnik HyperLogLogu

Ještě pár slov o průniku. Protože máme definováno sjednocení HLL vektorů, zdálo by se, že průnik je podobně jednoduchý, jen se místo maxima vezme minimum. A ono prd. Průnik se z různých důvodů vypočítat moc dobře nedá. Postupy na to existují, ale obyčejně mají příliš silné předpoklady (například, že obě multimnožiny jsou přibližně stejně velké) na to, aby ten odhad byl nějak použitelný a pokud tyto předpoklady nejsou splněné, tak algoritmus vrací totální babišnumera.

Má rada na závěr pro ty, kteří opravdu dočetli až sem tudíž zní: používejte sjednocení HLL vektorů. Nepoužívejte průnik HLL vektorů.