Kaya isipin natin. 5 pusa ay naka-lock sa kuwarto, at upang magising ang may-ari, kailangan nilang lahat ay sumang-ayon dito, dahil maaari nilang buksan ang pinto sa pamamagitan lamang ng pagsandal dito kasama ang lima sa kanila. Kung ang isa sa mga pusa ay pusa ni Schrödinger at ang iba pang mga pusa ay hindi alam ang kanyang desisyon, ang tanong ay lumitaw: "Paano nila ito magagawa?"
Sa artikulong ito, sasabihin ko sa iyo sa mga simpleng termino ang tungkol sa teoretikal na bahagi ng mundo ng mga distributed system at ang mga prinsipyo ng kanilang trabaho. At mababaw din na isaalang-alang ang pangunahing ideya na pinagbabatayan ng Paxos'a.
Kapag ang mga developer ay gumagamit ng mga imprastraktura ng ulap, iba't ibang mga database, gumagana sa mga kumpol ng isang malaking bilang ng mga node, tiwala sila na ang data ay magiging pare-pareho, ligtas at palaging magagamit. Ngunit nasaan ang mga garantiya?
Sa katunayan, ang mga garantiya na mayroon kami ay mga garantiya ng supplier. Ang mga ito ay inilarawan sa dokumentasyon tulad ng sumusunod: "Ang serbisyong ito ay lubos na maaasahan, mayroon itong ibinigay na SLA, huwag mag-alala, lahat ay gagana na ipinamamahagi gaya ng iyong inaasahan."
May posibilidad kaming maniwala sa pinakamahusay, dahil tiniyak sa amin ng matatalinong tiyuhin mula sa malalaking kumpanya na magiging maayos ang lahat. Hindi natin tinatanong ang ating sarili: bakit, sa katunayan, ito ay maaaring gumana? Mayroon bang anumang pormal na katwiran para sa tamang operasyon ng mga naturang sistema?
Pinuntahan ko kamakailan at napaka-inspirasyon ng temang ito. Ang mga lektura sa paaralan ay mas katulad ng mga klase sa pagsusuri sa matematika kaysa sa anumang bagay na nauugnay sa mga computer system. Ngunit ito ay eksakto kung paano ang pinakamahalagang mga algorithm na ginagamit namin araw-araw, nang hindi pinaghihinalaan ito, ay napatunayan sa isang pagkakataon.
Karamihan sa mga modernong distributed system ay gumagamit ng Paxos consensus algorithm at ang iba't ibang pagbabago nito. Ang pinaka-cool na bagay ay ang bisa at, sa prinsipyo, ang mismong posibilidad ng pagkakaroon ng algorithm na ito ay mapapatunayan lamang gamit ang isang panulat at papel. Kasabay nito, sa pagsasagawa, ang algorithm ay ginagamit sa malalaking sistema na nagpapatakbo sa isang malaking bilang ng mga node sa mga ulap.
Banayad na paglalarawan ng susunod na tatalakayin: ang problema ng dalawang heneralTingnan natin ang warm-up .
Mayroon kaming dalawang hukbo - pula at puti. Ang mga puting hukbo ay nakabase sa kinubkob na lungsod. Ang mga pulang tropang pinamumunuan ng mga heneral A1 at A2 ay matatagpuan sa dalawang panig ng lungsod. Ang gawain ng mga redheads ay salakayin ang puting lungsod at manalo. Gayunpaman, ang hukbo ng bawat pulang heneral ay indibidwal na mas maliit kaysa sa hukbo ng mga puti.
Mga kondisyon ng tagumpay para sa mga redheads: ang parehong mga heneral ay dapat umatake nang sabay upang magkaroon ng numerical advantage sa mga puti. Upang gawin ito, ang mga heneral A1 at A2 ay kailangang sumang-ayon sa isa't isa. Kung hiwalay ang pag-atake ng lahat, matatalo ang mga redheads.
Upang makipag-ayos, ang mga heneral A1 at A2 ay maaaring magpadala ng mga mensahero sa isa't isa sa pamamagitan ng teritoryo ng puting lungsod. Maaaring matagumpay na maabot ng mensahero ang isang kaalyadong heneral, o maaaring maharang ng kaaway. Tanong: mayroon bang ganitong pagkakasunud-sunod ng mga komunikasyon sa pagitan ng mga heneral na may pulang buhok (ang pagkakasunud-sunod ng pagpapadala ng mga mensahero mula A1 hanggang A2 at kabaliktaran mula A2 hanggang A1), kung saan ginagarantiyahan silang sumang-ayon sa isang pag-atake sa oras X. Dito, sa pamamagitan ng mga garantiya, nauunawaan na ang parehong mga heneral ay magkakaroon ng malinaw na kumpirmasyon na ang isang kaalyado (isa pang heneral) ay sasalakay nang eksakto sa takdang oras X.
Ipagpalagay na ang A1 ay nagpadala ng isang messenger sa A2 na may mensaheng: "Atake tayo ngayon sa hatinggabi!". Hindi maaaring umatake ang General A1 nang walang kumpirmasyon mula sa General A2. Kung nakarating na ang messenger mula sa A1, magpapadala ang pangkalahatang A2 ng kumpirmasyon na may mensaheng: "Oo, punan natin ang mga puti ngayon." Ngunit ngayon ay hindi alam ni General A2 kung nakarating na ang kanyang mensahero o hindi, wala siyang kasiguraduhan kung sabay-sabay ang pag-atake. Ngayon, kailangan na naman ng General A2 ng kumpirmasyon.
Kung ilalarawan pa natin ang kanilang komunikasyon, lumalabas ang sumusunod: gaano man karaming mga siklo ng pagpapalitan ng mensahe ang mayroon, walang paraan upang magarantiya ang parehong heneral na natanggap ang kanilang mga mensahe (ipagpalagay na ang alinman sa mga mensahero ay maaaring maharang).
Ang problema ng dalawang heneral ay isang mahusay na paglalarawan ng isang napakasimpleng ipinamamahaging sistema kung saan mayroong dalawang node na may hindi mapagkakatiwalaang komunikasyon. Kaya wala kaming 100% na garantiya na sila ay naka-synchronize. Tungkol sa mga katulad na problema lamang sa mas malaking sukat mamaya sa artikulo.
Ipinapakilala ang konsepto ng mga distributed system
Ang isang distributed system ay isang pangkat ng mga computer (mula rito ay tinutukoy bilang mga node) na maaaring makipagpalitan ng mga mensahe. Ang bawat indibidwal na node ay ilang autonomous na entity. Ang isang node ay maaaring magproseso ng mga gawain sa sarili nitong, ngunit upang makipag-usap sa iba pang mga node, kailangan nitong magpadala at tumanggap ng mga mensahe.
Paano partikular na ipinapatupad ang mga mensahe, anong mga protocol ang ginagamit - hindi ito interesado sa amin sa kontekstong ito. Mahalaga na ang mga node ng isang distributed system ay maaaring makipagpalitan ng data sa isa't isa sa pamamagitan ng pagpapadala ng mga mensahe.
Ang kahulugan mismo ay hindi mukhang masyadong kumplikado, ngunit tandaan na ang isang distributed system ay may ilang mga katangian na magiging mahalaga sa amin.
Mga katangian ng mga distributed system
- Concurrency – ang posibilidad ng paglitaw ng sabay-sabay o mapagkumpitensyang mga kaganapan sa system. Bukod dito, isasaalang-alang namin na ang mga kaganapang naganap sa dalawang magkaibang node ay posibleng magkasabay hanggang sa magkaroon kami ng malinaw na pagkakasunud-sunod kung saan nangyari ang mga kaganapang ito. At kadalasan hindi namin ginagawa.
- Walang pandaigdigang orasan. Wala kaming malinaw na pagkakasunud-sunod ng mga kaganapan dahil sa kakulangan ng isang pandaigdigang orasan. Sa ordinaryong mundo ng mga tao, nasanay na tayo sa katotohanan na mayroon tayong mga oras at oras na ganap. Nagbabago ang lahat pagdating sa mga distributed system. Kahit na ang mga ultra-tumpak na atomic na orasan ay naaanod, at may mga sitwasyon kung saan hindi natin masasabi kung alin sa dalawang pangyayari ang unang nangyari. Samakatuwid, hindi rin tayo maaaring umasa sa oras.
- Malayang pagkabigo ng mga node ng system. May isa pang problema: ang isang bagay ay maaaring magkamali dahil lamang sa aming mga node ay hindi walang hanggan. Maaaring mabigo ang hard drive, maaaring mag-reboot ang virtual machine sa cloud, maaaring kumurap ang network at mawawala ang mga mensahe. Bukod dito, may mga sitwasyon kung kailan gumagana ang mga node, ngunit sa parehong oras gumagana ang mga ito laban sa system. Nakatanggap pa nga ng hiwalay na pangalan ang huling klase ng mga problema: ang problema . Ang pinakasikat na halimbawa ng isang distributed system na may ganitong problema ay Blockchain. Ngunit ngayon hindi natin isasaalang-alang ang espesyal na klase ng mga problemang ito. Magiging interesado kami sa mga sitwasyon kung saan ang isa o higit pang mga node ay maaaring mabigo.
- Mga modelo ng komunikasyon (mga modelo ng pagmemensahe) sa pagitan ng mga node. Nalaman na namin na ang mga node ay nakikipag-ugnayan sa pamamagitan ng pagpapalitan ng mga mensahe. Mayroong dalawang kilalang modelo ng pagmemensahe: synchronous at asynchronous.
Mga modelo ng komunikasyon sa pagitan ng mga node sa mga distributed system
Kasabay na modelo - alam nating sigurado na mayroong isang tiyak na kilalang delta ng oras kung saan ang mensahe ay garantisadong maabot mula sa isang node patungo sa isa pa. Kung tapos na ang oras na ito at hindi pa dumating ang mensahe, ligtas nating masasabi na nabigo ang node. Sa gayong modelo, mayroon tayong predictable na oras ng paghihintay.
Asynchronous na modelo – sa mga asynchronous na modelo, ipinapalagay namin na ang oras ng paghihintay ay may hangganan, ngunit walang time delta pagkatapos nito matitiyak na nabigo ang node. Yung. ang oras ng paghihintay para sa isang mensahe mula sa isang node ay maaaring basta-basta mahaba. Ito ay isang mahalagang kahulugan, at pag-uusapan pa natin ito.
Ang konsepto ng consensus sa mga distributed system
Bago pormal na tukuyin ang konsepto ng pinagkasunduan, isaalang-alang ang isang halimbawa ng isang sitwasyon kung saan kailangan natin ito, ibig sabihin − Pagtitiklop ng State Machine.
Mayroon kaming ilang ipinamahagi na log. Gusto naming maging pare-pareho ito at naglalaman ng magkaparehong data sa lahat ng node ng isang distributed system. Kapag natutunan ng isa sa mga node ang isang bagong halaga na isusulat nito sa log, ang gawain nito ay ibigay ang halagang ito sa lahat ng iba pang mga node upang ang log ay ma-update sa lahat ng mga node, at lumipat ang system sa isang bagong pare-parehong estado. Kasabay nito, mahalaga na ang mga node ay sumang-ayon sa kanilang mga sarili: lahat ng mga node ay sumasang-ayon na ang iminungkahing bagong halaga ay tama, lahat ng mga node ay tinatanggap ang halagang ito, at tanging sa kasong ito ang lahat ay maaaring mag-log ng isang bagong halaga.
Sa madaling salita: wala sa mga node ang tumutol na mayroon silang mas napapanahong impormasyon, at ang iminungkahing halaga ay hindi tama. Ang isang kasunduan sa pagitan ng mga node at kasunduan sa iisang tamang tinanggap na halaga ay ang pinagkasunduan sa isang distributed system. Susunod, pag-uusapan natin ang tungkol sa mga algorithm na nagbibigay-daan sa isang distributed system na maabot ang consensus na may garantisadong.
Sa mas pormal na paraan, maaari nating tukuyin ang isang consensus algorithm (o simpleng consensus algorithm) bilang ilang function na kumukuha ng isang distributed system mula sa estado A hanggang sa estado B. Bukod dito, ang estado na ito ay tinatanggap ng lahat ng mga node, at lahat ng mga node ay maaaring kumpirmahin ito. Bilang ito ay lumiliko out, ang gawaing ito ay hindi sa lahat bilang maliit na tila sa unang tingin.
Mga katangian ng consensus algorithm
Ang consensus algorithm ay dapat magkaroon ng tatlong katangian upang ang system ay patuloy na umiral at magkaroon ng ilang pag-unlad sa paglipat mula sa estado patungo sa estado:
- Kasunduan – lahat ng wastong gumaganang node ay dapat magkaroon ng parehong halaga (sa mga artikulo ay matatagpuan din ang property na ito bilang isang safety property). Ang lahat ng mga node na gumagana na ngayon (hindi nasira at hindi nawalan ng contact sa iba pa) ay dapat magkasundo at tanggapin ang ilang pangwakas na karaniwang halaga.
Mahalagang maunawaan dito na ang mga node sa distributed system na aming isinasaalang-alang ay gustong sumang-ayon. Iyon ay, pinag-uusapan natin ngayon ang tungkol sa mga sistema kung saan ang isang bagay ay maaaring mabigo lamang (halimbawa, ang ilang mga node ay nabigo), ngunit sa sistemang ito ay tiyak na walang mga node na sadyang gumagana laban sa iba (ang gawain ng mga heneral ng Byzantine). Dahil sa property na ito, nananatiling pare-pareho ang system.
- Integridad - kung ang lahat ng wastong gumaganang mga node ay nag-aalok ng parehong halaga v, kaya dapat tanggapin ng bawat wastong gumaganang node ang halagang ito v.
- Pagwawakas - lahat ng wastong gumaganang node ay magkakaroon ng ilang halaga (liveness property), na nagpapahintulot sa algorithm na magkaroon ng progreso sa system. Ang bawat indibidwal na node na gumagana nang tama ay dapat maaga o huli ay tanggapin ang huling halaga at kumpirmahin ito: "Para sa akin, ang halagang ito ay totoo, sumasang-ayon ako sa buong sistema."
Isang halimbawa kung paano gumagana ang consensus algorithm
Habang ang mga katangian ng algorithm ay maaaring hindi ganap na malinaw. Samakatuwid, ilarawan namin sa isang halimbawa kung anong mga yugto ang pinagdadaanan ng pinakasimpleng consensus algorithm sa isang system na may kasabay na modelo ng pagmemensahe, kung saan gumagana ang lahat ng mga node tulad ng inaasahan, ang mga mensahe ay hindi nawawala at walang nasisira (nangyayari ba talaga ito?).
- Nagsisimula ang lahat sa marriage proposal (Propose). Ipagpalagay na ang isang kliyente ay kumokonekta sa isang node na tinatawag na "Node 1" at nagsimula ng isang transaksyon, na nagpapasa ng isang bagong halaga sa node - O. Mula ngayon, tatawagin natin ang "Node 1" alok. Habang ang nagmumungkahi na "Node 1" ay kailangang ipaalam ngayon sa buong sistema na mayroon siyang bagong data, at nagpapadala siya ng mga mensahe sa lahat ng iba pang mga node: "Tingnan! Natanggap ko ang halagang "O", at gusto kong isulat ito! Pakikumpirma na itatala mo rin ang "O" sa iyong log."
- Ang susunod na yugto ay ang pagboto para sa iminungkahing halaga (Pagboto). Para saan ito? Maaaring mangyari na ang ibang mga node ay nakatanggap ng mas kamakailang impormasyon, at mayroon silang data sa parehong transaksyon.
Kapag ipinadala ng node na "Node 1" ang propuse nito, sinusuri ng iba pang mga node ang kanilang mga log para sa data sa kaganapang ito. Kung walang salungatan, ang mga node ay nag-aanunsyo: "Oo, wala akong ibang data para sa kaganapang ito. Ang halaga ng 'O' ay ang pinaka-up-to-date na impormasyong nararapat sa amin."Sa anumang iba pang kaso, ang mga node ay maaaring tumugon sa "Node 1": "Makinig! Mayroon akong mas kamakailang data sa transaksyong ito. Hindi "Oh", ngunit isang mas mahusay."
Sa yugto ng pagboto, ang mga node ay nagkakaroon ng desisyon: alinman sa lahat ng ito ay tumatanggap ng parehong halaga, o isa sa kanila ang bumoto laban, na nagpapahiwatig na siya ay may mas kamakailang data.
- Kung ang pag-ikot ng pagboto ay matagumpay, at lahat ay pabor, ang sistema ay lilipat sa isang bagong yugto - pagtanggap ng halaga (Tanggapin). Kinokolekta ng "Node 1" ang lahat ng mga tugon mula sa iba pang mga node at mga ulat: "Ang lahat ay sumang-ayon sa halagang 'O'! Ngayon ay opisyal kong idineklara na ang "O" ay ang aming bagong kahulugan, pareho para sa lahat! Isulat ito sa iyong kuwaderno, huwag kalimutan. Sumulat sa iyong log!"
- Ang natitirang mga node ay nagpapadala ng kumpirmasyon (Tinanggap) na isinulat nila ang halagang "O" para sa kanilang sarili, walang bago na natanggap sa panahong ito (isang uri ng two-phase commit). Pagkatapos ng mahalagang kaganapang ito, isinasaalang-alang namin na natapos na ang ipinamahagi na transaksyon.
Kaya, ang consensus algorithm sa isang simpleng kaso ay binubuo ng apat na hakbang: magmungkahi, bumoto (pagboto), pagtanggap (tanggap), kumpirmasyon ng pagtanggap (tinanggap).
Kung sa ilang hakbang ay hindi namin maabot ang kasunduan, pagkatapos ay i-restart ang algorithm, na isinasaalang-alang ang impormasyong ibinigay ng mga node na tumangging kumpirmahin ang iminungkahing halaga.
Consensus algorithm sa asynchronous system
Bago iyon, maayos ang lahat, dahil ito ay tungkol sa kasabay na modelo ng pagmemensahe. Ngunit alam natin na sa modernong mundo ay nakasanayan na nating gawin ang lahat ng hindi sabaysabay. Paano gumagana ang isang katulad na algorithm sa isang system na may isang asynchronous na modelo ng pagmemensahe, kung saan naniniwala kami na ang oras ng paghihintay para sa isang tugon mula sa isang node ay maaaring basta-basta mahaba (nga pala, ang isang node failure ay maaari ding isaalang-alang bilang isang halimbawa kapag ang isang node maaaring tumugon ng arbitraryong mahaba).
Ngayong alam na natin kung paano gumagana ang consensus algorithm sa prinsipyo, ang tanong ay para sa mga matanong na mambabasa na umabot na sa puntong ito: kung gaano karaming mga node sa isang sistema ng mga N node na may isang asynchronous na modelo ng mensahe ang maaaring bumaba upang maabot pa rin ng system ang consensus ?
Ang tamang sagot at katwiran sa likod ng spoiler.Ang tamang sagot ay: 0. Kung kahit isang node sa isang asynchronous system ay bumaba, hindi makakamit ng system ang consensus. Ang pahayag na ito ay napatunayan sa kilalang FLP theorem (1985, Fischer, Lynch, Paterson, link sa orihinal sa dulo ng artikulo): "Ang imposibilidad ng pag-abot sa isang distributed consensus kung hindi bababa sa isang node ang nabigo."
Guys, tapos may problema tayo, sanay tayo na asynchronous ang lahat sa atin. At eto na. Paano magpatuloy sa buhay?
Napag-usapan lang natin ang tungkol sa teorya, tungkol sa matematika. Ano ang ibig sabihin ng "hindi maabot ang pinagkasunduan", ang pagsasalin mula sa wikang matematika tungo sa atin - engineering? Nangangahulugan ito na "hindi palaging makakamit", i.e. may isang kaso kung saan ang pinagkasunduan ay hindi matamo. At ano ang kaso na ito?
Ito ang eksaktong paglabag sa liveness property na inilarawan sa itaas. Wala kaming isang karaniwang kasunduan, at hindi maaaring umunlad ang system (hindi maaaring wakasan sa isang takdang panahon) sa kaso kung saan wala kaming tugon mula sa lahat ng mga node. Dahil sa isang asynchronous system, wala tayong predictable response time at hindi natin malalaman kung down ang isang node o nagtatagal lang bago tumugon.
Ngunit sa pagsasagawa, makakahanap tayo ng solusyon. Hayaan ang aming algorithm na tumakbo nang mahabang panahon kung sakaling mabigo (ito ay potensyal na tumakbo nang walang katapusan). Ngunit sa karamihan ng mga sitwasyon, kapag ang karamihan sa mga node ay gumagana nang tama, magkakaroon tayo ng pag-unlad sa system.
Sa pagsasagawa, kami ay nakikitungo sa bahagyang kasabay na mga modelo ng komunikasyon. Ang bahagyang synchronism ay nauunawaan bilang mga sumusunod: sa pangkalahatang kaso, mayroon kaming isang asynchronous na modelo, ngunit ang isang tiyak na konsepto ng "global stabilization time" ng isang tiyak na punto sa oras ay pormal na ipinakilala.
Ang sandaling ito sa oras ay maaaring hindi dumating para sa isang di-makatwirang mahabang panahon, ngunit isang araw dapat itong dumating. Magri-ring ang virtual na alarm clock, at mula sa sandaling iyon ay mahuhulaan natin ang time delta kung saan aabot ang mga mensahe. Mula sa puntong ito, lumiliko ang system mula sa asynchronous patungo sa kasabay. Sa pagsasagawa, nakikitungo tayo sa gayong mga sistema.
Ang algorithm ng Paxos ay nalulutas ang mga problema sa pinagkasunduan
ay isang pamilya ng mga algorithm na nilulutas ang problema ng pinagkasunduan para sa bahagyang kasabay na mga sistema, sa kondisyon na maaaring mabigo ang ilang node. Ang may-akda ng Paxos ay . Iminungkahi niya ang isang pormal na patunay ng pagkakaroon at kawastuhan ng algorithm noong 1989.
Ngunit ang patunay ay naging hindi mahalaga. Ang unang publikasyon ay inilabas lamang noong 1998 (33 mga pahina) na naglalarawan sa algorithm. Tulad ng nangyari, napakahirap na maunawaan, at noong 2001 isang paliwanag ang nai-publish para sa artikulo, na tumagal ng 14 na pahina. Ang mga volume ng mga publikasyon ay ibinigay upang ipakita na sa katunayan ang problema ng pinagkasunduan ay hindi lahat simple, at sa likod ng gayong mga algorithm mayroong isang malaking gawain ng pinakamatalinong tao.
Kapansin-pansin na si Leslie Lampor mismo sa kanyang lecture ay nabanggit na sa pangalawang artikulo-paliwanag ay mayroong isang pahayag, isang linya (hindi niya tinukoy kung alin), na maaaring bigyang-kahulugan sa iba't ibang paraan. At dahil dito, ang malaking bilang ng mga modernong pagpapatupad ng Paxos ay hindi gumagana nang tama.
Ang isang detalyadong pagsusuri ng gawain ng Paxos ay kukuha ng higit sa isang artikulo, kaya't susubukan kong ihatid ang pangunahing ideya ng algorithm nang maikli. Sa mga link sa dulo ng aking artikulo ay makakahanap ka ng mga materyales para sa karagdagang pagsisid sa paksang ito.
Mga tungkulin sa Paxos
Ang algorithm ng Paxos ay may konsepto ng mga tungkulin. Isaalang-alang ang tatlong pangunahing (may mga pagbabago na may mga karagdagang tungkulin):
- Mga nagmumungkahi (maaaring mayroon ding mga termino: mga pinuno o tagapag-ugnay). Ito ang mga taong natututo tungkol sa ilang bagong kahulugan mula sa gumagamit at nagsasagawa ng tungkulin ng pinuno. Ang kanilang gawain ay upang ilunsad ang isang round ng mga panukala para sa isang bagong halaga at coordinate ng karagdagang mga aksyon ng mga node. Bukod dito, pinapayagan ng Paxos ang pagkakaroon ng ilang lider sa ilang partikular na sitwasyon.
- Mga Tatanggap (Mga Botante). Ito ang mga node na bumoboto upang tanggapin o tanggihan ang isang partikular na halaga. Napakahalaga ng kanilang tungkulin, dahil ang desisyon ay nakasalalay sa kanila: kung anong estado ang pupuntahan ng system (o hindi pupunta) pagkatapos ng susunod na yugto ng consensus algorithm.
- Aaral. Mga node na simpleng tumatanggap at nagsusulat ng bagong tinatanggap na halaga kapag nagbago ang estado ng system. Hindi sila gumagawa ng mga desisyon, tumatanggap lang sila ng data at maibibigay ito sa end user.
Ang isang node ay maaaring pagsamahin ang ilang mga tungkulin sa iba't ibang mga sitwasyon.
Ang konsepto ng korum
Ipinapalagay namin na mayroon kaming isang sistema ng N mga node. At karamihan sa kanila F maaaring mabigo ang mga node. Kung nabigo ang mga F node, dapat ay mayroon tayong hindi bababa sa 2F+1 acceptor node.
Ito ay kinakailangan upang tayo ay palaging, kahit na sa pinakamasamang sitwasyon, "mabuti", tama ang gumaganang mga node ay may mayorya. Yan ay F+1 "mabuti" na mga node na sumang-ayon, at ang huling halaga ay tatanggapin. Kung hindi, maaaring may sitwasyon kung saan magkakaroon ng iba't ibang kahulugan ang iba't ibang lokal na grupo at hindi sila magkakasundo. Kaya kailangan natin ng absolute majority para manalo sa boto.
Pangkalahatang ideya ng Paxos consensus algorithm
Ipinapalagay ng algorithm ng Paxos ang dalawang malalaking yugto, na nahahati naman sa dalawang hakbang bawat isa:
- Phase 1a: Maghanda. Sa yugto ng paghahanda, ang pinuno (nagmumungkahi) ay nagpapaalam sa lahat ng mga node: “Nagsisimula kami ng bagong yugto ng pagboto. May bago tayong round. Ang bilang ng round na ito ay n. Magsisimula na tayong bumoto ngayon." Sa ngayon, nag-uulat lang ito ng pagsisimula ng isang bagong cycle, ngunit hindi nag-uulat ng bagong halaga. Ang gawain ng yugtong ito ay upang simulan ang isang bagong round at ipaalam sa lahat ang natatanging numero nito. Ang round number ay mahalaga, ito ay dapat na mas malaki kaysa sa lahat ng nakaraang mga numero ng pagboto mula sa lahat ng nakaraang mga pinuno. Dahil salamat sa round number na mauunawaan ng ibang mga node sa system kung gaano kasariwa ang data ng pinuno. Marahil ang ibang mga node ay mayroon nang mga resulta ng pagboto mula sa mga susunod na round at sasabihin lang sa pinuno na siya ay nasa likod ng mga oras.
- Phase 1b: Pangako. Kapag natanggap ng mga acceptor node ang bilang ng bagong yugto ng pagboto, dalawang resulta ang posible:
- Ang bilang n ng bagong boto ay mas malaki kaysa sa bilang ng alinman sa mga nakaraang boto kung saan lumahok ang tumanggap. Pagkatapos ang tumanggap ay nagpapadala ng pangako sa pinuno na hindi na ito lalahok sa anumang mga boto na may bilang na mas mababa sa n. Kung ang tumanggap ay bumoto na para sa isang bagay (iyon ay, tinanggap na nito ang ilang halaga sa ikalawang yugto), pagkatapos ay idaragdag nito ang tinanggap na halaga at ang bilang ng boto kung saan ito lumahok sa pangako nito.
- Kung hindi, kung alam na ng tumanggap ang tungkol sa mataas na bilang ng boto, maaari na lamang nitong balewalain ang hakbang ng paghahanda at hindi tumugon sa pinuno.
- Phase 2a: Tanggapin. Ang pinuno ay kailangang maghintay ng tugon mula sa korum (karamihan sa mga node sa system) at, kung ang kinakailangang bilang ng mga tugon ay natanggap, pagkatapos ay mayroon siyang dalawang pagpipilian para sa pagbuo ng mga kaganapan:
- Ang ilan sa mga tumanggap ay nagsumite ng mga halaga na kanilang binoto na. Sa kasong ito, pipiliin ng pinuno ang halaga mula sa boto na may pinakamataas na bilang. Tawagan natin ang halagang ito na x, at magpadala ng mensaheng tulad nito sa lahat ng mga node: "Tanggapin (n, x)", kung saan ang unang halaga ay ang numero ng pagboto mula sa sarili nitong hakbang na Magmungkahi, at ang pangalawang halaga ay para sa lahat ng nakalap, i.e. halaga kung saan, sa katunayan, bumoto tayo.
- Kung wala sa mga tumanggap ang nagpadala ng anumang halaga, ngunit nangako lang silang bumoto sa round na ito, maaaring anyayahan sila ng pinuno na bumoto para sa kanilang halaga, ang halaga kung saan siya naging pinuno sa lahat. Tawagin natin itong y. Nagpapadala ito sa lahat ng mga node ng mensahe ng form: "Tanggapin (n, y)", sa pamamagitan ng pagkakatulad sa nakaraang kinalabasan.
- Phase 2b: Tinanggap. Dagdag pa, ang mga node ng acceptor, sa pagtanggap ng mensaheng "Tanggapin (...)", mula sa pinuno ay sumasang-ayon dito (magpadala ng kumpirmasyon sa lahat ng mga node na sumasang-ayon sila sa bagong halaga) kung hindi sila nangako sa ilan (iba pa) ng lider na lumahok sa pagboto na may bilang ng round n' > nkung hindi, binabalewala nila ang prompt ng kumpirmasyon.
Kung ang karamihan ng mga node ay sumagot sa pinuno, at lahat sila ay nakumpirma ang bagong halaga, kung gayon ang bagong halaga ay itinuturing na tinanggap. Hooray! Kung ang karamihan ay hindi nai-type o may mga node na tumangging tanggapin ang bagong halaga, pagkatapos ang lahat ay magsisimulang muli.
Ito ay kung paano gumagana ang Paxos algorithm. Ang bawat isa sa mga yugtong ito ay may maraming mga subtleties, halos hindi namin isinasaalang-alang ang iba't ibang uri ng mga pagkabigo, mga problema ng maramihang mga pinuno, at marami pang iba, ngunit ang layunin ng artikulong ito ay upang ipakilala lamang ang mambabasa sa mundo ng distributed computing sa pinakamataas na antas.
Kapansin-pansin din na ang Paxos ay hindi lamang isa sa uri nito, mayroong iba pang mga algorithm, halimbawa, , ngunit ito ay isang paksa para sa isa pang artikulo.
Mga link sa mga materyales para sa karagdagang pag-aaral
Antas ng baguhan:
- , Preethi Kasireddy, artikulo sa blog sa Medium
- , Adi Kancherla, artikulo sa blog sa Medium
- Ittai Abraham blog
- , Ittai Abraham, artikulo sa blog
Leslie Laport Level:
- Fischer, Lynch at Paterson, research paper, 1985
- , Leslie Lamport, research paper, 1998
- , Leslie Lamport, research paper, 2001
Pinagmulan: www.habr.com