Այսպիսով, եկեք պատկերացնենք. Սենյակում փակված է 5 կատու, և որպեսզի գնան տիրոջը արթնացնեն, նրանք բոլորը պետք է պայմանավորվեն այս հարցում, քանի որ դուռը կարող են բացել միայն հինգի վրա հենված։ Եթե կատուներից մեկը Շրյոդինգերի կատուն է, իսկ մյուս կատուները չգիտեն նրա որոշման մասին, հարց է առաջանում. «Ինչպե՞ս կարող են դա անել»:
Այս հոդվածում ես ձեզ պարզ բառերով կպատմեմ բաշխված համակարգերի աշխարհի տեսական բաղադրիչի և դրանց գործունեության սկզբունքների մասին: Ես նաև մակերեսորեն կքննեմ Պաքսոսի հիմքում ընկած հիմնական գաղափարը։
Երբ մշակողները օգտագործում են ամպային ենթակառուցվածքները, տարբեր տվյալների բազաները և աշխատում են մեծ թվով հանգույցների կլաստերներում, նրանք վստահ են, որ տվյալները կլինեն ամբողջական, անվտանգ և միշտ հասանելի: Բայց որտե՞ղ են երաշխիքները։
Ըստ էության, մեր ունեցած երաշխիքները մատակարարի երաշխիքներն են: Փաստաթղթում դրանք նկարագրված են հետևյալ կերպ. «Այս ծառայությունը բավականին հուսալի է, ունի տրված SLA, մի անհանգստացեք, ամեն ինչ կաշխատի բաշխված, ինչպես դուք եք ակնկալում»:
Մենք հակված ենք հավատալ լավագույնին, քանի որ խոշոր ընկերությունների խելացի տղաները մեզ վստահեցնում էին, որ ամեն ինչ լավ է լինելու։ Մենք հարց չենք տալիս՝ իրականում ինչու՞ սա կարող է ընդհանրապես աշխատել: Կա՞ որևէ ֆորմալ հիմնավորում նման համակարգերի ճիշտ աշխատանքի համար:
Ես վերջերս գնացի և շատ ոգեշնչված էր այս թեմայից: Դպրոցում դասախոսություններն ավելի շատ նման էին հաշվարկի դասերի, քան համակարգչային համակարգերի հետ կապված: Բայց հենց այդպես էլ ժամանակին ապացուցվեցին ամենակարևոր ալգորիթմները, որոնք մենք օգտագործում ենք ամեն օր, առանց նույնիսկ դրա մասին իմանալու։
Ժամանակակից բաշխված համակարգերի մեծ մասը օգտագործում է Paxos-ի կոնսենսուսի ալգորիթմը և դրա տարբեր փոփոխությունները: Ամենաթեժն այն է, որ այս ալգորիթմի գոյության վավերականությունը և, սկզբունքորեն, հավանականությունը կարելի է ապացուցել պարզապես գրիչով և թղթով։ Գործնականում ալգորիթմն օգտագործվում է ամպերի հսկայական թվով հանգույցների վրա աշխատող խոշոր համակարգերում:
Թեթև պատկերացում, թե ինչ է քննարկվելու հետո՝ երկու գեներալների առաջադրանքԵկեք նայենք տաքացման համար .
Մենք ունենք երկու բանակ՝ կարմիր և սպիտակ։ Պաշարված քաղաքում տեղակայված են սպիտակ զորքերը: Կարմիր զորքերը՝ A1 և A2 գեներալների գլխավորությամբ, տեղակայված են քաղաքի երկու կողմերում։ Կարմրահերների խնդիրն է հարձակվել սպիտակ քաղաքի վրա և հաղթել: Սակայն յուրաքանչյուր կարմիր գեներալի բանակն առանձին-առանձին ավելի փոքր է, քան սպիտակների բանակը։
Կարմիրների հաղթական պայմանները՝ երկու գեներալներն էլ պետք է միաժամանակ գրոհեն, որպեսզի թվային առավելություն ունենան սպիտակների նկատմամբ։ Դրա համար A1 և A2 գեներալները պետք է համաձայնության գան միմյանց հետ: Եթե բոլորը հարձակվեն առանձին, ապա կարմրահերները կպարտվեն։
Համաձայնության հասնելու համար A1 և A2 գեներալները կարող են միմյանց մեսենջերներ ուղարկել սպիտակ քաղաքի տարածքով։ Սուրհանդակը կարող է հաջողությամբ հասնել դաշնակից գեներալի կամ կարող է որսալ թշնամու կողմից: Հարց. կա՞ կարմրահեր գեներալների միջև հաղորդակցության այնպիսի հաջորդականություն (A1-ից A2 մեսենջերներ ուղարկելու հաջորդականությունը և հակառակը A2-ից A1), որով նրանք երաշխավորված են համաձայնության գալու X ժամին հարձակման մասին: Ահա. երաշխիքները նշանակում են, որ երկու գեներալներն էլ կունենան միանշանակ հաստատում, որ դաշնակիցը (մեկ այլ գեներալ) անպայման հարձակվելու է նշանակված X ժամին։
Ենթադրենք, A1-ը մեսենջեր է ուղարկում A2-ին՝ «Եկեք հարձակվենք այսօր կեսգիշերին» հաղորդագրությունով: Գեներալ A1-ը չի կարող հարձակվել առանց գեներալ A2-ի հաստատման: Եթե A1-ի մեսենջերը ժամանել է, ապա գեներալ A2-ը հաստատում է ուղարկում հաղորդագրությամբ. «Այո, եկեք սպանենք սպիտակներին այսօր»: Բայց հիմա գեներալ A2-ը չգիտի՝ իր սուրհանդակը եկել է, թե ոչ, նա երաշխիք չունի՝ հարձակումը միաժամանակյա կլինի։ Այժմ General A2-ը կրկին հաստատման կարիք ունի։
Նրանց հաղորդակցության նկարագրությունը հետագայում բացահայտում է հետևյալը. անկախ նրանից, թե քանի հաղորդագրությունների ցիկլեր կան, ոչ մի կերպ չի կարելի երաշխավորել, որ երկու գեներալներն էլ ծանուցված են եղել իրենց հաղորդագրությունների ստացման մասին (ենթադրելով, որ մեսենջերից որևէ մեկը կարող է գաղտնալսվել):
Երկու գեներալների խնդիրը շատ պարզ բաշխված համակարգի հիանալի օրինակ է, որտեղ կան երկու անվստահելի հաղորդակցություններ ունեցող հանգույցներ: Սա նշանակում է, որ մենք 100% երաշխիք չունենք, որ դրանք համաժամանակացված են: Նմանատիպ խնդիրներ քննարկվում են միայն ավելի լայնածավալ հոդվածում ավելի ուշ:
Մենք ներկայացնում ենք բաշխված համակարգերի հայեցակարգը
Բաշխված համակարգը համակարգիչների խումբ է (այսուհետև դրանք կանվանենք հանգույցներ), որոնք կարող են փոխանակել հաղորդագրություններ: Յուրաքանչյուր առանձին հանգույց ինչ-որ ինքնավար էություն է: Հանգույցը կարող է ինքնուրույն մշակել առաջադրանքները, սակայն այլ հանգույցների հետ հաղորդակցվելու համար անհրաժեշտ է ուղարկել և ստանալ հաղորդագրություններ:
Թե կոնկրետ ինչպես են իրականացվում հաղորդագրությունները, ինչ արձանագրություններ են կիրառվում, սա մեզ չի հետաքրքրում այս համատեքստում։ Կարևոր է, որ բաշխված համակարգի հանգույցները կարողանան միմյանց հետ փոխանակել տվյալներ՝ ուղարկելով հաղորդագրություններ։
Սահմանումն ինքնին այնքան էլ բարդ չի թվում, բայց մենք պետք է հաշվի առնենք, որ բաշխված համակարգն ունի մի շարք ատրիբուտներ, որոնք կարևոր կլինեն մեզ համար:
Բաշխված համակարգերի հատկանիշներ
- Համադրություն - համակարգում միաժամանակյա կամ միաժամանակյա իրադարձությունների հավանականությունը: Ավելին, մենք կհամարենք իրադարձությունները, որոնք տեղի են ունենում երկու տարբեր հանգույցների վրա, որպես պոտենցիալ միաժամանակ, քանի դեռ չունենք այդ իրադարձությունների առաջացման հստակ կարգը: Բայց, որպես կանոն, մենք դա չունենք։
- Համաշխարհային ժամացույց չկա. Մենք չունենք իրադարձությունների հստակ հերթականություն՝ համաշխարհային ժամացույցի բացակայության պատճառով։ Մարդկանց սովորական աշխարհում մենք սովոր ենք այն փաստին, որ մենք ունենք ժամացույցներ և ժամանակ բացարձակապես: Ամեն ինչ փոխվում է, երբ խոսքը վերաբերում է բաշխված համակարգերին: Նույնիսկ գերճշգրիտ ատոմային ժամացույցները շեղվել են, և կարող են լինել իրավիճակներ, երբ մենք չենք կարող ասել, թե երկու իրադարձություններից որն է եղել առաջինը: Հետեւաբար, մենք էլ չենք կարող ժամանակի վրա հույս դնել։
- Համակարգի հանգույցների անկախ ձախողում. Կա ևս մեկ խնդիր՝ ինչ-որ բան կարող է սխալ լինել պարզապես այն պատճառով, որ մեր հանգույցները հավերժ չեն գործում: Կոշտ սկավառակը կարող է ձախողվել, ամպի վիրտուալ մեքենան կարող է վերագործարկվել, ցանցը կարող է թարթել, և հաղորդագրությունները կկորչեն: Ավելին, կարող են լինել իրավիճակներ, երբ հանգույցներն աշխատում են, բայց միևնույն ժամանակ աշխատում են համակարգի դեմ: Խնդիրների վերջին դասը նույնիսկ առանձին անուն ստացավ՝ խնդիր . Այս խնդրի հետ բաշխված համակարգի ամենահայտնի օրինակը Blockchain-ն է: Բայց այսօր մենք չենք դիտարկի խնդիրների այս հատուկ դասը: Մեզ կհետաքրքրեն այնպիսի իրավիճակներ, որոնց դեպքում պարզապես մեկ կամ մի քանի հանգույց կարող է ձախողվել:
- Հաղորդակցման մոդելներ (հաղորդագրության մոդելներ) հանգույցների միջև. Մենք արդեն հաստատել ենք, որ հանգույցները հաղորդակցվում են հաղորդագրությունների փոխանակման միջոցով: Գոյություն ունեն հաղորդագրությունների փոխանցման երկու հայտնի մոդելներ՝ համաժամանակյա և ասինխրոն:
Բաշխված համակարգերում հանգույցների միջև կապի մոդելներ
Սինխրոն մոդել – մենք հաստատ գիտենք, որ կա ժամանակի վերջավոր հայտնի դելտա, որի ընթացքում հաղորդագրությունը երաշխավորված է մի հանգույցից մյուսը հասնելու համար: Եթե այս ժամանակն անցել է, և հաղորդագրությունը չի հասել, ապա մենք կարող ենք հանգիստ ասել, որ հանգույցը ձախողվել է: Այս մոդելում մենք ունենք կանխատեսելի սպասման ժամանակներ:
Ասինխրոն մոդել – ասինխրոն մոդելներում մենք համարում ենք, որ սպասման ժամանակը վերջավոր է, բայց ժամանակի այնպիսի դելտա չկա, որից հետո մենք կարող ենք երաշխավորել, որ հանգույցը ձախողվել է: Նրանք. Հանգույցից հաղորդագրության սպասման ժամանակը կարող է կամայականորեն երկար լինել: Սա կարևոր սահմանում է, և մենք դրա մասին կխոսենք հետագա:
Համաձայնության հայեցակարգը բաշխված համակարգերում
Նախքան կոնսենսուսի հայեցակարգը պաշտոնապես սահմանելը, եկեք դիտարկենք մի իրավիճակի օրինակ, որտեղ մենք դրա կարիքն ունենք, մասնավորապես. Պետական մեքենայի կրկնօրինակում.
Մենք ունենք մի քանի բաշխված մատյան: Մենք կցանկանայինք, որ այն լինի հետևողական և պարունակի նույնական տվյալներ բաշխված համակարգի բոլոր հանգույցների վերաբերյալ: Երբ հանգույցներից մեկն իմանում է նոր արժեք, որը պատրաստվում է գրել տեղեկամատյանում, նրա խնդիրն է դառնում առաջարկել այդ արժեքը բոլոր մյուս հանգույցներին, որպեսզի գրանցամատյանը թարմացվի բոլոր հանգույցների վրա, և համակարգը տեղափոխվի նոր հետևողական վիճակ: Այս դեպքում կարևոր է, որ հանգույցները միմյանց հետ համաձայնվեն. բոլոր հանգույցները համաձայն են, որ առաջարկվող նոր արժեքը ճիշտ է, բոլոր հանգույցներն ընդունում են այս արժեքը, և միայն այս դեպքում բոլորը կարող են նոր արժեքը գրել գրանցամատյանում:
Այլ կերպ ասած՝ հանգույցներից ոչ մեկը չառարկեց, որ ավելի համապատասխան տեղեկատվություն ունի, և առաջարկվող արժեքը սխալ էր։ Հանգույցների միջև համաձայնությունը և մեկ ճիշտ ընդունված արժեքի վերաբերյալ համաձայնությունը բաշխված համակարգում կոնսենսուս է: Հաջորդը, մենք կխոսենք ալգորիթմների մասին, որոնք թույլ են տալիս բաշխված համակարգին երաշխավորել կոնսենսուսի հասնելու համար:
Ավելի պաշտոնական, մենք կարող ենք սահմանել կոնսենսուսի ալգորիթմը (կամ պարզապես կոնսենսուսի ալգորիթմը) որպես որոշակի ֆունկցիա, որը բաշխված համակարգը փոխանցում է A վիճակից B վիճակ: Ավելին, այս վիճակն ընդունվում է բոլոր հանգույցների կողմից, և բոլոր հանգույցները կարող են հաստատել այն: Ինչպես պարզվում է, այս առաջադրանքն ամենևին էլ այնքան տրիվիալ չէ, որքան թվում է առաջին հայացքից։
Համաձայնության ալգորիթմի հատկությունները
Համաձայնության ալգորիթմը պետք է ունենա երեք հատկություն, որպեսզի համակարգը շարունակի գոյություն ունենալ և որոշակի առաջընթաց ունենա վիճակից վիճակ տեղափոխվելու հարցում.
- Համաձայնություն - բոլոր ճիշտ գործող հանգույցները պետք է ունենան նույն արժեքը (հոդվածներում այս հատկությունը կոչվում է նաև անվտանգության հատկություն): Բոլոր հանգույցները, որոնք ներկայումս գործում են (չեն ձախողվել կամ չեն կորցրել կապը մյուսների հետ) պետք է համաձայնության գան և ընդունեն որոշ վերջնական ընդհանուր արժեք:
Այստեղ կարևոր է հասկանալ, որ բաշխված համակարգի հանգույցները, որոնք մենք դիտարկում ենք, ցանկանում են համաձայնել: Այսինքն, մենք հիմա խոսում ենք համակարգերի մասին, որոնցում ինչ-որ բան կարող է պարզապես ձախողվել (օրինակ, որոշ հանգույց ձախողվում է), բայց այս համակարգում հաստատ չկան հանգույցներ, որոնք միտումնավոր աշխատում են ուրիշների դեմ (բյուզանդական գեներալների առաջադրանքը): Այս հատկության շնորհիվ համակարգը մնում է հետևողական:
- ամբողջություն - եթե բոլոր ճիշտ աշխատող հանգույցներն առաջարկում են նույն արժեքը v, ինչը նշանակում է, որ յուրաքանչյուր ճիշտ գործող հանգույց պետք է ընդունի այս արժեքը v.
- Վախճան – բոլոր ճիշտ գործող հանգույցները, ի վերջո, կստանան որոշակի արժեք (կենդանության հատկություն), որը թույլ է տալիս ալգորիթմին առաջընթաց գրանցել համակարգում: Ճիշտ գործող յուրաքանչյուր հանգույց վաղ թե ուշ պետք է ընդունի վերջնական արժեքը և հաստատի այն. «Ինձ համար այս արժեքը ճիշտ է, ես համաձայն եմ ամբողջ համակարգի հետ»:
Համաձայնության ալգորիթմի աշխատանքի օրինակ
Մինչդեռ ալգորիթմի հատկությունները կարող են լիովին պարզ չլինել: Հետևաբար, մենք օրինակով կպատմենք, թե ինչ փուլերի միջով է անցնում ամենապարզ կոնսենսուսի ալգորիթմը համաժամանակյա հաղորդագրությունների մոդելով համակարգում, որտեղ բոլոր հանգույցները գործում են այնպես, ինչպես սպասվում էր, հաղորդագրությունները չեն կորչում և ոչինչ չի կոտրվում (դա իսկապես տեղի է ունենում):
- Ամեն ինչ սկսվում է ամուսնության առաջարկից (Առաջարկություն): Ենթադրենք, որ հաճախորդը միացել է «Հանգույց 1» կոչվող հանգույցին և սկսել է գործարք՝ հանգույցին փոխանցելով նոր արժեք՝ O: Այսուհետ մենք կանվանենք «Հանգույց 1»: առաջարկել. Որպես առաջարկող՝ «Հանգույց 1»-ն այժմ պետք է տեղեկացնի ամբողջ համակարգին, որ ունի թարմ տվյալներ և հաղորդագրություններ է ուղարկում մնացած բոլոր հանգույցներին. «O» իմաստը եկավ ինձ մոտ, և ես ուզում եմ այն գրել: Խնդրում ենք հաստատել, որ դուք նույնպես կգրանցեք «O» ձեր մատյանում»:
- Հաջորդ փուլը առաջարկվող արժեքի քվեարկությունն է (Voting): Ինչի համար է դա? Կարող է պատահել, որ այլ հանգույցներ ավելի թարմ տեղեկատվություն են ստացել, և նրանք ունեն տվյալներ նույն գործարքի վերաբերյալ:
Երբ «Node 1» հանգույցը ուղարկում է իր առաջարկը, մյուս հանգույցները ստուգում են իրենց տեղեկամատյանները այս իրադարձության վերաբերյալ տվյալների համար: Եթե հակասություններ չկան, հանգույցները հայտարարում են. «Այո, ես այլ տվյալներ չունեմ այս իրադարձության համար: «O» արժեքը մեզ արժանի ամենավերջին տեղեկատվությունն է»:Ցանկացած այլ դեպքում հանգույցները կարող են պատասխանել «Հանգույց 1»-ին. «Լսիր: Ես այս գործարքի վերաբերյալ ավելի նոր տվյալներ ունեմ: Ոչ թե «Օ», այլ ավելի լավ բան»:
Քվեարկության փուլում հանգույցները հանգում են որոշման՝ կա՛մ բոլորն ընդունում են նույն արժեքը, կա՛մ մեկը դեմ է քվեարկում՝ ցույց տալով, որ ավելի թարմ տվյալներ ունի։
- Եթե քվեարկության փուլը հաջող էր, և բոլորը կողմ էին, ապա համակարգը տեղափոխվում է նոր փուլ՝ արժեքի ընդունում։ «Հանգույց 1»-ը հավաքում է այլ հանգույցներից ստացված բոլոր պատասխանները և հայտնում. «Բոլորը համաձայնել են «O» արժեքի շուրջ: Հիմա ես պաշտոնապես հայտարարում եմ, որ «Օ»-ն մեր նոր իմաստն է, նույնը բոլորի համար: Գրեք այն ձեր փոքրիկ գրքում, մի մոռացեք: Գրի՛ր այն քո մատյանում»։
- Մնացած հանգույցները ուղարկում են հաստատում (Ընդունված), որ նրանք գրել են «O» արժեքը, այս ընթացքում ոչ մի նոր բան չի ստացվել (մի տեսակ երկփուլի կատարում): Այս նշանակալի իրադարձությունից հետո մենք համարում ենք, որ բաշխված գործարքն ավարտված է։
Այսպիսով, կոնսենսուսի ալգորիթմը պարզ դեպքում բաղկացած է չորս քայլերից՝ առաջարկել, քվեարկել (քվեարկել), ընդունել (ընդունել), հաստատել ընդունումը (ընդունվել):
Եթե ինչ-որ քայլում մենք չկարողացանք համաձայնության գալ, ապա ալգորիթմը նորից սկսվում է՝ հաշվի առնելով այն հանգույցների տրամադրած տեղեկատվությունը, որոնք հրաժարվել են հաստատել առաջարկվող արժեքը։
Համաձայնության ալգորիթմ ասինխրոն համակարգում
Մինչ այս ամեն ինչ հարթ էր, քանի որ մենք խոսում էինք սինխրոն հաղորդագրությունների մոդելի մասին։ Բայց մենք գիտենք, որ ժամանակակից աշխարհում մենք սովոր ենք ամեն ինչ անել ասինխրոն: Ինչպե՞ս է գործում նմանատիպ ալգորիթմը ասինխրոն հաղորդագրությունների մոդելով համակարգում, որտեղ մենք կարծում ենք, որ հանգույցից պատասխանի սպասման ժամանակը կարող է կամայականորեն երկար լինել (ի դեպ, հանգույցի ձախողումը կարելի է համարել նաև որպես օրինակ, երբ հանգույցը կարող է կամայականորեն երկար ժամանակ արձագանքել):
Այժմ, երբ մենք գիտենք, թե ինչպես է սկզբունքորեն աշխատում կոնսենսուսի ալգորիթմը, հարց է այն հետաքրքրասեր ընթերցողների համար, ովքեր հասել են դրան. ասինխրոն հաղորդագրության մոդելով N հանգույցների համակարգում քանի հանգույց կարող է ձախողվել, որպեսզի համակարգը դեռ կարողանա հասնել կոնսենսուսի:
Ճիշտ պատասխանն ու հիմնավորումը սփոյլերի հետևում են։Ճիշտ պատասխան: 0. Եթե ասինխրոն համակարգում նույնիսկ մեկ հանգույց ձախողվի, համակարգը չի կարողանա կոնսենսուսի հասնել: Այս պնդումը ապացուցված է որոշակի շրջանակներում հայտնի FLP թեորեմում (1985, Fischer, Lynch, Paterson, հղում հոդվածի վերջում բնօրինակին). «Բաշխված կոնսենսուսի հասնելու անհնարինությունը, եթե առնվազն մեկ հանգույց ձախողվի »:
Տղերք, ուրեմն մենք խնդիր ունենք, սովոր ենք, որ ամեն ինչ ասինխրոն լինի։ Եվ ահա այն. Ինչպե՞ս շարունակել ապրել:
Մենք ընդամենը խոսում էինք տեսությունից, մաթեմատիկայից։ Ի՞նչ է նշանակում «համաձայնություն ձեռք բերելը»՝ մաթեմատիկական լեզվից թարգմանելով մերը՝ ճարտարագիտության: Սա նշանակում է, որ «միշտ չի կարելի հասնել», այսինքն. Կա դեպք, երբ կոնսենսուսը հնարավոր չէ ձեռք բերել։ Սա ի՞նչ դեպք է։
Սա հենց վերը նկարագրված կենդանի հատկության խախտումն է։ Մենք չունենք ընդհանուր համաձայնություն, և համակարգը չի կարող առաջընթաց ունենալ (չի կարող ավարտվել վերջավոր ժամանակում) այն դեպքում, երբ մենք չունենք պատասխան բոլոր հանգույցներից։ Քանի որ ասինխրոն համակարգում մենք չունենք կանխատեսելի արձագանքման ժամանակ, և մենք չենք կարող իմանալ, թե արդյոք հանգույցը խափանվել է, թե պարզապես երկար ժամանակ է պահանջվում արձագանքելու համար:
Բայց գործնականում մենք կարող ենք լուծում գտնել։ Թող մեր ալգորիթմը կարողանա երկար աշխատել ձախողումների դեպքում (պոտենցիալ այն կարող է անվերջ աշխատել): Բայց շատ իրավիճակներում, երբ հանգույցների մեծ մասը ճիշտ է գործում, մենք կունենանք առաջընթաց համակարգում:
Գործնականում մենք գործ ունենք մասամբ սինխրոն հաղորդակցման մոդելների հետ: Մասնակի սինխրոնիան հասկացվում է հետևյալ կերպ. ընդհանուր դեպքում մենք ունենք ասինխրոն մոդել, սակայն ժամանակի որոշակի կետի «գլոբալ կայունացման ժամանակի» որոշակի հայեցակարգը պաշտոնապես ներկայացվում է:
Ժամանակի այս պահը կարող է երկար չգալ, բայց այն պետք է գա մի օր: Վիրտուալ զարթուցիչը կհնչի, և այդ պահից մենք կարող ենք կանխատեսել, թե որ ժամի դելտան կհասնի հաղորդագրությունները։ Այս պահից համակարգը ասինխրոնից վերածվում է սինխրոնի: Գործնականում մենք գործ ունենք հենց այդպիսի համակարգերի հետ։
Paxos ալգորիթմը լուծում է կոնսենսուսի խնդիրները
Ալգորիթմների ընտանիք է, որը լուծում է մասնակի համաժամանակյա համակարգերի կոնսենսուսի խնդիրը՝ որոշ հանգույցների ձախողման հնարավորության դեպքում: Paxos-ի հեղինակն է . Նա առաջարկել է ալգորիթմի գոյության և ճշգրտության պաշտոնական ապացույց 1989 թ.
Բայց ապացույցը պարզվեց, որ հեռու է տրիվիալ լինելուց։ Առաջին հրատարակությունը թողարկվել է միայն 1998 թվականին (33 էջ)՝ նկարագրելով ալգորիթմը։ Ինչպես պարզվեց, դա չափազանց դժվար էր հասկանալ, և 2001-ին հրապարակվեց հոդվածի բացատրությունը, որը 14 էջ էր պահանջում։ Հրապարակումների ծավալը տրված է ցույց տալու համար, որ իրականում կոնսենսուսի խնդիրն ամենևին էլ պարզ չէ, և նման ալգորիթմների հետևում թաքնված է ամենախելացի մարդկանց հսկայական աշխատանք։
Հետաքրքիր է, որ ինքը՝ Լեսլի Լեմպորտը, իր դասախոսության մեջ նշել է, որ երկրորդ բացատրական հոդվածում կա մեկ պնդում, մեկ տող (նա չի նշել, թե որն է), որը կարելի է տարբեր կերպ մեկնաբանել։ Եվ դրա պատճառով Paxos-ի ժամանակակից ներդրումների մեծ մասը լիովին ճիշտ չեն աշխատում:
Paxos-ի աշխատանքի մանրամասն վերլուծությունը կպահանջի մեկից ավելի հոդված, ուստի ես կփորձեմ շատ հակիրճ փոխանցել ալգորիթմի հիմնական գաղափարը: Իմ հոդվածի վերջում գտնվող հղումներում դուք կգտնեք նյութեր այս թեմայի հետագա խորասուզման համար:
Դերեր Պաքսոսում
Paxos ալգորիթմն ունի դերերի հայեցակարգ: Դիտարկենք երեք հիմնական (կան փոփոխություններ լրացուցիչ դերերով).
- Առաջարկողներ (տերմինները կարող են օգտագործվել նաև՝ առաջնորդներ կամ համակարգողներ). Սրանք այն տղաներն են, ովքեր օգտատերից սովորում են ինչ-որ նոր արժեքի մասին և ստանձնում առաջնորդի դերը: Նրանց խնդիրն է սկսել նոր արժեքի համար առաջարկների փուլ և համակարգել հանգույցների հետագա գործողությունները: Ավելին, Paxos-ը թույլ է տալիս որոշակի իրավիճակներում մի քանի առաջնորդների ներկայություն։
- Ընդունողներ (Ընտրողներ). Սրանք հանգույցներ են, որոնք քվեարկում են որոշակի արժեք ընդունելու կամ մերժելու համար: Նրանց դերը շատ կարևոր է, քանի որ նրանցից է կախված որոշումը՝ ինչ վիճակի կգնա (կամ չի գնա) համակարգը կոնսենսուսի ալգորիթմի հաջորդ փուլից հետո։
- Սովորողները. Հանգույցներ, որոնք պարզապես ընդունում և գրում են նոր ընդունված արժեքը, երբ համակարգի վիճակը փոխվել է: Նրանք որոշումներ չեն կայացնում, նրանք պարզապես ստանում են տվյալները և կարող են դրանք տալ վերջնական օգտագործողին:
Մեկ հանգույցը կարող է միավորել մի քանի դեր տարբեր իրավիճակներում:
Քվորում հասկացությունը
Մենք ենթադրում ենք, որ ունենք համակարգ N հանգույցներ Եվ նրանցից առավելագույնը F հանգույցները կարող են ձախողվել: Եթե F հանգույցները ձախողվեն, ապա մենք պետք է ունենանք առնվազն 2F+1 ընդունող հանգույցներ.
Սա անհրաժեշտ է, որպեսզի մենք միշտ ունենանք ճիշտ աշխատող «լավ» հանգույցների մեծամասնությունը, նույնիսկ ամենավատ իրավիճակում: Այն է F+1 «լավ» հանգույցները, որոնք համաձայնվել են, և վերջնական արժեքը կընդունվի: Հակառակ դեպքում, կարող է լինել մի իրավիճակ, երբ մեր տարբեր տեղական խմբերը տարբեր իմաստներ ստանան և չկարողանան պայմանավորվել միմյանց միջև: Ուստի ձայնը շահելու համար մեզ անհրաժեշտ է բացարձակ մեծամասնություն։
Ընդհանուր գաղափարը, թե ինչպես է աշխատում Paxos կոնսենսուսի ալգորիթմը
Paxos ալգորիթմը ներառում է երկու մեծ փուլ, որոնք իրենց հերթին բաժանվում են երկու փուլի՝ յուրաքանչյուրը.
- Փուլ 1ա. Պատրաստել. Նախապատրաստական փուլում առաջնորդը (առաջարկողը) տեղեկացնում է բոլոր հանգույցներին. «Մենք սկսում ենք քվեարկության նոր փուլ: Մեզ նոր փուլ է սպասվում. Այս փուլի թիվը n է: Հիմա կսկսենք քվեարկությունը»։ Առայժմ այն պարզապես հաղորդում է նոր ցիկլի սկիզբը, բայց չի հայտնում նոր արժեք: Այս փուլի խնդիրն է նախաձեռնել նոր փուլ և բոլորին տեղեկացնել դրա եզակի թվի մասին: Կլոր համարը կարևոր է, այն պետք է լինի ավելի մեծ արժեք, քան նախորդ բոլոր առաջատարների քվեարկության բոլոր թվերը: Քանի որ կլոր թվի շնորհիվ է, որ համակարգի մյուս հանգույցները կհասկանան, թե որքան թարմ են առաջատարի տվյալները: Հավանական է, որ մյուս հանգույցներն արդեն ունեն քվեարկության արդյունքներ շատ ավելի ուշ փուլերից և պարզապես առաջնորդին կասեն, որ նա հետ է մնում ժամանակից:
- Փուլ 1բ. Խոստում. Երբ ընդունող հանգույցները ստացան քվեարկության նոր փուլի համարը, հնարավոր է երկու արդյունք.
- Նոր քվեարկության n թիվը ավելի մեծ է, քան նախորդ քվեարկության թիվը, որին մասնակցել է ընդունողը: Այնուհետ ընդունողը խոստում է ուղարկում ղեկավարին, որ n-ից ցածր թվով այլևս չի մասնակցի քվեարկությանը։ Եթե ընդունողն արդեն քվեարկել է ինչ-որ բանի օգտին (այսինքն՝ նա արդեն ընդունել է ինչ-որ արժեք երկրորդ փուլում), ապա իր խոստմանը կցում է ընդունված արժեքը և ձայների քանակը, որին մասնակցել է։
- Հակառակ դեպքում, եթե ընդունողն արդեն գիտի ավելի բարձր թվով քվեարկության մասին, կարող է պարզապես անտեսել նախապատրաստական քայլը և չպատասխանել առաջատարին։
- Փուլ 2ա. Ընդունել. Առաջնորդը պետք է սպասի պատասխանի քվորումից (համակարգի հանգույցների մեծամասնությունը) և, եթե ստացվի անհրաժեշտ քանակի պատասխաններ, ապա նա ունի իրադարձությունների զարգացման երկու տարբերակ.
- Ընդունողներից ոմանք ուղարկեցին արժեքներ, որոնց օգտին արդեն քվեարկել էին: Այս դեպքում առաջատարը առավելագույն թվով քվեարկությունից ընտրում է արժեքը: Եկեք այս արժեքը կոչենք x, և այն ուղարկում է հաղորդագրություն բոլոր հանգույցներին, ինչպիսիք են. «Ընդունել (n, x)», որտեղ առաջին արժեքը քվեարկության թիվն է իր սեփական «Առաջարկի» քայլից, իսկ երկրորդ արժեքը այն է, ինչի համար հավաքվել են բոլորը, այսինքն. արժեքը, որի համար մենք իրականում քվեարկում ենք:
- Եթե ընդունողներից ոչ մեկը արժեք չի ուղարկել, այլ ուղղակի խոստացել է քվեարկել այս փուլում, առաջնորդը կարող է հրավիրել նրանց քվեարկելու իրենց արժեքի համար, այն արժեքի համար, որի համար նա առաջին հերթին դարձավ առաջնորդ։ Եկեք այն անվանենք y. Այն հաղորդագրություն է ուղարկում բոլոր հանգույցներին, ինչպիսիք են. «Ընդունել (n, y)», նախորդ արդյունքի նման:
- Փուլ 2b. Ընդունված. Այնուհետև, ընդունող հանգույցները, ստանալով «Ընդունել (...)» հաղորդագրությունը առաջնորդից, համաձայնում են դրա հետ (հաստատում ուղարկում են բոլոր հանգույցներին, որ նրանք համաձայն են նոր արժեքի հետ) միայն այն դեպքում, եթե նրանք չեն խոստացել որոշ (մյուս)): ղեկավարը կլոր համարով մասնակցել քվեարկությանը n' > n, հակառակ դեպքում նրանք անտեսում են հաստատման հարցումը։
Եթե հանգույցների մեծամասնությունը պատասխանել է առաջատարին, և բոլորը հաստատել են նոր արժեքը, ապա նոր արժեքը համարվում է ընդունված։ Ուռա՜ Եթե մեծամասնությունը չի հասնում կամ կան հանգույցներ, որոնք հրաժարվել են ընդունել նոր արժեքը, ապա ամեն ինչ սկսվում է նորից:
Այսպես է աշխատում Paxos ալգորիթմը։ Այս փուլերից յուրաքանչյուրն ունի բազմաթիվ նրբություններ, մենք գործնականում չենք դիտարկել տարբեր տեսակի ձախողումներ, բազմաթիվ առաջնորդների խնդիրներ և շատ ավելին, բայց այս հոդվածի նպատակը միայն ընթերցողին բարձր մակարդակով բաշխված հաշվարկների աշխարհին ծանոթացնելն է:
Հարկ է նաև նշել, որ Paxos-ը միակը չէ իր տեսակի մեջ, կան նաև այլ ալգորիթմներ, օրինակ. , բայց սա մեկ այլ հոդվածի թեմա է։
Հղումներ հետագա ուսումնասիրության համար նախատեսված նյութերին
Սկսնակ մակարդակ.
- , Preethi Kasireddy, բլոգի հոդված Medium-ում
- , Ադի Կանչերլա, բլոգային հոդված Medium-ում
- , Ittai Abraham, բլոգ
- , Ittai Abraham, բլոգի հոդված
Լեսլի Լեմպորտի մակարդակը.
- , Ֆիշեր, Լինչ և Պատերսոն, հետազոտական աշխատանք, 1985 թ
- , Լեսլի Լամպորտ, հետազոտական աշխատանք, 1998 թ
- , Լեսլի Լամպորտ, հետազոտական աշխատանք, 2001 թ
Source: www.habr.com