streamalism.org

1. Pregled

The HyperLogLog (HLL) struktura podataka je vjerojatnosna struktura podataka koja se koristi za procijeniti kardinalnost skupa podataka.

Pretpostavimo da imamo milijune korisnika i želimo izračunati broj različitih posjeta našoj web stranici. Naivna bi implementacija bila pohrana svakog jedinstvenog korisničkog ID-a u skup, a tada bi veličina skupa bila naša kardinalnost.

Kada se radi o vrlo velikim količinama podataka, brojanje kardinalnosti na ovaj će način biti vrlo neučinkovito jer će skup podataka zauzeti puno memorije.

Ali ako se slažemo s procjenom unutar nekoliko posto i ne treba nam točan broj jedinstvenih posjeta, tada možemo koristiti HLL, jer je dizajniran za upravo takav slučaj upotrebe - procjenjujući broj milijuna ili čak milijardi različitih vrijednosti.

2. Ovisnost Mavena

Za početak trebamo dodati ovisnost Mavena za hll knjižnica:

 net.agkn hll 1.6.0 

3. Procjena kardinalnosti pomoću HLL

Skoči pravo u - HLL konstruktor ima dva argumenta koja možemo prilagoditi prema svojim potrebama:

• log2m (baza dnevnika 2) - ovo je broj registara koje interno koristi HLL (napomena: specificiramo m)
• širina - ovo je broj bitova korištenih po registru

Ako želimo veću točnost, moramo ih postaviti na veće vrijednosti. Takva će konfiguracija imati dodatne troškove jer naša HLL zauzet će više memorije. Ako se slažemo s nižom točnošću, možemo smanjiti te parametre i naše HLL zauzet će manje memorije.

Stvorimo HLL za brojanje različitih vrijednosti za skup podataka sa 100 milijuna unosa. Mi ćemo postaviti log2m parametar jednak 14 i regwidth jednak 5 - razumne vrijednosti za skup podataka ove veličine.

Kada se svaki novi element umetne u HLL, potrebno ga je prethodno raspršiti. Koristit ćemo Hashing.murmur3_128 () iz knjižnice Guava (uključena u hll ovisnost) jer je i točna i brza.

HashFunction hashFunction = Hashing.murmur3_128 (); dugi brojOfElements = 100_000_000; dugo tolerirana razlika = 1_000_000; HLL hll = novi HLL (14, 5);

Odabir tih parametara trebao bi nam dati stopa pogreške ispod jedan posto (1.000.000 elemenata). Za trenutak ćemo ovo testirati.

Dalje, ubacimo 100 milijuna elemenata:

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

Konačno, to možemo testirati kardinalnost koju je vratio HLL je unutar našeg željenog praga pogreške:

duga kardinalnost = hll.cardinality (); assertThat (kardinalnost) .isCloseTo (numberOfElements, Offset.offset (toleratedDifference));

4. Veličina memorije od HLL

Možemo izračunati koliko naše memorije HLL iz prethodnog odjeljka uzet će se pomoću sljedeće formule: numberOfBits = 2 ^ log2m * regwidth.

U našem primjeru to će biti 2 ^ 14 * 5 bitova (otprilike 81000 bitova ili 8100 bajtova). Dakle, procjenjujući kardinalnost 100-milionskog skupa članova HLL zauzimao samo 8100 bajtova memorije.

Usporedimo ovo s naivnom provedbom skupa. U takvoj provedbi trebamo imati Postavi od 100 milijuna Dugo vrijednosti, koje bi zauzele 100,000,000 * 8 bajtova = 800,000,000 bajtova.

Vidimo da je razlika zapanjujuće velika. Koristeći HLL, trebamo samo 8100 bajtova, dok koristimo naivno Postavi za implementaciju trebalo bi nam oko 800 megabajta.

Kad uzmemo u obzir veće skupove podataka, razlika između HLL i naivni Postavi provedba postaje još veća.

5. Unija dvoje HLL-ovi

HLL ima jedno korisno svojstvo pri obavljanju sindikata. Kad uzmemo uniju dvoje HLL-ovi stvoreni iz različitih skupova podataka i mjere njegovu kardinalnost, dobit ćemo isti prag pogreške za sindikat koji bismo dobili da smo koristili jedan HLL i izračunao hash vrijednosti za sve elemente oba skupa podataka od početka.

Imajte na umu da bi, kad spojimo dva HLL-a, oba trebala imati isto log2m i regwidth parametara kako bi se dobili odgovarajući rezultati.

Isprobajmo to svojstvo tako što ćemo stvoriti dva HLL - jedan je popunjen vrijednostima od 0 do 100 milijuna, a drugi s vrijednostima od 100 milijuna do 200 milijuna:

HashFunction hashFunction = Hashing.murmur3_128 (); dugi brojOfElements = 100_000_000; dugo tolerirana razlika = 1_000_000; HLL firstHll = novi HLL (15, 5); HLL drugiHLL = novi 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);});

Imajte na umu da smo podesili konfiguracijske parametre HLL-ovi, povećavajući log2m parametar od 14, kao što se vidi u prethodnom odjeljku, do 15 za ovaj primjer, jer je rezultat HLL unija sadržavat će dvostruko više elemenata.

Dalje, spojimo prvoDavola i secondHll koristiti unija() metoda. Kao što vidite, procijenjena kardinalnost je unutar praga pogreške kao da smo kardinalnost uzeli iz jedne HLL s 200 milijuna elemenata:

firstHll.union (secondHLL); duga kardinalnost = firstHll.cardinality (); assertThat (kardinalnost) .isCloseTo (numberOfElements * 2, Offset.offset (toleratedDifference * 2)); 

6. Zaključak

U ovom vodiču pogledali smo HyperLogLog algoritam.

Vidjeli smo kako se koristi HLL za procjenu kardinalnosti skupa. To smo i vidjeli HLL je vrlo prostorno učinkovit u usporedbi s naivnim rješenjem. A operaciju sindikata izveli smo na dvoje HLL-ovi i potvrdio da se sindikat ponaša na isti način kao i pojedinac HLL.

Provedba svih ovih primjera i isječaka koda mogu se naći u projektu GitHub; ovo je Mavenov projekt, pa bi ga trebalo biti lako uvesti i pokrenuti kakav jest.