Такім чынам, уявім. У пакоі зачынены 5 катоў, і каб пайсці абудзіць гаспадара ім неабходна ўсім разам дамовіцца паміж сабой аб гэтым, бо дзверы яны могуць адчыніць толькі ўпяцёх наваліўшыся на яе. Калі адзін з катоў - кот Шрэдынгера, а астатнія каты не ведаюць аб яго рашэнні, узнікае пытанне: "Як яны могуць гэта зрабіць?"
У гэтым артыкуле я простай мовай раскажу вам пра тэарэтычны складнік свету размеркаваных сістэм і прынцыпы іх працы. А таксама павярхоўна разгледжу галоўную ідэю, якая ляжыць у аснове Paxos'а.
Калі распрацоўшчыкі карыстаюцца хмарнымі інфраструктурамі, рознымі базамі дадзеных, працуюць у кластарах з вялікай колькасці вузлоў, яны ўпэўненыя, што дадзеныя будуць цэласнымі, захоўнымі і заўсёды даступнымі. Але адкуль гарантыі?
Па сутнасці, гарантыі, якія ў нас ёсць - гэта гарантыі пастаўшчыка. Яны апісаны ў дакументацыі прыкладна наступным чынам: "Гэты сэрвіс дастаткова надзейны, у яго ёсць зададзены SLA, не хвалюйцеся, усё будзе размеркавана працаваць, як вы і чакаеце".
Мы схільныя верыць у лепшае, бо разумныя дзядзькі з вялікіх кампаній запэўнілі нас, што ўсё будзе добра. Мы не задаёмся пытаннем: а чаму, уласна, гэта ўвогуле можа працаваць? Ці ёсць нейкае фармальнае абгрунтаванне карэктнасці працы такіх сістэм?
Нядаўна я ездзіў на і вельмі натхніўся гэтай тэмай. Лекцыі ў школе больш нагадвалі заняткі па матэматычным аналізе, чым нешта звязанае з кампутарнымі сістэмамі. Але менавіта так у свой час і даказваліся найважнейшыя алгарытмы, якімі мы карыстаемся кожны дзень, самі таго не падазраючы.
У большасці сучасных размеркаваных сістэм выкарыстоўваецца алгарытм кансэнсусу Paxos і яго розныя мадыфікацыі. Самае крутое, што абгрунтаванасць і, у прынцыпе, сама магчымасць існавання гэтага алгарытму можа быць даказана проста з дапамогай ручкі і паперы. Пры гэтым на практыцы алгарытм прымяняецца ў вялікіх сістэмах, якія працуюць на вялікай колькасці вузлоў у аблоках.
Лайтавая ілюстрацыя таго, пра што пойдзе гаворка далей: задача двух генералаўДавайце для размінкі разбяром .
У нас ёсць дзве арміі - рудая і белая. Белыя войскі базуюцца ў абложаным горадзе. Рудыя войскі на чале з генераламі А1 і А2 размяшчаюцца па двух баках ад горада. Задача рудых - напасці на белы горад і перамагчы. Аднак войска кожнага рудага генерала паасобку меншае за войска белых.
Умовы перамогі для рудых: абодва генералы павінны напасці адначасова, каб мець колькасную перавагу над белымі. Для гэтага генералам А1 і А2 трэба дамовіцца сябар з сябрам. Калі кожны будзе нападаць па асобнасці, рудыя прайграюць.
Каб дамовіцца, генералы А1 і А2 могуць пасылаць сябар да сябра ганцоў праз тэрыторыю белага горада. Ганец можа паспяхова дабрацца да саюзнага генерала ці можа быць перахопленым супернікам. Пытанне: ці ёсць такая паслядоўнасць камунікацый паміж рудымі генераламі (паслядоўнасць адпраўкі ганцоў ад А1 да А2 і наадварот ад А2 да А1), пры якой яны гарантавана дамовяцца аб нападзе ў гадзіну Х. Тут, пад гарантыямі разумеецца, што абодва генерала будуць мець адназначнае пацверджанне , Што саюзнік (іншы генерал) сапраўды атакуе ў прызначаны час X.
Выкажам здагадку, што А1 пасылае ганца да А2 з пасланнем: "Давай нападам сёння апоўначы!". Генерал А1 не можа напасці без пацверджання ад генерала А2. Калі ганец ад А1 дайшоў, то генерал А2 пасылае пацверджанне з паведамленнем: "Так, давай сёння завалім белых". Але зараз генерал А2 не ведае, дайшоў яго ганец ці не, у яго няма гарантый, ці будзе напад адначасовым. Цяпер ужо генералу А2 зноў трэба пацверджанне.
Калі распісваць іх камунікацыю далей, высветліцца наступнае: колькі б ні было цыклаў абмену паведамленнямі, няма спосабу гарантавана паведаміць абодвум генералам аб тым, што іх паведамленні атрыманы (пры ўмове, што любы з ганцоў можа быць перахоплены).
Задача двух генералаў - гэта выдатная ілюстрацыя вельмі простай размеркаванай сістэмы, дзе ёсць два вузлы з ненадзейнай камунікацыяй. Значыць, у нас няма 100% гарантыі таго, што яны сінхранізуюцца. Пра падобныя праблемы толькі ў буйнейшым маштабе далей у артыкуле.
Уводзім паняцце размеркаваных сістэм
Размеркаваная сістэма - гэта група кампутараў (далей будзем называць іх вузламі), якія могуць абменьвацца паведамленнямі. Кожны асобны вузел - гэта некаторая аўтаномная сутнасць. Вузел можа самастойна апрацоўваць задачы, але каб узаемадзейнічаць з іншымі вузламі, яму трэба дасылаць і прымаць паведамленні.
Як канкрэтна рэалізаваны паведамленні, якія пратаколы выкарыстоўваюцца - гэта нас не цікавіць у дадзеным кантэксце. Важна, што вузлы размеркаванай сістэмы могуць абменьвацца сябар з сябрам дадзенымі шляхам адпраўкі паведамленняў.
Само азначэнне выглядае не вельмі складаным, але трэба ўлічваць, што ў размеркаванай сістэмы ёсць шэраг атрыбутаў, якія будуць важныя для нас.
Атрыбуты размеркаваных сістэм
- Паралеласць - магчымасць узнікнення адначасовых або канкурэнтных падзей у сістэме. Больш за тое, мы будзем лічыць, што падзеі, якія адбыліся на двух розных вузлах, патэнцыйна канкурэнтныя да таго часу, пакуль у нас няма дакладнага парадку ўзнікнення гэтых падзей. А, як правіла, у нас яго няма.
- Адсутнасць глабальных гадзін. У нас няма дакладнага парадку падзей з-за адсутнасці глабальных гадзін. У звычайным свеце людзей мы прывыклі да таго, што ў нас ёсць гадзіннік і час абсалютна. Усё мяняецца, калі гаворка заходзіць аб размеркаваных сістэмах. Нават у звышдакладных атамных гадзін ёсць дрыфце, і магчымыя сітуацыі, калі мы не можам сказаць, якая з двух падзей адбылося раней. Таму спадзявацца на час мы таксама ня можам.
- Незалежная адмова вузлоў сістэмы. Ёсць яшчэ адна праблема: нешта можа пайсці не так проста таму, што нашыя вузлы не вечныя. Можа выйсці са строю жорсткі дыск, перазагрузіцца віртуалка ў воблаку, можа міргнуць сетку і паведамленні згубяцца. Больш за тое, магчымыя сітуацыі, калі вузлы працуюць, але пры гэтым працуюць супраць сістэмы. Апошні клас праблем нават атрымаў асобную назву: праблема . Самы папулярны прыклад размеркаванай сістэмы з такой праблемай - гэта Blockchain. Але сёння мы не будзем разглядаць гэты адмысловы клас праблем. Нас будуць цікавіць сітуацыі, у якіх проста адзін ці некалькі вузлоў могуць выходзіць са строю.
- Мадэлі камунікацыі (мадэлі абмену паведамленнямі) паміж вузламі. Мы ўжо высветлілі, што вузлы размаўляюць шляхам абмену паведамленнямі. Ёсць дзве вядомыя мадэлі абмену паведамленнямі: сінхронная і асінхронная.
Мадэлі камунікацыі паміж вузламі ў размеркаваных сістэмах
Сінхронная мадэль - мы сапраўды ведаем, што ёсць канчатковая вядомая дэльта часу, за якую паведамленне гарантавана даходзіць ад аднаго вузла да іншага. Калі гэты час выйшаў, а паведамленне не прыйшло, мы можам смела казаць, што вузел выйшаў са строю. У такой мадэлі мы маем прадказальны час чакання.
Асінхронная мадэль - у асінхронных мадэлях мы лічым, што час чакання вядома, але не існуе такой дэльты часу, пасля якой можна гарантаваць, што вузел выйшаў з ладу. Г.зн. час чакання паведамлення ад вузла можа быць колькі заўгодна доўгім. Гэта важнае азначэнне, і мы пагаворым пра гэта далей.
Паняцце кансэнсусу ў размеркаваных сістэмах
Перш, чым фармальна вызначыць паняцце кансэнсусу, разгледзім прыклад сітуацыі, калі ён нам патрэбны, а менавіта - State Machine Replication.
У нас ёсць некаторы размеркаваны лог. Нам бы хацелася, каб ён быў кансістэнтным і змяшчаў ідэнтычныя дадзеныя на ўсіх вузлах размеркаванай сістэмы. Калі нейкі з вузлоў пазнае новае значэнне, якое ён збіраецца запісаць у лог, яго задачай становіцца прапанаваць гэтае значэнне ўсім астатнім вузлам, каб лог абнавіўся на ўсіх вузлах, і сістэма перайшла ў новы кансістэнтны стан. Пры гэтым важна, каб вузлы дамовіліся паміж сабой: усе вузлы пагадзіліся, што прапанаванае новае значэнне карэктна, усе вузлы гэтае значэнне прынялі, і толькі ў гэтым выпадку ўсе могуць запісаць у лог новае значэнне.
Іншымі словамі: ніхто з вузлоў не запярэчыў, што ў яго ёсць больш актуальная інфармацыя, а прапанаванае значэнне няправільнае. Дамоўленасць паміж вузламі і згода аб адзіным дакладным прынятым значэнні і ёсць кансэнсус у размеркаванай сістэме. Далей мы будзем казаць аб алгарытмах, якія дазваляюць размеркаванай сістэме гарантавана дасягаць кансэнсус.
Больш фармальна мы можам вызначыць алгарытм дасягнення кансэнсусу (ці проста алгарытм кансэнсусу), як некаторую функцыю, якая перакладае размеркаваную сістэму са стану А ў стан Б. Прычым гэты стан прынята ўсімі вузламі, і ўсе вузлы могуць яго пацвердзіць. Як высвятляецца, гэтая задача зусім не такая трывіяльная, як здаецца на першы погляд.
Уласцівасці алгарытму кансэнсусу
Алгарытм кансенсусу павінен валодаць трыма ўласцівасцямі, каб сістэма працягвала існаваць і мела нейкі прагрэс у пераходзе са стану ў стан:
- Пагадненне – усе карэктна якія працуюць вузлы павінны прыняць адно і тое ж значэнне (у артыкулах гэтая ўласцівасць таксама сустракаецца як safety property). Усе вузлы, якія зараз функцыянуюць (не выйшлі са строю і не страцілі сувязь з астатнімі) павінны прыйсці да пагаднення і прыняць нейкае фінальнае агульнае значэнне.
Тут важна разумець, што вузлы ў разгляданай намі размеркаванай сістэме жадаюць дамовіцца. Гэта значыць, мы зараз гаворым пра сістэмы, у якіх проста можа нешта адмовіць (напрыклад, адмовіць нейкі вузел), але ў гэтай сістэме дакладна няма вузлоў, якія наўмысна працуюць супраць іншых (задача візантыйскіх генералаў). За кошт гэтай уласцівасці сістэма застаецца кансістэнтнай.
- Цэласнасць - калі ўсе карэктна якія працуюць вузлы прапануюць адно і тое ж значэнне v, значыць кожны карэктна які працуе вузел павінен прыняць гэта значэнне v.
- Спыненне - усё карэктна якія працуюць вузлы ў канчатковым рахунку прымуць некаторае значэнне (liveness property), што дазваляе алгарытму мець прагрэс у сістэме. Кожны асобны карэктна які працуе вузел, павінен рана ці позна прыняць фінальнае значэнне і пацвердзіць гэта: "Для мяне - гэта значэнне праўдзіва, я згодзен са ўсёй сістэмай".
Прыклад працы алгарытму кансэнсусу
Пакуль уласцівасці алгарытму могуць быць не зусім зразумелымі. Таму праілюструем на прыкладзе, якія стадыі праходзіць найпросты алгарытм кансенсусу ў сістэме з сінхроннай мадэллю абмену паведамленнямі, у якой усе вузлы функцыянуюць як мае быць, паведамленні не губляюцца і нічога не ламаецца (няўжо такое і праўда здараецца?).
- Усё пачынаецца з прапановы рукі і сэрца (Propose). Выкажам здагадку, што да вузла пад назвай "Вузел 1" падключыўся кліент і пачаў транзакцыю, перадаўшы вузлу новае значэнне - О. З гэтага моманту "Вузел 1" мы будзем называць прапанова. Як proposer «Вузел 1» зараз павінен апавясціць усю сістэму аб тым, што ў яго ёсць свежыя дадзеныя, і ён рассылае ўсім астатнім вузлам паведамлення: «Глядзіце! Мне прыйшло значэнне "О", і я хачу яго запісаць! Прашу пацвердзіць, што вы таксама запішаце «О» у свой лог».
- Наступная стадыя - галасаванне за прапанаванае значэнне (Voting). Навошта яна патрэбна? Можа так здарыцца, што іншым вузлам прыйшла больш свежая інфармацыя, і ў іх ёсць дадзеныя па гэтай жа транзакцыі.
Калі вузел "Вузел 1" пасылае свой прапаўз, астатнія вузлы правяраюць у сваіх логах дадзеныя па гэтай падзеі. Калі ніякіх супярэчнасьцяў няма, вузлы аб'яўляюць: «Так, у мяне няма іншых дадзеных па гэтай падзеі. Значэнне «О» - гэта самая свежая інфармацыя, якую мы заслужылі».У любым іншым выпадку, вузлы могуць адказаць «вузлу 1»: «Паслухай! У мяне ёсць свежыя дадзеныя па гэтай транзакцыі. Не «О», а сёе-тое лепшае».
На стадыі галасавання вузлы прыходзяць да рашэння: альбо ўсе прымаюць адно значэнне, альбо нехта з іх галасуе супраць, пазначыўшы, што ў яго ёсць больш свежыя дадзеныя.
- Калі раунд галасавання прайшоў паспяхова, і ўсе былі "за", то сістэма пераходзіць у новую стадыю - прыняцце значэння (Accept). "Вузел 1" збірае ўсе адказы іншых вузлоў і паведамляе: "Усе пагадзіліся са значэннем "О"! Цяпер я афіцыйна заяўляю, што "О" - наша новае значэнне, адзінае для ўсіх! Запішыце сабе ў кніжачку, не забудзьцеся. Запішыце ў свой лог!»
- Астатнія вузлы дасылаюць пацверджанне (Accepted), што яны запісалі сабе значэнне "О", нічога новага за гэты час паступіць не паспела (свайго роду двухфазны коміт). Пасля гэтай знамянальнай падзеі мы лічым, што размеркаваная транзакцыя выканалася.
Такім чынам алгарытм кансэнсусу ў простым выпадку складаецца з чатырох крокаў: propose, галасаванне (voting), прыняцце (accept), пацверджанне прыняцця (accepted).
Калі на нейкім кроку мы не змаглі дасягнуць згоды, то алгарытм запускаецца нанова, з улікам той інфармацыі, якую дадуць вузлы, якія адмовіліся пацвярджаць прапанаванае значэнне.
Алгарытм кансэнсусу ў асінхроннай сістэме
Да гэтага ўсё было гладка, бо гаворка ішла пра сінхронную мадэль абмену паведамленнямі. Але мы-то ведаем, што ў сучасным свеце мы ўсё абвыклі рабіць асінхронна. Як жа аналагічны алгарытм працуе ў сістэме з асінхроннай мадэллю абмену паведамленнямі, дзе мы лічым, што час чакання адказу ад вузла можа быць калі заўгодна доўгім (дарэчы, вынахад вузла з ладу, можна таксама разглядаць як прыклад, калі вузел можа адказваць колькі заўгодна доўга. ).
Цяпер, калі мы ведаем, як у прынцыпе працуе алгарытм кансенсусу, пытанне да тых дапытлівых чытачоў, хто дайшоў да гэтага месца: колькі вузлоў у сістэме з N вузлоў з асінхроннай мадэллю паведамленняў можа выйсці са строю, каб сістэма па-ранейшаму магла дасягаць кансенсусу?
Правільны адказ і абгрунтаванне за спойлерам.Правільны адказ: 0. Калі хаця б адзін вузел у асінхроннай сістэме выходзіць з ладу, сістэма не зможа дасягнуць кансенсусу. Гэта сцвярджэнне даказана ў вядомай у пэўных колах тэарэме FLP (1985, Fischer, Lynch, Paterson, спасылка на арыгінал у канцы артыкула): "Немагчымасць дасягнення размеркаванага кансенсусу пры выхадзе са строю хаця б аднаго вузла".
Рабяты, тады ў нас праблема, мы жа абвыклі, што ў нас усё асінхронна. А тут такое. Як далей жыць?
Мы зараз казалі пра тэорыю, пра матэматыку. Што значыць "кансенсус не можа быць дасягнуты", перакладаючы з матэматычнай мовы на наш - інжынерны? Гэта значыць, што "не заўсёды можа быць дасягнуты", г.зн. існуе такі кейс, пры якім кансэнсус не дасягальны. А што гэта за выпадак?
Гэта якраз парушэнне liveness property, апісанае вышэй. У нас няма агульнай згоды, і сістэма не можа мець прагрэс (не можа завяршыцца за канчатковы час) у выпадку, калі ў нас няма адказу ад усіх вузлоў. Таму што ў асінхроннай сістэме ў нас няма прадказальнага часу адказу, і мы не можам ведаць, ці выйшаў вузел са строю ці проста доўга адказвае.
Але на практыцы мы можам знайсці рашэньне. Няхай наш алгарытм можа працаваць доўга ў выпадку адмоваў (патэнцыйна можа працаваць бясконца). Але ў большасці сітуацый, калі большасць вузлоў карэктна функцыянуюць, мы будзем мець прагрэс у сістэме.
На практыцы мы маем справу з часткова сінхроннымі мадэлямі камунікацый. Частковая сінхроннасць разумеецца так: у агульным выпадку ў нас асінхронная мадэль, але фармальна ўводзіцца нейкае паняцце "global stabilization time" нейкага моманту часу.
Гэты момант часу можа не надыходзіць колькі заўгодна доўга, але аднойчы ён павінен наступіць. Празвініць віртуальны будзільнік, і з гэтага моманту мы можам прадказаць дэльту часу, за якую паведамленні дойдуць. З гэтага моманту сістэма з асінхроннай ператвараецца ў сінхронную. На практыцы мы маем справу менавіта з такімі сістэмамі.
Алгарытм Paxos вырашае праблемы кансэнсусу
- гэта сямейства алгарытмаў, якія вырашаюць праблему кансенсусу для часткова сінхронных сістэм, пры ўмове што нейкія вузлы могуць выходзіць са строю. Аўтарам Paxos'а з'яўляецца . Ён прапанаваў фармальны доказ існавання і карэктнасці алгарытму ў 1989 годзе.
Але доказ аказаўся зусім нетрывіяльным. Першая публікацыя была выпушчана толькі ў 1998 годзе (33 старонкі) з апісаннем алгарытму. Як аказалася, яна была вельмі складанай для разумення, і ў 2001 годзе было апублікавана тлумачэнне да артыкула, якое заняло 14 старонак. Аб'ёмы публікацый прыведзены для таго, каб паказаць, што насамрэч праблема кансэнсусу зусім няпростая, і за падобнымі алгарытмамі ляжыць велізарная праца найразумнейшых людзей.
Цікава, што сам Леслі Лэмпарт у сваёй лекцыі заўважыў, што ў другім артыкуле-тлумачэнні ёсць адно сцвярджэнне, адзін радок (не ўдакладніў які), які можа быць па-рознаму трактаваны. І з-за гэтага вялікая колькасць сучасных рэалізацый Paxos працуюць не зусім карэктна.
Падрабязны разбор працы Paxos'а пацягне не на адзін артыкул, таму я пастараюся вельмі сцісла перадаць асноўную ідэю алгарытму. У спасылках у канцы майго артыкула вы знойдзеце матэрыялы для далейшага апускання ў гэтую тэму.
Ролі ў Paxos
У алгарытме Paxos ёсць паняцце роляў. Разгледзім тры асноўныя (ёсць мадыфікацыі з дадатковымі ролямі):
- Proposers (таксама могуць сустракацца тэрміны: лідэры ці каардынатары). Гэта хлопцы, якія даведаюцца аб нейкім новым значэнні ад карыстальніка і бяруць на сябе ролю лідэра. Іх задача запусціць раунд прапановы новага значэння і каардынаваць далейшыя дзеянні вузлоў. Прычым Paxos дапускае наяўнасць некалькіх лідэраў у пэўных сітуацыях.
- Acceptors (Voters). Гэта вузлы, якія галасуюць за прыняцце ці непрыняцце таго ці іншага значэння. Іх роля вельмі важная, таму што менавіта ад іх залежыць рашэнне: у які стан пяройдзе (ці не пяройдзе) сістэма пасля чарговага этапу алгарытму кансэнсусу.
- Навучэнцы. Вузлы, якія проста прымаюць і запісваюць новае прынятае значэнне, калі стан сістэмы змянілася. Яны не прымаюць рашэнні, проста атрымліваюць дадзеныя і могуць аддаць іх канчатковаму карыстачу.
Адзін вузел можа сумяшчаць некалькі роляў у розных сітуацыях.
Паняцце кворуму
Мы мяркуем, што ў нас ёсць сістэма з N вузлоў. І з іх максімум F вузлоў можа выходзіць са строю. Калі F вузлоў выходзіць са строю, значыць у нас у кластары павінна быць, як мінімум 2F + 1 вузлоў acceptor'аў.
Гэта трэба для таго, каб у нас заўсёды, нават у горшай сітуацыі "добрыя", карэктна працуючыя вузлы мелі большасць. Гэта значыць F + 1 "добрых" вузлоў, якія пагадзіліся, і фінальнае значэнне будзе прынята. У адваротным выпадку можа быць сітуацыя, калі ў нас розныя лакальныя групы прымуць рознае значэнне і не змогуць паміж сабой дамовіцца. Таму нам патрэбна абсалютная большасць, каб перамагчы ў галасаванні.
Агульная ідэя працы алгарытму кансэнсусу Paxos
Алгарытм Paxos мяркуе дзве вялікія фазы, якія ў сваю чаргу разбіваюцца на два крокі кожная:
- Phase 1a: Prepare. На этапе падрыхтоўкі лідэр (proposer) паведамляе ўсім вузлам: “Мы пачынаем новы этап галасавання. У нас новы раунд. Нумар гэтага раунда - n. Цяпер мы пачнем галасаваць». Пакуль ён проста паведамляе аб пачатку новага цыкла, але не паведамляе новае значэнне. Задача гэтага этапу ініцыяваць новы раунд і паведаміць усім яго ўнікальны нумар. Нумар раўнда важны, гэта павінна быць значэнне большае, чым усе папярэднія нумары галасаванняў ад усіх папярэдніх лідэраў. Бо менавіта дзякуючы нумару раўнда іншыя вузлы ў сістэме будуць разумець, наколькі свежыя дадзеныя ў лідара. Верагодна, у іншых вузлоў ужо ёсць вынікі галасавання з нашмат пазнейшых раундаў і яны проста раскажуць лідэру, што ён адстаў ад жыцця.
- Phase 1b: Promise. Калі вузлы-acceptor'ы атрымалі нумар новага этапу галасавання, магчымыя два зыходы:
- Нумар n новага галасавання большы за нумар любога з папярэдніх галасаванняў, у якім удзельнічаў acceptor. Тады acceptor дасылае лідэру абяцанне, што не будзе больш удзельнічаць ні ў якіх галасаваннях з меншым нумарам, чым n. Калі acceptor ужо паспеў за нешта прагаласаваць (г.зн. ён ужо ў другой фазе прыняў нейкае значэнне), то да свайго абяцання ён прыкладае прынятае значэнне і нумар галасавання, у якім ён удзельнічаў.
- У адваротным выпадку, калі acceptor ужо ведае аб галасаванні з вялікім нумарам, ён можа проста праігнараваць этап падрыхтоўкі і не адказваць лідэру.
- Phase 2a: Accept. Лідэру трэба дачакацца адказу ад кворуму (большасці вузлоў у сістэме) і, калі патрэбная колькасць адказаў атрымана, то ў яго ёсць два варыянты развіцця падзей:
- Некаторыя з acceptor'аў даслалі значэньні, за якія яны ўжо галасавалі. У гэтым выпадку лідэр выбірае значэнне з галасавання з максімальным нумарам. Назавем гэтае значэнне x, і рассылае ўсім вузлам паведамленне выгляду: "Accept (n, x)", дзе першае значэнне - нумар галасавання са свайго ж кроку Propose, а другое значэнне - то дзеля чаго ўсё збіраліся, г.зн. значэнне за якое, уласна, галасуем.
- Калі ніхто з acceptor'аў не даслаў ніякіх значэнняў, а проста яны паабяцалі галасаваць у гэтым раундзе, лідэр можа прапанаваць ім прагаласаваць за сваё значэнне, тое значэнне, дзеля якога ён увогуле стаў лідэрам. Назавем яго y. Ён рассылае ўсім вузлам паведамленне выгляду: "Accept (n, y)", па аналогіі з папярэднім зыходам.
- Phase 2b: Accepted. Далей, вузлы-acceptor'ы, пры атрыманні паведамлення «Accept(…)», ад лідэра згаджаюцца з ім (рассылаюць усім вузлам пацверджанне, што яны згодны з новым значэннем) толькі ў тым выпадку, калі яны не паабяцалі нейкаму (іншаму ) лідэру ўдзельнічаць у галасаваннях з нумарам раунда n' > n, у адваротным выпадку яны ігнаруюць запыт на пацверджанне.
Калі лідэру адказала большасць вузлоў, і ўсе яны пацвердзілі новае значэнне, то новае значэнне лічыцца прынятым. Ура! Калі ж большасць не набрана ці ёсць вузлы, якія адмовіліся прымаць новае значэнне, тое ўсё пачынаецца спачатку.
Вось так працуе алгарытм Paxos. У кожнага з гэтых этапаў ёсць шмат тонкасцяў, мы практычна не разгледзелі розныя віды адмоваў, праблемы множных лідэраў і многае іншае, але мэтай гэтага артыкула з'яўляецца толькі на верхнім узроўні пазнаёміць чытача са светам размеркаваных вылічэнняў.
Таксама варта заўважыць, што Paxos – не адзіны ў сваім родзе, ёсць і іншыя алгарытмы, напрыклад, , Але гэта ўжо тэма для іншага артыкула.
Спасылкі на матэрыялы для далейшага вывучэння
Узровень «навічок»:
- , Preethi Kasireddy, blog article on Medium
- , Adi Kancherla, blog article on Medium
- , Ittai Abraham, blog
- , Ittai Abraham, blog article
Узровень «Леслі Лэмпарт»:
- , Fischer, Lynch and Paterson, research paper, 1985
- , Leslie Lamport, research paper, 1998
- , Leslie Lamport, research paper, 2001
Крыніца: habr.com