streamalism.org

1. Áttekintés

A HyperLogLog (HLL) az adatszerkezet egy valószínűségi adatszerkezet megbecsülni egy adatkészlet számosságát.

Tegyük fel, hogy több millió felhasználónk van, és ki akarjuk számolni a weboldalunkon tett külön látogatások számát. Naiv megvalósítás az lenne, ha minden egyedi felhasználói azonosítót egy halmazban tárolunk, és akkor a halmaz mérete lesz a mi számosságunk.

Amikor nagyon nagy adatmennyiséggel van dolgunk, a kardinalitás ilyen módon történő megszámlálása nagyon nem hatékony, mivel az adatkészlet sok memóriát foglal el.

De ha jól állunk egy néhány százalékos becsléssel, és nincs szükségünk az egyedi látogatások pontos számára, akkor használhatjuk a HLL, mivel pontosan egy ilyen felhasználási esetre tervezték - becsülve milliók vagy akár milliárd különálló érték számát.

2. Maven-függőség

A kezdéshez hozzá kell adnunk a hll könyvtár:

 net.agkn hll 1.6.0 

3. A kardinalitás becslése a használatával HLL

Ugrás jobbra - a HLL A konstruktornak két érve van, amelyeket igényeink szerint módosíthatunk:

• log2m (2. rönkalap) - ez a belsőleg használt regiszterek száma HLL (megjegyzés: megadjuk a m)
• regwidth - ez a regiszterenként felhasznált bitek száma

Ha nagyobb pontosságot akarunk, akkor ezeket magasabb értékekre kell beállítanunk. Egy ilyen konfiguráció további költségekkel jár, mert a HLL több memóriát foglal el. Ha alacsonyabb pontossággal jól vagyunk, akkor csökkenthetjük ezeket a paramétereket, és a sajátunkat is HLL kevesebb memóriát foglal el.

Hozzunk létre egy HLL 100 millió bejegyzéssel rendelkező adatkészlet különálló értékeinek számlálása. Beállítjuk a log2m paraméter egyenlő 14 és regwidth egyenlő 5 - ésszerű értékek egy ekkora adatkészlethez.

Amikor minden új elem beillesztésre kerül a HLL, előzetesen kivonatolni kell. Használni fogjuk Hashing.murmur3_128 () a guavai könyvtárból (a hll függőség), mert pontos és gyors is.

HashFunction hashFunction = Hashing.murmur3_128 (); hosszú numberOfElements = 100_000_000; rég tolerált különbség = 1_000_000; HLL hll = új HLL (14, 5);

Ezeknek a paramétereknek a megválasztása egy hibaarány egy százalék alatt (1.000.000 elem). Egy pillanat múlva ezt teszteljük.

Ezután illesszük be a 100 millió elemet:

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

Végül ezt tesztelhetjük a kardinalitás, amelyet a HLL a kívánt hibaküszöbön belül van:

hosszú bíborosság = hll.kardinalitás (); assertThat (kardinalitás) .isCloseTo (numberOfElements, Offset.offset (toleratedDifference));

4. Memória mérete HLL

Kiszámíthatjuk, mennyi memóriánk van HLL az előző szakaszból a következő képletet használjuk: numberOfBits = 2 ^ log2m * regwidth.

Példánkban ez lesz 2 ^ 14 * 5 bit (nagyjából 81000 bit vagy 8100 bájt). Tehát megbecsülve egy 100 milliós tag halmazának számosságát HLL csak 8100 bájt memóriát foglalt el.

Hasonlítsuk össze ezt egy naiv halmaz megvalósítással. Egy ilyen megvalósításban rendelkeznünk kell a Készlet 100 millió Hosszú értékeket, amelyek elfoglalnák 100,000,000 * 8 bájtokat = 800,000,000 bájtokat.

Láthatjuk, hogy a különbség elképesztően nagy. Használata HLL, csak 8100 bájtra van szükségünk, miközben a naivakat használjuk Készlet megvalósításához nagyjából 800 megabájtra lenne szükségünk.

Ha nagyobb adathalmazokat veszünk figyelembe, akkor a különbség HLL és a naiv Készlet a végrehajtás még magasabbá válik.

5. Kettő egyesülése HLL-k

HLL a szakszervezetek végrehajtásakor egy előnyös tulajdonsága van. Amikor kettő egyesülését vesszük HLL-k különálló adatsorokból készítették és mérik annak kardinalitását, ugyanazt a küszöbértéket kapjuk meg az uniónál, amelyet akkor kapnánk, ha egyetlenet használnánk HLL és kezdettől fogva kiszámította a hash értékeket mindkét adathalmaz minden elemére.

Vegye figyelembe, hogy amikor két HLL-t egyesítünk, akkor mindkettőnek azonosnak kell lennie log2m és regwidth paraméterek a megfelelő eredmények elérése érdekében.

Teszteljük ezt a tulajdonságot kettő létrehozásával HLL-k - az egyik 0–100 millió, a második pedig 100–200 millió értékkel van feltöltve:

HashFunction hashFunction = Hashing.murmur3_128 (); hosszú numberOfElements = 100_000_000; rég tolerált különbség = 1_000_000; HLL firstHll = új HLL (15, 5); HLL secondHLL = új HLL (15, 5); LongStream.range (0, numberOfElements) .forEach (elem -> {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);});

Felhívjuk figyelmét, hogy beállítottuk a HLL-k, növelve a log2m paraméter az 14-ből, amint az előző szakaszban látható, 15-re ebben a példában, mivel az eredmény HLL az unió kétszer annyi elemet fog tartalmazni.

Ezután csatlakozzunk a firstHll és secondHll használni a unió() módszer. Amint láthatja, a becsült kardinalitás hibaküszöbön belül van, mintha egyből vettük volna a kardinalitást HLL 200 millió elemmel:

firstHll.union (secondHLL); hosszú kardinalitás = firstHll.cardinality (); assertThat (kardinalitás) .isCloseTo (numberOfElements * 2, Offset.offset (toleratedDifference * 2)); 

6. Következtetés

Ebben az oktatóanyagban megnéztük a HyperLogLog algoritmus.

Láttuk, hogyan kell használni a HLL megbecsülni egy halmaz számosságát. Ezt mi is láttuk HLL nagyon helytakarékos a naiv megoldáshoz képest. És kettőn végeztük a szakszervezeti műveletet HLL-k és ellenőrizte, hogy az unió ugyanúgy viselkedik, mint a szingli HLL.

Mindezen példák és kódrészletek megvalósítása megtalálható a GitHub projektben; ez egy Maven projekt, ezért könnyen importálhatónak és futtathatónak kell lennie.