streamalism.org

1. Prehľad

The HyperLogLog (HLL) dátová štruktúra je pravdepodobnostná dátová štruktúra zvyknutá na odhadnúť mohutnosť súboru údajov.

Predpokladajme, že máme milióny používateľov a chceme vypočítať počet samostatných návštev našej webovej stránky. Naivnou implementáciou by bolo uložiť každé jedinečné ID používateľa do množiny a veľkosť sady by bola potom našou mohutnosťou.

Pokiaľ máme do činenia s veľmi veľkým objemom dát, bude počítanie mohutnosti týmto spôsobom veľmi neefektívne, pretože dátový súbor zaberie veľa pamäte.

Ak sme však spokojní s odhadom do niekoľkých percent a nepotrebujeme presný počet jedinečných návštev, môžeme použiť HLL, pretože bol navrhnutý presne pre takýto prípad použitia - odhad počtu miliónov alebo dokonca miliárd odlišných hodnôt.

2. Závislosť od Maven

Na začiatok budeme musieť pridať závislosť Maven pre hll knižnica:

 net.agkn hll 1.6.0 

3. Odhad mohutnosti pomocou HLL

Skákanie priamo do - HLL konštruktor má dva argumenty, ktoré môžeme vyladiť podľa našich potrieb:

• log2m (základňa protokolu 2) - toto je počet registrov, ktoré interne používa server HLL (poznámka: špecifikujeme m)
• regwidth - toto je počet bitov použitých na register

Ak chceme vyššiu presnosť, musíme ich nastaviť na vyššie hodnoty. Takáto konfigurácia bude mať ďalšiu réžiu, pretože naša HLL zaberie viac pamäte. Ak sme v poriadku s nižšou presnosťou, môžeme tieto parametre znížiť HLL zaberie menej pamäte.

Vytvorme HLL počítať odlišné hodnoty pre množinu údajov so 100 miliónmi záznamov. Nastavíme log2m parameter rovný 14 a regwidth rovná 5 - primerané hodnoty pre súbor údajov tejto veľkosti.

Keď je každý nový prvok vložený do HLL, treba to vopred hašovať. Budeme používať Hashing.murmur3_128 () z knižnice Guava (súčasť balenia hll závislosť), pretože je presná aj rýchla.

HashFunction hashFunction = Hashing.murmur3_128 (); dlhé čísloOfElements = 100_000_000; dlho tolerovaný rozdiel = 1_000_000; HLL hll = nový HLL (14, 5);

Výber týchto parametrov by nám mal poskytnúť hodnotu chybovosť pod jedno percento (1 000 000 prvkov). O chvíľu to otestujeme.

Ďalej vložíme 100 miliónov prvkov:

LongStream.range (0, numberOfElements) .forEach (element -> {long hashedValue = hashFunction.newHasher (). PutLong (element) .hash (). AsLong (); hll.addRaw (hashedValue);});

Nakoniec to môžeme otestovať mohutnosť vrátená HLL je v rámci požadovaného limitu chyby:

dlhá mohutnosť = hll.kardinalita (); assertThat (mohutnosť) .isCloseTo (numberOfElements, Offset.offset (toleratedDifference));

4. Veľkosť pamäte HLL

Môžeme vypočítať, koľko pamäte máme HLL z predchádzajúcej časti použijeme nasledujúci vzorec: numberOfBits = 2 ^ log2m * regwidth.

V našom príklade to bude 2 ^ 14 * 5 bity (zhruba 81000 bity alebo 8100 bajtov). Takže odhad mohutnosti 100-miliónovej množiny členov pomocou HLL obsadil iba 8100 bajtov pamäte.

Porovnajme to s implementáciou naivnej množiny. Pri takejto implementácii musíme mať Nastaviť 100 miliónov Dlhé hodnoty, ktoré by obsadzovali 100,000,000 * 8 bajtov = 800,000,000 bajtov.

Vidíme, že rozdiel je neuveriteľne vysoký. Použitím HLL, potrebujeme iba 8100 bajtov, zatiaľ čo využívame naivitu Nastaviť na implementáciu by sme potrebovali zhruba 800 megabajtov.

Keď vezmeme do úvahy väčšie súbory údajov, rozdiel medzi HLL a naivné Nastaviť implementácia sa ešte zvyšuje.

5. Únia dvoch HLL

HLL má pri vykonávaní odborov jednu prospešnú vlastnosť. Keď vezmeme spojenie dvoch HLL vytvorený z odlišných súborov údajov a merať jeho mohutnosť, dostaneme rovnaký prah chýb pre úniu, aký by sme dostali, keby sme použili jeden HLL a od začiatku vypočítal hašovacie hodnoty pre všetky prvky oboch súborov údajov.

Všimnite si, že keď spojíme dva HLL, oba by mali mať rovnaké log2m a regwidth na dosiahnutie správnych výsledkov.

Vyskúšajme túto vlastnosť vytvorením dvoch HLL - jeden má hodnoty od 0 do 100 miliónov a druhý má hodnoty od 100 do 200 miliónov:

HashFunction hashFunction = Hashing.murmur3_128 (); dlhé čísloOfElements = 100_000_000; dlho tolerovaný rozdiel = 1_000_000; HLL prvýHll = nový HLL (15, 5); HLL druhý HLL = nový HLL (15, 5); LongStream.range (0, numberOfElements) .forEach (element -> {long hashedValue = hashFunction.newHasher () .putLong (element) .hash () .asLong (); firstHll.addRaw (hashedValue);}); LongStream.range (numberOfElements, numberOfElements * 2) .forEach (element -> {long hashedValue = hashFunction.newHasher () .putLong (element) .hash () .asLong (); secondHLL.addRaw (hashedValue);});

Upozorňujeme, že sme vyladili konfiguračné parametre súboru HLL, zvyšovanie log2m parameter od 14, ako je vidieť v predchádzajúcej časti, do 15 pre tento príklad, od výsledku HLL únie bude obsahovať dvakrát toľko prvkov.

Ďalej poďme zjednotiť prvýHll a druhýHll pomocou odbor () metóda. Ako vidíte, odhadovaná mohutnosť je v rámci prahovej hodnoty chyby, ako keby sme mohutnosť z jednej zobrali HLL s 200 miliónmi prvkov:

firstHll.union (secondHLL); dlhá mohutnosť = firstHll.kardinalita (); assertThat (mohutnosť) .isCloseTo (numberOfElements * 2, Offset.offset (toleratedDifference * 2)); 

6. Záver

V tomto tutoriáli sme sa pozreli na HyperLogLog algoritmus.

Videli sme, ako používať HLL odhadnúť mohutnosť množiny. To sme tiež videli HLL je v porovnaní s naivným riešením veľmi priestorovo efektívne. A odborovú operáciu sme vykonali na dvoch HLL a overil, že únia sa správa rovnako ako jednotlivec HLL.

Implementáciu všetkých týchto príkladov a útržkov kódu nájdete v projekte GitHub; toto je projekt Maven, takže by malo byť ľahké ho importovať a spustiť tak, ako je.