Se konsa, an n imajine. Gen 5 chat fèmen nan chanm nan, epi yo nan lòd yo ale reveye mèt kay la, yo tout bezwen dakò sou sa a nan mitan tèt yo, paske yo ka sèlman louvri pòt la ak senk nan yo apiye sou li. Si youn nan chat yo se chat Schrödinger a, ak lòt chat yo pa konnen sou desizyon l ', kesyon an rive: "Ki jan yo ka fè li?"
Nan atik sa a, mwen pral di w an tèm senp sou eleman nan teyorik nan mond lan nan sistèm distribiye ak prensip yo nan operasyon yo. Mwen pral tou supèrfisyèl egzamine lide prensipal ki kache Paxos.
Lè devlopè yo itilize enfrastrikti nwaj yo, divès baz done, ak travay nan grap nan yon gwo kantite nœuds, yo gen konfyans ke done yo pral konplè, an sekirite, epi yo toujou disponib. Men, ki kote garanti yo?
Esansyèlman, garanti nou genyen yo se garanti founisè. Yo dekri nan dokiman an jan sa a: "Sèvis sa a se byen serye, li gen yon SLA bay, pa enkyete, tout bagay pral travay distribye jan ou espere."
Nou gen tandans kwè nan pi bon an, paske mesye entelijan ki soti nan gwo konpayi asire nou ke tout bagay pral byen. Nou pa poze kesyon an: poukisa, an reyalite, sa a ka travay nan tout? Èske gen okenn jistifikasyon fòmèl pou operasyon kòrèk sistèm sa yo?
Mwen fèk ale nan epi li te trè enspire pa sijè sa a. Konferans nan lekòl yo te plis tankou klas kalkil pase yon bagay ki gen rapò ak sistèm òdinatè. Men, sa a se egzakteman ki jan algoritm ki pi enpòtan ke nou itilize chak jou, san yo pa menm konnen li, yo te pwouve nan yon sèl fwa.
Pifò sistèm modèn distribiye itilize algorithm konsansis Paxos ak modifikasyon divès kalite li yo. Bagay ki pi fre se ke validite a ak, nan prensip, posiblite pou egzistans algorithm sa a ka pwouve tou senpleman ak yon plim ak papye. Nan pratik, algorithm la itilize nan gwo sistèm kouri sou yon gwo kantite nœuds nan nwaj yo.
Yon ilistrasyon limyè sou sa ki pral diskite annapre: travay la nan de jeneralAnn pran yon gade pou yon chofe .
Nou gen de lame - wouj ak blan. Twoup blan yo baze nan vil ki sènen an. Twoup wouj ki te dirije pa jeneral A1 ak A2 yo sitiye sou de bò nan vil la. Travay rous yo se atake vil blan an epi genyen. Sepandan, lame a nan chak jeneral wouj endividyèlman pi piti pase lame blan an.
Kondisyon viktwa pou wouj yo: tou de jeneral yo dwe atake an menm tan pou yo ka gen yon avantaj nimerik sou blan yo. Pou fè sa, jeneral A1 ak A2 bezwen vin nan yon akò youn ak lòt. Si tout moun atake separeman, rous yo ap pèdi.
Pou jwenn yon akò, jeneral A1 ak A2 ka voye mesaje youn ak lòt atravè teritwa vil blan an. Mesaje a ka reyisi rive jwenn yon jeneral alye oswa lènmi an ka entèsepte. Kesyon: èske gen tankou yon sekans kominikasyon ant jeneral yo wouj-chveu (sekans nan voye mesaje soti nan A1 a A2 ak vis vèrsa soti nan A2 a A1), nan ki yo gen garanti yo dakò sou yon atak nan èdtan X. Isit la, garanti vle di ke tou de jeneral yo pral gen konfimasyon klè ke yon alye (yon lòt jeneral) pral definitivman atake nan moman an nonmen X.
Sipoze A1 voye yon mesaje bay A2 ak mesaj la: "Ann atake jodi a a minwi!" Jeneral A1 pa ka atake san konfimasyon Jeneral A2. Si mesaje ki soti nan A1 a te rive, Lè sa a, Jeneral A2 voye konfimasyon ak mesaj la: "Wi, ann touye blan yo jodi a." Men, kounye a Jeneral A2 pa konnen si mesaje li a te rive oswa ou pa, li pa gen okenn garanti si atak la pral similtane. Koulye a, Jeneral A2 ankò bezwen konfimasyon.
Si nou dekri plis kominikasyon yo, li vin klè ke kèlkeswa kantite sik echanj mesaj genyen, pa gen okenn fason pou garanti ke tou de jeneral yo te resevwa mesaj yo (si nou sipoze ke youn mesaje yo ka entèsepte).
Pwoblèm De Jeneral la se yon gwo ilistrasyon yon sistèm distribiye trè senp kote gen de nœuds ak kominikasyon ki pa fyab. Sa vle di nou pa gen yon garanti 100% ke yo senkronize. Pwoblèm ki sanble yo diskite sèlman sou yon echèl pi gwo pita nan atik la.
Nou prezante konsèp nan sistèm distribiye
Yon sistèm distribiye se yon gwoup òdinatè (apwe sa nou pral rele yo nœuds) ki ka fè echanj mesaj. Chak ne endividyèl se yon kalite antite otonòm. Yon ne ka trete travay poukont li, men yo nan lòd yo kominike ak lòt nœuds, li bezwen voye ak resevwa mesaj.
Ki jan egzakteman mesaj yo aplike, ki pwotokòl yo itilize - sa a pa nan enterè nou nan kontèks sa a. Li enpòtan ke nœuds yo nan yon sistèm distribye ka echanj done youn ak lòt lè yo voye mesaj.
Definisyon an li menm pa sanble trè konplike, men nou dwe pran an kont ke yon sistèm distribiye gen yon kantite atribi ki pral enpòtan pou nou.
Atribi sistèm distribiye yo
- Concurrency – posiblite pou evènman similtane oswa konkouran rive nan sistèm nan. Anplis, nou pral konsidere evènman ki rive sou de nœuds diferan yo dwe potansyèlman konkouran osi lontan ke nou pa gen yon lòd klè nan ensidan evènman sa yo. Men, kòm yon règ, nou pa genyen li.
- Pa gen revèy mondyal. Nou pa gen yon lòd klè nan evènman akòz mank nan yon revèy mondyal. Nan mond lan òdinè nan moun, nou yo abitye lefèt ke nou gen revèy ak tan absoliman. Tout bagay chanje lè li rive sistèm distribiye. Menm revèy atomik ultra presi gen flote, epi ka gen sitiyasyon kote nou pa ka di kilès nan de evènman ki te pase an premye. Se poutèt sa, nou pa ka konte sou tan tou.
- Echèk endepandan nan nœuds sistèm yo. Gen yon lòt pwoblèm: yon bagay ka ale mal tou senpleman paske nœuds nou yo pa dire pou tout tan. Disk di a ka echwe, machin vityèl nan nwaj la ka rdemare, rezo a ka bat je epi mesaj yo pral pèdi. Anplis, ka gen sitiyasyon kote nœuds travay, men an menm tan travay kont sistèm nan. Dènye klas pwoblèm yo menm te resevwa yon non apa: pwoblèm . Egzanp ki pi popilè nan yon sistèm distribiye ak pwoblèm sa a se Blockchain. Men jodi a nou p ap konsidere klas espesyal pwoblèm sa a. Nou pral enterese nan sitiyasyon kote tou senpleman youn oswa plis nœuds ka echwe.
- Modèl kominikasyon (modèl mesaj) ant nœuds. Nou te deja etabli ke nœuds kominike pa echanj mesaj. Gen de modèl mesaj byen koni: synchrone ak asynchrone.
Modèl kominikasyon ant nœuds nan sistèm distribiye
Modèl synchrone – nou konnen pou asire w ke gen yon delta fini li te ye nan tan pandan ki yon mesaj garanti yo rive soti nan yon ne nan yon lòt. Si tan sa a te pase epi mesaj la pa rive, nou ka di san danje ke ne a echwe. Nan modèl sa a nou gen tan ap tann previzib.
Modèl asynchrone – nan modèl asynchrone nou konsidere ke tan an ap tann se fini, men pa gen okenn delta sa yo nan tan apre sa nou ka garanti ke ne te echwe. Moun sa yo. Tan an ap tann pou yon mesaj ki soti nan yon ne ka abitrèman long. Sa a se yon definisyon enpòtan, epi nou pral pale sou li pi lwen.
Konsèp konsansis nan sistèm distribiye
Anvan fòmèlman defini konsèp konsansis la, ann konsidere yon egzanp yon sitiyasyon kote nou bezwen li, sètadi - Eta Machine Replication.
Nou gen kèk log distribye. Nou ta renmen li konsistan epi li genyen done ki idantik sou tout nœuds nan sistèm distribiye a. Lè youn nan nœuds yo aprann yon nouvo valè ke li pral ekri nan boutèy la, travay li vin ofri valè sa a nan tout lòt nœuds pou ke boutèy la mete ajou sou tout nœuds ak sistèm nan deplase nan yon nouvo eta konsistan. Nan ka sa a, li enpòtan pou nœuds yo dakò nan mitan tèt yo: tout nœuds dakò ke nouvo valè pwopoze a kòrèk, tout nœuds aksepte valè sa a, epi sèlman nan ka sa a tout moun ka ekri nouvo valè a nan boutèy la.
Nan lòt mo: pa youn nan nœuds yo objeksyon ke li te gen plis enfòmasyon ki enpòtan, ak valè yo pwopoze a pa kòrèk. Akò ant nœuds ak akò sou yon sèl valè kòrèk aksepte se konsansis nan yon sistèm distribiye. Apre sa, nou pral pale sou algoritm ki pèmèt yon sistèm distribye reyalize konsansis garanti.
Plis fòmèlman, nou ka defini yon algorithm konsansis (oswa tou senpleman yon algorithm konsansis) kòm yon sèten fonksyon ki transfere yon sistèm distribiye soti nan eta A nan eta B. Anplis, eta sa a aksepte pa tout nœuds, ak tout nœuds ka konfime li. Kòm li vire soti, travay sa a se pa nan tout kòm trivial jan li sanble nan premye gade.
Pwopriyete Algorithm konsansis la
Algorithm konsansis la dwe gen twa pwopriyete pou sistèm nan kontinye egziste epi li gen kèk pwogrè nan deplase soti nan eta a:
- Akò – tout nœuds ki fonksyone kòrèkteman dwe pran menm valè (nan atik yo rele pwopriyete sa a tou kòm pwopriyete sekirite). Tout nœuds ki ap fonksyone kounye a (pa echwe oswa pèdi kontak ak lòt yo) dwe vini nan yon akò epi aksepte kèk valè final komen.
Li enpòtan pou w konprann isit la ke nœuds yo nan sistèm distribiye nou ap konsidere vle dakò. Sa vle di, kounye a nou ap pale de sistèm kote yon bagay ka tou senpleman echwe (pa egzanp, kèk ne echwe), men nan sistèm sa a definitivman pa gen okenn nœuds ki fè espre travay kont lòt moun (tach la nan jeneral Bizanten). Akòz pwopriyete sa a, sistèm nan rete konsistan.
- Entegrite — si tout nœuds k ap travay kòrèkteman ofri menm valè a v, ki vle di chak ne opere kòrèkteman dwe aksepte valè sa a v.
- Revokasyon - tout nœuds opere kòrèkteman pral evantyèlman pran yon valè sèten (pwopriyete liveness), ki pèmèt algorithm la fè pwogrè nan sistèm nan. Chak moun k ap fonksyone kòrèkteman dwe pi bonè oswa pita aksepte valè final la epi konfime li: "Pou mwen, valè sa a se vre, mwen dakò ak tout sistèm nan."
Yon egzanp sou fason algorithm konsansis la ap travay
Pandan ke pwopriyete yo nan algorithm a pa ka totalman klè. Se poutèt sa, nou pral ilistre ak yon egzanp ki etap algorithm konsansis ki pi senp la pase nan yon sistèm ki gen yon modèl messagerie synchrone, nan ki tout nœuds fonksyone jan yo espere, mesaj yo pa pèdi epi pa gen anyen kraze (èske sa vrèman rive?).
- Tout bagay kòmanse ak yon pwopozisyon maryaj (Pwopoze). Ann sipoze ke yon kliyan konekte nan yon ne ki rele "Node 1" e li te kòmanse yon tranzaksyon, pase yon nouvo valè nan ne la - O. Depi koulye a, nou pral rele "Node 1" ofri. Kòm yon pwopozisyon, "Node 1" dwe kounye a notifye tout sistèm nan ke li gen done fre, epi li voye mesaj bay tout lòt nœuds: "Gade! Siyifikasyon "O" te vin jwenn mwen epi mwen vle ekri li! Tanpri konfime ke w ap anrejistre "O" tou nan jounal ou a."
- Pwochen etap la se vote pou valè yo pwopoze a (Voting). Pou kisa li ye? Li ka rive ke lòt nœuds te resevwa enfòmasyon ki pi resan, epi yo gen done sou menm tranzaksyon an.
Lè ne "Node 1" voye pwopozisyon li yo, lòt nœuds yo tcheke mòso bwa yo pou done sou evènman sa a. Si pa gen okenn kontradiksyon, nœuds yo anonse: "Wi, mwen pa gen okenn lòt done pou evènman sa a. Valè "O" se dènye enfòmasyon nou merite."Nan nenpòt lòt ka, nœuds ka reponn a "Node 1": "Koute! Mwen gen done ki pi resan sou tranzaksyon sa a. Pa 'O', men yon bagay pi bon."
Nan etap vòt la, nœuds yo pran yon desizyon: swa yo tout aksepte menm valè a, oswa youn nan yo vote kont, ki endike ke li gen done ki pi resan.
- Si wonn vòt la te reyisi epi tout moun te an favè, Lè sa a, sistèm nan deplase nan yon nouvo etap - Aksepte valè a. "Node 1" kolekte tout repons ki soti nan lòt nœuds ak rapò: "Tout moun te dakò sou valè "O"! Koulye a, mwen ofisyèlman deklare ke "O" se nouvo siyifikasyon nou an, menm bagay la tou pou tout moun! Ekri li nan ti liv ou a, pa bliye. Ekri li nan jounal ou!"
- Nœuds ki rete yo voye konfimasyon (Aksepte) ke yo te ekri valè "O"; pa gen anyen nouvo ki rive pandan tan sa a (yon kalite komèt de-faz). Apre evènman enpòtan sa a, nou konsidere ke tranzaksyon an distribye fini.
Kidonk, algorithm konsansis nan yon ka senp konsiste de kat etap: pwopoze, vote (vote), aksepte (aksepte), konfime akseptasyon (aksepte).
Si nan kèk etap nou pa t 'kapab jwenn akò, Lè sa a, algorithm la kòmanse ankò, pran an kont enfòmasyon yo bay nan nœuds yo ki te refize konfime valè yo pwopoze a.
Algorithm konsansis nan yon sistèm asynchrone
Anvan sa a, tout bagay te lis, paske nou t ap pale de yon modèl messagerie synchrone. Men, nou konnen ke nan mond lan modèn nou yo abitye fè tout bagay asynchrone. Ki jan yon algorithm menm jan an travay nan yon sistèm ak yon modèl mesaj asynchrone, kote nou kwè ke tan an ap tann pou yon repons soti nan yon ne ka abitrèman long (pa chemen an, echèk la nan yon ne ka konsidere tou kòm yon egzanp lè yon ne ka reponn pou yon tan abitrèman long).
Kounye a ke nou konnen ki jan algorithm konsansis la travay an prensip, yon kesyon pou lektè sa yo ki te fè l 'sa lwen: konbyen nœuds nan yon sistèm N nœuds ak yon modèl mesaj asynchrone ka echwe pou ke sistèm nan ka toujou rive nan konsansis?
Repons ki kòrèk la ak jistifikasyon se dèyè spoiler la.Repons ki kòrèk la se: 0. Si menm yon sèl ne nan yon sistèm asynchrone echwe, sistèm nan p ap kapab rive nan konsansis. Deklarasyon sa a pwouve nan teyorèm FLP, byen li te ye nan sèten sèk (1985, Fischer, Lynch, Paterson, lyen nan orijinal la nan fen atik la): "Enposib pou reyalize yon konsansis distribiye si omwen yon ne echwe. .”
Mesye, ebyen nou gen yon pwoblèm, nou abitye tout bagay asynchrone. Ak isit la li ye. Ki jan yo kontinye viv?
Nou te jis pale de teyori, de matematik. Ki sa "pa ka reyalize konsansis" vle di, tradui soti nan lang matematik nan lang nou an - jeni? Sa vle di ke "pa ka toujou reyalize", i.e. Gen yon ka kote konsansis pa ka reyalize. Ki kalite ka sa a?
Sa a se egzakteman vyolasyon pwopriyete a vivan ki dekri anwo a. Nou pa gen yon akò komen, epi sistèm nan pa ka gen pwogrè (pa ka konplete nan yon tan fini) nan ka a kote nou pa gen yon repons nan tout nœuds. Paske nan yon sistèm asynchrone nou pa gen okenn tan repons previzib epi nou pa ka konnen si yon node te fè aksidan oswa si jis pran yon bon bout tan pou reponn.
Men, nan pratik nou ka jwenn yon solisyon. Se pou algorithm nou an kapab travay pou yon tan long nan ka ta gen echèk (potansyèlman li ka travay endefiniman). Men, nan pifò sitiyasyon, lè pifò nœuds yo ap fonksyone kòrèkteman, nou pral gen pwogrè nan sistèm nan.
Nan pratik, nou fè fas ak modèl kominikasyon pasyèlman synchrone. Se yon pati nan synchrony konprann jan sa a: nan ka jeneral la, nou gen yon modèl asynchrone, men se yon sèten konsèp nan "tan estabilizasyon mondyal" nan yon sèten pwen nan tan fòmèlman prezante.
Moman sa a nan tan gendwa pa vini pou nenpòt ki kantite tan, men li dwe vini yon jou. Revèy alam vityèl la pral sonnen, epi apati moman sa a nou ka predi tan delta pou mesaj yo pral rive. Apati moman sa a, sistèm nan vire soti nan asynchrone a synchrone. Nan pratik, nou fè fas ak jisteman sistèm sa yo.
Algorithm Paxos la rezoud pwoblèm konsansis
se yon fanmi nan algoritm ki rezoud pwoblèm nan konsansis pou sistèm pasyèlman synchrone, sijè a posibilite ke kèk nœuds ka echwe. Otè Paxos se . Li te pwopoze yon prèv fòmèl nan egzistans lan ak kòrèkteman nan algorithm nan an 1989.
Men, prèv la te tounen soti byen lwen soti nan trivial. Premye piblikasyon an te pibliye sèlman an 1998 (33 paj) ki dekri algorithm la. Kòm li te tounen soti, li te trè difisil yo konprann, ak nan 2001 yo te pibliye yon eksplikasyon sou atik la, ki te pran 14 paj. Yo bay volim nan piblikasyon yo nan lòd yo montre ke an reyalite pwoblèm nan nan konsansis se pa nan tout senp, ak dèyè algoritm sa yo manti yon kantite lajan gwo travay pa moun ki pi entelijan.
Li enteresan ke Leslie Lamport li menm te note nan konferans li a ke nan dezyèm atik eksplikasyon an gen yon sèl deklarasyon, yon liy (li pa presize ki youn), ki ka entèprete nan diferan fason. Se poutèt sa, yon gwo kantite aplikasyon modèn Paxos pa travay konplètman kòrèkteman.
Yon analiz detaye sou travay Paxos ta pran plis pase yon atik, se konsa mwen pral eseye trè yon ti tan transmèt lide prensipal la nan algorithm la. Nan lyen ki nan fen atik mwen an w ap jwenn materyèl pou plis plonje nan sijè sa a.
Wòl nan Paxos
Algorithm Paxos la gen yon konsèp wòl. Ann konsidere twa prensipal yo (gen modifikasyon ak wòl adisyonèl):
- Pwopozisyon (tèm yo ka itilize tou: lidè oswa kowòdonatè). Sa yo se mesye yo ki aprann sou kèk nouvo valè nan men itilizatè a epi pran wòl nan lidè. Travay yo se lanse yon wonn nan pwopozisyon pou yon nouvo valè ak kowòdone plis aksyon nan nœuds yo. Anplis, Paxos pèmèt prezans plizyè lidè nan sèten sitiyasyon.
- Akseptè (Votè). Sa yo se nœuds ki vote pou aksepte oswa rejte yon valè patikilye. Wòl yo trè enpòtan, paske desizyon an depann de yo: nan ki eta sistèm lan pral (oswa pa pral) ale apre pwochen etap nan algorithm konsansis la.
- Apranti yo. Nœuds ki tou senpleman aksepte epi ekri nouvo valè aksepte lè eta a nan sistèm nan chanje. Yo pa pran desizyon, yo jis resevwa done yo epi yo ka bay itilizatè a fen li.
Yon ne ka konbine plizyè wòl nan diferan sitiyasyon.
Konsèp kowòm lan
Nou sipoze ke nou gen yon sistèm de N nœuds Ak nan yo maksimòm nan F nœuds ka febli. Si F nœuds echwe, Lè sa a, nou dwe gen omwen 2F+1 nœuds akseptè yo.
Sa a nesesè pou nou toujou gen majorite, menm nan sitiyasyon ki pi mal la, nan "bon" nœuds ki travay kòrèkteman. Sa vle di F+1 "bon" nœuds ki te dakò, ak valè final la pral aksepte. Sinon, ka gen yon sitiyasyon kote diferan gwoup lokal nou yo pran diferan siyifikasyon epi yo pa ka dakò youn ak lòt. Se poutèt sa, nou bezwen yon majorite absoli pou genyen vòt la.
Lide jeneral sou fason algorithm konsansis Paxos la ap travay
Algorithm Paxos la enplike de gwo faz, ki an vire yo divize an de etap chak:
- Faz 1a: Prepare. Pandan faz preparasyon an, lidè a (pwopoze a) enfòme tout nœuds yo: “N ap kòmanse yon nouvo faz vòt. Nou gen yon nouvo wonn. Nimewo wonn sa a se n. Kounye a nou pral kòmanse vote." Pou kounye a, li tou senpleman rapòte kòmansman yon nouvo sik, men li pa rapòte yon nouvo valè. Travay etap sa a se kòmanse yon nouvo wonn epi enfòme tout moun sou nimewo inik li yo. Nimewo wonn nan enpòtan, li dwe yon valè ki pi gran pase tout nimewo vòt anvan yo soti nan tout lidè anvan yo. Paske se gras a nimewo wonn lòt nœuds nan sistèm nan pral konprann ki jan dènye done lidè yo ye. Li posib ke lòt nœuds deja gen rezilta vòt nan jij pita yo epi yo pral tou senpleman di lidè a ke li se dèyè tan yo.
- Faz 1b: Pwomès. Lè nœuds akseptè yo te resevwa kantite nouvo etap vòt la, de rezilta posib:
- Nimewo n nouvo vòt la pi gran pase kantite nenpòt vòt anvan an kote moun ki aksepte a te patisipe. Lè sa a, moun k ap aksepte a voye yon pwomès bay lidè a ke li pa pral patisipe nan okenn vòt plis ak yon nimewo ki pi ba pase n. Si moun k ap aksepte a te deja vote pou yon bagay (sa vle di, li te deja aksepte kèk valè nan dezyèm faz la), Lè sa a, li tache valè a aksepte ak nimewo a nan vòt kote li te patisipe nan pwomès li.
- Sinon, si moun k ap aksepte a deja konnen sou vòt ki pi wo a, li ka tou senpleman inyore etap preparasyon an epi li pa reponn lidè a.
- Faz 2a: Aksepte. Lidè a bezwen rete tann pou yon repons nan kowòm nan (majorite nœuds nan sistèm nan) epi, si yo resevwa kantite repons ki nesesè yo, Lè sa a, li gen de opsyon pou devlopman nan evènman yo:
- Gen kèk nan akseptè yo voye valè ke yo te deja vote pou yo. Nan ka sa a, lidè a chwazi valè a nan vòt la ak kantite maksimòm la. Ann rele valè sa a x, epi li voye yon mesaj bay tout nœuds tankou: "Aksepte (n, x)", kote premye valè a se nimewo vòt ki soti nan pwòp etap Pwopozisyon li a, epi dezyèm valè a se sa tout moun te rasanble pou, i.e. valè pou nou vote aktyèlman.
- Si pa youn nan akseptè yo te voye okenn valè, men yo tou senpleman te pwomèt pou vote nan tou sa a, lidè a ka envite yo pou yo vote pou valè yo, valè pou ki li te vin yon lidè an plas an premye. Ann rele li y. Li voye yon mesaj bay tout nœuds tankou: "Aksepte (n, y)", menm jan ak rezilta anvan an.
- Faz 2b: Aksepte. Anplis de sa, nœuds akseptè yo, lè yo resevwa mesaj "Aksepte (...)" nan men lidè a, dakò ak li (voye konfimasyon bay tout nœuds ke yo dakò ak nouvo valè a) sèlman si yo pa te pwomèt kèk (lòt) ) lidè pou patisipe nan vòt ak nimewo wonn n' > n, otreman yo inyore demann konfimasyon an.
Si majorite nœuds reponn lidè a, ak tout nan yo konfime nouvo valè a, Lè sa a, nouvo valè a konsidere kòm aksepte. Houra! Si majorite a pa rive jwenn oswa gen nœuds ki refize aksepte nouvo valè a, Lè sa a, tout bagay kòmanse sou.
Men ki jan algorithm Paxos la ap travay. Chak nan etap sa yo gen anpil sibtilite, nou pratikman pa t 'konsidere divès kalite echèk, pwoblèm nan lidè miltip ak plis ankò, men objektif la nan atik sa a se sèlman prezante lektè a nan mond lan nan distribye informatique nan yon wo nivo.
Li se tou vo sonje ke Paxos se pa youn nan sèlman nan kalite li yo, gen lòt algoritm, pou egzanp, , men sa a se yon sijè pou yon lòt atik.
Lyen ki mennen nan materyèl pou plis etid
Nivo debutan:
- , Preethi Kasireddy, atik blog sou mwayen
- , Adi Kancherla, atik blog sou Medium
- , Ittai Abraham, blog
- , Ittai Abraham, atik blog
Nivo Leslie Lampport:
- , Fischer, Lynch and Paterson, papye rechèch, 1985
- , Leslie Lampport, papye rechèch, 1998
- , Leslie Lampport, papye rechèch, 2001
Sous: www.habr.com