מסנן CUCKOO לעומת BLOOM, מנקודת מבטו של גופר

במאמר זה, אני מנסה ליישם ולבדוק את היעילות של פילטר קוקיה על פני מסנן פריחה. (קרא את הפוסט הקודם ב- Chord DHT, הטמעת טבלת חשיש מופצת בגולנג)

מבוא

מבני נתונים הסתברותיים מועילים מאוד, במיוחד בעת עיבוד מערכי נתונים גדולים. ברוב הפעמים, תוך כדי עבודה בצד הנתונים של הדברים, תרצה לבצע פשוט "זה הפריט לא קיים" או "הוא הפריט שכבר קיים" בשאילתת הנתונים בזמן אמת. נניח שאתה רוצה לענות על שאילתות בזמן אמת, כמו מספר ה- ips הייחודיים, ה- ips הנפוצים ביותר, אם מודעה הוצגה כבר למשתמש, באמצעות מבני נתונים הסתברותיים מספקים דרך יעילה במקום לענות על שאילתות אלה. הגישה האופיינית לשאילתות כאלה תהיה להשתמש ב- HashMap או ב- HashTable, או לאחסן את זה מטמון חיצוני כלשהו (כמו redis), אך הבעיה היא עם מערכי נתונים גדולים, מבני נתונים פשוטים אלה לא יכולים להשתלב בזיכרון. כאן נכנסים לתמונה מבני נתונים הסתברותיים בגלל יתרונות המרחב והזמן שלהם.

דוגמה השתמש במקרים

  • Google Bigtable, Apache HBase ו- Apache Cassandra ו- Postgresql משתמשים במסנני Bloom כדי להפחית את חיפוש הדיסק אחר שורות או עמודות שאינם קיימים. הימנעות מחיפושים בדיסק יקרים מגדילה באופן משמעותי את הביצועים של פעולת שאילתת מסד נתונים.
  • מדיום משתמש במסנני בלום כדי לבדוק אם מאמר כבר הומלץ למשתמש
  • Ethereum משתמשת במסנני בלום כדי לאתר במהירות יומנים ב- blockchain Ethereum
  • דפדפן האינטרנט של גוגל כרום נהג להשתמש במסנן בלום כדי לזהות כתובות אתרים זדוניות. כל כתובת אתר נבדקה לראשונה מול פילטר בלום מקומי, ורק אם מסנן בלום החזיר תוצאה חיובית הייתה בדיקה מלאה של כתובת האתר שבוצעה (והמשתמש הזהיר, אם גם זה החזיר תוצאה חיובית)

מה יש ב"קוקיה "?

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

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

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

אלגוריתם

פרמטרים של המסנן:
1. שתי פונקציות Hash: h1 ו- h2
2. מערך B עם דליים n. הדלי ה- i נקרא B [i]

קלט: L, רשימת אלמנטים שיש להכניס למסנן הקוקיה.

אלגוריתם:
בעוד L אינה ריקה:
    תן ל- x להיות הפריט הראשון ברשימה L. הסר את x מהרשימה.
    אם B [h1 (x)] ריק:
        מקם x ב B [h1 (x)]
    אחרת, אם B [h2 (x) ריק]:
        מקם x ב B [h2 (x)]
    אחרת:
        תן ל- y להיות האלמנט ב- B [h2 (x)].
        הכן את y ל L
        מקם x ב B [h2 (x)]

יישום

היישום נראה די פשוט, אז החלטתי לנסות ולהשוות כמה הוא מרווח / זמן יעיל לעומת פילטר פורח. פילטר הקוקיה מורכב מטבלת חשיש של קוקיה המאחסנת את 'טביעות האצבע' של פריטים שהוכנסו. טביעת האצבע של פריט היא מחרוזת קצת שמקורם בחשיש של אותו פריט. שולחן hash של קוקיה מורכב ממערך דליים שבהם פריט שיש להכניס למיפוי לשני דליים אפשריים על סמך שתי פונקציות hash. ניתן להגדיר כל דלי לאחסון מספר טביעות אצבע משתנה. בדרך כלל, מסנן קוקיה מזוהה לפי טביעות האצבע וגודל הדלי שלו. לדוגמה, פילטר (2,4) מסנן קוקיה אוגר טביעות אצבע באורך 2 סיביות וכל דלי בטבלת ה- Hash של קוקיה יכול לאחסן עד 4 טביעות אצבע.

הכנסה

אלגוריתם:

f = טביעת אצבע (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
אם לדלי [i1] או לדלי [i2] יש ערך ריק אז
   להוסיף f לדלי הזה;
   חזרה בוצע;
// חייב להעביר פריטים קיימים;
i = בחר באופן אקראי i1 או i2;
עבור n = 0; n 
// Hashtable נחשב למלא;
כישלון חזרה;

קוד:

לחפש

אלגוריתם:

f = טביעת אצבע (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
אם לדלי [i1] או לדלי [i2] יש f אז
    להחזיר נכון;
להחזיר שווא;

קוד:

מחק

אלגוריתם:

f = טביעת אצבע (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
אם לדלי [i1] או לדלי [i2] יש f אז
   הסר עותק של f מהדלי הזה;
   להחזיר נכון;
להחזיר שווא;

קוד:

מבחן ביצועים

השתמשתי בספריה של וויל פיצג'רלד למבחן במסנן בלום. מנת ה- FPP (הסתברות חיובית כוזבת) שנלקחה למסנן קוקיה היא 0.001

מורכבות החלל

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

מורכבות זמן

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

ביצוע ניתוח זמן של שני המסננים מניב את התוצאות הבאות:

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

הסקה

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

קוד

הפניות

  • https://brilliant.org/wiki/cuckoo-filter/
  • https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
  • https://en.wikipedia.org/wiki/Cuckoo_hashing
  • https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo.html

P.S אם אתה מוצא שמשהו לא בסדר בבדיקות / היישום, אנא אל תהסס להשאיר את ההצעה / הערות שלך.