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

תַקצִיר

כל יום ב-Roblox, 65.5 מיליון משתמשים מעורבים במיליוני חוויות, בסך הכל 14.0 מיליארד שעות מדי רבעון. אינטראקציה זו יוצרת אגם נתונים בקנה מידה פטה-בייט, אשר מועשר למטרות ניתוח ולמידת מכונה (ML). זה עתיר משאבים להצטרף לטבלאות עובדות ומימדים באגם הנתונים שלנו, אז כדי לייעל זאת ולהפחית את ערבוב הנתונים, אימצנו את מסנני הפריחה הלומדים [1] - מבני נתונים חכמים המשתמשים ב-ML. על ידי חיזוי נוכחות, מסננים אלה חותכים במידה ניכרת את נתוני ההצטרפות, משפרים את היעילות ומפחיתים עלויות. לאורך הדרך, שיפרנו גם את ארכיטקטורות המודל שלנו והדגמנו את היתרונות המשמעותיים שהם מציעים להפחתת שעות הזיכרון והמעבד לעיבוד, כמו גם הגברת היציבות התפעולית.

מבוא

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

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

שיפור יעילות ההצטרפות עם מסנני פריחה נלמדים

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

אבולוציה ממסנני פריחה מסורתיים למסנני פריחה נלמדים

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

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

כחלק מעבודה זו, קבענו שני מדדים להערכת גישת ה-Learned Bloom Filter שלנו: גודל האובייקט המסודר הסופי של האינדקס וצריכת ה-CPU במהלך ביצוע שאילתות הצטרפות. 

ניווט באתגרי יישום

האתגר הראשוני שלנו היה להתמודד עם מערך אימון מוטה ביותר עם מעט מפתחות טבלת מימדים בטבלת העובדות. תוך כדי כך, ראינו חפיפה של כאחד מכל שלושה מפתחות בין הטבלאות. כדי להתמודד עם זה, מינפנו את גישת ה-Sandwich Learned Bloom Filter [2]. זה משלב מסנן בלום מסורתי ראשוני כדי לאזן מחדש את הפצת מערך הנתונים על ידי הסרת רוב המפתחות שהיו חסרים מטבלת העובדות, ולמעשה ביטול דגימות שליליות ממערך הנתונים. לאחר מכן, רק המפתחות הכלולים ב-Bloom Filter הראשוני, יחד עם התוצאות הכוזבות, הועברו למודל ה-ML, המכונה לעתים קרובות "אורקל נלמד". גישה זו הביאה למערך אימון מאוזן היטב עבור האורקל הנלמד, והתגבר ביעילות על סוגיית ההטיה.

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

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

שאילתת ההצטרפות המעודכנת שלנו באמצעות מסנני פריחה נלמדים היא כפי שמוצג להלן:

תוצאות

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

השוואת גודל מסנן בלום נלמדת

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

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

תוצאות שימוש במסנן בלום נלמד 

בסעיף זה, אנו משווים את הביצועים של חיבורים מבוססי Bloom Filter לאלה של צירופים רגילים על פני מספר מדדים. 

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

ראשית, גילינו שהטמעת Bloom Filter עמדה בביצועים טובים יותר מההצטרפות הרגילה בשיעור של עד 60% בשעות המעבד. ראינו עלייה בשימוש ב-CPU של שלב הסריקה עבור גישת Learned Bloom Filter עקב החישוב הנוסף שהושקע בהערכה של Bloom Filter. עם זאת, הסינון המקדים שנעשה בשלב זה הפחית את גודל הנתונים שעורבבו, מה שעזר להפחית את ה-CPU המשמש את השלבים במורד הזרם, ובכך הפחית את סך שעות ה-CPU.

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

ראינו גם שימוש מופחת במשאבים בעומסי העבודה האחרים שלנו בניסויים. במשך תקופה של שבועיים בכל חמשת עומסי העבודה, גישת ה-Learned Bloom Filter יצרה ממוצע חיסכון בעלויות יומיות of 25%, אשר אחראית גם על הכשרת מודלים ויצירת אינדקס.

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

הפניות

[1] T. Kraska, A. Beutel, EH Chi, J. Dean, and N. Polyzotis. המקרה למבני אינדקס נלמדים. https://arxiv.org/abs/1712.01208 2017.

[2] מ' מיצנמכר. אופטימיזציה של מסנני פריחה נלמדים על ידי סנדוויץ'. 

https://arxiv.org/abs/1803.01474 2018.

---

¹נכון ל-3 חודשים שהסתיימו ב-30 ביוני 2023

²נכון ל-3 חודשים שהסתיימו ב-30 ביוני 2023

• הפצת תוכן ויחסי ציבור מופעל על ידי SEO. קבל הגברה היום.
• PlatoData.Network Vertical Generative Ai. העצים את עצמך. גישה כאן.
• PlatoAiStream. Web3 Intelligence. הידע מוגבר. גישה כאן.
• PlatoESG. פחמן, קלינטק, אנרגיה, סביבה, שמש, ניהול פסולת. גישה כאן.
• PlatoHealth. מודיעין ביוטכנולוגיה וניסויים קליניים. גישה כאן.
• מקור: https://blog.roblox.com/2023/11/roblox-reduces-spark-join-query-costs-machine-learning-optimized-bloom-filters/