Meta-ն բաց կոդով հրապարակեց Rebalancer-ը՝ բաշխման խնդիրների գրադարանը

Meta-ն բաց կոդով հրապարակեց Rebalancer-ը

Meta-ն Apache 2.0 լիցենզիայով բաց կոդով հրապարակել է Rebalancer-ը՝ գրադարան, որը լուծում է բաշխման խնդիրներ. տրված օբյեկտների և բիների համար գտնում է այնպիսի տեղաբաշխում, որը բավարարում է սահմանափակումներին և օպտիմալացնում նպատակները։ Ընկերության տվյալներով՝ լուծիչը ներքին ենթակառուցվածքում օգտագործվում է ավելի քան ինը տարի։

Հրապարակման հետ հասանելի են facebook/rebalancer GitHub պահոցը, փաստաթղթերը, Python փաթեթը PyPI-ում և Docker-ում աշխատող Rebalancer Explorer ինտերֆեյսը։

Մեկ գրադարան՝ բազմաթիվ խնդիրների համար

Նույն ձևակերպումը կիրառվում է Meta-ի ենթակառուցվածքի մի քանի շերտերում. սերվերների դարակները տեղաբաշխվում են տվյալների կենտրոններում՝ հավասարաչափ բաշխելով դրանք էլեկտրական խափանումների տիրույթներում. սերվերները կցվում են ծառայություններին. իսկ օգտատերերի թրաֆիկը ուղղորդվում է բաշխված կենտրոններ՝ ուշացումն ու բեռնվածությունը հավասարակշռելու համար։

Rebalancer-ը հաղթահարում է երկու հիմնական խոչընդոտ՝ օգտագործման հարմարավետությունը և մասշտաբայնությունը։ Քաղաքականությունը ձեռքով բանաձևերի վերածելու փոխարեն ինժեներները խնդիրը նկարագրում են օբյեկտներով, բիներով, սահմանափակումներով և նպատակներով, և այն վերածվում է ուղղորդված ացիկլիկ գրաֆի (expression graph)։ CapacitySpec-ի, GroupCountSpec-ի և BalanceSpec-ի նման բնութագրերը սովորական նպատակները դարձնում են կրկնօգտագործելի բաղադրատոմսեր։

Օպտիմալ լուծիչ և լոկալ որոնում

Օպտիմալ լուծիչը խնդիրը վերածում է խառը ամբողջ թվերի ծրագրավորման մոդելի FICO Xpress-ի, Gurobi-ի կամ HiGHS-ի համար՝ փոփոխականների ագրեգացիայի և սիմետրիայի խախտման միջոցով փոքրացնելով այն։ Վատագույն դեպքում չափը համաչափ է օբյեկտների և բիների արտադրյալին, ուստի ամենամեծ խնդիրները դուրս են ցանկացած MIP լուծիչի հնարավորություններից։

Լոկալ որոնման լուծիչը աշխատում է անմիջապես գրաֆի վրա և ուսումնասիրում օբյեկտների տեղափոխումները բիների միջև։ Նրա հարևանությունը համաչափ է օբյեկտների և բիների գումարին, իսկ զուգահեռացումը թույլ է տալիս վայրկյանում միլիոնավոր գնահատումներ, ուստի Meta-ում խոշոր խնդիրները լուծվում են լոկալ որոնմամբ։

Մասշտաբը Meta-ում և դրանից դուրս

Meta-ի տվյալներով՝ Rebalancer-ը օրական լուծում է մոտ 40 միլիոն բաշխման խնդիր՝ ավելի քան 30 ձևակերպումներով։ P99 լուծման ժամանակը 12 վայրկյան է 265 հազար օբյեկտ և 3 200 բին ունեցող խնդրի դեպքում. 1 միլիոնից ավելի օբյեկտ և 5 000 բին ունեցող խնդիրների համար միջին ժամանակը 171 վայրկյան է։

Ենթակառուցվածքից դուրս գրադարանը կիրառվել է հանդիպումները սենյակներին կցելու, աջակցության հարցումները ինժեներներին բաշխելու համար։ Meta-ն նշում է, որ նման խնդիրները տարածված են առողջապահության, էներգետիկայի և լոգիստիկայում։