streamalism.org

1. Oversigt

Det HyperLogLog (HLL) datastruktur er en sandsynlig datastruktur, der bruges til estimer kardinaliteten af ​​et datasæt.

Antag, at vi har millioner af brugere, og at vi ønsker at beregne antallet af forskellige besøg på vores webside. En naiv implementering ville være at gemme hver unikke bruger-id i et sæt, og derefter ville sættets størrelse være vores kardinalitet.

Når vi har at gøre med meget store datamængder, vil optælling af kardinalitet på denne måde være meget ineffektiv, fordi datasættet tager meget hukommelse.

Men hvis vi har det godt med et skøn inden for et par procent og ikke har brug for det nøjagtige antal unikke besøg, kan vi bruge HLL, da det var designet til netop en sådan brugssag - estimering af antallet af millioner eller endog milliarder forskellige værdier.

2. Maven-afhængighed

For at komme i gang skal vi tilføje Maven-afhængighed for hll bibliotek:

 net.agkn hll 1.6.0 

3. Estimering af kardinalitet ved hjælp af HLL

Hoppe lige ind - den HLL konstruktør har to argumenter, som vi kan tilpasse efter vores behov:

• log2m (log base 2) - dette er antallet af registre, der bruges internt af HLL (Bemærk: vi specificerer m)
• genbredde - dette er antallet af anvendte bits pr. register

Hvis vi ønsker en højere nøjagtighed, skal vi indstille disse til højere værdier. En sådan konfiguration vil have ekstra omkostninger, fordi vores HLL vil optage mere hukommelse. Hvis vi har det fint med lavere nøjagtighed, kan vi sænke disse parametre, og vores HLL optager mindre hukommelse.

Lad os oprette en HLL at tælle forskellige værdier for et datasæt med 100 millioner poster. Vi indstiller log2m parameter lig med 14 og genbredde svarende til 5 - rimelige værdier for et datasæt af denne størrelse.

Når hvert nye element indsættes i HLL, det skal hashes på forhånd. Vi bruger Hashing.murmur3_128 () fra Guava - biblioteket (inkluderet i hll afhængighed) fordi det er både nøjagtigt og hurtigt.

HashFunction hashFunction = Hashing.murmur3_128 (); langt antalOfElements = 100_000_000; lang tolereret forskel = 1_000_000; HLL hll = ny HLL (14, 5);

At vælge disse parametre skal give os en fejlprocent under en procent (1.000.000 elementer). Vi vil teste dette om et øjeblik.

Lad os derefter indsætte de 100 millioner elementer:

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

Endelig kan vi teste det kardinaliteten returneret af HLL er inden for vores ønskede fejltærskel:

lang kardinalitet = hll.kardinalitet (); assertThat (cardinality) .isCloseTo (numberOfElements, Offset.offset (toleratedDifference));

4. Hukommelsesstørrelse på HLL

Vi kan beregne, hvor meget hukommelse vores HLL fra det foregående afsnit tager ved hjælp af følgende formel: numberOfBits = 2 ^ log2m * genbredde.

I vores eksempel vil det være 2 ^ 14 * 5 bits (ca. 81000 bits eller 8100 bytes). Så estimering af kardinaliteten af ​​et 100-million medlemssæt ved hjælp af HLL optog kun 8100 byte hukommelse.

Lad os sammenligne dette med en naiv sæt implementering. I en sådan implementering er vi nødt til at have en Sæt på 100 millioner Lang værdier, som ville besætte 100,000,000 * 8 bytes = 800,000,000 bytes.

Vi kan se forskellen er forbløffende stor. Ved brug af HLL, har vi kun brug for 8100 byte, mens vi bruger det naive Sæt implementering ville vi have brug for cirka 800 megabyte.

Når vi overvejer større datasæt, er forskellen mellem HLL og de naive Sæt implementeringen bliver endnu højere.

5. Union of Two HLL'er

HLL har en gavnlig egenskab, når de udfører fagforeninger. Når vi tager unionen af ​​to HLL'er oprettet ud fra forskellige datasæt og måler dets kardinalitet, vi får den samme fejltærskel for unionen, som vi ville få, hvis vi havde brugt en enkelt HLL og beregnet hashværdierne for alle elementer i begge datasæt fra starten.

Bemærk, at når vi forbinder to HLL'er, skal begge have det samme log2m og genbredde parametre for at give de korrekte resultater.

Lad os teste den egenskab ved at oprette to HLL'er - den ene er befolket med værdier fra 0 til 100 millioner, og den anden er befolket med værdier fra 100 millioner til 200 millioner:

HashFunction hashFunction = Hashing.murmur3_128 (); langt antalOfElements = 100_000_000; lang tolereret forskel = 1_000_000; HLL førstHll = ny HLL (15, 5); HLL andenHLL = ny 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);});

Bemærk, at vi har indstillet konfigurationsparametrene til HLL'er, øge log2m parameter fra 14, som det ses i det foregående afsnit, til 15 for dette eksempel, da den resulterende HLL union vil indeholde dobbelt så mange elementer.

Lad os derefter forbinde den førstHll og andenHll bruger Union() metode. Som du kan se, ligger den estimerede kardinalitet inden for en fejltærskel, som om vi havde taget kardinaliteten fra en HLL med 200 millioner elementer:

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

6. Konklusion

I denne vejledning kiggede vi på HyperLogLog algoritme.

Vi så, hvordan man bruger HLL at estimere kardinaliteten af ​​et sæt. Vi så det også HLL er meget pladseffektiv i forhold til den naive løsning. Og vi udførte fagforeningens operation på to HLL'er og verificeret, at foreningen opfører sig på samme måde som en enkelt HLL.

Implementeringen af ​​alle disse eksempler og kodestykker findes i GitHub-projektet; dette er et Maven-projekt, så det skal være let at importere og køre som det er.