streamalism.org

1. Overzicht

De HyperLogLog (HLL) datastructuur is een probabilistische datastructuur die wordt gebruikt schat de kardinaliteit van een gegevensset.

Stel dat we miljoenen gebruikers hebben en we willen het aantal verschillende bezoeken aan onze webpagina berekenen. Een naïeve implementatie zou zijn om elke unieke gebruikers-ID in een set op te slaan, en dan zou de grootte van de set onze kardinaliteit zijn.

Als we te maken hebben met zeer grote hoeveelheden gegevens, zal het op deze manier tellen van de kardinaliteit erg inefficiënt zijn omdat de gegevensset veel geheugen in beslag zal nemen.

Maar als we het goed vinden met een schatting binnen een paar procent en niet het exacte aantal unieke bezoeken nodig hebben, dan kunnen we de HLL, zoals het is ontworpen voor precies zo'n gebruikssituatie - het schatten van het aantal miljoenen of zelfs miljarden verschillende waarden.

2. Maven Afhankelijkheid

Om aan de slag te gaan, moeten we de Maven-afhankelijkheid toevoegen voor het hll bibliotheek:

 net.agkn hll 1.6.0 

3. Kardinaliteit schatten met behulp van HLL

Recht in springen - de HLL constructor heeft twee argumenten die we kunnen aanpassen aan onze behoeften:

• log2m (logboekbasis 2) - dit is het aantal registers dat intern wordt gebruikt door HLL (opmerking: we specificeren de m)
• herbreedte - dit is het aantal bits dat per register wordt gebruikt

Als we een hogere nauwkeurigheid willen, moeten we deze op hogere waarden instellen. Zo'n configuratie heeft extra overhead omdat onze HLL zal meer geheugen in beslag nemen. Als we het goed vinden met een lagere nauwkeurigheid, kunnen we die parameters verlagen, en onze HLL zal minder geheugen innemen.

Laten we een HLL om verschillende waarden te tellen voor een gegevensset met 100 miljoen vermeldingen. We zullen de log2m parameter gelijk aan 14 en herbreedte gelijk aan 5 - redelijke waarden voor een dataset van deze omvang.

Wanneer elk nieuw element wordt ingevoegd in het HLL, moet het van tevoren worden gehasht. We zullen gebruiken Hashing.murmur3_128 () uit de Guava-bibliotheek (inbegrepen bij de hll afhankelijkheid) omdat het zowel nauwkeurig als snel is.

HashFunction hashFunction = Hashing.murmur3_128 (); long numberOfElements = 100_000_000; lang toleratedDifference = 1_000_000; HLL hll = nieuwe HLL (14, 5);

Het kiezen van die parameters zou ons een foutenpercentage lager dan één procent (1.000.000 elementen). We zullen dit straks testen.

Laten we vervolgens de 100 miljoen elementen invoegen:

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

Eindelijk kunnen we dat testen de kardinaliteit geretourneerd door de HLL is binnen onze gewenste foutdrempel:

lange kardinaliteit = hll.cardinality (); assertThat (kardinaliteit) .isCloseTo (numberOfElements, Offset.offset (toleratedDifference));

4. Geheugengrootte van HLL

We kunnen berekenen hoeveel geheugen ons heeft HLL uit de vorige sectie zal de volgende formule gebruiken: numberOfBits = 2 ^ log2m * regwidth.

In ons voorbeeld zal dat zijn 2 ^ 14 * 5 bits (ongeveer 81000 bits of 8100 bytes). Dus het schatten van de kardinaliteit van een set van 100 miljoen leden met behulp van HLL bezet slechts 8100 bytes aan geheugen.

Laten we dit vergelijken met een naïeve setimplementatie. Bij een dergelijke implementatie hebben we een Set van 100 miljoen Lang waarden, die zouden bezetten 100,000,000 * 8 bytes = 800,000,000 bytes.

We kunnen zien dat het verschil verbazingwekkend groot is. Gebruik makend van HLL, we hebben slechts 8100 bytes nodig, terwijl we de naïeve gebruiken Set implementatie zouden we ongeveer 800 megabytes nodig hebben.

Als we grotere datasets bekijken, is het verschil tussen HLL en de naïef Set implementatie wordt zelfs nog hoger.

5. Unie van twee HLLs

HLL heeft één gunstige eigenschap bij het uitvoeren van vakbonden. Als we de vereniging van twee nemen HLLs gemaakt op basis van verschillende datasets en de kardinaliteit ervan meten, we krijgen dezelfde foutdrempel voor de unie die we zouden krijgen als we er een hadden gebruikt HLL en berekende de hash-waarden voor alle elementen van beide datasets vanaf het begin.

Merk op dat wanneer we twee HLL's verenigen, beide hetzelfde zouden moeten hebben log2m en herbreedte parameters om de juiste resultaten te verkrijgen.

Laten we die eigenschap testen door er twee te maken HLLs - één is gevuld met waarden van 0 tot 100 miljoen, en de tweede is gevuld met waarden van 100 miljoen tot 200 miljoen:

HashFunction hashFunction = Hashing.murmur3_128 (); long numberOfElements = 100_000_000; lang toleratedDifference = 1_000_000; HLL firstHll = nieuwe HLL (15, 5); HLL secondHLL = nieuwe 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);});

Houd er rekening mee dat we de configuratieparameters van het HLLs, het verhogen van de log2m parameter van 14, zoals gezien in de vorige sectie, tot 15 voor dit voorbeeld, aangezien het resulterende HLL union zal twee keer zoveel elementen bevatten.

Laten we vervolgens het firstHll en secondHll de ... gebruiken unie() methode. Zoals u kunt zien, ligt de geschatte kardinaliteit binnen een foutdrempel alsof we de kardinaliteit van één hadden genomen HLL met 200 miljoen elementen:

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

6. Conclusie

In deze tutorial hebben we de HyperLogLog algoritme.

We hebben gezien hoe we de HLL om de kardinaliteit van een set te schatten. Dat hebben we ook gezien HLL is erg ruimtebesparend in vergelijking met de naïeve oplossing. En we voerden de vakbondsoperatie uit op twee HLLs en verifieerde dat de vakbond zich op dezelfde manier gedraagt ​​als een single HLL.

De implementatie van al deze voorbeelden en codefragmenten is te vinden in het GitHub-project; dit is een Maven-project, dus het moet gemakkelijk te importeren en uit te voeren zijn zoals het is.