Сонымен, елестетіп көрейік. Бөлмеде құлыптаулы 5 мысық бар, иесін ояту үшін барлығы өзара келісіп алуы керек, өйткені есікті тек бесеуі сүйеніп ашады. Егер мысықтардың бірі Шредингердің мысығы болса, ал басқа мысықтар оның шешімі туралы білмесе, «Олар мұны қалай істей алады?» Деген сұрақ туындайды.
Бұл мақалада мен сіздерге бөлінген жүйелер әлемінің теориялық құрамдас бөлігі және олардың жұмыс істеу принциптері туралы қарапайым түрде айтып беремін. Мен сондай-ақ Paxos негізінде жатқан негізгі идеяны үстірт түрде қарастырамын.
Әзірлеушілер бұлттық инфрақұрылымдарды, әртүрлі дерекқорларды пайдаланғанда және көптеген түйіндердің кластерлерінде жұмыс істегенде, олар деректердің толық, қауіпсіз және әрқашан қолжетімді болатынына сенімді. Бірақ кепілдіктер қайда?
Негізінде, бізде бар кепілдіктер жеткізушілердің кепілдіктері болып табылады. Олар құжаттамада былай сипатталған: «Бұл қызмет өте сенімді, оның SLA берілген, уайымдамаңыз, бәрі сіз күткендей таратылады».
Біз ең жақсыға сенеміз, өйткені үлкен компаниялардың ақылды жігіттері бәрі жақсы болады деп сендірді. Біз сұрақ қоймаймыз: неге бұл мүлдем жұмыс істей алады? Мұндай жүйелердің дұрыс жұмыс істеуі үшін қандай да бір ресми негіздеме бар ма?
Мен жақында бардым және бұл тақырып өте шабыттанды. Мектептегі лекциялар компьютерлік жүйелермен байланысты емес, есептеу сабақтарына көбірек ұқсайтын. Бірақ біз күнделікті, тіпті білмей де қолданатын ең маңызды алгоритмдер дәл осылай дәлелденді.
Қазіргі таратылған жүйелердің көпшілігі Paxos консенсус алгоритмін және оның әртүрлі модификацияларын пайдаланады. Ең қызығы, бұл алгоритмнің негізділігін және бар болу мүмкіндігін қарапайым қағаз бен қаламмен дәлелдеуге болады. Іс жүзінде алгоритм бұлттағы түйіндердің үлкен санында жұмыс істейтін үлкен жүйелерде қолданылады.
Бұдан әрі талқыланатын нәрсенің жеңіл суреті: екі генералдың тапсырмасыКеліңіздер, жылынуды қарастырайық .
Біздің екі армиямыз бар - қызыл және ақ. Ақ әскерлер қоршауда қалған қалада орналасқан. А1 және А2 генералдары басқарған қызыл әскерлер қаланың екі жағында орналасқан. Қызылбастардың міндеті - ақ қалаға шабуыл жасап, жеңіске жету. Дегенмен, әрбір қызыл генералдың әскері ақ әскерден аз.
Қызылдар үшін жеңіс шарттары: ақтардан сан жағынан артықшылыққа ие болу үшін екі генерал да бір мезгілде шабуыл жасауы керек. Ол үшін А1 және А2 генералдары бір-бірімен келісімге келулері керек. Әркім жеке-жеке шабуылдаса, қызылдар жеңіледі.
Келісімге келу үшін А1 және А2 генералдары ақ қала аумағы арқылы бір-біріне хабаршылар жібере алады. Хабаршы одақтас генералға сәтті жетуі мүмкін немесе жау оны ұстап алуы мүмкін. Сұрақ: қызыл шашты генералдар арасында осындай байланыс тізбегі бар ма (шабармандарды А1-ден А2-ге және керісінше А2-ден А1-ге жіберу тізбегі), олар X сағатында шабуыл туралы келісуге кепілдік береді. Мұнда, кепілдіктер екі генералдың да одақтастың (басқа генералдың) белгіленген X уақытында міндетті түрде шабуыл жасайтынын біржақты растауын білдіреді.
A1 A2-ге хабаршы жіберді делік: «Бүгін түн ортасында шабуыл жасайық!» General A1 жалпы A2 растауынсыз шабуыл жасай алмайды. Егер A1 хабаршысы келсе, генерал A2: «Иә, бүгін ақтарды өлтірейік» деген хабарламамен растауды жібереді. Бірақ қазір генерал А2 оның хабаршысының келген-келмегенін білмейді, шабуылдың бір мезгілде болатынына кепілдік жоқ. Енді General A2 қайтадан растауды қажет етеді.
Егер олардың байланысын әрі қарай сипаттайтын болсақ, онда қанша хабарлама алмасу циклі болса да, екі генералдың да хабарларын алғанына кепілдік берудің ешбір жолы жоқ екені белгілі болады (егер мессенджердің де біреуін ұстап алу мүмкін болса).
Екі генерал мәселесі - сенімсіз байланысы бар екі түйін бар өте қарапайым үлестірілген жүйенің тамаша суреті. Бұл олардың синхрондалғанына бізде 100% кепілдік жоқ дегенді білдіреді. Ұқсас мәселелер тек кейінірек мақалада кеңірек талқыланады.
Біз үлестірілген жүйелер түсінігін енгіземіз
Бөлінген жүйе – бұл хабарламалармен алмасуға болатын компьютерлер тобы (бұдан әрі оларды түйіндер деп атаймыз). Әрбір жеке түйін автономды нысанның қандай да бір түрі болып табылады. Түйін тапсырмаларды өздігінен өңдей алады, бірақ басқа түйіндермен байланысу үшін хабарламаларды жіберу және қабылдау қажет.
Хабарламалар қалай нақты орындалады, қандай хаттамалар қолданылады - бұл контексте бізді қызықтырмайды. Бөлінген жүйенің түйіндері хабарламалар жіберу арқылы бір-бірімен деректер алмаса алуы маңызды.
Анықтаманың өзі өте күрделі болып көрінбейді, бірақ біз үлестірілген жүйенің біз үшін маңызды болатын бірқатар атрибуттары бар екенін ескеруіміз керек.
Бөлінген жүйелердің атрибуттары
- Біртектілік – жүйеде бір мезгілде немесе бір мезгілде орын алатын оқиғалардың мүмкіндігі. Сонымен қатар, біз екі түрлі түйінде орын алатын оқиғаларды, егер бізде бұл оқиғалардың нақты орын алу реті болмаса, бір мезгілде болуы мүмкін деп қарастырамыз. Бірақ, әдетте, бізде ол жоқ.
- Жаһандық сағат жоқ. Бізде жаһандық сағаттың жоқтығынан оқиғалардың нақты реті жоқ. Адамдардың қарапайым әлемінде бізде сағаттар мен уақыт мүлдем бар екеніне үйреніп қалғанбыз. Бөлінген жүйелерге келгенде бәрі өзгереді. Тіпті өте дәл атомдық сағаттарда дрейф бар және екі оқиғаның қайсысы бірінші болғанын айта алмайтын жағдайлар болуы мүмкін. Сондықтан біз де уақытқа сене алмаймыз.
- Жүйе түйіндерінің тәуелсіз істен шығуы. Тағы бір мәселе бар: бірдеңе дұрыс болмауы мүмкін, өйткені біздің түйіндеріміз мәңгілікке созылмайды. Қатты диск істен шығуы мүмкін, бұлттағы виртуалды машина қайта жүктелуі мүмкін, желі жыпылықтауы және хабарлар жоғалуы мүмкін. Сонымен қатар, түйіндер жұмыс істейтін, бірақ сонымен бірге жүйеге қарсы жұмыс істейтін жағдайлар болуы мүмкін. Есептердің соңғы класы тіпті жеке атау алды: мәселе . Бұл мәселе бар таратылған жүйенің ең танымал мысалы - Blockchain. Бірақ бүгін біз проблемалардың бұл ерекше класын қарастырмаймыз. Бізді бір немесе бірнеше түйін сәтсіздікке ұшырауы мүмкін жағдайлар қызықтырады.
- Түйіндер арасындағы байланыс үлгілері (хабарлама үлгілері).. Біз түйіндердің хабар алмасу арқылы байланысатынын анықтадық. Хабар алмасудың екі танымал моделі бар: синхронды және асинхронды.
Бөлінген жүйелердегі түйіндер арасындағы байланыстың модельдері
Синхронды модель – хабардың бір түйіннен екіншісіне жетуіне кепілдік берілген уақыттың белгілі дельтасы бар екенін біз анық білеміз. Егер бұл уақыт өтіп кетсе және хабарлама келмесе, түйін сәтсіз аяқталды деп сенімді түрде айта аламыз. Бұл модельде күтуге болатын күту уақыты бар.
Асинхронды модель – асинхронды модельдерде күту уақыты шекті деп есептейміз, бірақ түйіннің сәтсіз болғанына кепілдік бере алатындай уақыт дельтасы жоқ. Анау. Түйіннен хабарламаны күту уақыты ерікті түрде ұзақ болуы мүмкін. Бұл маңызды анықтама, біз бұл туралы әрі қарай айтатын боламыз.
Бөлінген жүйелердегі консенсус түсінігі
Консенсус ұғымын ресми түрде анықтамас бұрын, бізге қажет жағдайдың мысалын қарастырайық, атап айтқанда - Күй машинасының репликациясы.
Бізде таратылған журнал бар. Біз оның дәйекті болуын және таратылған жүйенің барлық түйіндерінде бірдей деректер болуын қалаймыз. Түйіндердің бірі журналға жазатын жаңа мәнді білгенде, оның міндеті журнал барлық түйіндерде жаңартылып, жүйе жаңа тұрақты күйге көшуі үшін осы мәнді барлық басқа түйіндерге ұсынуға айналады. Бұл жағдайда түйіндердің өзара келісуі маңызды: барлық түйіндер ұсынылған жаңа мәннің дұрыс екеніне келіседі, барлық түйіндер бұл мәнді қабылдайды және тек осы жағдайда ғана әркім журналға жаңа мән жаза алады.
Басқаша айтқанда: түйіндердің ешқайсысы оның маңыздырақ ақпараты бар екеніне қарсылық білдірмеді және ұсынылған мән дұрыс емес. Түйіндер арасындағы келісім және бір дұрыс қабылданған мән туралы келісім таратылған жүйеде консенсус болып табылады. Әрі қарай, бөлінген жүйенің консенсусқа жетуіне кепілдік беретін алгоритмдер туралы айтатын боламыз.
Ресми түрде біз консенсус алгоритмін (немесе жай ғана консенсус алгоритмін) бөлінген жүйені А күйінен В күйіне тасымалдайтын белгілі бір функция ретінде анықтауға болады. Оның үстіне бұл күйді барлық түйіндер қабылдайды және барлық түйіндер оны растай алады. Белгілі болғандай, бұл тапсырма бірінші көзқараста көрінетіндей тривиальды емес.
Консенсус алгоритмінің қасиеттері
Жүйенің өмір сүруін жалғастыру және күйден күйге өтуде белгілі бір прогреске жету үшін консенсус алгоритмінің үш қасиеті болуы керек:
- келісім – барлық дұрыс жұмыс істейтін түйіндер бірдей мәнді қабылдауы керек (мақалаларда бұл сипат қауіпсіздік қасиеті деп те аталады). Қазіргі уақытта жұмыс істеп тұрған барлық түйіндер (басқалармен байланысы үзілмеген немесе жоғалмаған) келісімге келіп, кейбір соңғы ортақ мәнді қабылдауы керек.
Бұл жерде біз қарастырып жатқан бөлінген жүйедегі түйіндер келіскісі келетінін түсіну маңызды. Яғни, біз қазір бірдеңе жай ғана сәтсіздікке ұшырауы мүмкін жүйелер туралы айтып отырмыз (мысалы, кейбір түйін сәтсіздікке ұшырайды), бірақ бұл жүйеде басқаларға қарсы әдейі жұмыс істейтін түйіндер міндетті түрде жоқ (Византия генералдарының міндеті). Бұл қасиетке байланысты жүйе тұрақты болып қалады.
- Адалдық — егер барлық дұрыс жұмыс істейтін түйіндер бірдей мәнді ұсынса v, яғни әрбір дұрыс жұмыс істейтін түйін осы мәнді қабылдауы керек v.
- Тоқтату – барлық дұрыс жұмыс істейтін түйіндер, сайып келгенде, алгоритмге жүйеде ілгерілеуге мүмкіндік беретін белгілі бір мәнді (өмірлік қасиеті) қабылдайды. Әрбір жеке дұрыс жұмыс істейтін түйін ерте ме, кеш пе соңғы мәнді қабылдауы және оны растауы керек: «Мен үшін бұл мән дұрыс, мен бүкіл жүйемен келісемін».
Консенсус алгоритмі қалай жұмыс істейтініне мысал
Алгоритмнің қасиеттері толығымен анық болмауы мүмкін. Сондықтан біз синхронды хабар алмасу моделі бар жүйеде ең қарапайым консенсус алгоритмі қандай кезеңдерден өтетінін мысалмен көрсетеміз, онда барлық түйіндер күткендей жұмыс істейді, хабарламалар жоғалмайды және ештеңе үзілмейді (бұл шынымен бола ма?).
- Барлығы некеге тұру туралы ұсыныстан басталады (Ұсыныс). Клиент «1-түйін» деп аталатын түйінге қосылып, транзакцияны бастады делік, түйінге жаңа мәнді – О береді. Бұдан былай «1-түйін» деп атаймыз. ұсыну. Ұсынушы ретінде «1-түйін» енді бүкіл жүйеге оның жаңа деректері бар екенін хабарлауы керек және ол барлық басқа түйіндерге хабарламалар жібереді: «Қараңыз! Маған «О» мағынасы келді, мен оны жазғым келеді! Сондай-ақ журналға «O» деп жазатыныңызды растаңыз.»
- Келесі кезең – ұсынылған мәнге дауыс беру (Дауыс беру). Ол не үшін? Басқа түйіндер соңғы ақпаратты алған және оларда бірдей транзакция туралы деректер болуы мүмкін.
«1-түйін» түйіні өз ұсынысын жіберген кезде, басқа түйіндер осы оқиға бойынша деректер үшін журналдарын тексереді. Егер қайшылықтар болмаса, түйіндер хабарлайды: «Иә, менде бұл оқиғаға қатысты басқа деректер жоқ. «O» мәні – бізге лайық соңғы ақпарат».Кез келген басқа жағдайда түйіндер «1-түйінге» жауап бере алады: «Тыңдаңыз! Менде бұл транзакция туралы соңғы деректер бар. «О» емес, жақсырақ нәрсе».
Дауыс беру кезеңінде түйіндер бір шешімге келеді: не бәрі бірдей мәнді қабылдайды, не олардың біреуі қарсы дауыс береді, бұл оның соңғы деректері бар екенін көрсетеді.
- Дауыс беру кезеңі сәтті өтіп, барлығы қолдаса, жүйе жаңа кезеңге – Құнды қабылдауға көшеді. «1-түйін» басқа түйіндерден барлық жауаптарды жинайды және есеп береді: «Барлығы «O» мәніне келісті! Енді мен ресми түрде мәлімдеймін: «О» біздің жаңа мағынамыз, барлығына бірдей! Оны кішкентай кітабыңызға жазыңыз, ұмытпаңыз. Оны журналыңызға жазып алыңыз!»
- Қалған түйіндер «O» мәнін жазып алғаны туралы растауды (Қабылданды) жібереді; осы уақыт ішінде жаңа ештеңе келген жоқ (екі фазалық міндеттеменің бір түрі). Осы маңызды оқиғадан кейін біз таратылған транзакция аяқталды деп есептейміз.
Осылайша, консенсус алгоритмі қарапайым жағдайда төрт қадамнан тұрады: ұсыну, дауыс беру (дауыс беру), қабылдау (қабылдау), қабылдауды растау (қабылдау).
Егер қандай да бір қадамда біз келісімге келе алмасақ, онда алгоритм ұсынылған мәнді растаудан бас тартқан түйіндер ұсынған ақпаратты ескере отырып, қайтадан басталады.
Асинхронды жүйедегі консенсус алгоритмі
Бұған дейін бәрі тегіс болды, өйткені біз синхронды хабар алмасу моделі туралы айтып отырмыз. Бірақ біз қазіргі әлемде бәрін асинхронды түрде жасауға дағдыланғанымызды білеміз. Ұқсас алгоритм асинхронды хабар алмасу моделі бар жүйеде қалай жұмыс істейді, онда түйіннен жауап күту уақыты ерікті түрде ұзақ болуы мүмкін деп санаймыз (айтпақшы, түйіннің істен шығуын да мысал ретінде қарастыруға болады. түйін ұзақ уақыт бойы жауап бере алады).
Енді біз консенсус алгоритмі қалай жұмыс істейтінін білетін болсақ, оны осы уақытқа дейін жасаған ізденімпаз оқырмандар үшін сұрақ: жүйе әлі де консенсусқа қол жеткізу үшін асинхронды хабарлама үлгісі бар N түйін жүйесіндегі қанша түйін сәтсіздікке ұшырауы мүмкін?
Дұрыс жауап пен негіздеме спойлердің артында.Дұрыс жауап: 0. Асинхронды жүйеде тіпті бір түйін сәтсіз болса, жүйе консенсусқа қол жеткізе алмайды. Бұл тұжырым FLP теоремасында дәлелденген, белгілі бір ортада белгілі (1985, Фишер, Линч, Патерсон, мақаланың соңындағы түпнұсқаға сілтеме): «Егер кем дегенде бір түйін сәтсіз болса, бөлінген консенсусқа қол жеткізу мүмкін еместігі. .”
Балалар, онда бізде бір мәселе бар, біз барлығына асинхронды болып үйреніп қалдық. Ал міне. Қалай өмір сүруді жалғастыру керек?
Біз тек теория туралы, математика туралы сөйлестік. Математикалық тілден біздің тілімізге – инженерияға аударғанда «консенсусқа қол жеткізу мүмкін емес» деген нені білдіреді? Бұл «әрқашан қол жеткізу мүмкін емес» дегенді білдіреді, яғни. Консенсусқа қол жеткізу мүмкін емес жағдай бар. Бұл қандай жағдай?
Бұл дәл жоғарыда сипатталған liveness қасиетінің бұзылуы. Бізде ортақ келісім жоқ және бізде барлық түйіндерден жауап болмаған жағдайда жүйеде ілгерілеушілік болмайды (шектелген уақытта аяқталмайды). Өйткені асинхронды жүйеде бізде болжамды жауап беру уақыты жоқ және біз түйіннің бұзылғанын немесе жауап беру үшін көп уақытты қажет ететінін біле алмаймыз.
Бірақ іс жүзінде біз шешімін таба аламыз. Біздің алгоритм сәтсіздікке ұшыраған жағдайда ұзақ уақыт жұмыс істей алатын болсын (ол шексіз жұмыс істей алады). Бірақ көптеген жағдайларда, көптеген түйіндер дұрыс жұмыс істегенде, жүйеде прогресс болады.
Іс жүзінде біз жартылай синхронды байланыс модельдерімен айналысамыз. Ішінара синхрония келесідей түсініледі: жалпы жағдайда бізде асинхронды модель бар, бірақ белгілі бір уақыт нүктесінің «жаһандық тұрақтандыру уақыты» белгілі бір тұжырымдамасы ресми түрде енгізілген.
Уақыттың бұл сәті ұзақ уақытқа келмеуі мүмкін, бірақ ол бір күні келуі керек. Виртуалды оятқыш шырылдайды және сол сәттен бастап біз хабарламалар келетін уақыттың дельтасын болжай аламыз. Осы сәттен бастап жүйе асинхрондыдан синхрондыға ауысады. Іс жүзінде біз дәл осындай жүйелермен айналысамыз.
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)», мұнда бірінші мән - өзінің Ұсыну қадамындағы дауыс беру нөмірі, ал екінші мән - барлығы жинаған нәрсе, яғни біз шын мәнінде дауыс беретін мән.
- Егер акцепторлардың ешқайсысы қандай да бір құндылықтарды жібермесе, бірақ олар осы раундта дауыс беруге уәде берсе, көшбасшы оларды бірінші кезекте көшбасшы болған құндылық үшін дауыс беруге шақыра алады. Оны у деп атаймыз. Ол алдыңғы нәтижеге ұқсас «Қабылдау (n, y)» сияқты барлық түйіндерге хабарлама жібереді.
- 2b кезеңі: қабылданды. Әрі қарай, акцепторлық түйіндер көшбасшыдан «Қабылдау(...)» хабарламасын алғаннан кейін онымен келіседі (барлық түйіндерге жаңа мәнмен келісетіндігі туралы растауды жібереді), егер олар кейбір (басқа) уәде бермесе ғана ) ) көшбасшысы дауыс беруге қатысады n' > n, әйтпесе олар растау сұрауын елемейді.
Егер түйіндердің көпшілігі көшбасшыға жауап берсе және олардың барлығы жаңа мәнді растаса, онда жаңа мән қабылданған болып саналады. Ура! Егер көпшілікке қол жеткізілмесе немесе жаңа мәнді қабылдаудан бас тартқан түйіндер болса, онда бәрі басынан басталады.
Paxos алгоритмі осылай жұмыс істейді. Осы кезеңдердің әрқайсысында көптеген нәзіктіктер бар, біз іс жүзінде сәтсіздіктердің әртүрлі түрлерін, бірнеше көшбасшылардың мәселелерін және тағы басқаларды қарастырмадық, бірақ бұл мақаланың мақсаты - оқырманды жоғары деңгейде таратылған есептеулер әлемімен таныстыру.
Айта кету керек, Paxos бұл тектің жалғыз түрі емес, басқа алгоритмдер бар, мысалы, , бірақ бұл басқа мақаланың тақырыбы.
Қосымша зерттеу үшін материалдарға сілтемелер
Бастауыш деңгейі:
- , Преэти Касиредди, Medium сайтындағы блог мақаласы
- , Ади Канчерла, Medium сайтындағы блог мақаласы
- , Ittai Abraham, блог
- , Ittai Abraham, блог мақаласы
Лесли Лэмпорт деңгейі:
- , Фишер, Линч және Патерсон, зерттеу жұмысы, 1985 ж
- , Лесли Лэмпорт, зерттеу жұмысы, 1998 ж
- , Лесли Лэмпорт, зерттеу жұмысы, 2001 ж
Ақпарат көзі: www.habr.com