Ji ber vê yekê, em xeyal bikin. Di jûreyê de 5 pisîk girtî ne, ji bo ku herin xwediyê xwe şiyar bikin, hewce ne ku hemî di nav xwe de li ser vê yekê li hev bikin, ji ber ku ew tenê dikarin derî vekin ku pênc ji wan pişta xwe bidin derî. Ger yek ji pisîkan pisîka Schrödinger be, û pisîkên din ji biryara wî nizanibin, ev pirs derdikeve holê: "Ew çawa dikarin wiya bikin?"
Di vê gotarê de, ez ê di derheqê pêkhateya teorîkî ya cîhana pergalên belavbûyî û prensîbên xebata wan de bi gotinên hêsan vebêjim. Di heman demê de ez ê ramana sereke ya ku di binê Paxos de ye jî bi awayekî rûpî binirxînim.
Gava ku pêşdebir binesaziyên ewr, databasên cihêreng, û di komikên hejmareke mezin a nokan de dixebitin bikar tînin, ew pêbawer in ku dê dane temam, ewledar û her gav berdest bin. Lê garantî li ku ne?
Di bingeh de, garantiyên ku me hene, garantiyên dabînker in. Ew di belgeyê de wiha têne diyar kirin: "Ev karûbar pir pêbawer e, SLA-ya wê heye, netirsin, her tişt dê wekî ku hûn hêvî dikin bi belavkirinê bixebitin."
Em bi ya herî baş bawer dikin, ji ber ku zilamên jîr ên ji pargîdaniyên mezin ji me re piştrast kirin ku dê her tişt baş be. Em vê pirsê napirsin: çima, bi rastî, ev dikare bi tevahî bixebite? Ma hincetek fermî ji bo xebata rast a pergalên weha heye?
Ez vê dawiyê çûm û ji vê mijarê pir inspired bû. Dersên li dibistanê ji tiştên ku bi pergalên komputerê ve girêdayî ne bêtir mîna dersên hesabkirinê bûn. Lê bi vî rengî algorîtmayên herî girîng ên ku em her roj bikar tînin, bêyî ku em pê zanibin, bi yek carî îsbat kirin.
Piraniya pergalên belavbûyî yên nûjen algorîtmaya lihevhatina Paxos û guheztinên wê yên cihêreng bikar tînin. Tiştê herî xweş ev e ku rastbûn û, di prensîbê de, pir îhtîmala hebûna vê algorîtmê bi tenê bi pênûs û kaxezek were îsbat kirin. Di pratîkê de, algorîtma di pergalên mezin de tê bikar anîn ku li ser hejmareke mezin girêkên di ewran de dixebitin.
Nîşanek sivik a tiştê ku dê paşê were nîqaş kirin: peywira du generalanKa em ji bo germkirinê binihêrin .
Du artêşên me hene - sor û spî. Leşkerên spî li bajarê dorpêçkirî ne. Leşkerên Sor bi serokatiya generalên A1 û A2 li du aliyên bajêr hene. Erka sorên sor ew e ku êrîşî bajarê spî bikin û bi ser bikevin. Lêbelê, artêşa her generalek sor bi serê xwe ji artêşa spî piçûktir e.
Şertên serketinê ji bo yên sor: divê her du general di heman demê de êrîş bikin da ku li ser spîyan xwedî avantajek hejmarî bin. Ji bo vê yekê, generalên A1 û A2 hewce ne ku bi hev re li hev bikin. Ger her kes ji hev cuda êrîş bike, dê sorên sor winda bikin.
Ji bo lihevkirinekê, generalên A1 û A2 dikarin bi rêya xaka bajarê spî ji hev re peyamnêran bişînin. Dibe ku qasid bi serfirazî bigihîje generalek hevalbend an jî ji hêla dijmin ve were girtin. Pirs: gelo di navbera generalên por sor de rêzek pêwendiyek wusa heye (rêza şandina peyamnêran ji A1 bo A2 û berevajî ji A2 bo A1), ku tê de garantî heye ku ew li ser êrîşek demjimêr X li hev bikin. Li vir, garantî tê vê wateyê ku her du general dê xwediyê piştrastiyek nezelal bin ku hevalbendek (generalek din) dê teqez di dema destnîşankirî X de êriş bike.
Bifikirin ku A1 peyamnêrek ji A2 re bişîne: "Werin em îro nîvê şevê êrîş bikin!" General A1 bêyî pejirandina General A2 nikare êrîş bike. Ger peyamnêrê A1 hatibe, wê hingê General A2 bi peyamê piştrast dike: "Erê, em îro spîyan bikujin." Lê niha General A2 nizane ka qasidê wî hatiye yan na, garantiya wî tune ku êrîş dê hemwext be. Naha General A2 dîsa hewceyê pejirandinê ye.
Ger em pêwendiya wan hîn bêtir rave bikin, diyar dibe ku çiqas çerxên pevguhertina peyaman hebin jî, bi tu awayî garantî tune ku her du generalan peyamên xwe wergirtine (bihesibînin ku her yek ji qasid dikare were girtin).
Pirsgirêka Du Generalan nîgarek mezin a pergalek belavkirî ya pir hêsan e ku tê de du girêk bi danûstendina nebawer hene. Ev tê vê wateyê ku em 100% garantiyek tune ku ew hevdemkirî ne. Pirsgirêkên bi vî rengî tenê di asteke mezintir de paşê di gotarê de têne nîqaş kirin.
Em têgeha pergalên belavbûyî destnîşan dikin
Pergala belavbûyî komek ji komputeran e (li vir em ê ji wan re bibêjin nod) ku dikarin peyaman biguhezînin. Her girêkek kesane celebek hebûnek xweser e. Nodek dikare bi serê xwe peywiran bişopîne, lê ji bo ku bi girêkên din re têkilî dayne, pêdivî ye ku ew peyaman bişîne û bistîne.
Mesaj tam çawa têne bicîh kirin, çi protokol têne bikar anîn - ev di vê çarçoveyê de ji me re ne eleqedar e. Girîng e ku girêkên pergalek belavbûyî bi şandina peyaman bi hev re daneyan biguherînin.
Pênas bi xwe pir tevlihev xuya nake, lê divê em vê yekê bihesibînin ku pergalek belavbûyî çend taybetmendiyên ku dê ji me re girîng bin hene.
Taybetmendiyên pergalên belavkirî
- Têkilî - îhtîmala ku bûyerên hevdem an hevdem di pergalê de diqewimin. Wekî din, em ê bûyerên ku li ser du girêkên cûda diqewimin wekî potansiyela hevdemî bihesibînin heya ku me rêzek zelal a rûdana van bûyeran tune be. Lê, wekî qaîdeyek, em wê tune.
- Saeta gerdûnî tune. Ji ber nebûna saeta gerdûnî rêgezeke me ya zelal a bûyeran nîne. Di cîhana asayî ya mirovan de, em bi vê yekê aciz in ku demjimêr û dem bi tevahî me hene. Dema ku ew tê pergalên belavkirî her tişt diguhere. Tewra demjimêrên atomî yên pir-rast jî diherikin, û dibe ku rewş hebin ku em nikaribin bibêjin kîjan ji du bûyeran pêşî qewimî. Ji ber vê yekê em nikarin xwe bispêrin demê jî.
- Têkçûna serbixwe ya girêkên pergalê. Pirsgirêkek din jî heye: tiştek dikare xelet bibe ji ber ku girêkên me herheyî nadomin. Dibe ku dîska hişk têk biçe, makîneya virtual ya di ewr de ji nû ve dest pê bike, dibe ku tor bişewitîne û peyam winda bibin. Wekî din, dibe ku rewş hebin ku nod dixebitin, lê di heman demê de li dijî pergalê dixebitin. Çîna dawîn a pirsgirêkan jî navek cuda wergirt: pirsgirêk . Mînaka herî populer a pergala belavkirî ya bi vê pirsgirêkê re Blockchain e. Lê îro em ê vê çîna taybetî ya pirsgirêkan nebînin. Em ê bala xwe bidin rewşên ku tê de tenê yek an çend girêk dikarin têk biçin.
- Modelên ragihandinê (modelên peyaman) di navbera nodes. Me berê destnîşan kir ku girêk bi pevguhertina peyaman re têkilî daynin. Du modelên ragihandinê yên naskirî hene: hevdem û asynkron.
Modelên danûstendinê di navbera girêkan de di pergalên belavbûyî de
Modela hevdem - em bi teqez dizanin ku deltayek demkî ya naskirî ya bêdawî heye ku tê de peyamek garantî ye ku bigihîje girêkek din. Ger ev dem derbas bûbe û peyam nehatibe, em dikarin bi ewlehî bibêjin ku girêk têk çûye. Di vê modelê de me demên bendê yên pêşbînîkirî hene.
Modela Asynchronous - Di modelên asynkron de em dihesibînin ku dema li bendê bi dawî ye, lê deltayek wusa ya ku piştî wê em dikarin garantî bikin ku girêk têk çûye tune. Ewan. Demjimêra li benda peyamek ji girêkek dikare bi kêfî dirêj be. Ev pênase girîng e, û em ê bêtir li ser biaxivin.
Têgeha lihevhatinê di pergalên belavbûyî de
Berî ku bi fermî têgeha lihevhatinê diyar bike, em mînakek rewşek ku em pê hewce ne, binihêrin - Replication Machine Dewletê.
Çend logên me yên belavkirî hene. Em dixwazin ku ew li ser hemî girêkên pergala belavkirî hevgirtî be û daneyên yeksan hebe. Dema ku yek ji girêkan nirxek nû ya ku ew ê li têketinê binivîsîne fêr dibe, peywira wê dibe ku vê nirxê pêşkêşî hemî girêkên din bike da ku têketin li ser hemî girêkan were nûve kirin û pergal berbi rewşek hevgirtî ya nû ve diçe. Di vê rewşê de, girîng e ku girêk di nav xwe de li hev bikin: hemî girêk li hev dikin ku nirxa nû ya pêşniyarkirî rast e, hemî girêk vê nirxê qebûl dikin, û tenê di vê rewşê de her kes dikare nirxa nû li têketinê binivîsîne.
Bi gotinek din: yek ji girêkan îtiraz nekir ku ew agahdariya bêtir têkildar heye, û nirxa pêşniyar xelet bû. Peymana di navbera girêkan û peymana li ser yek nirxek pejirandî ya rast di pergalek belavkirî de lihevhatinek e. Dûv re, em ê li ser algorîtmayên ku destûrê didin pergalek belavkirî garantî bikin ku bigihîje lihevkirinê biaxivin.
Bi awayekî fermîtir, em dikarin algorîtmayek lihevkirinê (an bi tenê algorîtmayek lihevkirinê) wekî fonksiyonek diyar a ku pergalek belavbûyî ji rewşa A vediguhezîne rewşa B, pênase bikin. Wekî din, ev rewş ji hêla hemî girêkan ve tê pejirandin, û hemî girêk dikarin wê piştrast bikin. Wekî ku dixuye, ev peywir bi qasî ku di nihêrîna pêşîn de xuya dike ne ew qas piçûk e.
Taybetmendiyên Algorîtmaya Lihevkirinê
Pêdivî ye ku algorîtmaya lihevhatinê sê taybetmendî hebe da ku pergal hebûna xwe bidomîne û di veguheztina ji dewletek bo dewletek de hin pêşkeftinek hebe:
- Lihevhatin - Pêdivî ye ku hemî girêkên ku bi rengek rast dixebitin heman nirxê bigirin (di gotaran de ev taybetmendî wekî taybetmendiya ewlehiyê jî tê binav kirin). Hemî girêkên ku niha kar dikin (bi yên din re têk neçûne an têkiliya xwe winda nekirine) divê li hev bikin û hin nirxa hevpar a dawîn qebûl bikin.
Girîng e ku li vir were fam kirin ku girêkên di pergala belavbûyî de ku em difikirin dixwazin li hev bikin. Ango, em niha behsa pergalên ku tê de tiştek bi hêsanî dikare têk biçe (mînak, hin girêk têk diçe), lê di vê pergalê de bê guman girêkên ku bi qestî li dijî yên din dixebitin tune ne (karê generalên Bîzansî). Ji ber vê taybetmendiyê, pergalê domdar dimîne.
- Linavketinî - Heke hemî nodên karên rast bi heman nirxê pêşkêş dikin v, ku tê vê wateyê ku her girêkek rast ku kar dike divê vê nirxê qebûl bike v.
- Xelasî - Hemî girêkên ku bi rêkûpêk dixebitin dê di dawiyê de hin nirxek (malbata zindîbûnê) bistînin, ku destûrê dide algorîtmayê ku di pergalê de pêşkeftinê çêbike. Pêdivî ye ku her ferdek bi rêkûpêk girêk zû an dereng nirxa paşîn qebûl bike û wê piştrast bike: "Ji bo min, ev nirx rast e, ez bi tevahî pergalê re razî me."
Mînakek ku çawa algorîtmaya lihevhatinê dixebite
Dema ku taybetmendiyên algorîtmê dibe ku bi tevahî zelal nebin. Ji ber vê yekê, em ê bi mînakek ronî bikin ka algorîtmaya lihevhatinê ya herî hêsan di pergalek bi modela peyamsaziya hevdemî de di kîjan qonaxê re derbas dibe, ku tê de hemî girêk wekî ku tê hêvî kirin tevdigerin, peyam winda nabin û tiştek naqede (ev bi rastî diqewime?).
- Her tişt bi pêşniyara zewacê (Pêşniyar) dest pê dike. Ka em bihesibînin ku xerîdarek bi girêkek bi navê "Node 1" ve girêdaye û dest bi danûstendinek kir, nirxek nû ji nodê re derbas kir - O. Ji nuha û pê ve, em ê gazî "Node 1" bikin. pêşnîyar. Wekî pêşniyarek, "Node 1" naha divê tevahiya pergalê agahdar bike ku daneyên nû hene, û ew ji hemî girêkên din re peyaman dişîne: "Binêre! Wateya "O" ji min re hat û ez dixwazim binivîsim! Ji kerema xwe piştrast bikin ku hûn ê "O" jî di têketina xwe de tomar bikin."
- Qonaxa paşîn dengdana ji bo nirxa pêşniyarkirî ye (Dengbêjî). Ji bo çi ye? Dibe ku biqewime ku girêkên din agahdariya nûtirîn wergirtine, û daneyên wan li ser heman danûstendinê hene.
Dema ku node "Node 1" pêşniyara xwe dişîne, girêkên din ji bo daneyên li ser vê bûyerê têketinên xwe kontrol dikin. Ger nakokî tune bin, girêkan wiha radigihînin: “Belê, ji bo vê bûyerê ti daneyên min ên din tune. Nirxa "O" agahdariya herî dawî ye ku em heq dikin."Di rewşek din de, girêk dikarin bersiva "Node 1" bidin: "Guhdarî bikin! Li ser vê danûstendinê bêtir daneyên min hene. Ne 'O', lê tiştek çêtir e."
Di qonaxa dengdanê de, girêk digihîjin biryarekê: an ew hemî heman nirxê qebûl dikin, an yek ji wan li dijî deng dide, ku nîşan dide ku daneyên wî yên nûtir hene.
- Ger gera dengdanê serketî bû û her kes alîgir bû, wê demê pergal berbi qonaxek nû ve diçe - Qebûlkirina nirxê. "Node 1" hemî bersivên ji girêkên din berhev dike û radigihîne: "Her kes li ser nirxa "O" li hev kir! Naha ez bi fermî radigihînim ku "O" wateya meya nû ye, ji bo her kesî yek e! Di pirtûka xweya piçûk de binivîsin, ji bîr nekin. Di qeyda xwe de binivîse!”
- Girêkên mayî tesdîqê dişînin (Qebûl kirin) ku wan nirxa "O" nivîsandine; di vê demê de tiştek nû nehatiye (cûreyek pêkanîna du qonax). Piştî vê bûyera girîng, em difikirin ku danûstendina belavkirî qediyaye.
Bi vî rengî, algorîtmaya lihevhatinê di rewşek hêsan de ji çar gavan pêk tê: pêşniyar kirin, dengdan (dengdan), qebûl kirin (qebûl kirin), pejirandin (qebûl kirin).
Ger di gavekê de me nikarîbû bigihêjin peymanê, wê hingê algorîtma dîsa dest pê dike, li gorî agahdariya ku ji hêla girêkên ku red kirine ku nirxa pêşniyar piştrast bikin têne peyda kirin.
Di pergalek asynchronous de algorîtmaya lihevhatinê
Beriya vê, her tişt xweş bû, ji ber ku me li ser modelek peyamsaziya hevdem dipeyivî. Lê em dizanin ku di cîhana nûjen de em bi kar tînin ku her tiştî bi asynkronî bikin. Çawa algorîtmayek wekhev di pergalek bi modela peyamsaziya asynchronous de dixebite, li ku derê em bawer dikin ku dema benda bersivek ji girêkek bi kêfî dirêj dibe (bi awayê, têkçûna girêk jî dikare wekî mînakek were hesibandin dema ku nodek dikare ji bo demek dirêj bi kêfî bersiv bide).
Naha ku em dizanin ku algorîtmaya lihevhatinê bi prensîbê çawa dixebite, pirsek ji bo wan xwendevanên lêkolîner ên ku heya nuha gihîştine vê yekê: çend girêk di pergalek N girêkên bi modela peyama asynchronous de dikarin têk biçin da ku pergal hîn jî bigihîje lihevkirinê?
Bersiva rast û hincet li pişt spoilerê ne.Bersiv rast e: 0. Ger di pergalek asynkron de yek girêk jî têk biçe, dê pergal nikaribe bigihîje lihevkirinê. Ev gotin di teorema FLP-ê de, ku di hin derdoran de navdar e (1985, Fischer, Lynch, Paterson, di dawiya gotarê de bi orîjînalê ve girêdide) de tê îspat kirin: "Ne gengaz e ku meriv bigihîje lihevhatinek belavkirî heke bi kêmanî yek nodek têk biçe. .
GUYS, hingê pirsgirêkek me heye, em ji her tiştî asynchronous re têne bikar anîn. Û va ye. Çawa berdewamkirina jiyanê?
Me tenê li ser teoriyê, li ser matematîkê dipeyivî. Wateya "lihevhatin nayê bidestxistin" tê çi wateyê, wergerandina ji zimanê matematîkî li zimanê me - endezyariyê? Ev tê wê wateyê ku "her gav nayên bidestxistin", ango. Bûyerek heye ku lihevhatinek pêk nayê. Ev çi halet e?
Ev tam binpêkirina milkê jîyanê ye ku li jor hatî destnîşan kirin. Lihevhatinek me ya hevpar tune, û pergal nikare pêşkeftinek hebe (nikare di demek bêdawî de biqede) di doza ku em bersivek ji hemî girêkan wernegirin. Ji ber ku di pergalek asynkron de dema me ya bersivdayînê ya pêşbînîkirî tune ye û em nikarin zanibin ka nodek têkçûye an tenê demek dirêj digire ku bersivê bide.
Lê di pratîkê de em dikarin çareseriyekê bibînin. Bila algorîtmaya me di rewşek têkçûn de bikaribe demek dirêj bixebite (bi potansiyel ew dikare bêdawî bixebite). Lê di pir rewşan de, dema ku pir girêk bi rêkûpêk tevdigerin, em ê di pergalê de pêşkeftinek hebe.
Di pratîkê de, em bi modelên ragihandinê yên qismî hevdem re mijûl dibin. Senkroniya qismî wiha tê fêmkirin: di rewşa giştî de, modelek me ya asynkron heye, lê têgehek diyar a "dema aramkirina gerdûnî" ya demek diyarkirî bi fermî tête destnîşan kirin.
Dibe ku ev dem ji bo demek dirêj neyê, lê divê rojek were. Dê demjimêra alarmê ya virtual zengil bike, û ji wê gavê ve em dikarin deltaya demjimêrê ya ku dê peyam werin pêşbînîkirin. Ji vê gavê û pê ve, pergal ji asynchronous vediguhere hemwext. Di pratîkê de, em bi pergalên bi vî rengî re mijûl dibin.
Algorîtmaya Paxos pirsgirêkên lihevhatinê çareser dike
malbatek algorîtmayan e ku pirsgirêka lihevhatinê ji bo pergalên qismî hevdemdar çareser dike, bi îhtîmala ku hin girêk têk biçin. Nivîskarê Paxos e . Wî di 1989 de delîlek fermî ya hebûn û rastbûna algorîtmayê pêşniyar kir.
Lê îspat derket ku ji sivikbûnê dûr bû. Weşana yekem tenê di sala 1998 de hate berdan (33 rûpel) ku algorîtmayê vedibêje. Wek ku xuya bû, ew pir dijwar bû ku têgihîştin, û di sala 2001 de ravekek gotarê hate weşandin, ku 14 rûpel girt. Hêjmara weşanan ji bo ku were destnîşan kirin ku bi rastî pirsgirêka lihevhatinê qet ne hêsan e, û li pişt van algorîtmayan xebatek pir mezin ji hêla mirovên herî jîr ve heye.
Balkêş e ku Leslie Lamport bi xwe jî di gotara xwe de destnîşan kir ku di gotara duyemîn a ravekirinê de yek gotinek, yek rêzek heye (wî diyar nekiriye ka kîjan), ku dikare bi awayên cûda were şîrove kirin. Û ji ber vê yekê, hejmareke mezin ji pêkanînên Paxos ên nûjen bi tevahî rast naxebitin.
Analîzek berfireh a xebata Paxos dê ji yek gotar zêdetir bigire, ji ber vê yekê ez ê hewl bidim ku pir bi kurtî ramana sereke ya algorîtmayê ragihînim. Di lînkên li dawiya gotara min de hûn ê materyalên ji bo vegerandina vê mijarê bibînin.
Rolên li Paxos
Algorîtmaya Paxos têgehek rolan heye. Ka em sê yên sereke bifikirin (guheztinên bi rolên zêde hene):
- Pêşniyar (şertan jî dikare were bikar anîn: serokên an koordînatoran). Ev zilam in ku ji bikarhêner hin nirxek nû fêr dibin û rola rêber digirin. Karê wan ew e ku ji bo nirxek nû dora pêşnîyaran bidin destpêkirin û kiryarên din ên girêkan hevrêz bikin. Wekî din, Paxos di hin rewşan de hebûna çend serokan destûr dide.
- Qebûlker (Dengdêr). Ev nod in ku deng didin pejirandin an redkirina nirxek taybetî. Rola wan pir girîng e, ji ber ku biryar bi wan ve girêdayî ye: pergal dê piştî qonaxa din a algorîtmaya lihevhatinê biçe kîjan dewletê (an na).
- Fêrker. Nodên ku dema ku rewşa pergalê guherî bi tenê nirxa pejirandî ya nû qebûl dikin û dinivîsin. Ew biryaran nagirin, ew tenê daneyan distînin û dikarin bidin bikarhênerê dawî.
Yek nod dikare di rewşên cûda de çend rolan li hev bike.
Têgeha quorum
Em texmîn dikin ku pergala me heye N nodes Û ji wan herî zêde F dibe ku nod têk biçin. Ger girêkên F têk biçin, wê hingê divê em bi kêmanî hebin 2F+1 girêkên qebûlker.
Ev pêdivî ye ku em her gav, di rewşa herî xirab de, piraniya girêkên "baş" ên ku rast dixebitin jî hebin. Ku heye F+1 girêkên "baş" ên ku li hev kirin, û nirxa paşîn dê were pejirandin. Wekî din, dibe ku rewşek çêbibe ku komên me yên herêmî wateyên cûda werbigirin û nikaribin di nav xwe de li hev bikin. Lewma ji bo bidestxistina dengan pêwîstiya me bi piraniya mitleq heye.
Fikra giştî ya ku çawa algorîtmaya lihevhatina Paxos dixebite
Algorîtmaya Paxos du qonaxên mezin pêk tîne, ku di encamê de her yek di du gavan de têne dabeş kirin:
- Qonaxa 1a: Amadekirin. Di qonaxa amadekariyê de, serkirde (pêşniyazkar) hemî girêkan agahdar dike: “Em dest bi qonaxek nû ya dengdanê dikin. Me dewreke nû heye. Hejmara vê dora n e. Niha em ê dest bi dengdanê bikin." Heya nuha, ew tenê destpêkirina çerxek nû radigihîne, lê nirxek nû rapor nake. Erka vê qonaxê ew e ku doreke nû bide destpêkirin û her kesî ji hejmara wê ya yekta agahdar bike. Hejmara dorê girîng e, divê ew nirxek ji hemî hejmarên dengdanê yên berê yên hemî serokên berê mezintir be. Ji ber ku bi saya jimareya dor e ku girêkên din ên pergalê dê fam bikin ku daneyên rêber çiqas nû ne. Ihtîmal e ku girêkên din berê xwedan encamên dengdanê yên ji dewreyên paşerojê ne û dê bi tenê ji rêber re bibêjin ku ew li paş deman e.
- Qonaxa 1b: Soz. Dema ku girêkên pejirandî hejmara qonaxa dengdanê ya nû wergirtin, du encam mimkun in:
- Hejmara n ya dengdana nû ji hejmara dengên berê yê ku qebûlker tê de beşdar bûye mezintir e. Paşê qebûlker sozekê ji serok re dişîne ku ew ê bi jimareyek ji n kêmtir beşdarî ti dengan nebe. Ger qebûlker berê dengê xwe daye tiştekî (ango di qonaxa duyemîn de jixwe hin nirx qebûl kiriye), wê demê nirxa pejirandî û hejmara dengên ku tê de beşdar bûye bi soza xwe ve girê dide.
- Wekî din, heke pejirandî jixwe di derbarê dengdana bi jimareya bilind de zanibe, ew dikare bi tenê gavê amadekariyê paşguh bike û bersivê nede rêber.
- Qonaxa 2a: Qebûl kirin. Pêdivî ye ku rêber li benda bersivek ji quorumê (piraniya girêkên pergalê) bimîne û, heke hejmara bersivên pêwîst were wergirtin, wê hingê ji bo pêşkeftina bûyeran du vebijarkên wî hene:
- Hin pejiran nirxên ku wan berê deng dabûn şandin. Di vê rewşê de, rêber nirxê ji dengdanê bi hejmara herî zêde hildibijêre. Werin em vê nirxê bi nav bikin x, û ew peyamek ji hemî girêkan re dişîne mîna: "Qebûl bike (n, x)", ku nirxa yekem hejmara dengdanê ye ji gava xweya Pêşniyarê, û nirxa duyemîn ew e ku her kes ji bo wê kom bûye, yanî nirxa ku em bi rastî deng didin.
- Ger yek ji qebûlkeran nirxek neşand, lê wan bi tenê soz da ku di vê dewrê de deng bidin, rêber dikare wan vexwîne ku dengê xwe bidin nirxa xwe, nirxa ku ew di rêza yekem de jê re bûye rêber. Em jê re bibêjin y. Ew ji hemî girêkan re peyamek dişîne mîna: "Qebûl (n, y)", mîna encama berê.
- Qonaxa 2b: Pejirandin. Wekî din, girêkên pejirandî, piştî ku peyama "Qebûl (...)" ji rêber werdigirin, bi wê re dipejirînin (teqezkirinê ji hemî girêkan re bişînin ku ew bi nirxa nû razî ne) tenê heke wan soz nedaye hin (yên din) ) serok bi jimareya dor beşdarî dengdanê bibe n' > n, wekî din ew daxwaznameya pejirandinê ji bîr dikin.
Ger piraniya girêkan bersivê bidin rêber, û hemî wan nirxa nû piştrast bikin, wê hingê nirxa nû qebûlkirî tê hesibandin. Hooray! Ger piraniyek negihîje an girêk hebin ku nirxa nû qebûl nekirine, wê hingê her tişt ji nû ve dest pê dike.
Bi vî rengî algorîtmaya Paxos dixebite. Her yek ji van qonaxan gelek hûrguliyên xwe hene, me bi pratîkî cûrbecûr têkçûn, pirsgirêkên gelek serokan û hêj bêtir li ber çavan negirt, lê mebesta vê gotarê tenê ew e ku xwendevan bi cîhana hesabkirina belavbûyî di astek bilind de bide nasîn.
Di heman demê de hêjayî gotinê ye ku Paxos ne tenê yek ji celebê xwe ye, algorîtmayên din jî hene, mînakî, , lê ev mijarek ji bo gotarek din e.
Girêdanên materyalên ji bo lêkolîna bêtir
Asta destpêkê:
- , Preethi Kasireddy, gotara blogê li ser Medium
- , Adi Kancherla, gotara blogê li ser Medium
- , Ittai Birahîm, blog
- , Ittai Birahîm, gotara blogê
Asta Leslie Lamport:
- , Fischer, Lynch and Paterson, kaxeza lêkolînê, 1985
- , Leslie Lamport, kaxeza lêkolînê, 1998
- , Leslie Lamport, kaxeza lêkolînê, 2001
Source: www.habr.com