streamalism.org

1. סקירה כללית

ה HyperLogLog (HLL) מבנה נתונים הוא מבנה נתונים הסתברותי שהיה רגיל מעריך את הקרדינליות של מערך הנתונים.

נניח שיש לנו מיליוני משתמשים ואנחנו רוצים לחשב את מספר הביקורים הנפרדים בדף האינטרנט שלנו. יישום נאיבי יהיה לאחסן כל מזהה משתמש ייחודי בערכה, ואז גודל הסט יהיה הקרדינליות שלנו.

כאשר אנו מתמודדים עם כמויות גדולות מאוד של נתונים, ספירת הקרדינליות בדרך זו תהיה מאוד לא יעילה מכיוון שמערך הנתונים ייקח זיכרון רב.

אבל אם אנחנו בסדר עם הערכה בתוך כמה אחוזים ואיננו זקוקים למספר המדויק של ביקורים ייחודיים, נוכל להשתמש ב HLL, מכיוון שהוא תוכנן בדיוק למקרה כזה לשימוש - אומדן את ספירת המיליונים ואף מיליארדי הערכים המובהקים.

2. תלות של Maven

כדי להתחיל נצטרך להוסיף את התלות של Maven עבור ה- hll סִפְרִיָה:

 net.agkn hll 1.6.0 

3. הערכת קרדינליות באמצעות HLL

קפיצה ישר פנימה - HLL לבנאי יש שני טיעונים שנוכל לצבוט בהתאם לצרכים שלנו:

• log2m (בסיס יומן 2) - זהו מספר המרשמים המשמשים באופן פנימי HLL (הערה: אנו מציינים את M)
• רוחב מחדש - זהו מספר הביטים המשמשים לכל רישום

אם אנו רוצים דיוק גבוה יותר, עלינו להגדיר אותם לערכים גבוהים יותר. לתצורה כזו תהיה תקורה נוספת מכיוון שלנו HLL יתפוס יותר זיכרון. אם אנחנו בסדר עם דיוק נמוך יותר, אנחנו יכולים להוריד את הפרמטרים האלה ואת שלנו HLL יתפוס פחות זיכרון.

בואו ניצור HLL לספור ערכים נפרדים עבור מערך נתונים עם 100 מיליון ערכים. נגדיר את log2m פרמטר שווה ל- 14 ו רוחב מחדש שווה ל 5 - ערכים סבירים עבור מערך נתונים בגודל זה.

כאשר כל אלמנט חדש מוכנס ל- HLL, צריך לשטוף אותו מראש. אנו נשתמש Hashing.murmur3_128 () מספריית גויאבה (כלול עם hll תלות) כי זה גם מדויק וגם מהיר.

HashFunction hashFunction = Hashing.murmur3_128 (); numberOfElements ארוך = 100_000_000; toleredDifference ארוך = 1_000_000; HLL hll = HLL חדש (14, 5);

בחירת אותם פרמטרים אמורה לתת לנו שיעור שגיאות מתחת לאחוז אחד (1,000,000 אלמנטים). נבדוק זאת עוד רגע.

לאחר מכן, בואו נכניס את 100 מיליון האלמנטים:

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

לבסוף נוכל לבדוק זאת הקרדינליות שהוחזרה על ידי HLL נמצא בסף השגיאה הרצוי שלנו:

קרדינליות ארוכה = hll.cardinality (); assertThat (cardinality) .isCloseTo (numberOfElements, Offset.offset (toleratedDifference));

4. גודל הזיכרון של HLL

אנחנו יכולים לחשב כמה זיכרון שלנו HLL מהסעיף הקודם ייקח באמצעות הנוסחה הבאה: numberOfBits = 2 ^ log2m * רוחב מחדש.

בדוגמה שלנו זה יהיה 2 ^ 14 * 5 ביטים (בערך 81000 ביטים או 8100 בתים). אז מעריכים את הקרדינליות של 100 מיליון חברים שקובעים באמצעות HLL תפוס 8100 בתים בלבד של זיכרון.

בואו נשווה זאת עם יישום סט נאיבי. ביישום כזה, עלינו להיות עם מַעֲרֶכֶת של 100 מיליון ארוך ערכים, אשר היו כובשים 100,000,000 * 8 בתים = 800,000,000 בתים.

אנו יכולים לראות שההבדל הוא גבוה להפליא. באמצעות HLL, אנו זקוקים ל 8100 בתים בלבד, בעוד שאנחנו משתמשים בתמימים מַעֲרֶכֶת היינו זקוקים לכ- 800 מגה.

כאשר אנו רואים מערכי נתונים גדולים יותר, ההבדל בין HLL והנאיבי מַעֲרֶכֶת היישום הופך להיות גבוה עוד יותר.

5. איחוד של שניים HLLs

HLL בעל תכונה מועילה אחת בעת ביצוע איגודים. כשאנחנו לוקחים את האיחוד של שניים HLLs נוצר מערכי נתונים מובחנים ומודדים את הקרדינליות שלו, נקבל את אותו סף שגיאה עבור האיחוד שהיינו מקבלים אם היינו משתמשים בסינגל אחד HLL וחישב את ערכי החשיש עבור כל האלמנטים של שני מערכי הנתונים מההתחלה.

שים לב שכאשר אנו מאחדים שני HLL, שניהם צריכים להיות זהים log2m ו רוחב מחדש פרמטרים להניב תוצאות מתאימות.

בואו נבדוק את המאפיין על ידי יצירת שניים HLLs - האחד מאוכלס בערכים שבין 0 ל -100 מיליון, והשני מאוכלס בערכים שבין 100 מיליון ל -200 מיליון:

HashFunction hashFunction = Hashing.murmur3_128 (); numberOfElements ארוך = 100_000_000; toleredDifference ארוך = 1_000_000; HLL firstHll = חדש HLL (15, 5); HLL secondHLL = HLL חדש (15, 5); LongStream.range (0, numberOfElements) .forEach (רכיב -> {long hashedValue = hashFunction.newHasher () .putLong (element) .hash () .asLong (); firstHll.addRaw (hashedValue);}); LongStream.range (numberOfElements, numberOfElements * 2) .forEach (רכיב -> {long hashedValue = hashFunction.newHasher () .putLong (element) .hash () .asLong (); secondHLL.addRaw (hashedValue);});

שים לב כי כיוונו את פרמטרי התצורה של ה- HLLs, הגדלת log2m פרמטר מ- 14, כפי שנראה בסעיף הקודם, ועד 15 לדוגמא זו, מכיוון שהתקבל HLL האיחוד יכיל פי שניים אלמנטים.

הבא, בואו לאחד את firstHll ו secondHll משתמש ב הִתאַחֲדוּת() שיטה. כפי שאתה יכול לראות, הקרדינליות המשוערת נמצאת בסף שגיאה כאילו לקחנו את הקרדינליות מאחת HLL עם 200 מיליון אלמנטים:

firstHll.union (secondHLL); קרדינליות ארוכה = firstHll.cardinality (); assertThat (cardinality) .isCloseTo (numberOfElements * 2, Offset. offset (toleratedDifference * 2)); 

6. מסקנה

במדריך זה, הסתכלנו על HyperLogLog אַלגוֹרִיתְם.

ראינו כיצד להשתמש ב- HLL לאמוד את הקרדינליות של סט. ראינו את זה גם HLL יעיל מאוד בחלל בהשוואה לפיתרון הנאיבי. וביצענו את פעולת האיחוד בשניים HLLs ואומת שהאיחוד מתנהג באותה צורה כמו יחיד HLL.

ניתן למצוא את היישום של כל הדוגמאות וקטעי הקוד בפרויקט GitHub; זהו פרויקט של Maven, כך שיהיה קל לייבא ולהפעיל אותו כפי שהוא.