Пас, биёед тасаввур кунем. Дар утоқ 5 гурба маҳкам аст ва барои бедор кардани соҳибхона ҳама бояд дар ин бора байни худ мувофиқа кунанд, зеро дарро танҳо панҷ нафарашон ба он такя карда метавонанд, кушоянд. Агар яке аз гурбахо гурбаи Шредингер бошаду гурбахои дигар аз карори у хабар надошта бошанд, саволе ба миён меояд: «Онхо чй тавр ин корро карда метавонанд?».
Дар ин мақола ман ба шумо бо ибораҳои оддӣ дар бораи ҷузъи назариявии ҷаҳони системаҳои тақсимшуда ва принсипҳои кори онҳо нақл мекунам. Ман инчунин ба таври рӯякӣ идеяи асосии Paxosро тафтиш мекунам.
Вақте ки таҳиягарон инфрасохтори абрӣ, пойгоҳи додаҳои гуногунро истифода мебаранд ва дар кластерҳои шумораи зиёди гиреҳҳо кор мекунанд, онҳо итминон доранд, ки маълумот пурра, бехатар ва ҳамеша дастрас хоҳад буд. Аммо кафолатҳо куҷоянд?
Аслан, кафолатҳое, ки мо дорем, кафолати таъминкунандагон мебошанд. Онҳо дар ҳуҷҷатҳо чунин тавсиф шудаанд: "Ин хидмат хеле боэътимод аст, он дорои SLA-и додашуда аст, хавотир нашав, ҳама чиз тавре ки шумо интизоред, тақсим карда мешавад."
Мо майл ба беҳтаринҳо боварӣ дорем, зеро бачаҳои оқил аз ширкатҳои бузург моро итминон доданд, ки ҳама чиз хуб мешавад. Мо савол намедиҳем: чаро, дар асл, ин метавонад умуман кор кунад? Оё барои кори дурусти чунин системаҳо ягон далели расмӣ вуҷуд дорад?
Ман ба наздикӣ рафтам ва аз ин мавзӯъ хеле илҳом гирифта буд. Лексияҳо дар мактаб бештар ба дарсҳои ҳисобкунӣ монанд буданд, на чизи марбут ба системаҳои компютерӣ. Аммо маҳз ҳамин тавр муҳимтарин алгоритмҳое, ки мо ҳар рӯз истифода мебарем, ҳатто надониста, дар як вақт исбот карда шуданд.
Аксари системаҳои паҳншудаи муосир алгоритми консенсуси Paxos ва дигаргуниҳои гуногуни онро истифода мебаранд. Аз ҳама ҷолиб он аст, ки дурустӣ ва, асосан, эҳтимолияти мавҷудияти ин алгоритмро танҳо бо қалам ва коғаз исбот кардан мумкин аст. Дар амал, алгоритм дар системаҳои калон, ки дар шумораи зиёди гиреҳҳои абрҳо кор мекунанд, истифода мешавад.
Тасвири равшани он чизе ки дар оянда муҳокима карда мешавад: вазифаи ду генералБиёед як гармкуниро дида бароем .
Мо ду лашкар дорем — сурху сафед. Нерӯҳои сафедпӯст дар шаҳри муҳосирашуда ҷойгир шудаанд. Кушунхои сурх бо сардории генералхои А1 ва А2 дар ду тарафи шахр вокеъ гардидаанд. Вазифаи сурхчаҳо ҳамла кардан ба шаҳри сафед ва ғалаба кардан аст. Бо вуҷуди ин, артиши ҳар як генерали сурх дар алоҳидагӣ аз артиши сафед хурдтар аст.
Шароити ғалаба барои сурхҳо: ҳарду генерал бояд дар як вақт ҳамла кунанд, то бар сафедпӯстон бартарии шумора дошта бошанд. Барои ин генералхои А1 ва А2 бояд бо хамдигар созиш кунанд. Агар хама алохида хучум кунанд, сурхчахо маглуб мешаванд.
Барои расидан ба созиш генералҳои А1 ва А2 метавонанд тавассути қаламрави шаҳри сафед ба ҳамдигар паёмбар фиристанд. Паёмбар метавонад бомуваффақият ба як генерали иттифоқчӣ бирасад ё аз ҷониби душман боздошта шавад. Савол: оё чунин пайдарпаии муошират байни генералҳои сурхрӯй вуҷуд дорад (пайванди фиристодани паёмбарон аз А1 ба А2 ва баръакс аз А2 ба А1), ки дар он онҳо кафолат дода мешавад, ки дар соати X дар бораи ҳамла розӣ шаванд. Дар ин ҷо, кафолатҳо маънои онро доранд, ки ҳарду генерал тасдиқи якхела хоҳанд дошт, ки иттифоқчӣ (генерали дигар) ҳатман дар вақти таъиншудаи X ҳамла хоҳад кард.
Фарз мекунем, ки A1 як паёмбареро ба A2 бо паёми зерин фиристод: "Биёед имрӯз нисфи шаб ҳамла кунем!" Генерал A1 наметавонад бидуни тасдиқи генерал A2 ҳамла кунад. Агар паёмбар аз A1 омада бошад, пас генерал A2 тасдиқро бо паём мефиристад: "Бале, биёед имрӯз сафедпӯстонро бикушем." Аммо ҳоло генерал А2 намедонад, ки паёмбараш омадааст ё на, ӯ кафолат надорад, ки ҳамла ҳамзамон хоҳад буд. Ҳоло General A2 боз ба тасдиқ ниёз дорад.
Агар муоширати онҳоро бештар тавсиф кунем, маълум мешавад, ки новобаста аз он ки чанд давраҳои табодули паёмҳо вуҷуд доранд, ҳеҷ роҳе кафолат дода наметавонад, ки ҳарду генерал паёмҳои онҳоро гирифтаанд (агар фарз кунем, ки ҳарду паёмбарро боздошт кардан мумкин аст).
Мушкилоти ду генерал як мисоли олии системаи тақсимшудаи хеле содда аст, ки дар он ду гиреҳ бо иртиботи беэътимод мавҷуданд. Ин маънои онро дорад, ки мо 100% кафолат надорем, ки онҳо ҳамоҳанг карда мешаванд. Проблемаҳои шабеҳ танҳо дар миқёси васеътар дар мақола муҳокима карда мешаванд.
Мо консепсияи системаҳои тақсимшударо ҷорӣ мекунем
Системаи тақсимшуда як гурӯҳи компютерҳо мебошад (минбаъд онҳоро гиреҳҳо меномем), ки метавонанд мубодилаи паёмҳоро дошта бошанд. Ҳар як гиреҳи инфиродӣ як намуди воҳиди мустақил аст. Гиреҳ метавонад мустақилона вазифаҳоро коркард кунад, аммо барои иртибот бо гиреҳҳои дигар, он бояд паёмҳоро ирсол ва қабул кунад.
Паёмҳо чӣ гуна иҷро мешаванд, кадом протоколҳо истифода мешаванд - ин барои мо дар ин замина ҷолиб нест. Муҳим аст, ки гиреҳҳои системаи тақсимшуда тавассути фиристодани паёмҳо метавонанд бо ҳамдигар маълумот мубодила кунанд.
Худи таъриф чандон мураккаб ба назар намерасад, аммо мо бояд ба назар гирем, ки системаи тақсимшуда дорои як қатор хусусиятҳое мебошад, ки барои мо муҳим хоҳанд буд.
Хусусиятҳои системаҳои тақсимшуда
- Ҳамзамон – имкони рух додани ҳодисаҳои ҳамзамон ё ҳамзамон дар система. Ғайр аз он, мо рӯйдодҳоеро, ки дар ду гиреҳи гуногун рух медиҳанд, эҳтимолан ҳамзамон мешуморем, то даме ки тартиби дақиқи пайдоиши ин рӯйдодҳоро надорем. Аммо, чун қоида, мо онро надорем.
- Соати ҷаҳонӣ нест. Мо аз сабаби набудани соати глобалӣ тартиби дақиқи рӯйдодҳоро надорем. Дар ҷаҳони оддии одамон мо ба он одат кардаем, ки мо соатҳо ва вақтро комилан дорем. Вақте ки сухан дар бораи системаҳои тақсимшуда меравад, ҳама чиз тағир меёбад. Ҳатто соатҳои хеле дақиқи атомӣ дрейф доранд ва мумкин аст вазъиятҳое бошанд, ки мо гуфта наметавонем, ки кадоме аз ин ду ҳодиса аввал рух додааст. Бинобар ин мо хам ба вакт умед баста наметавонем.
- Нокомии мустақили гиреҳҳои система. Мушкилоти дигар вуҷуд дорад: чизе метавонад хато кунад, зеро гиреҳҳои мо то абад давом намекунанд. Диски сахт метавонад ноком шавад, мошини маҷозӣ дар абр метавонад бозоғоз шавад, шабака чашмак мезанад ва паёмҳо гум мешаванд. Гузашта аз ин, метавонад ҳолатҳое вуҷуд дошта бошанд, ки гиреҳҳо кор мекунанд, аммо дар айни замон бар зидди система кор мекунанд. Синфи охирини мушкилот ҳатто номи алоҳида гирифт: мушкилот . Намунаи маъмултарини системаи тақсимшуда бо ин мушкилот Blockchain мебошад. Аммо имрӯз мо ин синфи махсуси мушкилотро баррасӣ намекунем. Мо ба ҳолатҳое таваҷҷӯҳ хоҳем кард, ки дар он танҳо як ё якчанд гиреҳҳо ноком мешаванд.
- Моделҳои иртиботӣ (моделҳои паёмнависӣ) байни гиреҳҳо. Мо аллакай муайян кардем, ки гиреҳҳо тавассути мубодилаи паёмҳо муошират мекунанд. Ду модели маъруфи паёмнависӣ мавҷуданд: синхронӣ ва асинхронӣ.
Моделҳои иртибот байни гиреҳҳо дар системаҳои тақсимшуда
Модели синхронӣ - мо аниқ медонем, ки як дельтаи маълуми вақт мавҷуд аст, ки дар давоми он паём аз як гиреҳ ба дигараш кафолат дода мешавад. Агар ин вақт гузашта бошад ва паём нарасидааст, мо метавонем бо боварӣ гуфта метавонем, ки гиреҳ ноком шудааст. Дар ин модел мо вақтҳои интизории пешбинишаванда дорем.
Модели асинхронӣ - дар моделҳои асинхронӣ мо ҳисоб мекунем, ки вақти интизорӣ маҳдуд аст, аммо чунин дельтаи вақт вуҷуд надорад, ки пас аз он мо кафолат дода метавонем, ки гиреҳ ноком шудааст. Онхое. Вақти интизории паём аз гиреҳ метавонад ба таври худсарона дароз бошад. Ин таърифи муҳим аст ва мо минбаъд дар ин бора сӯҳбат хоҳем кард.
Консепсияи консенсус дар системаҳои тақсимшуда
Пеш аз он ки мафҳуми консенсусро ба таври расмӣ муайян кунем, биёед мисоли вазъиятеро дида бароем, ки ба он ниёз дорем, яъне - Репликатсияи мошини давлатӣ.
Мо як сабти тақсимшуда дорем. Мо мехоҳем, ки он пайваста бошад ва дорои маълумоти якхела дар ҳама гиреҳҳои системаи тақсимшуда бошад. Вақте ки яке аз гиреҳҳо арзиши наверо меомӯзад, ки вай ба журнал навиштан мехоҳад, вазифаи он пешниҳод кардани ин арзиш ба ҳама гиреҳҳои дигар мегардад, то ки гузориш дар ҳама гиреҳҳо нав карда шавад ва система ба ҳолати нави пайваста ҳаракат кунад. Дар ин ҳолат муҳим аст, ки гиреҳҳо дар байни худ мувофиқат кунанд: ҳама гиреҳҳо мувофиқат мекунанд, ки арзиши нави пешниҳодшуда дуруст аст, ҳама гиреҳҳо ин арзишро қабул мекунанд ва танҳо дар ин ҳолат ҳама метавонанд арзиши навро ба қайд нависанд.
Ба ибораи дигар: ҳеҷ яке аз гиреҳҳо эътироз накарданд, ки он дорои маълумоти бештар мувофиқ аст ва арзиши пешниҳодшуда нодуруст аст. Созишнома байни гиреҳҳо ва созишнома дар бораи арзиши ягонаи дурусти қабулшуда консенсус дар системаи тақсимшуда мебошад. Минбаъд, мо дар бораи алгоритмҳое сӯҳбат хоҳем кард, ки ба системаи тақсимшуда имкон медиҳанд, ки ба консенсус кафолат дода шаванд.
Ба таври расмӣ, мо метавонем алгоритми консенсусро (ё танҳо алгоритми консенсус) ҳамчун функсияи муайяне муайян кунем, ки системаи тақсимшударо аз ҳолати А ба ҳолати B интиқол медиҳад. Илова бар ин, ин ҳолат аз ҷониби ҳама гиреҳҳо қабул карда мешавад ва ҳама гиреҳҳо метавонанд онро тасдиқ кунанд. Чунон ки маълум мешавад, ин вазифа на он кадар майда-чуйдаест, ки дар назари аввал ба назар мерасад.
Хусусиятҳои алгоритми консенсус
Алгоритми консенсус бояд се хосият дошта бошад, то мавҷудияти система идома ёбад ва дар гузаштан аз як ҳолат ба ҳолат каме пешравӣ дошта бошад:
- Созишнома – ҳамаи гиреҳҳои дуруст коркунанда бояд як арзиш дошта бошанд (дар мақолаҳо ин амвол инчунин моликияти бехатарӣ номида мешавад). Ҳама гиреҳҳое, ки дар айни замон кор мекунанд (намуваффақият ва ё иртиботро бо дигарон гум накардаанд) бояд ба созиш бирасанд ва арзиши умумии ниҳоиро қабул кунанд.
Дар ин ҷо фаҳмидан муҳим аст, ки гиреҳҳои системаи тақсимшуда, ки мо дар назар дорем, розӣ шудан мехоҳанд. Яъне, мо ҳоло дар бораи системаҳое сухан меронем, ки дар онҳо чизе танҳо ноком шуда метавонад (масалан, баъзе гиреҳ ноком мешавад), аммо дар ин система бешубҳа ягон гиреҳе вуҷуд надорад, ки дидаю дониста бар зидди дигарон кор кунанд (вазифаи генералҳои Византия). Аз сабаби ин моликият, система пайваста боқӣ мемонад.
- пуррагӣ — агар хамаи гиреххои дуруст коркунанда як хел арзиш дошта бошанд v, ки маънои онро дорад, ки ҳар як гиреҳи дуруст коркунанда бояд ин арзишро қабул кунад v.
- Қатъкунӣ - ҳама гиреҳҳои дуруст коркунанда дар ниҳоят арзиши муайянро (хосияти зинда) мегиранд, ки ба алгоритм имкон медиҳад, ки дар система пешрафт кунад. Ҳар як гиреҳи дуруст коркунанда бояд дер ё зуд арзиши ниҳоиро қабул кунад ва онро тасдиқ кунад: "Барои ман, ин арзиш дуруст аст, ман бо тамоми система розӣ ҳастам."
Намунаи чӣ гуна кор кардани алгоритми консенсус
Дар ҳоле ки хосиятҳои алгоритм метавонад комилан равшан набошад. Аз ин рӯ, мо бо мисол нишон медиҳем, ки алгоритми соддатарини консенсус дар система бо модели синхронии паёмнависӣ, ки дар он ҳама гиреҳҳо мувофиқи интизорӣ кор мекунанд, паёмҳо гум намешаванд ва ҳеҷ чиз мешиканад (оё ин воқеан рӯй медиҳад?) кадом марҳилаҳоро тай мекунад.
- Ҳамааш аз пешниҳоди издивоҷ оғоз мешавад (Пешниҳод). Фарз мекунем, ки муштарӣ ба гиреҳ бо номи "Гиреҳи 1" пайваст шуда, транзаксияро оғоз карда, арзиши навро ба гиреҳ интиқол медиҳад - O. Минбаъд мо "Гиреҳи 1" -ро даъват мекунем. пешниҳодкунанда. Ҳамчун пешниҳодкунанда, "Гиреҳи 1" акнун бояд тамоми системаро огоҳ созад, ки он дорои маълумоти тоза аст ва он ба ҳама гиреҳҳои дигар паёмҳо мефиристад: "Инак! Маънои «Эй» ба сари ман омад ва ман онро навиштан мехоҳам! Лутфан тасдиқ кунед, ки шумо инчунин "O" -ро дар сабти худ сабт мекунед."
- Марҳилаи навбатӣ овоздиҳӣ барои арзиши пешниҳодшуда мебошад (Овоздиҳӣ). Он барои чӣ? Шояд рӯй диҳад, ки гиреҳҳои дигар маълумоти навтар гирифтаанд ва онҳо дар бораи як транзаксия маълумот доранд.
Вақте ки гиреҳи "Гиреҳи 1" пешниҳоди худро мефиристад, гиреҳҳои дигар сабтҳои худро барои маълумот дар бораи ин ҳодиса тафтиш мекунанд. Агар ягон ихтилоф вуҷуд надошта бошад, гиреҳҳо эълон мекунанд: «Бале, ман дар бораи ин ҳодиса маълумоти дигар надорам. Арзиши "O" маълумоти охиринест, ки мо сазовори онем."Дар ҳама ҳолатҳои дигар, гиреҳҳо метавонанд ба "Гиреҳи 1" ҷавоб диҳанд: "Гӯш кунед! Ман дар бораи ин транзаксия маълумоти охирин дорам. На 'O', балки чизи беҳтаре."
Дар марҳилаи овоздиҳӣ, гиреҳҳо ба як қарор меоянд: ё ҳама арзиши якхеларо қабул мекунанд, ё яке аз онҳо бар зидди он овоз медиҳад, ки вай маълумоти навтарин дорад.
- Агар даври овоздиҳӣ бомуваффақият гузашт ва ҳама ҷонибдор бошанд, пас система ба марҳилаи нав мегузарад - Қабули арзиш. "Гиреҳи 1" ҳама посухҳоро аз гиреҳҳои дигар ҷамъоварӣ мекунад ва гузориш медиҳад: "Ҳама дар бораи арзиши "О" розӣ шуданд! Ҳоло расман эълон мекунам, ки “О” маънои нави мост, барои ҳама яксон аст! Онро дар китоби хурди худ нависед, фаромӯш накунед. Онро дар журнали худ нависед!».
- Гиреҳҳои боқимонда тасдиқро мефиристанд (Қабул карда шудааст), ки онҳо арзиши "O" -ро навиштаанд; дар ин муддат ҳеҷ чизи наве ворид нашудааст (як навъ ӯҳдадории думарҳила). Пас аз ин рӯйдоди муҳим, мо фикр мекунем, ки муомилоти тақсимшуда анҷом ёфт.
Њамин тариќ, алгоритми консенсус дар њолати оддї аз чор зина иборат аст: пешнињод кардан, овоз додан (овоз додан), ќабул (ќабул), тасдиќи ќабул (ќабул).
Агар дар ягон қадам мо ба созиш расида натавонем, алгоритм бо назардошти маълумоти аз ҷониби гиреҳҳое, ки аз тасдиқи арзиши пешниҳодшуда саркашӣ кардаанд, дубора оғоз меёбад.
Алгоритми консенсус дар системаи асинхронӣ
Пеш аз ин, ҳама чиз ҳамвор буд, зеро мо дар бораи модели паёмнависии синхронӣ гап мезадем. Аммо мо медонем, ки дар ҷаҳони муосир мо одат кардаем, ки ҳама чизро ба таври асинхронӣ иҷро кунем. Чӣ тавр як алгоритми шабеҳ дар система бо модели паёмнависии асинхронӣ кор мекунад, ки дар он мо боварӣ дорем, ки вақти интизории посух аз гиреҳ метавонад ба таври худсарона тӯлонӣ бошад (дар омади гап, нокомии гиреҳро низ метавон мисол овард, вақте ки гиреҳ метавонад барои муддати дароз худсарона ҷавоб диҳад).
Акнун, ки мо медонем, ки алгоритми консенсус аслан чӣ гуна кор мекунад, савол барои он хонандагони кунҷков, ки онро то ба имрӯз анҷом додаанд: чанд гиреҳ дар системаи N гиреҳ бо модели паёми асинхронӣ ноком шуда метавонад, то система то ҳол ба консенсус расида тавонад?
Ҷавоби дуруст ва асосноккунӣ дар паси спойлер аст.Ҷавоби дуруст аст: 0. Агар ҳатто як гиреҳ дар системаи асинхронӣ ноком шавад, система наметавонад ба консенсус ноил шавад. Ин изҳорот дар теоремаи FLP исбот шудааст, ки дар доираҳои муайян маълум аст (1985, Фишер, Линч, Патерсон, истинод ба нусхаи аслӣ дар охири мақола): "Имконнопазирии ноил шудан ба консенсуси тақсимшуда, агар ҳадди аққал як гиреҳ ноком шавад. .»
Бачаҳо, пас мо мушкилие дорем, мо одат кардаем, ки ҳама чиз асинхронӣ аст. Ва ин ҷост. Чӣ тавр зиндагӣ карданро давом додан мумкин аст?
Мо танҳо дар бораи назария, дар бораи математика гап мезадем. Аз забони риёзӣ ба забони мо - муҳандисӣ тарҷума кардани "ба консенсус ноил шудан мумкин нест" чӣ маъно дорад? Ин маънои онро дорад, ки "на ҳамеша ба даст овардан мумкин нест", яъне. Ҳолате вуҷуд дорад, ки дар он консенсус ба даст оварда намешавад. Ин чӣ гуна парванда аст?
Ин махз вайрон кардани моликияти зиндагонии дар боло зикршуда мебошад. Мо як созишномаи умумӣ надорем ва система наметавонад пешрафт дошта бошад (дар як муддати муайян ба итмом нарасидааст) дар ҳолате, ки мо аз ҳама гиреҳҳо посух надорем. Зеро дар системаи асинхронӣ мо вақти вокуниши пешгӯинашаванда надорем ва мо наметавонем бидонем, ки гиреҳ суқут кардааст ё барои посух додан вақти зиёд мегирад.
Аммо дар амал мо илоче ёфта метавонем. Бигзор алгоритми мо дар сурати нокомиҳо муддати тӯлонӣ кор кунад (эҳтимолан он метавонад номуайян кор кунад). Аммо дар аксари ҳолатҳо, вақте ки аксари гиреҳҳо дуруст кор мекунанд, мо дар система пешравӣ хоҳем дошт.
Дар амал мо бо моделҳои алоқаи қисман синхронӣ сару кор дорем. Синхронияи қисман ин тавр фаҳмида мешавад: дар ҳолати умумӣ мо модели асинхронӣ дорем, аммо мафҳуми муайяни «вақти мӯътадилшавии глобалӣ»-и як нуқтаи муайяни вақт расман ҷорӣ карда мешавад.
Ин лаҳза метавонад дар муддати тӯлонӣ наояд, аммо он рӯзе бояд фаро расад. Соати занги виртуалӣ занг мезанад ва аз он лаҳза мо метавонем дельтаи вақтро, ки барои он паёмҳо меоянд, пешгӯӣ кунем. Аз ин лаҳза, система аз асинхронӣ ба синхронӣ мегузарад. Дар амал мо бо чунин системахо машгул мешавем.
Алгоритми Paxos мушкилоти консенсусро ҳал мекунад
як оилаи алгоритмҳоест, ки масъалаи консенсусро барои системаҳои қисман синхронӣ ҳал мекунанд, бо назардошти эҳтимолияти нокомии баъзе гиреҳҳо. Муаллифи Paxos аст . Вай дар соли 1989 далели расмии мавҷудият ва дурустии алгоритмро пешниҳод кард.
Аммо далели он аз ночизӣ дур буд. Нашри аввал танҳо дар соли 1998 (33 саҳифа), ки алгоритмро тавсиф мекунад, нашр шуд. Тавре маълум шуд, фаҳмидани он ниҳоят мушкил буд ва дар соли 2001 шарҳи мақола нашр шуд, ки 14 саҳифаро дар бар мегирад. Ҳаҷми нашрияҳо барои нишон додани он оварда шудааст, ки дар асл масъалаи консенсус умуман оддӣ нест ва дар паси чунин алгоритмҳо миқдори зиёди кори одамони донотарин меистад.
Ҷолиб он аст, ки худи Лесли Лэмпорт дар лексияи худ қайд кардааст, ки дар мақолаи дуюми шарҳӣ як изҳорот, як сатр мавҷуд аст (ӯ мушаххас накардааст, ки кадоме аз онҳост), ки онро бо тарзҳои гуногун шарҳ додан мумкин аст. Ва аз ин сабаб, шумораи зиёди татбиқҳои муосири Paxos комилан дуруст кор намекунанд.
Таҳлили муфассали кори Paxos зиёда аз як мақоларо дар бар мегирад, бинобар ин ман кӯшиш мекунам, ки идеяи асосии алгоритмро ба таври мухтасар баён кунам. Дар истинодҳое, ки дар охири мақолаи ман ҷойгиранд, шумо барои ғарқ кардани минбаъдаи ин мавзӯъ мавод пайдо мекунед.
Нақшҳо дар Paxos
Алгоритми Paxos мафҳуми нақшҳоро дорад. Биёед се чизи асосиро дида бароем (тағирот бо нақшҳои иловагӣ мавҷуданд):
- Пешниҳодкунандагон (ин истилоҳҳо метавонанд истифода шаванд: роҳбарон ё ҳамоҳангсозон). Инҳо бачаҳо ҳастанд, ки аз корбар арзиши навро меомӯзанд ва нақши пешворо ба ӯҳда мегиранд. Вазифаи онҳо ин аст, ки як даври пешниҳодҳо барои арзиши нав ва ҳамоҳангсозии амалиёти минбаъдаи гиреҳҳо. Ғайр аз он, Paxos имкон медиҳад, ки дар ҳолатҳои муайян ҳузури якчанд роҳбарон дошта бошанд.
- Қабулкунандагон (интихобкунандагон). Ин гиреҳҳое мебошанд, ки барои қабул ё рад кардани арзиши мушаххас овоз медиҳанд. Нақши онҳо хеле муҳим аст, зеро тасмим аз онҳо вобаста аст: система пас аз марҳилаи навбатии алгоритми консенсус ба кадом ҳолат мегузарад (ё намехоҳад).
- Донишҷӯён. Гиреҳҳое, ки ҳангоми тағир ёфтани ҳолати система арзиши нави қабулшударо қабул мекунанд ва менависанд. Онҳо қарор қабул намекунанд, онҳо танҳо маълумотро мегиранд ва метавонанд онро ба корбари ниҳоӣ диҳанд.
Як гиреҳ метавонад якчанд нақшҳоро дар ҳолатҳои гуногун муттаҳид созад.
Консепсияи кворум
Мо тахмин мезанем, ки мо системаи N гиреҳҳо Ва аз онҳо ҳадди аксар F гиреҳҳо метавонанд ноком шаванд. Агар гиреҳҳои F ноком шаванд, мо бояд ҳадди аққал дошта бошем 2F+1 гиреҳҳои қабулкунанда.
Ин барои он зарур аст, ки мо ҳамеша аксарият, ҳатто дар бадтарин вазъият гиреҳҳои «хуб»-ро дошта бошем, ки дуруст кор мекунанд. Яъне F+1 гиреҳҳои "хуб", ки мувофиқат карданд ва арзиши ниҳоӣ қабул карда мешавад. Дар акси хол чунин вазъияте ба миён меояд, ки гуруххои гуногуни махаллии мо маънохои гуногунро ба худ гирифта, байни худ созиш карда наметавонанд. Аз ин рӯ, мо бояд аксарияти мутлақи овозҳоро ба даст орем.
Идеяи умумӣ дар бораи чӣ гуна кор кардани алгоритми консенсуси Paxos
Алгоритми Paxos ду марҳилаи калонро дар бар мегирад, ки дар навбати худ ба ду марҳила тақсим мешаванд:
- Марҳилаи 1а: Тайёр кунед. Дар марҳилаи омодагӣ роҳбар (пешниҳодкунанда) ба ҳама гиреҳҳо хабар медиҳад: «Мо марҳилаи нави овоздиҳиро оғоз мекунем. Мо даври нав дорем. Шумораи ин давра n аст. Ҳоло мо ба овоздиҳӣ шурӯъ мекунем." Ҳоло он танҳо дар бораи оғози давраи нав хабар медиҳад, аммо арзиши навро гузориш намедиҳад. Вазифаи ин марҳила оғоз кардани даври нав ва огоҳ кардани рақами беназири он аст. Рақами давр муҳим аст, он бояд аз ҳама рақамҳои овоздиҳии қаблии ҳамаи пешвоёни қаблӣ арзише бошад. Зеро маҳз ба шарофати рақами мудаввар, гиреҳҳои дигари система дарк хоҳанд кард, ки маълумоти пешво то чӣ андоза нав аст. Эҳтимол дорад, ки гиреҳҳои дигар аллакай натиҷаҳои овоздиҳиро аз давраҳои хеле дертар доранд ва танҳо ба пешво мегӯянд, ки ӯ аз замонҳо ақиб мондааст.
- Марҳилаи 1b: Ваъда. Вақте ки гиреҳҳои қабулкунанда рақами марҳилаи нави овоздиҳиро гирифтанд, ду натиҷа имконпазир аст:
- Шумораи n овози нав аз шумораи овозҳои қаблӣ, ки дар он қабулкунанда иштирок кардааст, зиёдтар аст. Сипас қабулкунанда ба пешво ваъда медиҳад, ки дар дигар овозҳо бо шумораи камтар аз n иштирок намекунад. Агар қабулкунанда аллакай барои чизе овоз дода бошад (яъне дар марҳилаи дуюм аллакай як арзишро қабул карда бошад), пас ба ваъдаи худ арзиши қабулшуда ва шумораи овозҳое, ки дар он иштирок кардааст, замима мекунад.
- Дар акси ҳол, агар қабулкунанда аллакай дар бораи овоздиҳии баландтар маълумот дошта бошад, он метавонад ба қадами омодагӣ беэътиноӣ кунад ва ба пешво ҷавоб надиҳад.
- Марҳилаи 2а: Қабул. Раҳбар бояд посухи кворумро интизор шавад (аксарияти гиреҳҳои система) ва агар шумораи зарурии ҷавобҳо гирифта шавад, пас ӯ ду имкони рушди рӯйдодҳоро дорад:
- Баъзе аз қабулкунандагон арзишҳоеро фиристоданд, ки онҳо аллакай ба онҳо овоз додаанд. Дар ин ҳолат, роҳбар арзишро аз овоз бо шумораи ҳадди аксар интихоб мекунад. Биёед ин арзишро x номида, он ба ҳамаи гиреҳҳо паёме мефиристад: "Қабул (n, x)", ки арзиши аввал рақами овоздиҳӣ аз қадами пешниҳоди худ аст ва арзиши дуюм он чизест, ки ҳама барои он ҷамъ омадаанд, яъне. арзише, ки мо воқеан барои он овоз медиҳем.
- Агар ҳеҷ яке аз қабулкунандагон ягон арзиш нафиристоданд, аммо онҳо танҳо ваъда доданд, ки дар ин давр овоз медиҳанд, роҳбар метавонад онҳоро барои овоздиҳӣ барои арзиши онҳо, ки дар ҷои аввал пешво шуд, даъват кунад. Биёед онро y меномем. Он ба ҳама гиреҳҳо паём мефиристад: "Қабул кунед (n, y)", монанд ба натиҷаи қаблӣ.
- Марҳилаи 2b: Қабул карда шудааст. Ғайр аз он, гиреҳҳои қабулкунанда пас аз гирифтани паёми "Қабул (...)" аз роҳбар, бо он розӣ мешаванд (ба ҳама гиреҳҳо тасдиқ мекунанд, ки онҳо бо арзиши нав розӣ ҳастанд) танҳо дар сурате, ки онҳо ба баъзе (дигар) ваъда надодаанд) ) пешво барои иштирок кардан дар овоздихй бо ракамхои рау- н' > Н, дар акси ҳол онҳо дархости тасдиқро нодида мегиранд.
Агар аксарияти гиреҳҳо ба пешво ҷавоб дода бошанд ва ҳамаи онҳо арзиши навро тасдиқ кунанд, пас арзиши нав қабулшуда ҳисобида мешавад. Ура! Агар ба аксарият ноил нашаванд ё гиреҳҳое вуҷуд дошта бошанд, ки арзиши навро қабул накарданд, ҳама чиз аз нав оғоз меёбад.
Алгоритми Paxos ҳамин тавр кор мекунад. Ҳар яке аз ин марҳилаҳо нозукиҳои зиёд доранд, мо амалан намудҳои гуногуни нокомиҳо, мушкилоти пешвоёни сершумор ва ғайраро баррасӣ накардаем, аммо ҳадафи ин мақола танҳо муаррифии хонанда ба ҷаҳони компютерҳои тақсимшуда дар сатҳи баланд аст.
Инчунин бояд қайд кард, ки Paxos ягона намуди он нест, алгоритмҳои дигар мавҷуданд, масалан, , аммо ин мавзӯъ барои мақолаи дигар аст.
Истинодҳо ба маводҳо барои омӯзиши минбаъда
Сатҳи ибтидоӣ:
- , Преэти Касиредди, мақолаи блог дар Medium
- , Ади Канчерла, мақолаи блог дар Medium
- , Ittai Abraham, блог
- , Ittai Abraham, мақолаи блог
Сатҳи Лесли Лэмпорт:
- , Фишер, Линч ва Патерсон, мақолаи тадқиқотӣ, 1985
- , Лесли Лампорт, мақолаи тадқиқотӣ, 1998
- , Лесли Лампорт, мақолаи тадқиқотӣ, 2001
Манбаъ: will.com