Meta משחררת בקוד פתוח את Rebalancer לבעיות שיוך

Meta משחררת את Rebalancer בקוד פתוח

Meta פרסמה בקוד פתוח את Rebalancer, ברישיון Apache 2.0. הספרייה פותרת בעיות שיוך: בהינתן קבוצת אובייקטים וקבוצת בינים, היא מוצאת שיוך שמקיים אילוצים וממטב מטרות מוגדרות. לפי החברה, הפותר משמש בתוך Meta יותר מתשע שנים.

הפרסום כולל את המאגר facebook/rebalancer ב-GitHub, תיעוד, חבילת Python ב-PyPI, ואת Rebalancer Explorer — ממשק ווב ארוז ב-Docker לניפוי תקלים בהתנהגות הפותר.

ספרייה אחת, בעיות רבות

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

Rebalancer מתמודד עם שני החסמים שמעכבים בדרך כלל מסגרות אופטימיזציה לשימוש חוזר: נוחות שימוש וסקייל. במקום לתרגם מדיניות לנוסחאות מתמטיות ביד, מהנדסים מתארים את הבעיה באובייקטים, בינים, אילוצים ומטרות, והיא מומרת לגרף מכוון ללא מעגלים (expression graph). מפרטים מוכנים כמו CapacitySpec, GroupCountSpec ו-BalanceSpec הופכים מטרות נפוצות למתכונים לשימוש חוזר.

פותר אופטימלי וחיפוש מקומי

הפותר האופטימלי ממיר את הבעיה למודל תכנות מעורב שלם עבור FICO Xpress, Gurobi או HiGHS, ומצמצם אותו באמצעות אגירת משתנים ושבירת סימטריה. במקרה הגרוע גודל המודל גדל כמכפלת מספר האובייקטים במספר הבינים, ולכן הבעיות הגדולות ביותר מחוץ ליכולתו של כל פותר MIP.

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

היקף השימוש ב-Meta ומעבר לה

לפי Meta, Rebalancer פותר כיום כ-40 מיליון בעיות שיוך ביום ביותר מ-30 נוסחים. זמן הפתרון ב-P99 הוא 12 שניות לבעיה עם 265 אלף אובייקטים ו-3,200 בינים; בבעיות של יותר ממיליון אובייקטים ו-5,000 בינים זמן הפתרון הממוצע הוא 171 שניות.

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