איך Bloom Filter בודק קיום ערך בלי לשמור אותו בכלל¶
תארו לעצמכם שאתם צריכים לבדוק, מיליארד פעמים ביום, אם כתובת אתר מסוימת נמצאת ברשימה שחורה שמכילה עשרות מיליוני כתובות. אפשר לשמור את כל הרשימה בטבלת גיבוב רגילה ולבדוק מולה, אבל זה דורש כמות זיכרון עצומה. מבנה נתונים בשם Bloom Filter פותר את זה בצורה שנשמעת כמעט בלתי אפשרית - הוא בודק קיום, כמעט תוך הבטחה מהירה, בלי לשמור אף אחד מהערכים עצמם.
הרעיון הבסיסי - מערך ביטים במקום רשימה¶
Bloom Filter הוא, בבסיסו, רק מערך ארוך של ביטים, שכולם מתחילים באפס. אין בו שום מקום ששומר את הערכים עצמם - לא את הכתובת, לא שום דבר שמזהה אותה. במקום זה, כל ערך שרוצים "להוסיף" למסנן עובר כמה פונקציות גיבוב שונות בו-זמנית, נגיד שלוש פונקציות, שכל אחת מהן מחזירה מיקום שונה במערך הביטים. כל מיקום שהתקבל הופך מ-0 ל-1.
איך בודקים אם ערך "קיים"¶
כדי לבדוק אם ערך מסוים נמצא במסנן, מריצים עליו בדיוק את אותן שלוש פונקציות גיבוב, ומקבלים שלושה מיקומים. אם כל שלושת הביטים באותם מיקומים הם 1, המסנן עונה "כנראה כן, הערך הזה קיים". אם ולו ביט אחד מתוך השלושה הוא עדיין 0, המסנן עונה בביטחון מוחלט "לא, הערך הזה בטוח לא נוסף אף פעם" - כי אם הוא היה נוסף, כל שלושת הביטים המתאימים לו היו הופכים ל-1 בזמן ההוספה.
למה "כנראה כן" ולא "בטוח כן"¶
כאן טמון הטריק המרכזי, וגם המחיר. מכיוון שכמה ערכים שונים יכולים "לחלוק" את אותם ביטים במקרה, כי יש מספר סופי של ביטים במערך אבל מספר עצום של ערכים אפשריים, יכול לקרות שכל שלושת הביטים הרלוונטיים לערך מסוים הפכו ל-1 מהוספה של ערכים אחרים לגמרי, בלי שהערך הזה עצמו נוסף בכלל. זה נקרא תוצאה חיובית שגויה (false positive) - Bloom Filter אמר "כנראה כן" על ערך שלמעשה מעולם לא נוסף.
הנקודה הקריטית - Bloom Filter לעולם לא טועה בכיוון ההפוך. הוא לעולם לא יגיד "לא" על ערך שבאמת נוסף. הבטחת ה-0 שלו מוחלטת, הבטחת ה-1 שלו הסתברותית. זו הסיבה שהוא שימושי בדיוק במקרים שבהם "אולי" מספיק כדי לחסוך עבודה, כל עוד "בטוח לא" תמיד נכון.
למה זה שימושי דווקא בגלל ה-"אולי"¶
הדוגמה הקלאסית - מסד נתונים גדול שרוצה לדעת אם מפתח מסוים בכלל קיים, לפני שהוא טורח לבצע חיפוש יקר בדיסק. הוא בודק קודם מול Bloom Filter קטן שיושב בזיכרון. אם התשובה "בטוח לא", המסד נתונים חוסך לגמרי את הפנייה היקרה לדיסק, כי הוא יודע בוודאות שאין טעם לחפש. אם התשובה "כנראה כן", הוא ממשיך לחיפוש האמיתי כרגיל, כי צריך לוודא. כך, ברוב המקרים שבהם ערך באמת לא קיים, נחסכת פנייה יקרה, ורק לעיתים נדירות, כשיש התנגשות מקרית, נעשית פנייה מיותרת.
למה זה חוסך כל כך הרבה זיכרון¶
היתרון המרכזי לעומת טבלת גיבוב רגילה הוא שגודל המסנן לא תלוי באורך הערכים עצמם, רק במספר הביטים שהוקצו מראש. אפשר לייצג עשרות מיליוני כתובות אתרים ארוכות במסנן שתופס רק כמה מגה-בייטים בודדים, מול הזיכרון הרב שהיה נדרש לשמור את כל הכתובות בפועל. המחיר היחיד הוא שיעור קטן ומבוקר של תשובות חיוביות שגויות, שאפשר לכוונן על ידי גודל המערך ומספר פונקציות הגיבוב.
למה כדאי להכיר את זה¶
Bloom Filter מופיע בכל מקום שבו יש בעיה של "בדיקת קיום מהירה במאגר ענק" - דפדפנים משתמשים בו לבדוק כתובות זדוניות, מסדי נתונים משתמשים בו כדי לחסוך פניות דיסק מיותרות, ומערכות רשת משתמשות בו לסינון מהיר. זה בדיוק הסוג של מבנה נתונים חכם שבונים עליו הבנה עמוקה יותר בקורס התכנות הבסיסי שלנו, אחרי שמבינים היטב את היסודות של טבלאות גיבוב.
קורס התכנות הבסיסי שלנו בונה את ההבנה של מבני נתונים שלב אחר שלב.
יש לכם שאלה על מבנה נתונים שחוסך זיכרון או זמן? שאלו בדיסקורד.
לסיכום¶
Bloom Filter מוותר על ודאות מלאה בתמורה לחיסכון עצום בזיכרון - הוא לעולם לא טועה כשהוא אומר "לא", אבל לפעמים טועה כשהוא אומר "כנראה כן". במקרים שבהם המטרה היא לחסוך עבודה יקרה על מקרים שוודאי לא קיימים, זו בדיוק הפשרה הנכונה.