Kahoo, a re nahaneng. Ho na le likatse tse 5 tse koaletsoeng ka kamoreng, 'me e le hore li tsose mong'a tsona, kaofela li lokela ho lumellana ka sena har'a tsona, hobane li ka bula lemati feela ka tse hlano tsa tsona tse itšetlehileng ka eona. Haeba e 'ngoe ea likatse ke katse ea Schrödinger,' me likatse tse ling ha li tsebe ka qeto ea hae, potso e hlaha: "Ba ka e etsa joang?"
Sehloohong sena, ke tla u bolella ka mantsoe a bonolo mabapi le karolo ea theory ea lefats'e ea litsamaiso tse ajoang le melao-motheo ea ts'ebetso ea tsona. Ke tla boela ke hlahlobe taba ea mantlha e thehiloeng Paxos.
Ha bahlahisi ba sebelisa lisebelisoa tsa maru, li-database tse fapa-fapaneng, 'me ba sebetsa ka lihlopha tsa palo e kholo ea li-node, ba na le tšepo ea hore data e tla ba e feletseng, e sireletsehileng,' me e fumaneha kamehla. Empa litiisetso li hokae?
Ha e le hantle, litiiso tseo re nang le tsona ke litiisetso tsa bafani ba thepa. Li hlalositsoe litokomaneng ka tsela e latelang: "Tšebeletso ena e tšepahala haholo, e na le SLA e fanoeng, se tšoenyehe, ntho e 'ngoe le e' ngoe e tla sebetsa ka mokhoa oo u neng u lebeletse ka oona."
Re atisa ho lumela ho tse molemo ka ho fetisisa, hobane bahlankana ba bohlale ba lik'hamphani tse kholo ba ile ba re tiisetsa hore ntho e 'ngoe le e' ngoe e tla loka. Ha re botse potso: hobaneng, ha e le hantle, see se ka sebetsa ho hang? Na ho na le mabaka a molao bakeng sa tšebetso e nepahetseng ea litsamaiso tse joalo?
Haufinyane tjena ke ile mme o khothalelitsoe haholo ke sehlooho sena. Lithuto sekolong li ne li tšoana le litlelase tsa calculus ho e-na le ho hong ho amanang le litsamaiso tsa likhomphutha. Empa ena ke eona tsela eo li-algorithms tsa bohlokoa ka ho fetisisa tseo re li sebelisang letsatsi le letsatsi, ntle le ho e tseba, li netefalitsoeng ka nako e le 'ngoe.
Litsamaiso tse ngata tsa sejoale-joale tse ajoang li sebelisa algorithm ea Paxos consensus le liphetoho tsa eona tse fapaneng. Ntho e pholileng ka ho fetisisa ke hore bonnete le, ha e le hantle, monyetla oa ho ba teng ha algorithm ena o ka pakoa feela ka pene le pampiri. Ha e le hantle, algorithm e sebelisoa lits'ebetsong tse kholo tse tsamaeang ka palo e kholo ea li-node marung.
Papiso e bonolo ea se tla tšohloa nakong e tlang: mosebetsi oa balaoli ba babeliHa re shebeng ho futhumatsa .
Re na le mabotho a mabeli - e khubelu le e tšoeu. Mabotho a makhooa a lula motseng o lika-likelitsoeng. Mabotho a khubelu a etelletsoeng pele ke balaoli ba A1 le A2 a fumaneha ka mahlakoreng a mabeli a toropo. Mosebetsi oa bo-redheads ke ho hlasela motse o mosoeu le ho hlōla. Leha ho le joalo, lebotho la molaoli e mong le e mong ea khubelu ka bomong ke le lenyenyane ho feta lebotho le tšoeu.
Maemo a tlhōlo bakeng sa ba khubelu: balaoli ka bobeli ba tlameha ho hlasela ka nako e le 'ngoe e le hore ba be le phaello ea palo ho feta makhooa. Ho etsa sena, balaoli ba A1 le A2 ba hloka ho lumellana. Haeba bohle ba hlasela ka thoko, li-redheads li tla lahleheloa.
Ho fihlela tumellano, balaoli ba A1 le A2 ba ka romellana manģosa ho pholletsa le sebaka sa toropo e tšoeu. Moromuoa a ka atleha ho fihla ho molaoli oa sesole kapa a khahlametsoa ke sera. Potso: na ho na le tatellano e joalo ea puisano pakeng tsa balaoli ba moriri o mofubelu (tatelano ea ho romela manģosa ho tloha A1 ho ea ho A2 le ka tsela e fapaneng ho tloha A2 ho ea ho A1), moo ba tiiselitsoeng ho lumellana ka tlhaselo ka hora X. Mona, litiiso li bolela hore balaoli ka bobeli ba tla ba le netefatso e hlakileng ea hore motsoalle (kakaretso e mong) o tla hlasela ka nako e behiloeng X.
A re re A1 e romela lenqosa ho A2 ka molaetsa o reng: "Ha re hlaseleng kajeno har'a mp'a bosiu!" Kakaretso ea A1 e ke ke ea hlasela ntle le tiiso ho tsoa ho General A2. Haeba lenģosa le tsoang ho A1 le fihlile, joale General A2 o romela tiiso ka molaetsa o reng: "E, ha re bolaee makhooa kajeno." Empa joale General A2 ha a tsebe hore na lenģosa la hae le fihlile kapa che, ha a na tiiso ea hore na tlhaselo e tla ba ka nako e le 'ngoe. Joale General A2 e boetse e hloka netefatso.
Haeba re tsoela pele ho hlalosa puisano ea bona, hoa hlaka hore ho sa tsotellehe hore na ho na le lipotoloho tse kae tsa phapanyetsano ea melaetsa, ha ho na mokhoa oa ho tiisa hore balaoli ka bobeli ba fumane melaetsa ea bona (ho nka hore lenģosa le ka amoheloa).
Bothata ba Bobeli ba Kakaretso ke papiso e ntle haholo ea tsamaiso e bonolo haholo e ajoang moo ho nang le li-node tse peli tse nang le puisano e sa tšepahaleng. Sena se bolela hore ha re na 100% tiisetso ea hore li hokahantsoe. Mathata a tšoanang a tšohloa feela ka tekanyo e khōloanyane hamorao sehloohong.
Re hlahisa mohopolo oa litsamaiso tse ajoang
Sistimi e ajoang ke sehlopha sa likhomphutha (ka mor'a moo re tla li bitsa li-node) tse ka fapanyetsanang melaetsa. Node ka 'ngoe ke mofuta o itseng oa setheo se ikemetseng. Node e ka sebetsana le mesebetsi ka boeona, empa e le hore e buisane le li-node tse ling, e hloka ho romela le ho amohela melaetsa.
Hantle-ntle melaetsa e kenngoa ts'ebetsong joang, ho sebelisoa li-protocol - sena ha se re thahaselle tabeng ena. Ke habohlokoa hore li-node tsa tsamaiso e fanoeng li ka fapanyetsana data ka ho romellana melaetsa.
Tlhaloso ka boeona ha e shebahale e le thata haholo, empa re tlameha ho ela hloko hore tsamaiso e ajoang e na le litšobotsi tse ngata tse tla ba tsa bohlokoa ho rona.
Litšobotsi tsa litsamaiso tse ajoang
- Chelete ea chelete - monyetla oa ho etsahala ka nako e le 'ngoe kapa ka nako e le 'ngoe tsamaisong. Ho feta moo, re tla nka liketsahalo tse etsahalang libakeng tse peli tse fapaneng hore li ka etsahala ka nako e le 'ngoe ha feela re se na tatellano e hlakileng ea liketsahalo tsa liketsahalo tsena. Empa, joalo ka molao, ha re na eona.
- Ha ho oache ea lefatše lohle. Ha re na tatellano e hlakileng ea liketsahalo ka lebaka la khaello ea oache ea lefatše lohle. Lefatšeng le tloaelehileng la batho, re tloaetse taba ea hore re na le lioache le nako ka ho feletseng. Ntho e 'ngoe le e' ngoe e fetoha ha ho tluoa tabeng ea litsamaiso tse ajoang. Esita le lioache tsa liathomo tse tsebang hantle haholo li na le ho hoholeha, ’me ho ka ’na ha e-ba le maemo ao ho ’ona re ke keng ra tseba hore na ke ketsahalo efe ho tse peli e etsahetseng pele. Ka hona, le rōna re ke ke ra itšetleha ka nako.
- Ho hloleha ho ikemetseng ha li-node tsa sistimi. Ho na le bothata bo bong: ho na le ntho e ka tsamaeang hampe hobane feela li-node tsa rona li sa tšoarelle ka ho sa feleng. Hard drive e ka 'na ea hlōleha, mochine oa sebele o ka leru o ka qala hape, marang-rang a ka panya' me melaetsa e tla lahleha. Ho feta moo, ho ka 'na ha e-ba le maemo ao li-node li sebetsang ho tsona, empa ka nako e ts'oanang li sebetsa khahlanong le tsamaiso. Sehlopha sa ho qetela sa mathata se bile sa fumana lebitso le fapaneng: bothata . Mohlala o tummeng ka ho fetisisa oa tsamaiso e ajoang le bothata bona ke Blockchain. Empa kajeno re ke ke ra nahana ka sehlopha sena se khethehileng sa mathata. Re tla thahasella maemo ao ho ’ona node e le ’ngoe kapa ho feta e ka ’nang ea hlōleha.
- Mehlala ea puisano (mehlala ea melaetsa) lipakeng tsa li-node. Re se re hlokometse hore li-node li buisana ka ho fapanyetsana melaetsa. Ho na le mefuta e 'meli ea melaetsa e tsebahalang: synchronous le asynchronous.
Mehlala ea puisano lipakeng tsa li-node ho litsamaiso tse ajoang
Moetso oa synchronous - re tseba hantle hore ho na le karolo e lekanyelitsoeng e tsejoang ea nako eo ka eona molaetsa o tiiselitsoeng ho fihla ho tloha sebakeng se seng ho ea ho se seng. Haeba nako ena e fetile mme molaetsa ha o e-s'o fihle, re ka bua ka mokhoa o sireletsehileng hore node e hlōlehile. Moetsong ona re na le linako tsa ho leta tse boletsoeng esale pele.
Asynchronous ea mohlala - ka mehlala ea asynchronous re nka hore nako ea ho leta e felile, empa ha ho na sebaka se joalo sa nako ka mor'a moo re ka tiisang hore node e hlōlehile. Tseo. Nako ea ho emela molaetsa o tsoang ho node e ka ba nako e telele. Ena ke tlhaloso ea bohlokoa, 'me re tla bua ka eona ho ea pele.
Khopolo ea tumellano ka litsamaiso tse ajoang
Pele re hlalosa ka molao mohopolo oa tumellano, ha re hlahlobeng mohlala oa boemo boo re bo hlokang, e leng - State Machine Replication.
Re na le log e phatlalalitsoeng. Re ka rata hore e lumellane 'me e be le data e ts'oanang ho li-node tsohle tsa sistimi e ajoang. Ha e 'ngoe ea li-node e ithuta boleng bo bocha boo e tla e ngolla ho log, mosebetsi oa eona e ba ho fana ka boleng bona ho li-node tse ling kaofela e le hore log e nchafatsoe ho li-node tsohle' me tsamaiso e fallela boemong bo bocha bo tsitsitseng. Tabeng ena, ke habohlokoa hore li-node li lumellane har'a tsona: li-node tsohle li lumellane hore boleng bo bocha bo reriloeng bo nepahetse, li-node tsohle li amohela boleng bona, 'me feela tabeng ena motho e mong le e mong a ka ngola boleng bo bocha ho log.
Ka mantsoe a mang: ha ho le e 'ngoe ea li-node e hanyetsang hore e na le boitsebiso bo nepahetseng haholoanyane,' me boleng bo reriloeng bo ne bo fosahetse. Tumellano pakeng tsa li-node le tumellano ka boleng bo amohelehang bo amohelehang ke tumellano tsamaisong e ajoang. Ka mor'a moo, re tla bua ka li-algorithms tse lumellang tsamaiso e ajoang hore e tiisetsoe ho fihlela tumellano.
Ka mokhoa o hlophisitsoeng haholoanyane, re ka hlalosa algorithm ea tumellano (kapa feela algorithm ea tumellano) e le mosebetsi o itseng o fetisang tsamaiso e ajoang ho tloha sebakeng sa A ho ea sebakeng sa B. Ho feta moo, naha ena e amoheloa ke li-node tsohle, 'me li-node tsohle li ka li tiisa. Ha e le hantle, mosebetsi ona ha o bonolo joalokaha o bonahala qalong.
Thepa ea Algorithm ea Consensus
Algorithm ea tumellano e tlameha ho ba le thepa e meraro e le hore sistimi e tsoelepele ho ba teng mme e be le tsoelo-pele e itseng ea ho tloha mmuso ho ea ho naha:
- Tumellano - li-node tsohle tse sebetsang ka nepo li tlameha ho nka boleng bo lekanang (lingoloeng thepa ena e boetse e bitsoa thepa ea polokeho). Li-node tsohle tse ntseng li sebetsa (ha li so hlolehe kapa li lahlehetsoe ke ho kopana le tse ling) li tlameha ho lumellana le ho amohela boleng bo bong ba ho qetela bo tšoanang.
Ho bohlokoa ho utloisisa mona hore li-node tsamaisong e ajoang eo re e nahanang e batla ho lumellana. Ke hore, hona joale re bua ka litsamaiso tseo ho tsona ntho e ka hlōlehang feela (mohlala, node e 'ngoe e hlōleha), empa tsamaisong ena ha ho na li-node tse sebetsang ka boomo khahlanong le tse ling (mosebetsi oa balaoli ba Byzantine). Ka lebaka la thepa ena, tsamaiso e lula e tsitsitse.
- botšepehi ba - haeba li-node tsohle tse sebetsang hantle li fana ka boleng bo tšoanang v, ho bolelang hore node e 'ngoe le e 'ngoe e sebetsang hantle e tlameha ho amohela boleng bona v.
- Ho khaotsa - li-node tsohle tse sebetsang ka mokhoa o nepahetseng li tla qetella li nka boleng bo itseng (thepa ea liveness), e lumellang algorithm ho etsa tsoelo-pele tsamaisong. Motho e mong le e mong ea sebetsang ka nepo o tlameha ho amohela boleng ba ho qetela kapa hamorao mme a bo tiise: "Ho 'na, boleng bona ke 'nete, ke lumellana le tsamaiso eohle."
Mohlala oa kamoo algorithm ea tumellano e sebetsang kateng
Le hoja thepa ea algorithm e ka 'na ea se ke ea hlaka ka ho feletseng. Ka hona, re tla bontša ka mohlala hore na ke mehato efe eo algorithm e bonolo ea tumellano e tsamaeang ho eona tsamaisong e nang le mohlala oa melaetsa oa synchronous, moo li-node tsohle li sebetsang kamoo ho lebeletsoeng kateng, melaetsa ha e lahlehe 'me ha ho letho le robehileng (na see se hlile se etsahala?).
- Tsohle li qala ka tlhahiso ea lenyalo (Propose). A re nke hore mofani o kopantsoe le node e bitsoang "Node 1" 'me a qala ts'ebetso, a fetisa boleng bo bocha ho node - O. Ho tloha joale ho ea pele, re tla bitsa "Node 1" nyehelo. Joaloka moeletsi, "Node 1" joale e tlameha ho tsebisa tsamaiso eohle hore e na le data e ncha, 'me e romela melaetsa ho li-node tse ling kaofela: "Bona! Moelelo “O” o ile oa tla ho ’na ’me ke batla ho o ngola fatše! Ka kopo netefatsa hore o tla ngola le "O" tlalehong ea hau.
- Mokhahlelo o latelang ke ho voutela boleng bo reriloeng (Voting). E etselitsoe eng? Ho ka 'na ha etsahala hore li-node tse ling li fumane boitsebiso ba morao-rao,' me li na le boitsebiso bo mabapi le transaction e tšoanang.
Ha node "Node 1" e romella tlhahiso ea eona, li-node tse ling li hlahloba lintlha tsa tsona bakeng sa lintlha tse mabapi le ketsahalo ena. Haeba ho se na likhanyetsano, li-node li phatlalatsa: "E, ha ke na lintlha tse ling bakeng sa ketsahalo ena. Boleng ba "O" ke lintlha tsa morao-rao tseo re li tšoanelang.Boemong bofe kapa bofe, li-node li ka arabela "Node 1": "Mamela! Ke na le lintlha tsa morao-rao mabapi le khoebo ena. Eseng 'O', empa ho hong ho betere."
Sethaleng sa ho vouta, li-node li fihla qetong: ebang ke bohle ba amohelang boleng bo tšoanang, kapa e mong oa bona o khetha khahlanong le bona, a bontšang hore o na le lintlha tsa morao-rao.
- Haeba potoloho ea likhetho e ne e atlehile 'me e mong le e mong a rata, joale tsamaiso e fallela sethaleng se secha - Ho amohela boleng. "Node 1" e bokella likarabo tsohle ho tsoa ho li-node tse ling 'me e tlaleha: "E mong le e mong o ile a lumellana le boleng "O"! Joale ke phatlalatsa ka molao hore “O” ke moelelo oa rōna o mocha, o tšoanang ho bohle! E ngole bukeng ea hau e nyenyane, u se ke ua lebala. E ngole bukeng ya hao!”
- Li-node tse setseng li romella netefatso (E amohetsoe) hore li ngotse boleng ba "O"; ha ho letho le lecha le fihlileng nakong ena (mofuta oa boitlamo ba mekhahlelo e 'meli). Ka mor'a ketsahalo ena ea bohlokoa, re nahana hore khoebo e ajoang e phethiloe.
Ka hona, algorithm ea tumellano tabeng e bonolo e na le mehato e mene: ho etsa tlhahiso, ho vouta (ho vouta), ho amohela (ho amohela), ho tiisa ho amoheloa (ho amoheloa).
Haeba ka mohato o itseng re ne re sa khone ho fihlela tumellano, joale algorithm e qala hape, e nahanela boitsebiso bo fanoeng ke li-node tse hanneng ho tiisa boleng bo reriloeng.
Algorithm ea Consensus tsamaisong e sa tloaelehang
Pele ho sena, ntho e 'ngoe le e' ngoe e ne e le boreleli, hobane re ne re bua ka mohlala oa melaetsa oa synchronous. Empa rea tseba hore lefatšeng la kajeno re tloaetse ho etsa ntho e 'ngoe le e' ngoe ka mokhoa o sa tšoaneng. Algorithm e ts'oanang e sebetsa joang tsamaisong e nang le mohlala oa melaetsa ea asynchronous, moo re lumelang hore nako ea ho emela karabo e tsoang ho node e ka ba nako e telele (ka tsela, ho hlōleha ha node ho ka boela ha nkoa e le mohlala node e ka arabela nako e telele ka mokhoa o ikhethileng).
Kaha joale rea tseba hore na algorithm ea tumellano e sebetsa joang ka molao-motheo, potso ho babali ba batlang ho tseba ba entseng ho fihlela joale: ke li-node tse kae tsamaisong ea li-node tsa N tse nang le mohlala oa molaetsa oa asynchronous li ka hlōleha e le hore tsamaiso e ntse e ka fihlela tumellano?
Karabo e nepahetseng le tokafatso ke ka mor'a spoiler.Karabo e nepahetseng ke: 0. Haeba esita le node e le 'ngoe tsamaisong ea asynchronous e hlōleha, tsamaiso e ke ke ea khona ho fihlela tumellano. Polelo ena e pakoa ke khopolo-taba ea FLP, e tsebahalang likarolong tse itseng (1985, Fischer, Lynch, Paterson, e hokahanya le ea pele qetellong ea sehlooho): “Ho se khonehe ho finyella tumellano e ajoang haeba bonyane node e le ’ngoe e hlōleha. .”
Banna, joale re na le bothata, re tloaetse hore ntho e 'ngoe le e' ngoe e be asynchronous. Mme ke ena. Joang ho tsoela pele ho phela?
Re ne re bua feela ka theory, ka lipalo. "Tumellano e ke ke ea finyelloa" e bolela eng, ho fetolela ho tloha puong ea lipalo ho ea ho ea rona - boenjiniere? Sena se bolela hore "hase kamehla e ka finyelloang", i.e. Ho na le nyeoe eo ho eona tumellano e ke keng ea finyelloa. Ke nyeoe ea mofuta ofe ee?
Sena ke hantle tlōlo ea thepa ea liveness e hlalositsoeng ka holimo. Ha re na tumellano e tšoanang, 'me tsamaiso e ke ke ea e-ba le tsoelo-pele (e ke ke ea phethela ka nako e lekanyelitsoeng) ha re se na karabo ho tsoa ho li-node tsohle. Hobane tsamaisong ea asynchronous ha re na nako ea ho arabela e ka tsejoang esale pele 'me re ke ke ra tseba hore na node e senyehile kapa e nka nako e telele ho arabela.
Empa ka ts'ebetso re ka fumana tharollo. Etsa hore algorithm ea rona e khone ho sebetsa nako e telele ha ho ka ba le liphoso (mohlomong e ka sebetsa ka nako e sa lekanyetsoang). Empa maemong a mangata, ha li-node tse ngata li sebetsa hantle, re tla ba le tsoelo-pele tsamaisong.
Ha e le hantle, re sebetsana le mekhoa ea puisano e sa tšoaneng. Synchrony e sa fellang e utloisisoa ka tsela e latelang: ka kakaretso, re na le mohlala oa asynchronous, empa khopolo e itseng ea "nako ea botsitso ea lefats'e" ea ntlha e itseng ka nako e hlahisoa ka molao.
Nako ena ka nako e kanna ea se ke ea fihla bolelele ba nako, empa e tlameha ho tla letsatsi le le leng. Oache ea alamo e tla lla, 'me ho tloha motsotsong oo re ka bolela esale pele nako eo melaetsa e tla fihla ka eona. Ho tloha motsotsong ona ho ea pele, sistimi e fetoha ho tloha ho asynchronous ho ea ho synchronous. Ha e le hantle, re sebetsana le litsamaiso tse joalo hantle.
Algorithm ea Paxos e rarolla mathata a tumellano
ke lelapa la li-algorithms tse rarollang bothata ba tumellano bakeng sa litsamaiso tse sa tšoaneng tsa synchronous, ho itšetlehile ka monyetla oa hore li-node tse ling li ka hlōleha. Mongoli oa Paxos ke . O ile a fana ka tlhahiso ea bopaki ba molao ba ho ba teng le ho nepahala ha algorithm ka 1989.
Empa bopaki bo ile ba bonahala e le bo sa reng letho. Khatiso ea pele e ile ea lokolloa feela ka 1998 (maqephe a 33) e hlalosang algorithm. Ha e le hantle, ho ne ho le thata haholo ho utloisisa, 'me ka 2001 ho ile ha hatisoa tlhaloso ea sehlooho sena, e neng e nka maqephe a 14. Bophahamo ba lingoliloeng bo fanoa e le ho bontša hore ha e le hantle bothata ba tumellano ha bo bonolo ho hang, 'me ka mor'a li-algorithms tse joalo ho na le mosebetsi o mongata oa batho ba bohlale ka ho fetisisa.
Hoa thahasellisa hore Leslie Lamport ka boeena o ile a hlokomela puong ea hae hore sehloohong sa bobeli se hlalosang ho na le polelo e le 'ngoe, mola o le mong (ha aa ka a hlalosa hore na ke ofe), o ka hlalosoang ka litsela tse sa tšoaneng. Mme ka lebaka la sena, palo e kholo ea ts'ebetsong ea sejoale-joale ea Paxos ha e sebetse ka nepo.
Tlhahlobo e qaqileng ea mosebetsi oa Paxos e ka nka sengoloa se fetang se le seng, kahoo ke tla leka ho fetisa mohopolo oa mantlha oa algorithm ka bokhutšoane. Lihokelong tse qetellong ea sengoloa sa ka u tla fumana lisebelisoa tsa ho qoela ka ho eketsehileng sehloohong sena.
Likarolo tsa Paxos
Paxos algorithm e na le mohopolo oa mesebetsi. A re nahaneng ka tse tharo tse kholo (ho na le liphetoho tse nang le likarolo tse eketsehileng):
- Baeletsi (mantsoe a ka boela a sebelisoa: baetapele kapa bahokahanyi). Bana ke bashanyana ba ithutang ka boleng bo bong bo bocha ho tsoa ho mosebelisi mme ba nka karolo ea moetapele. Mosebetsi oa bona ke ho qala letoto la litlhahiso bakeng sa boleng bo bocha le ho hokahanya liketso tse ling tsa li-node. Ho feta moo, Paxos e lumella ho ba teng ha baetapele ba 'maloa maemong a itseng.
- Ba amohelang (Bakhethi). Tsena ke li-node tse voutelang ho amohela kapa ho hana boleng bo itseng. Karolo ea bona ke ea bohlokoa haholo, hobane qeto e itšetlehile ka bona: hore na tsamaiso e tla ea (kapa e ke ke ea e) ka mor'a mohato o latelang oa algorithm ea tumellano.
- Baithuti. Li-node tse amohelang le ho ngola boleng bo bocha bo amoheloang ha boemo ba sistimi bo fetohile. Ha ba etse liqeto, ba amohela feela data mme ba ka e fa mosebelisi oa ho qetela.
Node e le 'ngoe e ka kopanya likarolo tse' maloa maemong a fapaneng.
Khopolo ea quorum
Re nka hore re na le tsamaiso ea N nodes Le ea bona palo e kahodimodimo F li-node li ka hloleha. Haeba F node e hloleha, joale re tlameha ho ba le bonyane 2F+1 li-node tse amohelang.
Sena sea hlokahala e le hore kamehla re be le bongata, esita le boemong bo bobe ka ho fetisisa, ba li-node tse "ntle" tse sebetsang hantle. Ke hore F+1 "tse ntle" li-node tse lumellaneng, 'me boleng ba ho qetela bo tla amoheloa. Ho seng joalo, ho ka ba le boemo boo lihlopha tsa rona tse fapaneng tsa lehae li nkang meelelo e fapaneng 'me li sitoa ho lumellana har'a tsona. Ka hona, re hloka bongata bo felletseng hore re hape likhetho.
Mohopolo o akaretsang oa hore na algorithm ea Paxos consensus e sebetsa joang
Algorithm ea Paxos e kenyelletsa mekhahlelo e 'meli e meholo, eo le eona e arotsoeng ka mehato e' meli e 'ngoe le e 'ngoe:
- Mokhahlelo oa 1a: Lokisetsa. Nakong ea boitokiso, moetapele (mosisi) o tsebisa libaka tsohle: “Re qala mohato o mocha oa ho vouta. Re na le potoloho e ncha. Palo ea potoloho ena ke n. Joale re tla qala ho khetha." Hajoale, e tlaleha feela qalo ea potoloho e ncha, empa ha e tlalehe boleng bo bocha. Mosebetsi oa sethaleng sena ke ho qala potoloho e ncha le ho tsebisa bohle ka palo ea eona e ikhethang. Nomoro e pota-potileng e bohlokoa, e tlameha ho ba boleng bo boholo ho feta linomoro tsohle tse fetileng tsa likhetho ho tsoa ho baetapele bohle ba fetileng. Hobane ke ka lebaka la palo e pota-potileng hore li-node tse ling tsamaisong li tla utloisisa hore na data ea moetapele ke ea morao-rao hakae. Ho ka etsahala hore li-node tse ling li se li ntse li e-na le liphetho tsa likhetho tsa morao-rao 'me li tla bolella moetapele feela hore o ka morao ho nako.
- Mokhahlelo oa 1b: Tšepiso. Ha li-node tsa ba amohelang li fumana palo ea sethala se secha sa ho vouta, ho ka ba le liphetho tse peli:
- Nomoro n ea voutu e ncha e kholo ho feta palo ea likhetho tse fetileng tseo moamoheli a ileng a nka karolo ho tsona. Ebe moamoheli o romela tšepiso ho moetapele hore a ke ke a kenya letsoho likhethong tse ling hape tse nang le palo e tlase ho n. Haeba moamoheli a se a ntse a voutetse ntho e itseng (ke hore, o se a amohetse boleng bo itseng karolong ea bobeli), joale o kopanya boleng bo amohelehang le palo ea khetho eo a ileng a kenya letsoho ho eona tšepisong ea hae.
- Ho seng joalo, haeba moamoheli a se a ntse a tseba ka likhetho tse phahameng, a ka hlokomoloha mohato oa ho itokisa mme a se ke a arabela moetapele.
- Mokhahlelo oa 2a: Amohela. Moetapele o hloka ho emela karabo ho tsoa ho quorum (boholo ba li-node tsamaisong) mme, haeba palo e hlokahalang ea likarabo e amoheloa, o na le likhetho tse peli bakeng sa nts'etsopele ea liketsahalo:
- Ba bang ba ba amohelang ba ile ba romela litekanyetso tseo ba neng ba se ba li voutetse. Tabeng ena, moeta-pele o khetha boleng ho tloha likhethong ka palo e kholo. Ha re bitse boleng bona x, 'me e romela molaetsa ho li-node tsohle tse kang: "Amohela (n, x)", moo boleng ba pele e leng nomoro ea ho vouta ho tloha mohatong oa eona oa Tlhahiso, 'me boleng ba bobeli ke boo bohle ba bo bokaneng, i.e. boleng boo re bo voutang.
- Haeba ha ho le ea mong oa ba amohelang ba rometseng litekanyetso leha e le life, empa ba tšepisitse feela ho vouta sebakeng sena, moeta-pele a ka ba memela ho voutela boleng ba bona, boleng boo e ileng ea e-ba moetapele pele. Ha re e bitse y. E romela molaetsa ho li-node tsohle tse kang: "Amohela (n, y)", e tšoanang le sephetho se fetileng.
- Mokhahlelo oa 2b: E amohetsoe. Ho feta moo, li-node tse amohelang, ha li amohela molaetsa oa "Accept(...)" ho tsoa ho moetapele, li lumellana le eona (romella tiiso ho li-node tsohle hore li lumellana le boleng bo bocha) hafeela ba sa tšepisa tse ling (tse ling) ) moetapele ho kenya letsoho ho vouta ka nomoro e chitja n'> n, ho seng joalo ba hlokomoloha kopo ea tiiso.
Haeba bongata ba li-node bo arabetse moeta-pele, 'me kaofela ha bona ba tiisa boleng bo bocha, joale boleng bo bocha bo nkoa bo amohelehile. Hooray! Haeba bongata bo sa fihleloe kapa ho na le li-node tse hanneng ho amohela boleng bo bocha, joale ntho e 'ngoe le e' ngoe e qala.
Ena ke tsela eo algorithm ea Paxos e sebetsang ka eona. E 'ngoe le e' ngoe ea mekhahlelo ena e na le lintho tse ngata tse poteletseng, ha rea ka ra nahana ka mefuta e fapaneng ea liphoso, mathata a baetapele ba bangata le tse ling tse ngata, empa morero oa sengoloa sena ke feela ho tsebisa 'mali lefats'eng la likhomphutha tse ajoang maemong a holimo.
Hape ke habohlokoa ho hlokomela hore Paxos ha se eona feela ea mofuta oa eona, ho na le li-algorithms tse ling, mohlala, , empa ena ke sehlooho sa sehlooho se seng.
Lihokelo tsa lisebelisoa bakeng sa boithuto bo tsoelang pele
Boemo ba ho qala:
- , Preethi Kasireddy, sengoloa sa blog ho Medium
- , Adi Kancherla, sengoloa sa blog ho Medium
- , Itai Abraham, blog
- , Itai Abraham, sehlooho sa blog
Boemo ba Leslie Lamport:
- , Fischer, Lynch le Paterson, pampiri ea lipatlisiso, 1985
- , Leslie Lamport, pampiri ea lipatlisiso, 1998
- , Leslie Lamport, pampiri ea lipatlisiso, 2001
Source: www.habr.com