HyperLogLog: egyedi elemek számolása a Redisben alacsony memóriával

Képzelje el, hogy egy népszerű weboldalt üzemeltet, és szeretné tudni, hány egyedi látogató keresi fel naponta. Vagy egy mobilalkalmazás fejlesztőjeként érdekli, hány egyedi felhasználó indította el az appot egy adott időszakban. Esetleg egy online hirdetési platformot kezel, és azt vizsgálná, hány egyedi felhasználó látta a hirdetéseit. Ezek a feladatok első ránézésre egyszerűnek tűnhetnek, de amint az adatok volumene növekszik, a hagyományos számlálási módszerek gyorsan falakba ütköznek. Itt jön képbe a HyperLogLog, egy zseniális algoritmus, amelyet a Redis is natívan támogat, forradalmasítva az egyedi elemek számolását alacsony memóriával.

A probléma: Skálázható egyedi számlálás

A legegyszerűbb megközelítés az egyedi elemek számolására az lenne, ha minden egyes beérkező elemet eltárolnánk egy halmazban (pl. Redis SET vagy egy adatbázis tábla), majd megszámolnánk az elemeket ebben a halmazban. Ez a módszer tökéletesen pontos, de van egy óriási hátránya: a memóriafelhasználás arányosan növekszik az egyedi elemek számával. Ha milliárdnyi egyedi IP-címről, felhasználói azonosítóról vagy termékazonosítóról van szó, ez a megközelítés irreálisan magas memóriát igényelne, ami költséges és lassú műveletekhez vezetne.

Például, ha 100 millió egyedi felhasználót kell tárolnunk, és minden felhasználói azonosító átlagosan 10 bájt, akkor már 1 GB memóriára van szükségünk csak az azonosítók tárolására, nem is beszélve a halmaz (SET) adatszerkezet overheadjéről. Ráadásul a beszúrások és lekérdezések is lassabbá válhatnak hatalmas halmazok esetén. A valós idejű analitikához, ahol gyors válaszra van szükség, ez a megoldás gyakran nem megfelelő.

Mi az a HyperLogLog?

A HyperLogLog (HLL) egy probabilisztikus adatszerkezet, amely képes becsülni egy halmazban lévő egyedi elemek számát rendkívül alacsony és fix memóriaigény mellett, függetlenül az elemek számától. Igen, jól olvasta: függetlenül attól, hogy 1000 vagy 10 milliárd egyedi elemet próbálunk megszámolni, a memóriafelhasználás gyakorlatilag állandó marad. Ennek ára az, hogy az eredmény nem 100%-osan pontos, hanem egy becslés, de rendkívül kis hibahatárral. A Redis implementációja például tipikusan 0.81%-os relatív szórású hibát garantál, ami a legtöbb analitikai feladathoz bőven elegendő.

A HyperLogLog a Big Data világának egyik legfontosabb eszköze, mivel lehetővé teszi a valós idejű, skálázható analitikát ott, ahol a pontos számlálás egyszerűen nem kivitelezhető a memória- vagy számítási kapacitás korlátai miatt.

Hogyan működik a HyperLogLog? Az intuíció

A HyperLogLog működésének alapja meglehetősen intuitív, még ha a mögöttes matematika (amelyet a cikk terjedelme miatt nem boncolgatunk mélyen) bonyolult is lehet. Képzeljen el egy olyan kísérletet, ahol folyamatosan dobunk egy érmével, és figyeljük, hányszor kapunk egymás után fejet, mielőtt először írást kapnánk. Minél többször dobáljuk az érmét (azaz minél több egyedi elemet látunk), annál valószínűbb, hogy egyszer hosszú sorozatban is fejet kapunk. Ha valaki azt mondja, hogy hatszor dobott egymás után fejet, anélkül, hogy írást kapott volna, akkor azt feltételezzük, hogy valószínűleg már nagyon sok érmedobást végzett.

A HyperLogLog hasonló elven működik, de az érmedobások helyett a beérkező elemek hash értékeit használja. Minden egyes beérkező elemről először egy determinisztikus hash függvényt számolunk (pl. SHA1 vagy MurmurHash), amely az elemet egy nagy, véletlenszerű bináris számmá alakítja. Ezt követően megvizsgáljuk ezeknek a bináris hash értékeknek a „vezető nulláit” (leading zeros).

Ha egy hash érték bináris reprezentációja például 0001011..., akkor két vezető nullája van.
Ha 0000101..., akkor négy vezető nullája van.

Az intuitív gondolat az, hogy ha sok egyedi elemet látunk, akkor előbb-utóbb valószínűleg találunk egy olyan hash értéket, amelynek nagyon sok vezető nullája van. Minél több vezető nullát találunk, annál valószínűbb, hogy már sok egyedi elemet feldolgoztunk. A HyperLogLog nem egyetlen ilyen maximális leading zero értéket tárol, hanem az adatfolyamot több „vödörre” (bucketre) osztja, és minden vödörhöz eltárolja a maximális vezető nulla számot, amit abban a vödörben talált. Ezeknek a maximális értékeknek a harmonikus átlagából becsüli meg az algoritmus a teljes egyedi elemszámot.

Ez az okos megközelítés teszi lehetővé, hogy az algoritmus csupán néhány bájtnyi memóriával (a vödrök számától függően) képes legyen milliárdnyi egyedi elem becsült számát tárolni.

HyperLogLog a Redisben

A Redis natívan támogatja a HyperLogLog adatszerkezetet, és három egyszerű paranccsal használható:

1. PFADD (Probabilistic Add)

A PFADD parancs használatával adhatunk hozzá elemeket a HyperLogLog struktúrához. A parancs neve (PFADD) a „Probabilistic Filter Add” rövidítése.

PFADD mykey element1 element2 element3 ...

Példa:

127.0.0.1:6379> PFADD unique_visitors "user:123" "user:456" "user:123" "user:789"
(integer) 1
127.0.0.1:6379> PFADD unique_visitors "user:999" "user:123"
(integer) 1

Figyeljük meg, hogy a „user:123” elemet többször is hozzáadtuk, de a HyperLogLog csak egyszer veszi figyelembe az egyedi számlálásnál. A PFADD parancs visszatérési értéke 1, ha a HyperLogLog struktúra frissítésre került (azaz valószínűleg egy új egyedi elemet láttunk, vagy egy korábbi leading zero rekordot felülírtunk), és 0, ha nem.

2. PFCOUNT (Probabilistic Count)

A PFCOUNT parancs visszaadja a HyperLogLog struktúrában becsült egyedi elemek számát.

PFCOUNT mykey [mykey2 ...]

Példa:

127.0.0.1:6379> PFADD unique_visitors "user:123" "user:456" "user:123" "user:789"
(integer) 1
127.0.0.1:6379> PFCOUNT unique_visitors
(integer) 3
127.0.0.1:6379> PFADD unique_visitors "user:999" "user:123"
(integer) 1
127.0.0.1:6379> PFCOUNT unique_visitors
(integer) 4

A fenti példában az első PFADD után „user:123”, „user:456” és „user:789” elemek kerültek be, így a számlálás 3. A második PFADD után „user:999” is bekerült, így a becslés 4. Még ha a „user:123” többször is szerepel, az csak egyszer számít.

A PFCOUNT képes több HyperLogLog kulcsot is kezelni, és azok egyesített egyedi elemszámát megbecsülni. Ez különösen hasznos, ha például napi statisztikákat gyűjtünk, majd a heti vagy havi összegzést szeretnénk lekérdezni.

127.0.0.1:6379> PFADD day1_visitors "user:1" "user:2"
(integer) 1
127.0.0.1:6379> PFADD day2_visitors "user:2" "user:3"
(integer) 1
127.0.0.1:6379> PFCOUNT day1_visitors day2_visitors
(integer) 3
# It correctly estimates 3 unique users ("user:1", "user:2", "user:3") across both days.

3. PFMERGE (Probabilistic Merge)

A PFMERGE parancs lehetővé teszi több HyperLogLog struktúra egyesítését egyetlen új struktúrába. Ez akkor hasznos, ha hosszú távú aggregációkat szeretnénk létrehozni, például napi HLL-eket összevonni heti HLL-be.

PFMERGE destkey sourcekey1 [sourcekey2 ...]

Példa:

127.0.0.1:6379> PFADD day1_visitors "user:A" "user:B"
(integer) 1
127.0.0.1:6379> PFADD day2_visitors "user:B" "user:C"
(integer) 1
127.0.0.1:6379> PFMERGE week1_visitors day1_visitors day2_visitors
OK
127.0.0.1:6379> PFCOUNT week1_visitors
(integer) 3

Memóriaigény a Redisben

A Redis HyperLogLog implementációja kivételesen memóriaeffektív. Egyetlen HLL kulcs kezdetben nagyon kis memóriát foglal (sparse representation), de ahogy az egyedi elemek száma nő, egy fix méretű, 12288 bájtos (12 KB) sűrű reprezentációra vált. Ez a 12 KB méret konstans, függetlenül attól, hogy 1 millió vagy 1 milliárd egyedi elemet becsülünk. Ez az egyik legvonzóbb tulajdonsága.

Felhasználási esetek

A HyperLogLog rendkívül sokoldalú, és számos területen alkalmazható, ahol a skálázható egyedi számlálás kulcsfontosságú:

Weboldal látogatottság: Egyedi IP-címek vagy felhasználói munkamenet-azonosítók számlálása naponta, hetente, havonta.
Mobilalkalmazás analitika: Aktív felhasználók, egyedi események (pl. kattintások, letöltések) száma.
Hirdetésmegjelenítések: Egyedi felhasználók, akik láttak egy adott hirdetést, vagy egy kampány egyedi elérése.
Adatfolyam feldolgozás: Valós idejű egyedi metrikák számolása streaming adatokból.
Hálózati monitorozás: Egyedi forrás- vagy cél IP-címek száma egy hálózaton.
Keresőmotorok: Egyedi keresési lekérdezések száma.

Előnyök és Hátrányok

Előnyök:

Rendkívül alacsony memóriaigény: Ahogy már említettük, ez a legfőbb előnye. A fix 12 KB (Redisben) memóriahasználat kulcsfontosságú a nagy adatmennyiségek kezelésénél.
Gyors működés: A PFADD, PFCOUNT és PFMERGE műveletek időbeli komplexitása nagyon alacsony, gyakorlatilag konstans (O(1)), ami lehetővé teszi a valós idejű feldolgozást.
Skálázhatóság: Kiválóan alkalmas hatalmas adathalmazok és magas bemeneti sebesség kezelésére.
Egyszerű használat: A Redis parancsok egyszerűek és intuitívak, ami megkönnyíti az implementációt.
Összevonhatóság: A HLL struktúrák könnyen egyesíthetők (PFMERGE, vagy PFCOUNT több kulccsal), ami rugalmasságot biztosít az aggregációkhoz.

Hátrányok:

Probabilisztikus természet: Ez nem egy pontos számláló. Mindig van egy kis hibahatár az eredményben. Bár a Redis HLL implementációjának tipikus hibája nagyon alacsony (0.81%), ez kritikus lehet bizonyos alkalmazásoknál, ahol az abszolút pontosság elengedhetetlen (pl. pénzügyi tranzakciók).
Nincs elem visszaállítás: A HyperLogLog nem tárolja magukat az elemeket, csak egy becslést ad a számukról. Ezért nem tudjuk lekérdezni, hogy mely elemeket adtuk hozzá, vagy ellenőrizni, hogy egy adott elem már benne van-e.
Fix hibahatár: A Redis implementációjában a hibahatár rögzített (nem konfigurálható, mint egyes más HLL implementációkban, ahol a memória/pontosság trade-off állítható).

Mikor válasszuk a HyperLogLogot, és mikor mást?

A választás mindig a konkrét alkalmazási igényektől függ:

Pontos számlálás és elemek lekérdezése szükséges? Ha az abszolút pontosság kritikus, vagy ha később lekérdezné, hogy egy adott elem benne van-e a halmazban, vagy ha az elemeket listázni szeretné, akkor használjon Redis SET adatszerkezetet. Fontos azonban észben tartani a SET magas memóriaigényét nagy adathalmazok esetén.
Becsült egyedi számlálás, alacsony memóriaigény és sebesség a prioritás? Akkor a HyperLogLog a tökéletes választás. Ez az adatszerkezet kiválóan alkalmas analitikai feladatokra, ahol a „kb.” elég jó.

Gyakorlati tanácsok és legjobb gyakorlatok

Mérje fel a hibahatárt: Mielőtt HyperLogLog-ot használna, győződjön meg arról, hogy a 0.81%-os relatív standard hiba elfogadható az Ön alkalmazásához. A legtöbb analitikai célra ez bőven elegendő.
Használja a PFMERGE-et aggregációkhoz: Ha napi, heti, havi statisztikákat szeretne gyűjteni, hozzon létre külön HLL kulcsokat minden időszakra (pl. visitors:20231026), majd használja a PFMERGE parancsot ezek összevonására hosszabb időtávokhoz (pl. weekly_visitors:2023_W43).
Kulcsok elnevezése: Használjon világos és konzisztens elnevezési konvenciókat a HLL kulcsokhoz, különösen, ha időalapú aggregációkat végez.
Ne használja pénzügyi vagy kritikus adatokhoz: Soha ne használja HLL-t olyan helyzetekben, ahol az adatok integritása vagy abszolút pontossága alapvető fontosságú (pl. számlák, pénzügyi tranzakciók, jogi dokumentumok).

Összefoglalás

A HyperLogLog egy kivételesen elegáns és hatékony megoldás a Redis-ben az egyedi elemek számolására, különösen nagy adatmennyiségek esetén. Képessége, hogy konstans, alacsony memóriával működjön, miközben rendkívül gyors becsléseket ad, felbecsülhetetlenné teszi az analitikai és Big Data alkalmazásokban. Bár nem nyújt abszolút pontosságot, a tipikusan alacsony hibahatár miatt a legtöbb üzleti és technológiai igény kielégítésére alkalmas. Ha szembesül a skálázható egyedi számlálás kihívásával, és egy kis becslési hiba elfogadható, akkor a HyperLogLog a Redis-ben egy olyan eszköz, amelyet feltétlenül meg kell ismernie és használnia kell.