Choncho, tiyeni tiyerekeze. Pali amphaka 5 otsekedwa m'chipindamo, ndipo kuti apite kudzutsa mwiniwakeyo, onse ayenera kugwirizana pa izi pakati pawo, chifukwa amatha kutsegula chitseko ndi asanu akutsamira. Ngati amphaka mmodzi ndi mphaka wa Schrödinger, ndipo amphaka ena sadziwa za chisankho chake, funso limakhala lakuti: "Kodi angachite bwanji?"
M'nkhaniyi, ndikuwuzani m'mawu osavuta za gawo lachidziwitso la dziko la machitidwe ogawidwa ndi mfundo za ntchito yawo. Ndilingaliranso mwachiphamaso lingaliro lalikulu lomwe lili Paxos.
Madivelopa akamagwiritsa ntchito zida zamtambo, ma database osiyanasiyana, ndikugwira ntchito m'magulu ambiri a node, amakhala ndi chidaliro kuti deta ikhala yathunthu, yotetezeka, komanso kupezeka nthawi zonse. Koma zitsimikizo zili kuti?
Kwenikweni, zitsimikizo zomwe tili nazo ndi zitsimikizo za ogulitsa. Zafotokozedwa m'malemba motere: "Ntchitoyi ndi yodalirika, ili ndi SLA yopatsidwa, musadandaule, zonse zigwira ntchito monga momwe mukuyembekezera."
Timakonda kukhulupirira zabwino kwambiri, chifukwa anyamata anzeru ochokera kumakampani akulu adatitsimikizira kuti zonse zikhala bwino. Sitikufunsa funso: chifukwa chiyani, kwenikweni, izi zitha kugwira ntchito konse? Kodi pali zifukwa zomveka zogwirira ntchito moyenera machitidwe otere?
Posachedwapa ndinapitako ndipo adalimbikitsidwa kwambiri ndi mutu uwu. Maphunziro a kusukulu anali ngati makalasi owerengetsera kusiyana ndi zina zokhudzana ndi makompyuta. Koma umu ndi momwe ma algorithms ofunikira kwambiri omwe timagwiritsa ntchito tsiku lililonse, osadziwa, adatsimikiziridwa nthawi imodzi.
Machitidwe amakono omwe amagawidwa amagwiritsa ntchito Paxos consensus algorithm ndi zosintha zake zosiyanasiyana. Chozizira kwambiri ndikuti kutsimikizika komanso, makamaka, kuthekera kwa kukhalapo kwa algorithm iyi kumatha kutsimikiziridwa ndi cholembera ndi pepala. M'malo mwake, ma algorithms amagwiritsidwa ntchito m'makina akuluakulu omwe akuyenda pama node ambiri m'mitambo.
Chitsanzo chopepuka cha zomwe tidzakambirane m'tsogolomu: ntchito ya akazembe awiriTiyeni tiwone za kutentha .
Tili ndi ankhondo awiri - ofiira ndi oyera. Asilikali oyera amakhala mumzinda wazingidwa. Asilikali ofiira otsogozedwa ndi akazembe A1 ndi A2 ali mbali ziwiri za mzindawo. Ntchito ya redheads ndikuukira mzinda woyera ndikupambana. Komabe, gulu lankhondo la kazembe aliyense wofiira payekhapayekha ndi locheperapo kuposa gulu lankhondo loyera.
Kupambana kwa ofiira: akuluakulu onse awiri ayenera kuukira nthawi imodzi kuti akhale ndi chiwerengero choposa azungu. Kuti achite izi, akuluakulu A1 ndi A2 ayenera kugwirizana. Ngati aliyense akuukira padera, redheads adzataya.
Kuti agwirizane, akuluakulu A1 ndi A2 amatha kutumiza amithenga kwa wina ndi mzake kudutsa dera la mzinda woyera. Mthengayo atha kufikira wamkulu wa gulu logwirizana kapena kulandidwa ndi mdani. Funso: kodi pali mndandanda wa mauthenga otere pakati pa akuluakulu a tsitsi lofiira (kutsatizana kwa kutumiza amithenga kuchokera ku A1 kupita ku A2 ndi mosemphanitsa kuchokera ku A2 kupita ku A1), momwe akutsimikiziridwa kuti avomereza kuukira pa ola la X. Pano, zitsimikizo zikutanthauza kuti akuluakulu onse awiri adzakhala ndi chitsimikizo chodziwika bwino kuti wothandizira (mkulu wina) adzaukiradi pa nthawi yoikika X.
Tiyerekeze kuti A1 itumiza mthenga kwa A2 ndi uthenga: "Tiyeni tiwukire lero pakati pausiku!" General A1 sangathe kuwukira popanda kutsimikiziridwa ndi General A2. Ngati mthenga wochokera ku A1 wafika, ndiye General A2 amatumiza chitsimikiziro ndi uthengawo: "Inde, tiyeni tiphe azungu lero." Koma tsopano General A2 sakudziwa ngati mthenga wake wafika kapena ayi, alibe chitsimikizo ngati kuukira kudzachitika nthawi imodzi. Tsopano General A2 ikufunikanso kutsimikiziridwa.
Tikapitiriza kufotokoza kulankhulana kwawo, zikuwonekeratu kuti ziribe kanthu kuti pali maulendo angati otumizirana mauthenga, palibe njira yotsimikizira kuti akuluakulu onse awiri alandira mauthenga awo (poganiza kuti mthenga akhoza kulandidwa).
Vuto la Awiri Awiri ndi fanizo lalikulu la dongosolo losavuta logawidwa pomwe pali ma node awiri omwe ali ndi kulumikizana kosadalirika. Izi zikutanthauza kuti tilibe chitsimikizo cha 100% kuti alumikizidwa. Mavuto ofananawo akukambidwa pamlingo waukulu pambuyo pake m’nkhaniyo.
Timayambitsa lingaliro la machitidwe ogawidwa
Dongosolo logawidwa ndi gulu la makompyuta (pambuyo pake tidzawatcha ma node) omwe amatha kusinthana mauthenga. Node iliyonse ndi mtundu wina wazinthu zodziyimira pawokha. Node imatha kukonza ntchito yokha, koma kuti ilumikizane ndi ma node ena, imayenera kutumiza ndi kulandira mauthenga.
Momwe mauthenga amagwiritsidwira ntchito, ndi ndondomeko ziti zomwe zimagwiritsidwa ntchito - izi sizosangalatsa kwa ife mu nkhaniyi. Ndikofunika kuti node za dongosolo logawidwa likhoza kusinthanitsa deta wina ndi mzake potumiza mauthenga.
Tanthauzo lenilenilo silikuwoneka lovuta kwambiri, koma tiyenera kuganizira kuti dongosolo logawidwa liri ndi makhalidwe angapo omwe adzakhala ofunika kwa ife.
Makhalidwe a machitidwe ogawidwa
- Chandalama - kuthekera kwa zochitika panthawi imodzi kapena nthawi imodzi zomwe zimachitika mu dongosolo. Komanso, tidzaona zochitika zomwe zimachitika pamagulu awiri osiyana kuti zikhale zofanana malinga ngati tilibe ndondomeko yomveka bwino ya zochitikazi. Koma, monga lamulo, tilibe.
- Palibe wotchi yapadziko lonse lapansi. Tilibe dongosolo lomveka bwino la zochitika chifukwa cha kusowa kwa wotchi yapadziko lonse lapansi. M’dziko la anthu wamba, tinazoloŵera kuti tili ndi mawotchi ndi nthaŵi ndithu. Chilichonse chimasintha pankhani yogawa machitidwe. Ngakhale mawotchi olondola kwambiri a atomiki amatha kusuntha, ndipo pangakhale zinthu zina zomwe sitingathe kudziwa kuti ndi iti mwa zinthu ziwiri zimene zinachitika poyamba. Choncho, sitingadalirenso nthawi.
- Kulephera kodziyimira pawokha kwa node zadongosolo. Palinso vuto lina: chinachake chikhoza kusokonekera chifukwa chakuti mfundo zathu sizikhalitsa. Chosungiracho chikhoza kulephera, makina enieni omwe ali mumtambo akhoza kuyambiranso, maukonde akhoza kuthwanima ndipo mauthenga adzatayika. Komanso, pakhoza kukhala zochitika zomwe node zimagwira ntchito, koma nthawi yomweyo zimagwira ntchito motsutsana ndi dongosolo. Gulu lomaliza lamavuto lidalandiranso dzina losiyana: vuto . Chitsanzo chodziwika kwambiri cha dongosolo logawidwa ndi vutoli ndi Blockchain. Koma lero sitingaganizire gulu lapaderali la mavuto. Tidzakhala ndi chidwi ndi zochitika zomwe mfundo imodzi kapena zingapo zingalephereke.
- Njira zoyankhulirana (zotumizirana mauthenga) pakati pa node. Takhazikitsa kale kuti ma node amalumikizana pogawana mauthenga. Pali mitundu iwiri yodziwika bwino ya mauthenga: synchronous ndi asynchronous.
Zitsanzo zoyankhulirana pakati pa node mu machitidwe ogawidwa
Synchronous model - tikudziwa motsimikiza kuti pali nthawi yodziwika yodziwika bwino yomwe uthenga umatsimikizika kuti ufika kuchokera ku mfundo imodzi kupita ku ina. Ngati nthawiyi yadutsa ndipo uthenga sunafike, tikhoza kunena kuti node yalephera. Muchitsanzo ichi tili ndi nthawi zodikira zodziwikiratu.
Asynchronous model - mu zitsanzo za asynchronous timaona kuti nthawi yodikirira ndi yomaliza, koma palibe delta ya nthawi yomwe tingathe kutsimikizira kuti node yalephera. Iwo. Nthawi yodikirira uthenga wochokera ku node ikhoza kukhala yayitali. Ili ndilo tanthauzo lofunika, ndipo tidzakambirana zambiri.
Lingaliro la mgwirizano mu machitidwe ogawidwa
Tisanafotokoze momveka bwino lingaliro la kuvomerezana, tiyeni tikambirane chitsanzo cha nthawi yomwe tikufunikira, monga - State Machine Replication.
Tili ndi chipika chogawidwa. Tikufuna kuti ikhale yosasinthasintha komanso ikhale ndi deta yofanana pamagulu onse a dongosolo logawidwa. Pamene imodzi mwa node ikuphunzira mtengo watsopano womwe udzalembera ku chipikacho, ntchito yake imakhala yopereka mtengo uwu ku ma node ena onse kuti chipikacho chisinthidwe pazitsulo zonse ndipo dongosololo limasunthira ku chikhalidwe chatsopano chokhazikika. Pankhaniyi, ndikofunikira kuti ma node agwirizane pakati pawo: ma node onse amavomereza kuti mtengo watsopano womwe waperekedwa ndi wolondola, ma node onse amavomereza mtengo uwu, ndipo pokhapokha aliyense atha kulemba mtengo watsopano ku chipikacho.
Mwa kuyankhula kwina: palibe node imodzi yomwe inatsutsa kuti ili ndi zambiri zowonjezera, ndipo mtengo woperekedwawo unali wolakwika. Mgwirizano pakati pa mfundo ndi mgwirizano pa mtengo umodzi wovomerezeka wovomerezeka ndi mgwirizano mu dongosolo logawidwa. Kenaka, tidzakambirana za ma aligorivimu omwe amalola dongosolo logawidwa kuti likwaniritse mgwirizano wotsimikizika.
Mwachidziwitso, tikhoza kufotokozera algorithm yogwirizana (kapena kungoti algorithm yogwirizana) monga ntchito inayake yomwe imasamutsa dongosolo logawidwa kuchokera ku boma A kupita ku boma B. Komanso, dziko ili likuvomerezedwa ndi mfundo zonse, ndipo mfundo zonse zimatha kutsimikizira. Monga momwe zikukhalira, ntchito imeneyi si yaing'ono monga momwe imawonekera poyamba.
Makhalidwe a Consensus Algorithm
Ma algorithm ogwirizana ayenera kukhala ndi zinthu zitatu kuti dongosololi lipitirire kukhalapo ndikupita patsogolo kuchokera kumayiko kupita kumayiko:
- Mgwirizano - malo onse ogwiritsira ntchito moyenera ayenera kutenga mtengo womwewo (m'nkhani zomwe katunduyu amatchulidwanso kuti chitetezo). Ma node onse omwe akugwira ntchito pakali pano (sanalephere kapena kutha kulumikizana ndi ena) ayenera kugwirizana ndikuvomereza mtengo wina wofanana.
Ndikofunika kumvetsetsa apa kuti ma node mu dongosolo logawidwa lomwe tikuliganizira likufuna kuvomereza. Ndiko kuti, tsopano tikukamba za machitidwe omwe chinachake chimatha kulephera (mwachitsanzo, mfundo zina zimalephera), koma m'dongosolo lino palibe mfundo zomwe zimagwira ntchito mwadala motsutsana ndi ena (ntchito ya akuluakulu a Byzantine). Chifukwa cha katundu uyu, dongosololi limakhalabe lokhazikika.
- Kukhulupirika - ngati ma node onse ogwira ntchito moyenera amapereka mtengo womwewo v, zomwe zikutanthauza kuti nodi iliyonse yogwira ntchito moyenera iyenera kuvomereza mtengowu v.
- Kutha - node zonse zogwira ntchito moyenera pamapeto pake zidzatenga mtengo wina (liveness katundu), zomwe zimalola kuti algorithm ipite patsogolo mu dongosolo. Munthu aliyense wogwiritsa ntchito molondola ayenera kuvomereza posakhalitsa mtengo wake ndikutsimikizira: "Kwa ine, mtengo uwu ndi wowona, ndikugwirizana ndi dongosolo lonselo."
Chitsanzo cha momwe ma algorithm ogwirizana amagwirira ntchito
Ngakhale katundu wa aligorivimu sangakhale omveka bwino. Choncho, tidzafotokozera ndi chitsanzo kuti ndi magawo ati omwe algorithm yosavuta yogwirizana imadutsa mu dongosolo lomwe lili ndi ndondomeko yotumizira mauthenga, momwe ma node onse amagwira ntchito monga momwe amayembekezera, mauthenga satayika ndipo palibe chomwe chimasweka (kodi izi zimachitikadi?).
- Zonse zimayamba ndi kufunsira ukwati (Propose). Tiyerekeze kuti kasitomala wolumikizidwa ku node yotchedwa "Node 1" ndikuyamba kugulitsa, ndikudutsa mtengo watsopano ku node - O. Kuyambira tsopano, tidzatcha "Node 1" kufunsira. Monga wofotokozera, "Node 1" iyenera kudziwitsa dongosolo lonse kuti ili ndi deta yatsopano, ndipo imatumiza mauthenga kuzinthu zina zonse: "Tawonani! Tanthauzo la "O" linabwera kwa ine ndipo ndikufuna kulilemba! Chonde tsimikizirani kuti mudzalembanso "O" mu chipika chanu."
- Gawo lotsatira ndikuvotera mtengo womwe waperekedwa (Kuvota). Ndi cha chiyani? Zitha kuchitika kuti ma node ena alandila zidziwitso zaposachedwa, ndipo ali ndi data pazochita zomwezo.
Node "Node 1" ikatumiza malingaliro ake, ma node ena amayang'ana zipika zawo kuti adziwe zambiri pamwambowu. Ngati palibe zotsutsana, ma node amalengeza kuti: "Inde, ndilibe chidziwitso china pamwambowu. Mtengo wa "O" ndi chidziwitso chaposachedwa chomwe tikuyenera.Mulimonsemo, ma node amatha kuyankha "Node 1": "Mverani! Ndili ndi zambiri zaposachedwa kwambiri pamalondawa. Osati 'O', koma china chake chabwino."
Pa voti, ma node amafika pachigamulo: mwina onse amavomereza mtengo womwewo, kapena mmodzi wa iwo amavotera, kusonyeza kuti ali ndi deta yaposachedwa.
- Ngati voti yozungulira inali yopambana ndipo aliyense anali kukomera, ndiye kuti dongosololi likupita kumalo atsopano - kuvomereza mtengo (Kuvomereza). "Node 1" imasonkhanitsa mayankho onse kuchokera ku mfundo zina ndikunena kuti: "Aliyense adagwirizana ndi mtengo" O "! Tsopano ndikulengeza kuti "O" ndi tanthauzo lathu latsopano, chimodzimodzi kwa aliyense! Lembani mu bukhu lanu laling'ono, musaiwale. Lembani mu chipika chanu!”
- Ma node otsalawo amatumiza chitsimikiziro (chovomerezedwa) kuti alemba mtengo "O"; palibe chatsopano chomwe chafika panthawiyi (mtundu wa magawo awiri). Pambuyo pa chochitika chofunikira ichi, tikuwona kuti ntchito yogawidwa yatha.
Choncho, algorithm yogwirizana mu nkhani yosavuta imakhala ndi masitepe anayi: perekani, kuvota (kuvota), kuvomereza (kuvomereza), kutsimikizira kuvomereza (kuvomerezedwa).
Ngati pa sitepe inayake sitinathe kumvana, ndiye kuti algorithm imayambanso, poganizira zomwe zaperekedwa ndi ma node omwe anakana kutsimikizira mtengo womwe waperekedwa.
Consensus algorithm mu asynchronous system
Izi zisanachitike, zonse zinali zosalala, chifukwa tinali kukamba za mtundu wa mauthenga osakanikirana. Koma tikudziwa kuti m'dziko lamakono timakonda kuchita zonse mosagwirizana. Kodi algorithm yofananira imagwira ntchito bwanji m'dongosolo lokhala ndi ma asynchronous messaging model, pomwe timakhulupirira kuti nthawi yodikirira kuyankha kuchokera ku node imatha kukhala yayitali mopanda malire (mwa njira, kulephera kwa node kungaganizidwenso ngati chitsanzo node imatha kuyankha kwa nthawi yayitali mosasamala).
Tsopano popeza tikudziwa momwe ma algorithm ogwirizana amagwirira ntchito mwadongosolo, funso kwa owerenga ofunsa omwe apanga izi: ndi ma node angati mu dongosolo la N node yokhala ndi ma asynchronous message model angalephere kuti dongosololi lithe kufikira mgwirizano?
Yankho lolondola ndi kulungamitsidwa ali kumbuyo wowononga.Yankho lolondola ndi lakuti: 0. Ngati ngakhale node imodzi mu dongosolo la asynchronous ikulephera, dongosololi silingathe kukwaniritsa mgwirizano. Mawu awa akutsimikiziridwa mu chiphunzitso cha FLP, chodziwika bwino m'magulu ena (1985, Fischer, Lynch, Paterson, kugwirizana ndi choyambirira kumapeto kwa nkhaniyo): "Kusatheka kukwaniritsa mgwirizano wogawidwa ngati mfundo imodzi yalephera. .”
Anyamata ndiye tili ndi vuto, tazolowera chilichonse kukhala chosasinthika. Ndipo ndi izi. Kodi kupitiriza kukhala ndi moyo?
Tinkangokamba za chiphunzitso, za masamu. Kodi "kuvomerezana sikutheka" kumatanthauza chiyani, kumasulira kuchokera ku chinenero cha masamu kupita ku chathu - engineering? Izi zikutanthauza kuti "sizingatheke nthawi zonse", i.e. Pali nkhani yomwe kuvomerezana sikutheka. Ndi mlandu wanji uwu?
Uku ndikuphwanya ndendende katundu wa liveness tafotokozazi. Tilibe mgwirizano wamba, ndipo dongosololi silingathe kupita patsogolo (sangathe kumaliza mu nthawi yomaliza) ngati tilibe yankho kuchokera ku mfundo zonse. Chifukwa mu dongosolo la asynchronous tilibe nthawi yodziwikiratu yoyankha ndipo sitingathe kudziwa ngati node yawonongeka kapena ikungotenga nthawi yaitali kuti iyankhe.
Koma m’zochita tingapeze yankho. Lolani ma algorithm athu azitha kugwira ntchito kwa nthawi yayitali ngati zitalephera (mwina zitha kugwira ntchito mpaka kalekale). Koma nthawi zambiri, ma node ambiri akamagwira ntchito moyenera, tidzakhala ndikupita patsogolo mudongosolo.
M'machitidwe, timachita ndi njira zolumikizirana pang'ono. Synchrony yapang'ono imamveka motere: nthawi zambiri, tili ndi chitsanzo chofanana, koma lingaliro lina la "nthawi yokhazikika yapadziko lonse" ya nthawi inayake imayambitsidwa.
Mphindi mu nthawi iyi sangabwere kwa nthawi yayitali, koma iyenera kubwera tsiku limodzi. Wotchi ya alamu idzalira, ndipo kuyambira nthawi imeneyo tikhoza kulosera nthawi yomwe mauthengawo adzafike. Kuyambira nthawi ino, dongosolo limatembenuka kuchoka ku asynchronous kupita ku synchronous. M'machitidwe, timachita ndi machitidwe oterowo.
Algorithm ya Paxos imathetsa mavuto ogwirizana
ndi gulu la ma aligorivimu omwe amathetsa vuto lachigwirizano pamakina osakanikirana pang'ono, malinga ndi kuthekera kuti mfundo zina zitha kulephera. Wolemba Paxos ndi . Adapereka umboni wotsimikizira kukhalapo ndi kulondola kwa algorithm mu 1989.
Koma umboniwo unali wochepa kwambiri. Kusindikiza koyamba kunatulutsidwa kokha mu 1998 (masamba 33) akufotokoza ndondomekoyi. Monga momwe zinalili, zinali zovuta kwambiri kumvetsetsa, ndipo mu 2001 kufotokozera nkhaniyo kunasindikizidwa, yomwe inatenga masamba 14. Kuchuluka kwa zofalitsa kumaperekedwa kuti asonyeze kuti kwenikweni vuto la mgwirizano silili lophweka, ndipo kumbuyo kwa ma aligorivimu amenewa kuli ntchito yaikulu ya anthu anzeru kwambiri.
N'zochititsa chidwi kuti Leslie Lamport mwiniwakeyo adanena m'nkhani yake kuti m'nkhani yachiwiri yofotokozera pali mawu amodzi, mzere umodzi (sanatchule kuti ndi uti), womwe ungatanthauzidwe m'njira zosiyanasiyana. Ndipo chifukwa cha izi, kuchuluka kwazinthu zamakono za Paxos sizigwira ntchito moyenera.
Kusanthula mwatsatanetsatane ntchito ya Paxos kungatenge nkhani yopitilira imodzi, kotero ndiyesera kufotokoza mwachidule lingaliro lalikulu la algorithm. Mu maulalo kumapeto kwa nkhani yanga mupeza zida zopititsira patsogolo pamutuwu.
Maudindo ku Paxos
Algorithm ya Paxos ili ndi lingaliro la maudindo. Tiyeni tikambirane zazikulu zitatu (pali zosintha ndi maudindo owonjezera):
- Othandizira (mawuwa angagwiritsidwenso ntchito: atsogoleri kapena ogwirizanitsa). Awa ndi anyamata omwe amaphunzira za mtengo wina watsopano kuchokera kwa wogwiritsa ntchito ndikutenga udindo wa mtsogoleri. Ntchito yawo ndikukhazikitsa malingaliro amtundu watsopano ndikugwirizanitsa zochita zina za node. Komanso, Paxos amalola kukhalapo kwa atsogoleri angapo nthawi zina.
- Ovomereza (Ovota). Awa ndi ma node omwe amavotera kuvomereza kapena kukana mtengo wake. Udindo wawo ndi wofunikira kwambiri, chifukwa chigamulocho chimadalira iwo: boma liti (kapena silingapite) pambuyo pa gawo lotsatira la algorithm yogwirizana.
- Ophunzira. Node zomwe zimangovomereza ndikulemba mtengo wovomerezeka watsopano pamene dongosolo lasintha. Samapanga zisankho, amangolandira deta ndipo akhoza kuipereka kwa wogwiritsa ntchito.
Node imodzi imatha kuphatikiza maudindo angapo munthawi zosiyanasiyana.
Lingaliro la quorum
Timaganiza kuti tili ndi ndondomeko N mfundo Ndipo a iwo ndi opambana F nodes akhoza kulephera. Ngati F node zalephera, ndiye kuti tiyenera kukhala nazo 2F+1 node zolandila.
Izi ndi zofunika kuti nthawi zonse tikhale ndi ambiri, ngakhale zinthu zovuta kwambiri, za "zabwino" mfundo zomwe zimagwira ntchito moyenera. Ndiko kuti F+1 "zabwino" mfundo zomwe zinagwirizana, ndipo mtengo womaliza udzalandiridwa. Kupanda kutero, pakhoza kukhala nthawi yomwe magulu athu osiyanasiyana amatengera matanthauzo osiyanasiyana ndipo sangagwirizane pakati pawo. Chifukwa chake, timafunikira anthu ambiri kuti tipambane mavoti.
Lingaliro wamba momwe Paxos consensus algorithm imagwirira ntchito
Paxos aligorivimu imaphatikizapo magawo awiri akulu, omwe amagawidwa m'magawo awiri:
- Gawo 1a: Konzekerani. Panthawi yokonzekera, mtsogoleri (wopereka malingaliro) amadziwitsa ma node onse kuti: "Tikuyamba gawo latsopano lovota. Tili ndi kuzungulira kwatsopano. Nambala ya round iyi ndi n. Tsopano tiyamba kuvota." Pakadali pano, imangonena za kuyambika kwa kuzungulira kwatsopano, koma silinena za mtengo watsopano. Ntchito ya siteji iyi ndikuyambitsa kuzungulira kwatsopano ndikudziwitsa aliyense za nambala yake yapadera. Nambala yozungulira ndiyofunikira, iyenera kukhala yamtengo wapatali kuposa manambala onse ovota am'mbuyomu ochokera kwa atsogoleri onse am'mbuyomu. Chifukwa ndi chifukwa cha chiwerengero chozungulira kuti ma node ena mu dongosolo adzamvetsetsa momwe deta ya mtsogoleriyo iliri posachedwa. Ndizotheka kuti ma node ena ali kale ndi zotsatira zovota pambuyo pake ndipo amangouza mtsogoleri kuti ali kumbuyo.
- Gawo 1b: Lonjezo. Pamene ma node ovomereza adalandira chiwerengero cha voti yatsopano, zotsatira ziwiri ndizotheka:
- Nambala n ya voti yatsopano ndi yaikulu kuposa chiwerengero cha voti iliyonse yam'mbuyo yomwe wovomereza adachita nawo. Ndiye wolandirayo amatumiza lonjezo kwa mtsogoleri kuti sadzachita nawo mavoti ena omwe ali ndi nambala yotsika kuposa n. Ngati wolandira wavotera kale chinachake (ndiko kuti, wavomereza kale phindu linalake mu gawo lachiwiri), ndiye amaphatikiza mtengo wovomerezeka ndi chiwerengero cha mavoti omwe adachita nawo lonjezo.
- Apo ayi, ngati wovomereza akudziwa kale za mavoti apamwamba, akhoza kungonyalanyaza sitepe yokonzekera ndikusayankha mtsogoleri.
- Gawo 2a: Landirani. Mtsogoleri ayenera kuyembekezera kuyankha kuchokera ku quorum (ma node ambiri mu dongosolo) ndipo, ngati chiwerengero chofunikira cha mayankho chilandiridwa, ndiye kuti ali ndi njira ziwiri zopangira zochitika:
- Ena mwa omwe adavomereza adatumiza zinthu zomwe adavotera kale. Pankhaniyi, mtsogoleri amasankha mtengo kuchokera pavoti ndi chiwerengero chachikulu. Tiyeni tiyitane mtengo uwu x, ndipo imatumiza uthenga ku ma node onse monga: "Landirani (n, x)", pomwe mtengo woyamba ndi nambala yovota kuchokera pagawo lake Longoyerekeza, ndipo mtengo wachiwiri ndi womwe aliyense wasonkhanitsira, i.e. mtengo womwe timavotera.
- Ngati palibe amene amavomereza adatumiza makhalidwe, koma adangolonjeza kuti adzavotera kuzungulira uku, mtsogoleriyo akhoza kuwaitana kuti avotere mtengo wawo, mtengo umene adakhala mtsogoleri poyamba. Tiyeni tizitcha y. Imatumiza uthenga ku ma node onse monga: "Landirani (n, y)", mofanana ndi zotsatira zam'mbuyo.
- Gawo 2b: Lalandiridwa. Komanso, mfundo zovomerezeka, atalandira uthenga wa "Landirani (...)" kuchokera kwa mtsogoleri, agwirizane nawo (tumizani chitsimikiziro ku mfundo zonse kuti akugwirizana ndi mtengo watsopano) pokhapokha ngati sanalonjeze (zina) ) mtsogoleri kutenga nawo gawo povota ndi nambala yozungulira n> n, apo ayi amanyalanyaza pempho lotsimikizira.
Ngati ma node ambiri adayankha mtsogoleriyo, ndipo onsewo adatsimikizira mtengo watsopano, ndiye kuti mtengo watsopanowo umatengedwa kuti ndi wovomerezeka. Uwu! Ngati ambiri sanafikire kapena pali mfundo zomwe zinakana kuvomereza mtengo watsopano, ndiye kuti zonse zimayamba.
Umu ndi momwe algorithm ya Paxos imagwirira ntchito. Iliyonse mwa magawowa ili ndi zobisika zambiri, sitinaganizire mitundu yosiyanasiyana ya zolephera, zovuta za atsogoleri angapo ndi zina zambiri, koma cholinga cha nkhaniyi ndikungodziwitsa owerenga kudziko lamakompyuta ogawidwa pamlingo wapamwamba.
Ndizoyeneranso kudziwa kuti Paxos si yokhayo yamtundu wake, pali ma aligorivimu ena, mwachitsanzo, , koma uwu ndi mutu wa nkhani ina.
Maulalo kuzinthu zophunzirira mopitilira
Mulingo woyambira:
- , Preethi Kasireddy, nkhani ya blog pa Medium
- , Adi Kancherla, nkhani ya blog pa Medium
- , Itai Abraham, blog
- , Itai Abraham, nkhani ya pabulogu
Leslie Lamport mlingo:
- , Fischer, Lynch ndi Paterson, pepala lofufuzira, 1985
- , Leslie Lamport, kafukufuku pepala, 1998
- , Leslie Lamport, kafukufuku pepala, 2001
Source: www.habr.com